Debian Codegraph @

src/list.c

raw
1 /*
2 * list.c - List related functions
3 *
4 * Copyright (c) 2000-2024 Shiro Kawai <[email protected]>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the authors nor the names of its contributors
18 * may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 #define LIBGAUCHE_BODY
35 #include "gauche.h"
36 #include "gauche/priv/pairP.h"
37
38 /*
39 * Classes
40 */
41
42 static ScmClass *list_cpl[] = {
43 SCM_CLASS_STATIC_PTR(Scm_ListClass),
44 SCM_CLASS_STATIC_PTR(Scm_SequenceClass),
45 SCM_CLASS_STATIC_PTR(Scm_CollectionClass),
46 SCM_CLASS_STATIC_PTR(Scm_TopClass),
47 NULL
48 };
49
50 SCM_DEFINE_BUILTIN_CLASS(Scm_ListClass, NULL, NULL, NULL, NULL, list_cpl+1);
51 SCM_DEFINE_BUILTIN_CLASS(Scm_PairClass, NULL, NULL, NULL, NULL, list_cpl);
52 SCM_DEFINE_BUILTIN_CLASS(Scm_NullClass, NULL, NULL, NULL, NULL, list_cpl);
53
54 /*
55 * CONSTRUCTOR
56 */
57
58 ScmObj Scm_Cons(ScmObj car, ScmObj cdr)
59 {
60 ScmPair *z = SCM_NEW(ScmPair);
61 /* NB: these ENSURE_MEMs are moved here from vm loop to reduce
62 the register pressure there. In most cases these increases
63 just a couple of mask-and-test instructions on the data on
64 the register. */
65 SCM_FLONUM_ENSURE_MEM(car);
66 SCM_FLONUM_ENSURE_MEM(cdr);
67 SCM_SET_CAR_UNCHECKED(z, car);
68 SCM_SET_CDR_UNCHECKED(z, cdr);
69 return SCM_OBJ(z);
70 }
71
72 ScmObj Scm_Acons(ScmObj caar, ScmObj cdar, ScmObj cdr)
73 {
74 ScmPair *y = SCM_NEW(ScmPair);
75 ScmPair *z = SCM_NEW(ScmPair);
76 SCM_SET_CAR_UNCHECKED(y, caar);
77 SCM_SET_CDR_UNCHECKED(y, cdar);
78 SCM_SET_CAR_UNCHECKED(z, SCM_OBJ(y));
79 SCM_SET_CDR_UNCHECKED(z, cdr);
80 return SCM_OBJ(z);
81 }
82
83 ScmObj Scm_List(ScmObj elt, ...)
84 {
85 if (elt == NULL) return SCM_NIL;
86
87 va_list pvar;
88 va_start(pvar, elt);
89 ScmObj cdr = Scm_VaList(pvar);
90 va_end(pvar);
91 return Scm_Cons(elt, cdr);
92 }
93
94
95 ScmObj Scm_Conses(ScmObj elt, ...)
96 {
97 if (elt == NULL) return SCM_NIL;
98
99 va_list pvar;
100 va_start(pvar, elt);
101 ScmObj cdr = Scm_VaCons(pvar);
102 va_end(pvar);
103 if (cdr == NULL) return elt;
104 else return Scm_Cons(elt, cdr);
105 }
106
107
108 ScmObj Scm_VaList(va_list pvar)
109 {
110 ScmObj start = SCM_NIL, cp = SCM_NIL, obj;
111
112 for (obj = va_arg(pvar, ScmObj);
113 obj != NULL;
114 obj = va_arg(pvar, ScmObj))
115 {
116 if (SCM_NULLP(start)) {
117 start = SCM_OBJ(SCM_NEW(ScmPair));
118 SCM_SET_CAR_UNCHECKED(start, obj);
119 SCM_SET_CDR_UNCHECKED(start, SCM_NIL);
120 cp = start;
121 } else {
122 ScmObj item;
123 item = SCM_OBJ(SCM_NEW(ScmPair));
124 SCM_SET_CDR_UNCHECKED(cp, item);
125 SCM_SET_CAR_UNCHECKED(item, obj);
126 SCM_SET_CDR_UNCHECKED(item, SCM_NIL);
127 cp = item;
128 }
129 }
130 return start;
131 }
132
133
134 ScmObj Scm_VaCons(va_list pvar SCM_UNUSED)
135 {
136 Scm_Panic("Scm_VaCons: not implemented");
137 return SCM_UNDEFINED;
138 }
139
140 ScmObj Scm_ArrayToList(ScmObj *elts, ScmSize nelts)
141 {
142 return Scm_ArrayToListWithTail(elts, nelts, SCM_NIL);
143 }
144
145 ScmObj Scm_ArrayToListWithTail(ScmObj *elts, ScmSize nelts, ScmObj tail)
146 {
147 ScmObj h = SCM_NIL, t = SCM_NIL;
148 if (elts) {
149 for (ScmSize i=0; i<nelts; i++) SCM_APPEND1(h, t, *elts++);
150 }
151 if (!SCM_NULLP(tail)) SCM_APPEND(h, t, tail);
152 return h;
153 }
154
155 ScmObj *Scm_ListToArray(ScmObj list, ScmSize *nelts, ScmObj *store, int alloc)
156 {
157 ScmSize len = Scm_Length(list);
158 if (len < 0) Scm_Error("proper list required, but got %S", list);
159
160 ScmObj *array;
161 if (store == NULL) {
162 array = SCM_NEW_ARRAY(ScmObj, len);
163 } else {
164 if (*nelts < len) {
165 if (!alloc)
166 Scm_Error("ListToArray: storage too small");
167 array = SCM_NEW_ARRAY(ScmObj, len);
168 } else {
169 array = store;
170 }
171 }
172 ScmSize i = 0;
173 for (ScmObj lp=list; i<len; i++, lp=SCM_CDR(lp)) {
174 array[i] = SCM_CAR(lp);
175 }
176 *nelts = len;
177 return array;
178 }
179
180 /* cXr stuff */
181
182 #define CXR(cname, sname, body) \
183 ScmObj cname (ScmObj obj) \
184 { \
185 ScmObj obj2 = obj; \
186 body \
187 return obj2; \
188 }
189
190 #define A \
191 if (!SCM_PAIRP(obj2)) Scm_Error("bad object: %S", obj); \
192 obj2 = SCM_CAR(obj2);
193
194 #define D \
195 if (!SCM_PAIRP(obj2)) Scm_Error("bad object: %S", obj); \
196 obj2 = SCM_CDR(obj2);
197
198 CXR(Scm_Car, "car", A)
199 CXR(Scm_Cdr, "cdr", D)
200 CXR(Scm_Caar, "caar", A A)
201 CXR(Scm_Cadr, "cadr", D A)
202 CXR(Scm_Cdar, "cdar", A D)
203 CXR(Scm_Cddr, "cddr", D D)
204
205 void Scm_SetCar(ScmObj pair, ScmObj obj)
206 {
207 if (!SCM_PAIRP(pair)) {
208 Scm_Error("set-car!: Pair required, but got: %S", pair);
209 }
210 ScmExtendedPairDescriptor *d = Scm__GetExtendedPairDescriptor(pair);
211 if (d) {
212 if (d->flags & SCM_PAIR_IMMUTABLE) {
213 Scm_Error("attempt to mutate car of an immutable pair %S with %S",
214 pair, obj);
215 }
216 if (d->setCar) {
217 d->setCar(pair, obj);
218 return;
219 }
220 }
221 SCM_CAR(pair) = obj;
222 }
223
224 void Scm_SetCdr(ScmObj pair, ScmObj obj)
225 {
226 if (!SCM_PAIRP(pair)) {
227 Scm_Error("set-cdr!: Pair required, but got: %S", pair);
228 }
229 ScmExtendedPairDescriptor *d = Scm__GetExtendedPairDescriptor(pair);
230 if (d) {
231 if (d->flags & SCM_PAIR_IMMUTABLE) {
232 Scm_Error("attempt to mutate cdr of an immutable pair %S with %S",
233 pair, obj);
234 }
235 if (d->setCdr) {
236 d->setCdr(pair, obj);
237 return;
238 }
239 }
240 SCM_CDR(pair) = obj;
241 }
242
243 /*
244 * List manipulate routines:
245 */
246
247 /* Scm_Length
248 return length of list in C integer.
249 If the argument is a dotted list, return -1.
250 If the argument is a circular list, return -2. */
251
252 ScmSize Scm_Length(ScmObj obj)
253 {
254 ScmObj slow = obj;
255 ScmSize len = 0;
256
257 for (;;) {
258 if (SCM_NULLP(obj)) break;
259 if (!SCM_PAIRP(obj)) return SCM_LIST_DOTTED;
260
261 obj = SCM_CDR(obj);
262 len++;
263 if (SCM_NULLP(obj)) break;
264 if (!SCM_PAIRP(obj)) return SCM_LIST_DOTTED;
265
266 obj = SCM_CDR(obj);
267 slow = SCM_CDR(slow);
268 if (obj == slow) return SCM_LIST_CIRCULAR;
269 len++;
270 }
271 return len;
272 }
273
274 /* Scm_CopyList(list)
275 * Copy toplevel list LIST. LIST can be improper.
276 * If LIST is not a pair, return LIST itself.
277 * Note: For the naming consistency, this should be Scm_ListCopy().
278 */
279
280 ScmObj Scm_CopyList(ScmObj list)
281 {
282 if (!SCM_PAIRP(list)) return list;
283 ScmObj tortoise = list, hare = list;
284
285 ScmObj start = SCM_NIL, last = SCM_NIL;
286 for (;;) {
287 if (!SCM_PAIRP(hare)) break;
288 SCM_APPEND1(start, last, SCM_CAR(hare));
289 hare = SCM_CDR(hare);
290
291 if (!SCM_PAIRP(hare)) break;
292 SCM_APPEND1(start, last, SCM_CAR(hare));
293 hare = SCM_CDR(hare);
294 tortoise = SCM_CDR(tortoise);
295 if (hare == tortoise) {
296 Scm_Error("Attempt to copy a circular list: %S", list);
297 }
298 }
299 if (!SCM_NULLP(hare)) SCM_SET_CDR_UNCHECKED(last, hare);
300 return start;
301 }
302
303 /* Scm_AlistCopy(alist)
304 * Copy the spine and each pair of alist. If there's non-pair element
305 * it's included as is. We detect a cycle.
306 * NB: We won't allow 'dotted' alist.
307 */
308 ScmObj Scm_AlistCopy(ScmObj alist)
309 {
310 if (!SCM_PAIRP(alist)) return alist;
311 ScmObj tortoise = alist, hare = alist;
312
313 ScmObj start = SCM_NIL, last = SCM_NIL;
314 for (;;) {
315 if (!SCM_PAIRP(hare)) break;
316 if (SCM_PAIRP(SCM_CAR(hare))) {
317 ScmObj p = Scm_Cons(SCM_CAAR(hare), SCM_CDAR(hare));
318 SCM_APPEND1(start, last, p);
319 } else {
320 SCM_APPEND1(start, last, SCM_CAR(hare));
321 }
322 hare = SCM_CDR(hare);
323
324 if (!SCM_PAIRP(hare)) break;
325 if (SCM_PAIRP(SCM_CAR(hare))) {
326 ScmObj p = Scm_Cons(SCM_CAAR(hare), SCM_CDAR(hare));
327 SCM_APPEND1(start, last, p);
328 } else {
329 SCM_APPEND1(start, last, SCM_CAR(hare));
330 }
331 hare = SCM_CDR(hare);
332
333 tortoise = SCM_CDR(tortoise);
334 if (hare == tortoise) {
335 Scm_Error("Attempt to copy a circular alist: %S", alist);
336 }
337 }
338 if (!SCM_NULLP(hare)) Scm_Error("Dotted alist isn't allowed: %S", alist);
339 return start;
340 }
341
342
343 /* Scm_MakeList(len, fill)
344 * Make a list of specified length.
345 * Note that <len> is C-integer.
346 */
347
348 ScmObj Scm_MakeList(ScmSmallInt len, ScmObj fill)
349 {
350 if (len < 0) {
351 Scm_Error("make-list: negative length given: %ld", len);
352 }
353 ScmObj start = SCM_NIL, last = SCM_NIL;
354 while (len--) {
355 SCM_APPEND1(start, last, fill);
356 }
357 return start;
358 }
359
360
361 /* Scm_Append2X(list, obj)
362 * Replace cdr of last pair of LIST for OBJ.
363 * If LIST is not a pair, return OBJ.
364 */
365
366 ScmObj Scm_Append2X(ScmObj list, ScmObj obj)
367 {
368 ScmObj cp;
369 SCM_FOR_EACH(cp, list) {
370 if (SCM_NULLP(SCM_CDR(cp))) {
371 Scm_SetCdr(cp, obj);
372 return list;
373 }
374 }
375 return obj;
376 }
377
378 /* Scm_Append2(list, obj)
379 * Copy LIST and append OBJ to it.
380 * If LIST is not a pair, return OBJ.
381 */
382
383 ScmObj Scm_Append2(ScmObj list, ScmObj obj)
384 {
385 if (SCM_NULLP(list)) return obj;
386
387 ScmObj cp, start = SCM_NIL, last = SCM_NIL;
388 SCM_FOR_EACH(cp, list) {
389 SCM_APPEND1(start, last, SCM_CAR(cp));
390 }
391 if (!SCM_NULLP(cp)) {
392 Scm_Error("proper list required, but got %S", list);
393 }
394 SCM_SET_CDR_UNCHECKED(last, obj);
395
396 return start;
397 }
398
399 ScmObj Scm_Append(ScmObj args)
400 {
401 ScmObj start = SCM_NIL, last = SCM_NIL, cp;
402 SCM_FOR_EACH(cp, args) {
403 if (!SCM_PAIRP(SCM_CDR(cp))) {
404 if (SCM_NULLP(start)) return SCM_CAR(cp);
405 SCM_SET_CDR_UNCHECKED(last, SCM_CAR(cp));
406 break;
407 } else if (SCM_NULLP(SCM_CAR(cp))) {
408 continue;
409 } else if (!SCM_PAIRP(SCM_CAR(cp))) {
410 Scm_Error("pair required, but got %S", SCM_CAR(cp));
411 } else {
412 SCM_APPEND(start, last, Scm_CopyList(SCM_CAR(cp)));
413 if (SCM_PAIRP(last) && !SCM_NULLP(SCM_CDR(last))) {
414 Scm_Error("proper list required, but got %S", SCM_CAR(cp));
415 }
416 }
417 }
418 return start;
419 }
420
421 /* Scm_Reverse2(list, tail)
422 * Reverse LIST, and append TAIL to the result.
423 * If LIST is an improper list, cdr of the last pair is ignored.
424 * If LIST is not a pair, TAIL is returned.
425 * Scm_Reverse(list)
426 * Scm_Reverse2(list, SCM_NIL). Just for the backward compatibility.
427 */
428
429 ScmObj Scm_Reverse2(ScmObj list, ScmObj tail)
430 {
431 if (!SCM_PAIRP(list)) return tail;
432
433 ScmPair *p = SCM_NEW(ScmPair);
434 SCM_SET_CAR_UNCHECKED(p, SCM_NIL);
435 SCM_SET_CDR_UNCHECKED(p, tail);
436 ScmObj result = SCM_OBJ(p);
437 ScmObj cp;
438 SCM_FOR_EACH(cp, list) {
439 SCM_SET_CAR_UNCHECKED(result, SCM_CAR(cp));
440 p = SCM_NEW(ScmPair);
441 SCM_SET_CAR_UNCHECKED(p, SCM_NIL);
442 SCM_SET_CDR_UNCHECKED(p, result);
443 result = SCM_OBJ(p);
444 }
445 return SCM_CDR(result);
446 }
447
448 ScmObj Scm_Reverse(ScmObj list)
449 {
450 return Scm_Reverse2(list, SCM_NIL);
451 }
452
453
454 /* Scm_Reverse2X(list, tail)
455 * Return reversed list of LIST. Pairs in previous LIST is used to
456 * create new list. TAIL is appended to the result.
457 * If LIST is not a pair, returns TAIL.
458 * If LIST is an improper list, cdr of the last cell is ignored.
459 */
460
461 ScmObj Scm_Reverse2X(ScmObj list, ScmObj tail)
462 {
463 if (!SCM_PAIRP(list)) return tail;
464 ScmObj first, next, result = tail;
465 for (first = list; SCM_PAIRP(first); first = next) {
466 next = SCM_CDR(first);
467 Scm_SetCdr(first, result);
468 result = first;
469 }
470 return result;
471 }
472
473 ScmObj Scm_ReverseX(ScmObj list)
474 {
475 return Scm_Reverse2X(list, SCM_NIL);
476 }
477
478 /* Scm_ListTail(list, i, fallback)
479 * Scm_ListRef(list, i, fallback)
480 * Note that i is C-INTEGER. If i is out of bound, signal error.
481 */
482
483 ScmObj Scm_ListTail(ScmObj list, ScmSmallInt i, ScmObj fallback)
484 {
485 if (i < 0) goto err;
486 ScmSmallInt cnt = i;
487 while (cnt-- > 0) {
488 if (!SCM_PAIRP(list)) goto err;
489 list = SCM_CDR(list);
490 }
491 return list;
492 err:
493 if (SCM_UNBOUNDP(fallback)) Scm_Error("argument out of range: %ld", i);
494 return fallback;
495 }
496
497 ScmObj Scm_ListRef(ScmObj list, ScmSmallInt i, ScmObj fallback)
498 {
499 if (i < 0) goto err;
500 for (ScmSmallInt k=0; k<i; k++) {
501 if (!SCM_PAIRP(list)) goto err;
502 list = SCM_CDR(list);
503 }
504 if (!SCM_PAIRP(list)) goto err;
505 return SCM_CAR(list);
506 err:
507 if (SCM_UNBOUNDP(fallback)) {
508 Scm_Error("argument out of range: %ld", i);
509 }
510 return fallback;
511 }
512
513 /* Scm_LastPair(l)
514 * Return last pair of (maybe improper) list L.
515 * If L is not a pair, signal error.
516 */
517
518 ScmObj Scm_LastPair(ScmObj l)
519 {
520 if (!SCM_PAIRP(l)) Scm_Error("pair required: %S", l);
521
522 ScmObj slow = l;
523 for (;;) {
524 if (!SCM_PAIRP(SCM_CDR(l))) return l;
525 l = SCM_CDR(l);
526 if (!SCM_PAIRP(SCM_CDR(l))) return l;
527 l = SCM_CDR(l);
528 slow = SCM_CDR(slow);
529 if (l == slow) Scm_Error("list is circular: %S", l);
530 }
531 return SCM_UNDEFINED; /* NOTREACHED */
532 }
533
534 /* Scm_Memq(obj, list)
535 * Scm_Memv(obj, list)
536 * Scm_Member(obj, list)
537 * LIST must be a list. Return the first sublist whose car is obj.
538 * If obj doesn't occur in LIST, or LIST is not a pair, #f is returned.
539 */
540
541 ScmObj Scm_Memq(ScmObj obj, ScmObj list)
542 {
543 SCM_FOR_EACH(list, list) if (obj == SCM_CAR(list)) return list;
544 return SCM_FALSE;
545 }
546
547 ScmObj Scm_Memv(ScmObj obj, ScmObj list)
548 {
549 SCM_FOR_EACH(list, list) {
550 if (Scm_EqvP(obj, SCM_CAR(list))) return list;
551 }
552 return SCM_FALSE;
553 }
554
555 ScmObj Scm_Member(ScmObj obj, ScmObj list, int cmpmode)
556 {
557 SCM_FOR_EACH(list, list) {
558 if (Scm_EqualM(obj, SCM_CAR(list), cmpmode)) return list;
559 }
560 return SCM_FALSE;
561 }
562
563 /* delete. */
564 ScmObj Scm_Delete(ScmObj obj, ScmObj list, int cmpmode)
565 {
566 if (SCM_NULLP(list)) return SCM_NIL;
567
568 ScmObj start = SCM_NIL, last = SCM_NIL, cp, prev = list;
569 SCM_FOR_EACH(cp, list) {
570 if (Scm_EqualM(obj, SCM_CAR(cp), cmpmode)) {
571 for (; prev != cp; prev = SCM_CDR(prev))
572 SCM_APPEND1(start, last, SCM_CAR(prev));
573 prev = SCM_CDR(cp);
574 }
575 }
576 if (list == prev) return list;
577 if (SCM_NULLP(start)) return prev;
578 if (SCM_PAIRP(prev)) SCM_SET_CDR(last, prev);
579 return start;
580 }
581
582 ScmObj Scm_DeleteX(ScmObj obj, ScmObj list, int cmpmode)
583 {
584 ScmObj cp, prev = SCM_NIL;
585 SCM_FOR_EACH(cp, list) {
586 if (Scm_EqualM(obj, SCM_CAR(cp), cmpmode)) {
587 if (SCM_NULLP(prev)) {
588 list = SCM_CDR(cp);
589 } else {
590 Scm_SetCdr(prev, SCM_CDR(cp));
591 }
592 } else {
593 prev = cp;
594 }
595 }
596 return list;
597 }
598
599
600 /*
601 * assq, assv, assoc
602 * ALIST must be a list of pairs. Return the first pair whose car
603 * is obj. If ALIST contains non pair, it's silently ignored.
604 */
605
606 ScmObj Scm_Assq(ScmObj obj, ScmObj alist)
607 {
608 if (!SCM_LISTP(alist)) Scm_Error("assq: list required, but got %S", alist);
609 ScmObj cp;
610 SCM_FOR_EACH(cp,alist) {
611 ScmObj entry = SCM_CAR(cp);
612 if (!SCM_PAIRP(entry)) continue;
613 if (obj == SCM_CAR(entry)) return entry;
614 }
615 return SCM_FALSE;
616 }
617
618 ScmObj Scm_Assv(ScmObj obj, ScmObj alist)
619 {
620 if (!SCM_LISTP(alist)) Scm_Error("assv: list required, but got %S", alist);
621 ScmObj cp;
622 SCM_FOR_EACH(cp,alist) {
623 ScmObj entry = SCM_CAR(cp);
624 if (!SCM_PAIRP(entry)) continue;
625 if (Scm_EqvP(obj, SCM_CAR(entry))) return entry;
626 }
627 return SCM_FALSE;
628 }
629
630 ScmObj Scm_Assoc(ScmObj obj, ScmObj alist, int cmpmode)
631 {
632 if (!SCM_LISTP(alist)) Scm_Error("assoc: list required, but got %S", alist);
633 ScmObj cp;
634 SCM_FOR_EACH(cp,alist) {
635 ScmObj entry = SCM_CAR(cp);
636 if (!SCM_PAIRP(entry)) continue;
637 if (Scm_EqualM(obj, SCM_CAR(entry), cmpmode)) return entry;
638 }
639 return SCM_FALSE;
640 }
641
642 /* Assoc-delete */
643 ScmObj Scm_AssocDelete(ScmObj elt, ScmObj alist, int cmpmode)
644 {
645 if (!SCM_LISTP(alist)) {
646 Scm_Error("assoc-delete: list required, but got %S", alist);
647 }
648 if (SCM_NULLP(alist)) return SCM_NIL;
649
650 ScmObj start = SCM_NIL, last = SCM_NIL, cp, p, prev = alist;
651 SCM_FOR_EACH(cp, alist) {
652 p = SCM_CAR(cp);
653 if (SCM_PAIRP(p)) {
654 if (Scm_EqualM(elt, SCM_CAR(p), cmpmode)) {
655 for (; prev != cp; prev = SCM_CDR(prev))
656 SCM_APPEND1(start, last, SCM_CAR(prev));
657 prev = SCM_CDR(cp);
658 }
659 }
660 }
661 if (alist == prev) return alist;
662 if (SCM_NULLP(start)) return prev;
663 if (SCM_PAIRP(prev)) SCM_SET_CDR(last, prev);
664 return start;
665 }
666
667 ScmObj Scm_AssocDeleteX(ScmObj elt, ScmObj alist, int cmpmode)
668 {
669 if (!SCM_LISTP(alist)) {
670 Scm_Error("assoc-delete!: list required, but got %S", alist);
671 }
672 ScmObj cp, prev = SCM_NIL;
673 SCM_FOR_EACH(cp, alist) {
674 ScmObj e = SCM_CAR(cp);
675 if (SCM_PAIRP(e)) {
676 if (Scm_EqualM(elt, SCM_CAR(e), cmpmode)) {
677 if (SCM_NULLP(prev)) {
678 alist = SCM_CDR(cp);
679 continue;
680 } else {
681 Scm_SetCdr(prev, SCM_CDR(cp));
682 }
683 }
684 }
685 prev = cp;
686 }
687 return alist;
688 }
689
690 /* DeleteDuplicates. preserve the order of original list. N^2 algorithm */
691
692 ScmObj Scm_DeleteDuplicates(ScmObj list, int cmpmode)
693 {
694 ScmObj result = SCM_NIL, tail = SCM_NIL, lp;
695 SCM_FOR_EACH(lp, list) {
696 if (SCM_FALSEP(Scm_Member(SCM_CAR(lp), result, cmpmode))) {
697 SCM_APPEND1(result, tail, SCM_CAR(lp));
698 }
699 }
700 if (!SCM_NULLP(lp) && !SCM_NULLP(tail)) SCM_SET_CDR(tail, lp);
701 return result;
702 }
703
704 ScmObj Scm_DeleteDuplicatesX(ScmObj list, int cmpmode)
705 {
706 ScmObj lp;
707
708 SCM_FOR_EACH(lp, list) {
709 ScmObj obj = SCM_CAR(lp);
710 ScmObj tail = Scm_DeleteX(obj, SCM_CDR(lp), cmpmode);
711 if (SCM_CDR(lp) != tail) Scm_SetCdr(lp, tail);
712 }
713 return list;
714 }
715
716 /*
717 * Monotonic Merge
718 *
719 * Merge lists, keeping the order of elements (left to right) in each
720 * list. If there's more than one way to order an element, choose the
721 * first one appears in the given list of lists.
722 * Returns SCM_FALSE if the lists are inconsistent to be ordered
723 * in the way.
724 *
725 * START is an item of the starting point. It is inserted into the result
726 * first. SEQUENCES is a list of lists describing the order of preference.
727 *
728 * The algorithm is used in C3 linearization of class precedence
729 * calculation, described in the paper
730 * http://www.webcom.com/~haahr/dylan/linearization-oopsla96.html.
731 * Since the algorithm is generally useful, I implement the core routine
732 * of the algorithm here.
733 */
734
735 ScmObj Scm_MonotonicMerge(ScmObj sequences)
736 {
737 ScmObj result = SCM_NIL;
738 int nseqs = Scm_Length(sequences);
739 if (nseqs < 0) Scm_Error("bad list of sequences: %S", sequences);
740 ScmObj *seqv = SCM_NEW_ARRAY(ScmObj, nseqs);
741 for (ScmObj *sp=seqv;
742 SCM_PAIRP(sequences);
743 sp++, sequences=SCM_CDR(sequences)) {
744 *sp = SCM_CAR(sequences);
745 }
746
747 for (;;) {
748 /* have we consumed all the inputs? */
749 ScmObj *sp;
750 for (sp=seqv; sp<seqv+nseqs; sp++) {
751 if (!SCM_NULLP(*sp)) break;
752 }
753 if (sp == seqv+nseqs) return Scm_ReverseX(result);
754
755 /* select candidate */
756 ScmObj next = SCM_FALSE;
757 for (sp = seqv; sp < seqv+nseqs; sp++) {
758 if (!SCM_PAIRP(*sp)) continue;
759 ScmObj h = SCM_CAR(*sp);
760 ScmObj *tp;
761 for (tp = seqv; tp < seqv+nseqs; tp++) {
762 if (!SCM_PAIRP(*tp)) continue;
763 if (!SCM_FALSEP(Scm_Memq(h, SCM_CDR(*tp)))) {
764 break;
765 }
766 }
767 if (tp != seqv+nseqs) continue;
768 next = h;
769 break;
770 }
771
772 if (SCM_FALSEP(next)) return SCM_FALSE; /* inconsistent */
773
774 /* move the candidate to the result */
775 result = Scm_Cons(next, result);
776 for (sp = seqv; sp < seqv+nseqs; sp++) {
777 if (SCM_PAIRP(*sp) && SCM_EQ(next, SCM_CAR(*sp))) {
778 *sp = SCM_CDR(*sp);
779 }
780 }
781 }
782 /* NOTREACHED */
783 }
784
785 /*
786 * Extended pairs
787 */
788
789 static ScmObj make_extended_pair(ScmExtendedPairDescriptor *desc,
790 ScmObj car, ScmObj cdr, ScmObj attrs)
791 {
792 ScmRealExtendedPair *xp = SCM_NEW(ScmRealExtendedPair);
793 /* ScmRealExtendedPair is not an ScmObj, and
794 ScmExtendedPairDescriptor is not an ScmClass. To avoid confusion,
795 we manually tweak tag bits.
796 */
797 xp->hiddenTag = SCM_WORD((ScmByte*)desc + 7);
798 xp->data.car = car;
799 xp->data.cdr = cdr;
800 xp->data.attributes = attrs;
801 return SCM_OBJ(&xp->data); /* hide the first word */
802 }
803
804 /* "vanilla" extended pair. used mainly to hold extra attributes, but
805 otherwise behaves like normal pairs.
806 NB: Static initialization with ScmClass* requires extra care on
807 Windows. To avoid complication, we initialize the klass field in
808 _Init() routine.
809 */
810 static ScmExtendedPairDescriptor mpair_desc SCM_ALIGN8 = {
811 NULL, /* will be SCM_CLASS_PAIR */
812 0,
813 NULL,
814 NULL
815 };
816
817 ScmObj Scm_MakeExtendedPair(ScmObj car, ScmObj cdr, ScmObj attrs)
818 {
819 return make_extended_pair(&mpair_desc, car, cdr, attrs);
820 }
821
822 /* Returns NULL if p isn't an extended pair. */
823 ScmExtendedPairDescriptor *Scm__GetExtendedPairDescriptor(ScmObj p)
824 {
825 if (!SCM_EXTENDED_PAIR_P(p)) return NULL;
826 ScmRealExtendedPair *z = (ScmRealExtendedPair*)(((ScmObj*)p) - 1);
827 SCM_ASSERT((z->hiddenTag&0x7) == 0x7);
828 return (ScmExtendedPairDescriptor *)(z->hiddenTag-7);
829 }
830
831 /* Returns vanilla extended pair descriptor */
832 ScmExtendedPairDescriptor *Scm__GetDefaultExtendedPairDesctiptor()
833 {
834 return &mpair_desc;
835 }
836
837 ScmObj Scm_PairAttr(ScmPair *pair)
838 {
839 if (SCM_EXTENDED_PAIR_P(pair)) {
840 return SCM_EXTENDED_PAIR(pair)->attributes;
841 } else {
842 return SCM_NIL;
843 }
844 }
845
846 /* The common scenario is to use ExtendedCons in place of Cons,
847 then add attributes later. So we provide this. */
848 ScmObj Scm_ExtendedCons(ScmObj car, ScmObj cdr)
849 {
850 return Scm_MakeExtendedPair(car, cdr, SCM_NIL);
851 }
852
853 ScmObj Scm_PairAttrGet(ScmPair *pair, ScmObj key, ScmObj fallback)
854 {
855 if (!SCM_EXTENDED_PAIR_P(pair)) {
856 goto fallback;
857 }
858
859 ScmObj p = Scm_Assq(key, SCM_EXTENDED_PAIR(pair)->attributes);
860 if (SCM_PAIRP(p)) return SCM_CDR(p);
861 fallback:
862 if (fallback == SCM_UNBOUND)
863 Scm_Error("No value associated with key %S in pair attributes of %S",
864 key, SCM_OBJ(pair));
865 return fallback;
866 }
867
868 ScmObj Scm_PairAttrSet(ScmPair *pair, ScmObj key, ScmObj value)
869 {
870 if (!SCM_EXTENDED_PAIR_P(pair)) {
871 Scm_Error("Cannot set pair attribute (%S) to non-extended pair: %S",
872 key, SCM_OBJ(pair));
873 }
874
875 /* We update the attribute list non-destructively.
876 In case if two threads update the list simultaneously, one change
877 can be lost, but no invalid access can occur. Guaranteeing mutex
878 is the caller's responsibility, though.
879 */
880 ScmObj xs, attrs = SCM_EXTENDED_PAIR(pair)->attributes;
881 SCM_FOR_EACH(xs, attrs) {
882 SCM_ASSERT(SCM_PAIRP(SCM_CAR(xs)));
883 if (SCM_EQ(SCM_CAAR(xs), key)) {
884 /* need to copy up to here */
885 ScmObj h = SCM_NIL, t = SCM_NIL, ys;
886 SCM_FOR_EACH(ys, attrs) {
887 if (SCM_EQ(ys, xs)) {
888 SCM_APPEND1(h, t, Scm_Cons(key, value));
889 SCM_APPEND(h, t, SCM_CDR(xs));
890 SCM_EXTENDED_PAIR(pair)->attributes = h;
891 return SCM_UNDEFINED;
892 }
893 SCM_APPEND1(h, t, SCM_CAR(ys));
894 }
895 SCM_ASSERT(FALSE); /* Shouldn't be here */
896 }
897 }
898 SCM_EXTENDED_PAIR(pair)->attributes = Scm_Acons(key, value, attrs);
899 return SCM_UNDEFINED;
900 }
901
902 /*
903 * Immutable pairs
904 */
905
906 /* not cheap. usually you don't want to check this and let it catched
907 in set-car!/set-cdr!. */
908 int Scm_ImmutablePairP(ScmObj obj)
909 {
910 if (!SCM_EXTENDED_PAIR_P(obj)) return FALSE;
911 ScmExtendedPairDescriptor *d = Scm__GetExtendedPairDescriptor(obj);
912 return d->flags & SCM_PAIR_IMMUTABLE;
913 }
914
915 static ScmExtendedPairDescriptor ipair_desc SCM_ALIGN8 = {
916 NULL, /* will be SCM_CLASS_PAIR. see above. */
917 SCM_PAIR_IMMUTABLE,
918 NULL,
919 NULL
920 };
921
922 ScmObj Scm_MakeImmutablePair(ScmObj car, ScmObj cdr, ScmObj attrs)
923 {
924 return make_extended_pair(&ipair_desc, car, cdr, attrs);
925 }
926
927 void Scm__InitList()
928 {
929 mpair_desc.klass = SCM_CLASS_PAIR;
930 ipair_desc.klass = SCM_CLASS_PAIR;
931 }
932
933 /* Temporary - Check if normal pairs are all aligned with 2-word boundary */
934 #if GAUCHE_CHECK_PAIR_ALIGNMENT
935 int Scm_CheckingPairP(ScmObj obj)
936 {
937 if (SCM_HPTRP(obj)&&(SCM_HTAG(obj)!=7||Scm_PairP(SCM_OBJ(obj)))) {
938 if (SCM_WORD(obj) & SIZEOF_LONG) {
939 if ((SCM_WORD((ScmObj*)obj - 1) & 7) != 7) {
940 fprintf(stderr, "Unaligned pair %p\n", obj);
941 }
942 }
943 return TRUE;
944 }
945 return FALSE;
946 }
947 #endif /*GAUCHE_CHECK_PAIR_ALIGNMENT*/