1 /*
2 * List functions for CLISP
3 * Bruno Haible 1990-2005, 2017
4 * Marcus Daniels 8.4.1994
5 * Sam Steingold 1999-2009
6 * German comments and names translated into English: Reini Urban 2008-01
7 */
8 #include "lispbibl.c"
9
10 /* (PROG1 (CONS STACK_1 STACK_0) skipSTACK(2))
11 removes 2 objects from STACK
12 can trigger GC */
cons_from_stack(void)13 local inline maygc object cons_from_stack (void)
14 {
15 var object ret = allocate_cons();
16 Cdr(ret) = popSTACK();
17 Car(ret) = popSTACK();
18 return ret;
19 }
20
21 /* UP: Copies a list
22 copy_list(list)
23 > list: List
24 < result: Copy of the list
25 can trigger GC */
copy_list(object old_list)26 modexp maygc object copy_list (object old_list) {
27 /* Method: (copy-list l) = (mapcar #'identity l), mapcar forwards */
28 if (atomp(old_list))
29 return old_list;
30 else { /* List with at least one element */
31 var object run;
32 pushSTACK(old_list);
33 {
34 var object new_list = allocate_cons();
35 run = STACK_0; /* run runs through the old list */
36 Car(new_list) = Car(run);
37 STACK_0 = new_list;
38 pushSTACK(new_list);
39 }
40 /* Loop: STACK_1 is the whole copy, STACK_0 = LAST of it, */
41 /* run = the correspondend Cons of the original list. */
42 while ( run=Cdr(run), consp(run) ) {
43 /* one more Cons */
44 pushSTACK(run); /* save run */
45 var object new_cons = allocate_cons(); /* allocate new Cons */
46 run = popSTACK(); /* run back */
47 Cdr(STACK_0) = new_cons; /* and put as CDR of the LAST */
48 Car(new_cons) = Car(run); /* copy CAR */
49 STACK_0 = new_cons; /* this is now the new LAST */
50 }
51 Cdr(popSTACK()) = run; /* keep same (CDR (LAST old_list)) */
52 return popSTACK();
53 }
54 }
55
56 /* UP: Reverses a list by copying
57 reverse(list)
58 > list: List (x1 ... xm)
59 < result: reversed List (xm ... x1)
60 can trigger GC */
reverse(object list)61 global maygc object reverse (object list) {
62 pushSTACK(list); pushSTACK(NIL);
63 while (!endp(list)) {
64 /* Here is for r=1,...,m: */
65 /* STACK_0 = (xr-1 ... x1), list = (xr ... xm) */
66 STACK_1 = Cdr(list);
67 /* Here is for r=1,...,m: */
68 /* STACK_0 = (xr-1 ... x1), STACK_1 = (xr+1 ... xm) */
69 pushSTACK(Car(list));
70 {
71 var object new_cons = allocate_cons();
72 Car(new_cons) = popSTACK(); /* = xr */
73 Cdr(new_cons) = STACK_0; /* = (xr-1 ... x1) */
74 STACK_0 = new_cons; /* = (xr ... x1) */
75 }
76 list = STACK_1; /* list := (xr+1 ... xm) */
77 }
78 list = popSTACK(); skipSTACK(1); return list;
79 }
80 #if 0
81 /* another possibility: */
82 global object reverse (object list) {
83 pushSTACK(list); pushSTACK(NIL);
84 while (mconsp(STACK_1)) {
85 var object new_cons = allocate_cons();
86 var object old_cons = STACK_1;
87 STACK_1 = Cdr(old_cons);
88 Car(new_cons) = Car(old_cons);
89 Cdr(new_cons) = STACK_0;
90 STACK_0 = new_cons;
91 }
92 list = popSTACK(); skipSTACK(1); return list;
93 }
94 #endif
95
96 /* UP: get the list length and the last atom
97 > obj: object
98 < len: list length
99 < last: the last atom */
llength1(object list,object * last)100 modexp uintL llength1 (object list, object* last) {
101 var uintL count = 0;
102 while (consp(list)) {
103 count++; list=Cdr(list);
104 }
105 if (last) *last = list;
106 return count;
107 }
108
109 /* UP: Constructs a list with exactly len elements.
110 make_list(len)
111 > STACK_0: Initial value for all elements
112 > uintL len: wanted list length
113 < result: List with len elements
114 can trigger GC */
make_list(uintL len)115 modexp maygc object make_list (uintL len) {
116 pushSTACK(NIL);
117 while (len--) {
118 /* STACK_0 = old list, STACK_1 = initial value */
119 var object new_cons = allocate_cons();
120 Car(new_cons) = STACK_1; Cdr(new_cons) = STACK_0;
121 STACK_0 = new_cons;
122 }
123 return popSTACK();
124 }
125
126 /* UP: Reverses a list in-place, destructively.
127 nreverse(list)
128 > list: List (x1 ... xm)
129 < result: List (xm ... x1), EQ to the old */
nreverse(object list)130 modexp object nreverse (object list) {
131 /* Algorithm:
132 (lambda (L)
133 (cond ((atom L) L)
134 ((atom (cdr L)) L)
135 ((atom (cddr L)) (rotatef (car L) (cadr L)) L)
136 (t (let ((L1 (cdr L)))
137 (do ((L3 L1 (cdr L3))
138 (L2 nil (rplacd L3 L2)))
139 ((atom (cdr L3))
140 (setf (cdr L) L2)
141 (setf (cdr L1) L3)
142 (rotatef (car L) (car L3))))
143 L)))) */
144 if (consp(list)) { /* (atom L) -> L */
145 var object list3 = Cdr(list); /* L3 := (cdr L) */
146 if (!endp(list3)) { /* (atom (cdr L)) -> L */
147 if (!endp(Cdr(list3))) {
148 var object list1 = list3; /* Begin with L1 = L3 = (cdr L) */
149 var object list2 = NIL; /* and L2 = NIL */
150 do {
151 var object h = Cdr(list3); /* save (cdr L3), */
152 Cdr(list3) = list2; /* replace by L2, */
153 list2 = list3; /* L2 := old L3 */
154 list3 = h; /* L3 := old (cdr L3) */
155 } while (!endp(Cdr(list3))); /* (atom (cdr L3)) -> end */
156 /* L3 is the last and L2 the last but one list Cons. */
157 Cdr(list) = list2; /* (setf (cdr L) L2) */
158 Cdr(list1) = list3; /* (setf (cdr L1) L3) */
159 }
160 /* exchange (car list) and (car list3): */
161 var object h = Car(list);
162 Car(list) = Car(list3);
163 Car(list3) = h;
164 }
165 }
166 return list;
167 }
168
169 /* UP: A0 := (nreconc A0 A1)
170 nreconc(list,obj)
171 > list: List
172 > obj: Object
173 < result: (nreconc A0 A1) */
nreconc(object list,object obj)174 global object nreconc (object list, object obj) {
175 if (!endp(list)) { /* (atom L) -> L */
176 var object list3 = Cdr(list); /* L3 := (cdr L) */
177 if (!endp(list3)) { /* (atom (cdr L)) -> L */
178 if (!endp(Cdr(list3))) {
179 var object list1 = list3; /* Begin with L1 = L3 = (cdr L) */
180 var object list2 = NIL; /* and L2 = NIL */
181 do {
182 var object h = Cdr(list3); /* save (cdr L3), */
183 Cdr(list3) = list2; /* replace by L2, */
184 list2 = list3; /* L2 := old L3 */
185 list3 = h; /* L3 := old (cdr L3) */
186 } while (!endp(Cdr(list3))); /* (atom (cdr L3)) -> end */
187 /* L3 is the last and L2 the last but one list Cons. */
188 Cdr(list) = list2; /* (setf (cdr L) L2) */
189 Cdr(list1) = list3; /* (setf (cdr L1) L3) */
190 }
191 /* exchange (car list) and (car list3): */
192 {
193 var object h = Car(list);
194 Car(list) = Car(list3);
195 Car(list3) = h;
196 }
197 Cdr(list3) = obj; /* (setf (cdr L3) O) */
198 } else {
199 Cdr(list) = obj;
200 }
201 return list;
202 } else
203 return obj;
204 }
205
206 /* UP: Construct (delete obj (the list list) :test #'EQ)
207 deleteq(list,obj)
208 Remove from list all elements EQ to obj.
209 > obj: to be removed element
210 > list: List
211 < result: modified List */
deleteq(object list,object obj)212 modexp object deleteq (object list, object obj) {
213 var object list1 = list;
214 var object list2 = list;
215 while (!atomp(list2)) {
216 /* Here is either list1=list2=list or (cdr list1) = list2. */
217 if (eq(Car(list2),obj))
218 /* Remove (car list2): */
219 if (eq(list2,list)) {
220 /* Still at the start of the list */
221 list2 = list1 = list = Cdr(list2);
222 } else {
223 /* advanced the start of the list */
224 Cdr(list1) = list2 = Cdr(list2);
225 }
226 else {
227 /* Remove nothing, advance: */
228 list1 = list2; list2 = Cdr(list2);
229 }
230 }
231 return list;
232 }
233
234 /* UP: Returns (car obj), with type check */
car(object obj)235 local object car (object obj) {
236 if (consp(obj))
237 return Car(obj);
238 else if (nullp(obj))
239 return obj;
240 else
241 error_list(obj);
242 }
243
244 /* UP: Returns (cdr obj), with type check */
cdr(object obj)245 local object cdr (object obj) {
246 if (consp(obj))
247 return Cdr(obj);
248 else if (nullp(obj))
249 return obj;
250 else
251 error_list(obj);
252 }
253
254 LISPFUNNR(car,1)
255 { /* (CAR list), CLTL p. 262 */
256 VALUES1(car(popSTACK()));
257 }
258
259 LISPFUNNR(cdr,1)
260 { /* (CDR list), CLTL p. 262 */
261 VALUES1(cdr(popSTACK()));
262 }
263
264 LISPFUNNR(caar,1)
265 { /* (CAAR list), CLTL p. 263 */
266 VALUES1(car(car(popSTACK())));
267 }
268
269 LISPFUNNR(cadr,1)
270 { /* (CADR list), CLTL p. 263 */
271 VALUES1(car(cdr(popSTACK())));
272 }
273
274 LISPFUNNR(cdar,1)
275 { /* (CDAR list), CLTL p. 263 */
276 VALUES1(cdr(car(popSTACK())));
277 }
278
279 LISPFUNNR(cddr,1)
280 { /* (CDDR list), CLTL p. 263 */
281 VALUES1(cdr(cdr(popSTACK())));
282 }
283
284 LISPFUNNR(caaar,1)
285 { /* (CAAAR list), CLTL p. 263 */
286 VALUES1(car(car(car(popSTACK()))));
287 }
288
289 LISPFUNNR(caadr,1)
290 { /* (CAADR list), CLTL p. 263 */
291 VALUES1(car(car(cdr(popSTACK()))));
292 }
293
294 LISPFUNNR(cadar,1)
295 { /* (CADAR list), CLTL p. 263 */
296 VALUES1(car(cdr(car(popSTACK()))));
297 }
298
299 LISPFUNNR(caddr,1)
300 { /* (CADDR list), CLTL p. 263 */
301 VALUES1(car(cdr(cdr(popSTACK()))));
302 }
303
304 LISPFUNNR(cdaar,1)
305 { /* (CDAAR list), CLTL p. 263 */
306 VALUES1(cdr(car(car(popSTACK()))));
307 }
308
309 LISPFUNNR(cdadr,1)
310 { /* (CDADR list), CLTL p. 263 */
311 VALUES1(cdr(car(cdr(popSTACK()))));
312 }
313
314 LISPFUNNR(cddar,1)
315 { /* (CDDAR list), CLTL p. 263 */
316 VALUES1(cdr(cdr(car(popSTACK()))));
317 }
318
319 LISPFUNNR(cdddr,1)
320 { /* (CDDDR list), CLTL p. 263 */
321 VALUES1(cdr(cdr(cdr(popSTACK()))));
322 }
323
324 LISPFUNNR(caaaar,1)
325 { /* (CAAAAR list), CLTL p. 263 */
326 VALUES1(car(car(car(car(popSTACK())))));
327 }
328
329 LISPFUNNR(caaadr,1)
330 { /* (CAAADR list), CLTL p. 263 */
331 VALUES1(car(car(car(cdr(popSTACK())))));
332 }
333
334 LISPFUNNR(caadar,1)
335 { /* (CAADAR list), CLTL p. 263 */
336 VALUES1(car(car(cdr(car(popSTACK())))));
337 }
338
339 LISPFUNNR(caaddr,1)
340 { /* (CAADDR list), CLTL p. 263 */
341 VALUES1(car(car(cdr(cdr(popSTACK())))));
342 }
343
344 LISPFUNNR(cadaar,1)
345 { /* (CADAAR list), CLTL p. 263 */
346 VALUES1(car(cdr(car(car(popSTACK())))));
347 }
348
349 LISPFUNNR(cadadr,1)
350 { /* (CADADR list), CLTL p. 263 */
351 VALUES1(car(cdr(car(cdr(popSTACK())))));
352 }
353
354 LISPFUNNR(caddar,1)
355 { /* (CADDAR list), CLTL p. 263 */
356 VALUES1(car(cdr(cdr(car(popSTACK())))));
357 }
358
359 LISPFUNNR(cadddr,1)
360 { /* (CADDDR list), CLTL p. 263 */
361 VALUES1(car(cdr(cdr(cdr(popSTACK())))));
362 }
363
364 LISPFUNNR(cdaaar,1)
365 { /* (CDAAAR list), CLTL p. 263 */
366 VALUES1(cdr(car(car(car(popSTACK())))));
367 }
368
369 LISPFUNNR(cdaadr,1)
370 { /* (CDAADR list), CLTL p. 263 */
371 VALUES1(cdr(car(car(cdr(popSTACK())))));
372 }
373
374 LISPFUNNR(cdadar,1)
375 { /* (CDADAR list), CLTL p. 263 */
376 VALUES1(cdr(car(cdr(car(popSTACK())))));
377 }
378
379 LISPFUNNR(cdaddr,1)
380 { /* (CDADDR list), CLTL p. 263 */
381 VALUES1(cdr(car(cdr(cdr(popSTACK())))));
382 }
383
384 LISPFUNNR(cddaar,1)
385 { /* (CDDAAR list), CLTL p. 263 */
386 VALUES1(cdr(cdr(car(car(popSTACK())))));
387 }
388
389 LISPFUNNR(cddadr,1)
390 { /* (CDDADR list), CLTL p. 263 */
391 VALUES1(cdr(cdr(car(cdr(popSTACK())))));
392 }
393
394 LISPFUNNR(cdddar,1)
395 { /* (CDDDAR list), CLTL p. 263 */
396 VALUES1(cdr(cdr(cdr(car(popSTACK())))));
397 }
398
399 LISPFUNNR(cddddr,1)
400 { /* (CDDDDR list), CLTL p. 263 */
401 VALUES1(cdr(cdr(cdr(cdr(popSTACK())))));
402 }
403
404 LISPFUN(cons,seclass_no_se,2,0,norest,nokey,0,NIL)
405 { /* (CONS obj1 obj2), CLTL p. 264 */
406 VALUES1(cons_from_stack());
407 }
408
409 /* UP: Tests the equality of two trees.
410 tree_equal(stackptr,pcall_test,arg1,arg2)
411 > arg1,arg2: two trees
412 > stackptr: Pointer to the stack
413 > A5: Adress of a test function, which compares arg1 and arg2 and may access
414 the :TEST/:TEST-NOT arguments in *(stackptr+1).L resp.
415 *(stackprt+0).L
416 < result: true if equal, otherwise false
417 can trigger GC */
tree_equal(const gcv_object_t * stackptr,funarg_t * pcall_test,object arg1,object arg2)418 local maygc bool tree_equal (const gcv_object_t* stackptr, funarg_t* pcall_test,
419 object arg1, object arg2) {
420 start:
421 if (atomp(arg1))
422 if (atomp(arg2))
423 /* arg1 and arg2 both are atoms */
424 return pcall_test(stackptr,arg1,arg2);
425 else
426 return false;
427 else
428 if (atomp(arg2))
429 return false;
430 else {
431 /* arg1 and arg2 both are Cons */
432 check_STACK(); check_SP();
433 pushSTACK(Cdr(arg1)); pushSTACK(Cdr(arg2));
434 if (tree_equal(stackptr,pcall_test,Car(arg1),Car(arg2))) { /* recursive on CARs */
435 /* if equal, compare tail-recursively the CDRs */
436 arg2 = popSTACK(); arg1 = popSTACK(); goto start;
437 } else {
438 skipSTACK(2); return false;
439 }
440 }
441 }
442
443 LISPFUN(tree_equal,seclass_default,2,0,norest,key,2, (kw(test),kw(test_not)) )
444 { /* (TREE-EQUAL x y :test :test-not), CLTL p. 264 */
445 var gcv_object_t* stackptr = &STACK_0;
446 /* check :TEST/:TEST-NOT arguments: */
447 var funarg_t* pcall_test = check_test_args(stackptr);
448 VALUES_IF(tree_equal(stackptr,pcall_test,STACK_3,STACK_2));
449 skipSTACK(4);
450 }
451
452 /* UP: check whether OBJ ends a proper list
453 endp(obj)
454 > obj: object
455 < result: true if obj is the list end NIL,
456 false if obj is a Cons.
457 error otherwise */
endp(object obj)458 modexp bool endp (object obj) {
459 if (consp(obj))
460 return false;
461 else if (nullp(obj))
462 return true;
463 else
464 error_proper_list_dotted(TheSubr(subr_self)->name,obj);
465 }
466
467 LISPFUNNF(endp,1)
468 { /* (ENDP object), CLTL p. 264 */
469 VALUES_IF(endp(popSTACK()));
470 }
471
472 /* Finds the length of a possibly circular or dotted list.
473 list_length(list,&dotted)
474 > list: an object
475 < result: the length (integer >= 0, or NIL for circular lists)
476 < dotted: if non-circular, the last atom, i.e., the indicator whether the list
477 is dotted
478 can trigger GC */
list_length(object list,object * dottedp)479 global maygc object list_length (object list, object *dottedp) {
480 /* (defun list-length (list)
481 (do ((n 0 (+ n 2))
482 (fast list (cddr fast))
483 (slow list (cdr slow)))
484 (nil)
485 (when (endp fast) (return n))
486 (when (endp (cdr fast)) (return (1+ n)))
487 (when (eq (cdr fast) slow) (return nil))))
488 (see CLtL p 265) */
489 var object fast = list;
490 var object slow = fast;
491 var uintL n = 0;
492 while (consp(fast)) {
493 fast = Cdr(fast); n++;
494 if (atomp(fast))
495 break;
496 if (eq(fast,slow))
497 return NIL;
498 fast = Cdr(fast); n++;
499 slow = Cdr(slow);
500 }
501 pushSTACK(fast);
502 var object len = UL_to_I(n);
503 *dottedp = popSTACK();
504 return len;
505 }
506
507 LISPFUNNR(list_length,1)
508 { /* (LIST-LENGTH list), CLTL p. 265 */
509 var object tail = NIL;
510 var object len = list_length(popSTACK(),&tail);
511 if (nullp(tail))
512 VALUES1(len);
513 else
514 error_proper_list_dotted(S(list_length),tail);
515 }
516
517 LISPFUNNR(list_length_dotted,1)
518 { /* traverses the list just once, otherwise equivalent to
519 (defun list-length-dotted (l)
520 (let ((ll (list-length l)))
521 (when ll (values ll (cdr (last l)))))) */
522 var object tail = NIL;
523 var object len = list_length(popSTACK(),&tail);
524 if (nullp(len))
525 VALUES1(NIL);
526 else
527 VALUES2(len,tail);
528 }
529
530 LISPFUNNR(list_length_proper,1)
531 { /* traverses the list just once, otherwise equivalent to
532 (defun list-length-proper (l)
533 (if (proper-list-p l)
534 (length l)
535 (error ...))) */
536 var object tail = NIL;
537 var object len = list_length(STACK_0,&tail);
538 if (!nullp(tail)) error_proper_list_dotted(S(list_length_proper),tail);
539 if (nullp(len)) error_proper_list_circular(S(list_length_proper),STACK_0);
540 VALUES1(len); skipSTACK(1);
541 }
542
543 LISPFUNNR(list_length_in_bounds_p,4)
544 { /* (sys::list-length-in-bounds-p obj n m restp) tests whether obj, as a list,
545 starts with at least n conses and is either a proper list with < m conses
546 or (if restp) has at least m conses or (if not restp) is a proper list with
547 exactly m conses. */
548 if (!posfixnump(STACK_2)) error_posfixnum(STACK_2);
549 if (!posfixnump(STACK_1)) error_posfixnum(STACK_1);
550 var object obj = STACK_3;
551 var uintV n = posfixnum_to_V(STACK_2);
552 var uintV i;
553 for (i = n; i > 0; i--) {
554 if (!consp(obj)) goto no;
555 obj = Cdr(obj);
556 }
557 { var uintV m = posfixnum_to_V(STACK_1);
558 if (m < n) goto no;
559 for (i = m-n; i > 0; i--) {
560 if (!consp(obj)) {
561 if (nullp(obj))
562 break;
563 else
564 goto no;
565 }
566 obj = Cdr(obj);
567 }
568 }
569 if (nullp(STACK_0) && !nullp(obj))
570 goto no;
571 VALUES1(T); skipSTACK(4); return;
572 no:
573 VALUES1(NIL); skipSTACK(4);
574 }
575
576 LISPFUN(proper_list_length_in_bounds_p,seclass_read,2,1,norest,nokey,0,NIL)
577 { /* (sys::proper-list-length-in-bounds-p obj n) tests whether obj is a
578 proper-list with at least n conses.
579 (sys::proper-list-length-in-bounds-p obj n m) tests whether obj is a
580 proper-list with at least n and at most m conses. */
581 if (!posfixnump(STACK_1)) error_posfixnum(STACK_1);
582 if (boundp(STACK_0) && !posfixnump(STACK_0)) error_posfixnum(STACK_0);
583 var object tail = NIL;
584 var object len = list_length(STACK_2,&tail);
585 if (nullp(tail) && !nullp(len)) {
586 var uintL l = I_to_UL(len);
587 if ((posfixnum_to_V(STACK_1) <= l)
588 && (!boundp(STACK_0) || (l <= posfixnum_to_V(STACK_0))))
589 VALUES1(T);
590 else
591 VALUES1(NIL);
592 } else
593 VALUES1(NIL);
594 skipSTACK(3);
595 }
596
597 /* proper_list_p(obj)
598 returns true if obj is a proper list, i.e. a list which is neither dotted
599 nor circular, i.e. a list which ends in NIL. */
proper_list_p(object obj)600 global bool proper_list_p (object obj) {
601 var object fast = obj;
602 var object slow = fast;
603 while (consp(fast)) {
604 fast = Cdr(fast);
605 if (atomp(fast))
606 break;
607 if (eq(fast,slow))
608 return false;
609 fast = Cdr(fast);
610 slow = Cdr(slow);
611 }
612 return nullp(fast);
613 }
614
615 /* We cannot have lists longer than 1<<32 for RAM reasons
616 but we must accept arbitrary positive integers in NTH, LAST &c.
617 Here we truncate large integers to ~0.
618 can trigger GC */
get_integer_truncate(object number)619 local maygc uintL get_integer_truncate (object number) {
620 /* for speed, handle the most common case first */
621 if (posfixnump(number)) {
622 #if (intVsize>intLsize)
623 if (posfixnum_to_V(number) >= vbitm(intLsize))
624 return ~(uintL)0; /* most-positive-uintL */
625 #endif
626 return posfixnum_to_V(number);
627 }
628 number = check_pos_integer(number);
629 if (uint32_p(number)) return I_to_UL(number);
630 return ~(uintL)0; /* most-positive-uintL */
631 }
632
633 LISPFUNNR(nth,2)
634 { /* (NTH integer list), CLTL p. 265 */
635 var uintL count = get_integer_truncate(STACK_1);
636 var object list = STACK_0;
637 while (count--) { list = cdr(list); } /* count CDRs */
638 VALUES1(car(list)); /* one CAR */
639 skipSTACK(2);
640 }
641
642 LISPFUNNR(first,1)
643 { /* (FIRST list), CLTL p. 266 */
644 VALUES1(car(popSTACK()));
645 }
646
647 LISPFUNNR(second,1)
648 { /* (SECOND list), CLTL p. 266 */
649 VALUES1(car(cdr(popSTACK())));
650 }
651
652 LISPFUNNR(third,1)
653 { /* (THIRD list), CLTL p. 266 */
654 VALUES1(car(cdr(cdr(popSTACK()))));
655 }
656
657 LISPFUNNR(fourth,1)
658 { /* (FOURTH list), CLTL p. 266 */
659 VALUES1(car(cdr(cdr(cdr(popSTACK())))));
660 }
661
662 LISPFUNNR(fifth,1)
663 { /* (FIFTH list), CLTL p. 266 */
664 VALUES1(car(cdr(cdr(cdr(cdr(popSTACK()))))));
665 }
666
667 LISPFUNNR(sixth,1)
668 { /* (SIXTH list), CLTL p. 266 */
669 VALUES1(car(cdr(cdr(cdr(cdr(cdr(popSTACK())))))));
670 }
671
672 LISPFUNNR(seventh,1)
673 { /* (SEVENTH list), CLTL p. 266 */
674 VALUES1(car(cdr(cdr(cdr(cdr(cdr(cdr(popSTACK()))))))));
675 }
676
677 LISPFUNNR(eighth,1)
678 { /* (EIGHTH list), CLTL p. 266 */
679 VALUES1(car(cdr(cdr(cdr(cdr(cdr(cdr(cdr(popSTACK())))))))));
680 }
681
682 LISPFUNNR(ninth,1)
683 { /* (NINTH list), CLTL p. 266 */
684 VALUES1(car(cdr(cdr(cdr(cdr(cdr(cdr(cdr(cdr(popSTACK()))))))))));
685 }
686
687 LISPFUNNR(tenth,1)
688 { /* (TENTH list), CLTL p. 266 */
689 VALUES1(car(cdr(cdr(cdr(cdr(cdr(cdr(cdr(cdr(cdr(popSTACK())))))))))));
690 }
691
692 LISPFUNNR(rest,1)
693 { /* (REST list), CLTL p. 266 */
694 VALUES1(cdr(popSTACK()));
695 }
696
697 LISPFUNNR(nthcdr,2)
698 { /* (NTHCDR integer list), CLTL p. 267 */
699 var uintL count = get_integer_truncate(STACK_1);
700 var object list = STACK_0;
701 while (count--) {
702 if (consp(list))
703 /* Walk list. */
704 list = Cdr(list);
705 else if (nullp(list))
706 /* End of list reached. */
707 break;
708 else
709 error_list(list);
710 }
711 VALUES1(list);
712 skipSTACK(2);
713 }
714
715 /* (SYS::CONSES-P n object) determines whether the object is a list
716 consisting of length n at least. Similar to
717 (if (= n 0) t (consp (nthcdr (- n 1) object)))
718 except that it is robust against dotted lists, or to
719 (if (= n 0) t (and (listp object) (>= (length object) n)))
720 except that it is robust against circular and dotted lists. */
721 LISPFUNNR(conses_p,2) {
722 var uintL count = get_integer_truncate(STACK_1);
723 var object list = STACK_0;
724 value1 = T;
725 if (count > 0) {
726 if (atomp(list))
727 value1 = NIL;
728 else
729 for (; --count > 0;) {
730 list = Cdr(list);
731 if (atomp(list)) {
732 value1 = NIL;
733 break;
734 }
735 }
736 }
737 mv_count=1;
738 skipSTACK(2);
739 }
740
741 /* Get a replacement for the circular list
742 can trigger GC */
replace_circular_list(object list)743 local maygc object replace_circular_list (object list) {
744 dynamic_bind(S(print_circle),T);
745 pushSTACK(NIL); /* no PLACE */
746 pushSTACK(list); pushSTACK(TheSubr(subr_self)->name);
747 check_value(error_condition,GETTEXT("~S: ~S is a circular list"));
748 dynamic_unbind(S(print_circle));
749 return value1;
750 }
751
752 LISPFUN(last,seclass_read,1,1,norest,nokey,0,NIL)
753 { /* (LAST list [n]), CLtL2 p. 416-417, dpANS p. 14-34
754 (defun last (list &optional (n 1))
755 (check-type n (integer 0 *))
756 (check-type list list)
757 (do ((l list (cdr l))
758 (r list)
759 (i 0 (+ i 1)))
760 ((atom l) r)
761 (when (>= i n) (pop r)))) */
762 var object intarg = popSTACK();
763 /* check optional integer argument: */
764 var uintL count = (boundp(intarg) ? get_integer_truncate(intarg) : 1);
765 var object list = check_list(popSTACK());
766 /* Optimisation of the two most common cases count=1 and count=0: */
767 switch (count) {
768 case 0: { last_0_restart:
769 var object slow = list;
770 while (consp(list)) {
771 list = Cdr(list);
772 if (atomp(list)) break;
773 if (eq(list,slow)) {
774 list = check_list(replace_circular_list(list));
775 goto last_0_restart;
776 }
777 list = Cdr(list);
778 slow = Cdr(slow);
779 }
780 } break;
781 case 1: { last_1_restart:
782 var object list2;
783 var object slow = list;
784 if (consp(list)) {
785 while (1) {
786 /* list is a Cons. */
787 list2 = Cdr(list); if (atomp(list2)) break; list = list2;
788 if (eq(list,slow)) {
789 list = check_list(replace_circular_list(list));
790 goto last_1_restart;
791 }
792 list2 = Cdr(list); if (atomp(list2)) break; list = list2;
793 slow = Cdr(slow);
794 }
795 }
796 }
797 break;
798 default: { last_default_restart:
799 var object list2 = list;
800 var object slow = list;
801 var uintL ii = count;
802 do {
803 if (atomp(list2))
804 goto done;
805 list2 = Cdr(list2);
806 } while (--ii);
807 while (consp(list2)) {
808 list2 = Cdr(list2); list = Cdr(list); if (atomp(list2)) break;
809 if (eq(list,slow)) {
810 list = check_list(replace_circular_list(list));
811 goto last_default_restart;
812 }
813 list2 = Cdr(list2); list = Cdr(list);
814 }
815 done: ;
816 }
817 break;
818 }
819 VALUES1(list);
820 }
821
822 /* UP: Constructs a list with given elements.
823 listof(len)
824 > uintC len: wanted list length
825 > on STACK: len Objects, first at the top
826 < result: list of these objects
827 removes len elements from the STACK
828 changes STACK, can trigger GC */
listof(uintC len)829 modexp maygc object listof (uintC len) {
830 pushSTACK(NIL); /* starting with empty list */
831 /* Cons len times the arguments to the front of this list: */
832 while (len--) {
833 var object new_cons = allocate_cons();
834 Cdr(new_cons) = popSTACK();
835 Car(new_cons) = STACK_0;
836 STACK_0 = new_cons;
837 }
838 return popSTACK();
839 }
840
841 LISPFUN(list,seclass_no_se,0,0,rest,nokey,0,NIL)
842 { /* (LIST {object}), CLTL p. 267 */
843 VALUES1(listof(argcount));
844 }
845
846 LISPFUN(liststar,seclass_no_se,1,0,rest,nokey,0,NIL)
847 { /* (LIST* obj1 {object}), CLTL p. 267 */
848 /* Former list already on the stack */
849 /* Cons the argcount arguments to the front of this list: */
850 while (argcount--) {
851 var object new_cons = allocate_cons();
852 Cdr(new_cons) = popSTACK(); /* next argument before */
853 Car(new_cons) = STACK_0;
854 STACK_0 = new_cons;
855 }
856 VALUES1(popSTACK());
857 }
858
859 LISPFUN(make_list,seclass_no_se,1,0,norest,key,1, (kw(initial_element)) )
860 { /* (MAKE-LIST size :initial-element), CLTL p. 268 */
861 if (!boundp(STACK_0)) /* check :initial-element */
862 STACK_0 = NIL; /* default :initial-element is NIL */
863 VALUES1(make_list(I_to_UL(check_uint32(STACK_1))));
864 skipSTACK(2);
865 }
866
867 LISPFUN(append,seclass_read,0,0,rest,nokey,0,NIL)
868 { /* (APPEND {list}), CLTL p. 268 */
869 if (argcount==0) {
870 VALUES1(NIL); /* no arguments -> return NIL as result */
871 } else {
872 /* Append arguments. Run the loop argcount-1 times: */
873 while (--argcount) {
874 /* STACK_0 = result list from right. */
875 /* STACK_1 := (append STACK_1 STACK_0), increase STACK by 1: */
876 var object list1;
877 {
878 var object list2 = popSTACK(); /* result list (from right) */
879 list1 = STACK_0; /* Argument to be added to the front */
880 STACK_0 = list2; /* stack resulting list */
881 }
882 /* list1 needs to be a list: */
883 if (atomp(list1))
884 if (nullp(list1))
885 ; /* if list1=NIL: (append nil x) = x, do nothing */
886 else
887 error_list(list1);
888 else {
889 /* (append list1 STACK_0), and list1 is a Cons: */
890 /* Copy list1 and keep last Cons: */
891 var object run;
892 pushSTACK(list1);
893 {
894 var object new_list = allocate_cons();
895 run = STACK_0; /* run runs through the old list list1 */
896 Car(new_list) = Car(run);
897 STACK_0 = new_list;
898 pushSTACK(new_list);
899 }
900 /* Loop: STACK_1 has the full copy, STACK_0 = LAST of it, */
901 /* run = the corresponding Cons of the original list list1. */
902 while ( run=Cdr(run), !endp(run) ) {
903 /* one more Cons */
904 pushSTACK(run); /* save run */
905 var object new_cons = allocate_cons(); /* allocate new Cons */
906 run = popSTACK(); /* put back run */
907 Cdr(STACK_0) = new_cons; /* and add as CDR of the LAST */
908 Car(new_cons) = Car(run); /* copy CAR */
909 STACK_0 = new_cons; /* this is now the new LAST */
910 }
911 /* Copy ready. STACK_2 = current result list, */
912 /* STACK_1 = copy of list1, STACK_0 = LAST of it. */
913 run = popSTACK(); /* end of copy */
914 list1 = popSTACK(); /* copy finished */
915 /*if (!nullp(Cdr(run))) ????
916 error_proper_list_dotted(TheSubr(subr_self)->name,Cdr(run));*/
917 Cdr(run) = STACK_0; /* add result copy */
918 STACK_0 = list1; /* and the is the new result list */
919 }
920 }
921 VALUES1(popSTACK()); /* result list as value */
922 }
923 }
924
925 LISPFUNNR(copy_list,1)
926 { /* (COPY-LIST list), CLTL p. 268 */
927 VALUES1(copy_list(check_list(popSTACK())));
928 }
929
930 /* UP: Copies an A-list
931 copy_alist(alist)
932 > alist: A-list
933 < result: Copy of the A-list
934 can trigger GC */
copy_alist(object alist)935 local maygc object copy_alist (object alist) {
936 /* Algorithm:
937 Instead of
938 (mapcar #'(lambda (x) (if (consp x) (cons (car x) (cdr x)) x)) l)
939 the list is first copied via copy-list, then the conses among the top
940 level elements of the copy are replaced with conses with same CAR and CDR. */
941 alist = copy_list(alist);
942 pushSTACK(alist); /* save result list */
943 /* a-list runs through to the result list */
944 while (!endp(alist)) {
945 if (mconsp(Car(alist))) {
946 pushSTACK(alist); /* save a-list */
947 var object new_cons = allocate_cons(); /* new Cons */
948 alist = popSTACK(); /* a-list back */
949 {
950 var object old_cons = Car(alist);
951 Car(new_cons) = Car(old_cons); Cdr(new_cons) = Cdr(old_cons);
952 }
953 Car(alist) = new_cons;
954 }
955 alist = Cdr(alist);
956 }
957 return popSTACK();
958 }
959
960 LISPFUNNR(copy_alist,1) /* (COPY-ALIST alist), CLTL p. 268 */
961 { VALUES1(copy_alist(popSTACK())); }
962
963 /* UP: Copies a tree. */
copy_tree(object tree)964 local object copy_tree (object tree) {
965 if (atomp(tree))
966 return tree; /* Return atom unchanged */
967 else {
968 check_STACK(); check_SP();
969 pushSTACK(Cdr(tree)); /* Save CDR */
970 {
971 var object temp = copy_tree(Car(tree)); /* Copy the CAR recursively */
972 tree = STACK_0;
973 STACK_0 = temp; /* Save CAR copy */
974 temp = copy_tree(tree); /* Copy the CDR recursively */
975 pushSTACK(temp); /* Save CDR copy */
976 }
977 return cons_from_stack();
978 }
979 }
980
981 LISPFUNNR(copy_tree,1) /* (COPY-TREE tree), CLTL p. 269 */
982 { VALUES1(copy_tree(popSTACK())); }
983
984 LISPFUNNR(revappend,2)
985 { /* (REVAPPEND list object), CLTL p. 269 */
986 while (!endp(STACK_1)) {
987 var object new_cons = allocate_cons(); /* new Cons */
988 Car(new_cons) = Car(STACK_1); Cdr(new_cons) = STACK_0; /* (cons (car list) object) */
989 STACK_0 = new_cons; /* This is the new, longer object */
990 STACK_1 = Cdr(STACK_1); /* Shorten list */
991 }
992 VALUES1(popSTACK());
993 skipSTACK(1);
994 }
995
996 LISPFUN(nconc,seclass_default,0,0,rest,nokey,0,NIL)
997 { /* (NCONC {list}), CLTL p. 269 */
998 if (argcount==0) {
999 VALUES1(NIL); /* no arguments -> return NIL as result */
1000 } else {
1001 /* Append arguments. Run the loop for argcount-1 times: */
1002 while (--argcount) {
1003 /* STACK_0 = current result list from right. */
1004 /* STACK_1 := (nconc STACK_1 STACK_0), increase STACK by 1: */
1005 if (matomp(STACK_1))
1006 if (nullp(STACK_1)) {
1007 STACK_1 = STACK_0; skipSTACK(1); /* result list stays, skip argument */
1008 } else
1009 error_list(STACK_1);
1010 else {
1011 /* Add result list to (cdr (last STACK_1)): */
1012 var object list1 = STACK_1;
1013 var object list2;
1014 while (1) {
1015 /* Here list1 is a Cons. */
1016 list2 = Cdr(list1);
1017 if (atomp(list2))
1018 break;
1019 list1 = list2;
1020 }
1021 /* list1 is the last Cons of the argument STACK_1 */
1022 Cdr(list1) = popSTACK(); /* Add current result list */
1023 /* STACK_0 = new result list */
1024 }
1025 }
1026 VALUES1(popSTACK());
1027 }
1028 }
1029
1030 LISPFUNN(nreconc,2) /* (NRECONC list1 list2), CLTL p. 269 */
1031 {
1032 var object list1 = check_list(STACK_1);
1033 var object list2 = STACK_0; skipSTACK(2);
1034 VALUES1(nreconc(list1,list2));
1035 }
1036
1037 LISPFUNN(list_nreverse,1) /* (SYS::LIST-NREVERSE list) */
1038 { /* as (NREVERSE list), if list is a list. */
1039 VALUES1(nreverse(popSTACK()));
1040 }
1041
1042 /* check that the argument is a non-circular list and return its length
1043 can trigger GC */
check_list_length(gcv_object_t * list_)1044 local inline maygc uintL check_list_length (gcv_object_t *list_) {
1045 while(1) {
1046 /* Give an error if the argument is not a list. (It's stupid to allow
1047 dotted lists of length > 0 but to forbid dotted lists of length 0,
1048 but that's how ANSI CL specifies it.) */
1049 if (!listp(*list_)) *list_ = check_list_replacement(*list_);
1050 var object dotted_p;
1051 var object llen = list_length(*list_,&dotted_p);
1052 if (!nullp(llen)) return I_to_UL(llen);
1053 *list_ = replace_circular_list(*list_);
1054 }
1055 }
1056
1057 LISPFUN(butlast,seclass_read,1,1,norest,nokey,0,NIL)
1058 { /* (BUTLAST list [integer]), CLTL p. 271 */
1059 var object intarg = popSTACK();
1060 /* check optional integer argument: */
1061 var uintL count = (boundp(intarg) ? get_integer_truncate(intarg) : 1);
1062 var uintL len = check_list_length(&STACK_0); /* list length */
1063 if (len<=count) {
1064 VALUES1(NIL); skipSTACK(1); /* length(list)<=count -> return NIL */
1065 } else {
1066 var uintL new_len = len - count; /* >0 */
1067 /* Creates a copy of the first new_len conses of the list STACK_0: */
1068 var object new_list = make_list(new_len); /* allocate new list */
1069 /* Copy list elements one by one, until new_list is full: */
1070 var object new_run = new_list; /* runs through the new list */
1071 var object old_run = popSTACK(); /* runs through the old list */
1072 do {
1073 Car(new_run) = Car(old_run);
1074 old_run = Cdr(old_run); new_run = Cdr(new_run);
1075 } while (!atomp(new_run));
1076 VALUES1(new_list);
1077 }
1078 }
1079
1080 LISPFUN(nbutlast,seclass_default,1,1,norest,nokey,0,NIL)
1081 { /* (NBUTLAST list [integer]), CLTL p. 271 */
1082 var object intarg = popSTACK();
1083 /* check optional integer argument: */
1084 var uintL count = (boundp(intarg) ? get_integer_truncate(intarg) : 1);
1085 var uintL len = check_list_length(&STACK_0); /* list length */
1086 if (len<=count) {
1087 VALUES1(NIL); skipSTACK(1); /* length(list)<=count -> return NIL */
1088 } else {
1089 var uintL new_len = len - count; /* >0 */
1090 var object run = STACK_0; /* runs through the list */
1091 /* take new_len-1 times the CDR and then set the CDR to NIL: */
1092 while (--new_len) run = Cdr(run);
1093 Cdr(run) = NIL;
1094 VALUES1(popSTACK()); /* return list */
1095 }
1096 }
1097
1098 LISPFUNNR(ldiff,2)
1099 { /* (LDIFF list sublist), CLTL p. 272 */
1100 var object sublist = popSTACK();
1101 /* Search where sublist begins in list: */
1102 var uintL new_len = 0;
1103 var bool found_p = false;
1104 {
1105 var object listr = STACK_0;
1106 #ifndef X3J13_175
1107 while (!((found_p = eql(listr,sublist)) || endp(listr))) {
1108 listr = Cdr(listr); new_len++;
1109 }
1110 #else
1111 if (!listp(listr))
1112 error_list(listr);
1113 while (!((found_p = eql(listr,sublist)) || atomp(listr))) {
1114 listr = Cdr(listr); new_len++;
1115 }
1116 #endif
1117 }
1118 /* Return a copy of the first new_len conses of the list STACK_0: */
1119 var object new_list = make_list(new_len); /* allocate new list */
1120 /* Copy list elements one by one, until new_list is full: */
1121 var object new_run = new_list; /* runs through the new list */
1122 var object old_run = popSTACK(); /* runs through the old list */
1123 if (consp(new_run)) while (1) { /* loop! */
1124 Car(new_run) = Car(old_run);
1125 if (atomp(Cdr(new_run))) {
1126 if (!found_p)
1127 Cdr(new_run) = Cdr(old_run);
1128 break;
1129 }
1130 old_run = Cdr(old_run); new_run = Cdr(new_run);
1131 }
1132 VALUES1(new_list);
1133 }
1134
1135 /* check_cons(obj)
1136 > obj: an object
1137 < result: a cons, either the same as obj or a replacement
1138 can trigger GC */
check_cons_replacement(object obj)1139 local maygc object check_cons_replacement (object obj) {
1140 do {
1141 pushSTACK(NIL); /* no PLACE */
1142 pushSTACK(obj); /* TYPE-ERROR slot DATUM */
1143 pushSTACK(S(cons)); /* TYPE-ERROR slot EXPECTED-TYPE */
1144 pushSTACK(obj); pushSTACK(TheSubr(subr_self)->name);
1145 check_value(type_error,GETTEXT("~S: ~S is not a pair"));
1146 obj = value1;
1147 } while (!consp(obj));
1148 return obj;
1149 }
check_cons(object obj)1150 local inline maygc object check_cons (object obj) {
1151 if (!consp(obj))
1152 obj = check_cons_replacement(obj);
1153 return obj;
1154 }
1155
1156 LISPFUNN(rplaca,2) /* (RPLACA cons object), CLTL p. 272 */
1157 {
1158 var object arg1 = check_cons(STACK_1);
1159 var object arg2 = STACK_0;
1160 skipSTACK(2);
1161 Car(arg1) = arg2;
1162 VALUES1(arg1);
1163 }
1164
1165 LISPFUNN(prplaca,2) /* (SYS::%RPLACA cons object) */
1166 { /* like (RPLACA cons object), but return object as value */
1167 var object arg1 = check_cons(STACK_1);
1168 var object arg2 = STACK_0;
1169 skipSTACK(2);
1170 Car(arg1) = arg2;
1171 VALUES1(arg2);
1172 }
1173
1174 LISPFUNN(rplacd,2) /* (RPLACD cons object), CLTL p. 272 */
1175 {
1176 var object arg1 = check_cons(STACK_1);
1177 var object arg2 = STACK_0;
1178 skipSTACK(2);
1179 Cdr(arg1) = arg2;
1180 VALUES1(arg1);
1181 }
1182
1183 LISPFUNN(prplacd,2) /* (SYS::%RPLACD cons object) */
1184 { /* like (RPLACD cons object), but return object as value */
1185 var object arg1 = check_cons(STACK_1);
1186 var object arg2 = STACK_0;
1187 skipSTACK(2);
1188 Cdr(arg1) = arg2;
1189 VALUES1(arg2);
1190 }
1191
1192 /* (funcall TESTFUN ...) */
1193 #define CALL_TEST(p) (*pcall_test)(p,*(p STACKop 3),value1)
1194
1195 /* UP: Replaces in the tree all elements x, which KEY passes the TESTFUNction,
1196 by NEW. Construktively (copying).
1197 subst(tree,stackptr,up_fun)
1198 > tree: the Tree
1199 > stackptr: *(stackptr-2) = NEW, *(stackptr-1) = KEY
1200 > up_fun: TESTFUN = Adress of the test function,
1201 called with same stackptr and with (KEY x) as argument.
1202 Returns true or false.
1203 < result: (evtl. newer) tree
1204 can trigger GC */
subst(object tree,gcv_object_t * stackptr,funarg_t * pcall_test)1205 local maygc object subst (object tree, gcv_object_t* stackptr,
1206 funarg_t* pcall_test) {
1207 /* First calculate (KEY tree) and call TESTFUN: */
1208 pushSTACK(tree); /* save tree */
1209 funcall_key(*(stackptr STACKop -1),tree); /* (KEY tree) */
1210 if (CALL_TEST(stackptr)) { /* (funcall TESTFUN ...) */
1211 /* Test ok */
1212 skipSTACK(1); return *(stackptr STACKop -2); /* return NEW as value */
1213 } else /* Test not ok */
1214 if (matomp(STACK_0)) {
1215 /* Argument is an atom -> keep it unchanged */
1216 return popSTACK();
1217 } else {
1218 /* Argument is a Cons -> call SUBST recursively: */
1219 check_STACK(); check_SP();
1220 /* call recursively for the CDR: */
1221 var object new_cdr = subst(Cdr(STACK_0),stackptr,pcall_test);
1222 pushSTACK(new_cdr); /* Save CDR result */
1223 /* call recursively for the CAR: */
1224 var object new_car = subst(Car(STACK_1),stackptr,pcall_test);
1225 if (eq(new_car,Car(STACK_1)) && eq(STACK_0,Cdr(STACK_1))) {
1226 /* both unchanged */
1227 skipSTACK(1); /* skip CDR result */
1228 return popSTACK();
1229 } else {
1230 STACK_1 = new_car; /* save CAR result */
1231 return cons_from_stack();
1232 }
1233 }
1234 }
1235
1236 LISPFUN(subst,seclass_default,3,0,norest,key,3,
1237 (kw(test),kw(test_not),kw(key)) )
1238 { /* (SUBST new old tree :test :test-not :key), CLTL p. 273 */
1239 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1240 var funarg_t* pcall_test = check_test_args(&STACK_1); /* :TEST/:TEST-NOT arguments on STACK_2,STACK_1 */
1241 pushSTACK(STACK_5); /* newobj */
1242 /* stack layout: new, old, tree, test, test_not, key, new. */
1243 VALUES1(subst(STACK_4,&STACK_2,pcall_test)); /* do the substitution */
1244 skipSTACK(7);
1245 }
1246
1247 LISPFUN(subst_if,seclass_default,3,0,norest,key,1, (kw(key)) )
1248 { /* (SUBST-IF new pred tree :key), CLTL p. 273 */
1249 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1250 pushSTACK(STACK_3); /* newobj */
1251 /* stack layout: new, pred, tree, key, new. */
1252 VALUES1(subst(STACK_2,&STACK_2,&call_if)); /* do the substitution */
1253 skipSTACK(5);
1254 }
1255
1256 LISPFUN(subst_if_not,seclass_default,3,0,norest,key,1, (kw(key)) )
1257 { /* (SUBST-IF-NOT new pred tree :key), CLTL p. 273 */
1258 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1259 pushSTACK(STACK_3); /* newobj */
1260 /* stack layout: new, pred, tree, key, new. */
1261 VALUES1(subst(STACK_2,&STACK_2,&call_if_not)); /* do the substitution */
1262 skipSTACK(5);
1263 }
1264
1265 /* UP: Replaces in the tree all elements x, which KEY passes the TESTFUNction,
1266 by NEW. Destructively (in-place).
1267 nsubst(tree,stackptr,up_fun)
1268 > tree: the Tree
1269 > stackptr: *(stackptr-2) = NEW, *(stackptr-1) = KEY
1270 > up_fun: TESTFUN = Adress of the test function,
1271 called with same stackptr and with (KEY x) as argument.
1272 Returns true or false.
1273 < result: same tree CAR
1274 can trigger GC */
nsubst(object tree,gcv_object_t * stackptr,funarg_t * pcall_test)1275 local maygc object nsubst (object tree, gcv_object_t* stackptr,
1276 funarg_t* pcall_test) {
1277 /* First calculate (KEY tree) and call TESTFUN: */
1278 pushSTACK(tree); /* save tree */
1279 funcall_key(*(stackptr STACKop -1),tree); /* (KEY tree) */
1280 if (CALL_TEST(stackptr)) { /* (funcall TESTFUN ...) */
1281 /* Test ok */
1282 skipSTACK(1); return *(stackptr STACKop -2); /* NEW as value */
1283 } else { /* Test not ok */
1284 if (mconsp(STACK_0)) {
1285 /* Argument is a Cons -> call NSUBST recursively: */
1286 check_STACK(); check_SP();
1287 { /* call recursively for the CDR: */
1288 var object modified_cdr = nsubst(Cdr(STACK_0),stackptr,pcall_test);
1289 Cdr(STACK_0) = modified_cdr;
1290 }
1291 { /* call recursively for the CAR: */
1292 var object modified_car = nsubst(Car(STACK_0),stackptr,pcall_test);
1293 Car(STACK_0) = modified_car;
1294 }
1295 }
1296 return popSTACK(); /* return original tree address */
1297 }
1298 }
1299
1300 LISPFUN(nsubst,seclass_default,3,0,norest,key,3,
1301 (kw(test),kw(test_not),kw(key)) )
1302 { /* (NSUBST new old tree :test :test-not :key), CLTL p. 274 */
1303 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1304 var funarg_t* pcall_test = check_test_args(&STACK_1); /* :TEST/:TEST-NOT arguments on STACK_2,STACK_1 */
1305 pushSTACK(STACK_5); /* newobj */
1306 /* stack layout: new, old, tree, test, test_not, key, new. */
1307 VALUES1(nsubst(STACK_4,&STACK_2,pcall_test)); /* do the substitution */
1308 skipSTACK(7);
1309 }
1310
1311 LISPFUN(nsubst_if,seclass_default,3,0,norest,key,1, (kw(key)) )
1312 { /* (NSUBST-IF new pred tree :key), CLTL p. 274 */
1313 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1314 pushSTACK(STACK_3); /* newobj */
1315 /* stack layout: new, pred, tree, key, new. */
1316 VALUES1(nsubst(STACK_2,&STACK_2,&call_if)); /* do the substitution */
1317 skipSTACK(5);
1318 }
1319
1320 LISPFUN(nsubst_if_not,seclass_default,3,0,norest,key,1, (kw(key)) )
1321 { /* (NSUBST-IF-NOT new pred tree :key), CLTL p. 274 */
1322 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1323 pushSTACK(STACK_3); /* newobj */
1324 /* stack layout: new, pred, tree, key, new. */
1325 VALUES1(nsubst(STACK_2,&STACK_2,&call_if_not)); /* do the substitution */
1326 skipSTACK(5);
1327 }
1328
1329 /* UP: return the first list element, whose CAR passed the TESTFUNction.
1330 sublis_assoc(stackptr)
1331 > *(stackptr+3) = alist
1332 > stackptr: *(stackptr-1) = KEY
1333 > pcall_test = TESTFUN = test function, called on each list element
1334 (u . v) with the same stackptr and with (KEY x) and u as arguments.
1335 returns true, when the test passes, false otherwise.
1336 < return: list element (a CONS) or NIL
1337 can trigger GC */
sublis_assoc(gcv_object_t * stackptr,funarg_t * pcall_test)1338 local maygc object sublis_assoc (gcv_object_t* stackptr, funarg_t* pcall_test)
1339 {
1340 var object alist = *(stackptr STACKop 3);
1341 pushSTACK(alist); /* save the list ((u . v) ...) */
1342 while (!endp(STACK_0)) {
1343 /* How to treat atoms in the list?
1344 a. One can ignore them.
1345 b. One can signal an error on them.
1346 c. One can signal an error only for non-NIL atoms.
1347 Obviously (b) is best, because it provides the best possible
1348 error checking. But CLtL2 and CLHS both contain a "note" that
1349 suggests to some people that atoms are ignored, therefore I
1350 assume that there is code outside which assumes this behaviour,
1351 and we must not signal an error on it.
1352 Note: To other people this note suggests that only NILs are
1353 ignored, and they suggest (c). This is inconsistent with the
1354 definition of "association list" in the CLHS glossary and with
1355 the general use of alists as lookup tables.
1356 Therefore we implement (a).
1357 SDS 2003-03-08: I am changing the behavior to (c) because
1358 it is more in line with the ASSOC behavior */
1359 var object head = Car(STACK_0);
1360 if (mconsp(head)) { /* skip atoms in the list */
1361 /* test whether the 2-argument test function pcall_test, called on u and
1362 the value in *(stackptr-2), returns true: */
1363 var bool erg = /* 2-argument test function, called on (KEY x) and u */
1364 pcall_test(stackptr, *(stackptr STACKop -2), Car(head));
1365 if (erg) /* test passed ==> return x = (u . v) = (CAR alist) */
1366 return Car(popSTACK());
1367 /* test failed */
1368 } else if (!nullp(head))
1369 error_list(head);
1370 STACK_0 = Cdr(STACK_0); /* tail recursion */
1371 }
1372 skipSTACK(1); /* forget alist */
1373 /* reached list end ==> return NIL */
1374 return NIL;
1375 }
1376
1377 /* UP: Replaces in tree all x by its A-LIST representation (by ASSOC):
1378 x is replaced by the first v, so that (u . v) is a member in ALIST and
1379 (KEY x) and u pass the TESTFUNction. Constructively (copying).
1380 sublis(tree,stackptr)
1381 > tree: the Tree
1382 > stackptr: *(stackptr-1) = KEY, *(stackptr+3) = ALIST,
1383 *(stackptr-2) is free for (KEY x)
1384 < result: (evtl. newer) Tree
1385 can trigger GC */
sublis(object tree,gcv_object_t * stackptr,funarg_t * pcall_test)1386 local maygc object sublis (object tree, gcv_object_t* stackptr, funarg_t* pcall_test) {
1387 /* First calculate (KEY tree) and call ASSOC: */
1388 pushSTACK(tree); /* save tree */
1389 funcall_key(*(stackptr STACKop -1),tree); /* (KEY tree) */
1390 *(stackptr STACKop -2) = value1; /* save for sublis_assoc */
1391 var object assoc_erg = sublis_assoc(stackptr,pcall_test);
1392 if (consp(assoc_erg)) { /* Test ok */
1393 skipSTACK(1); return Cdr(assoc_erg); /* (CDR (ASSOC ...)) as value */
1394 } else /* Test not ok */
1395 if (matomp(STACK_0)) {
1396 /* Argument is an atom -> keep unchanged */
1397 return popSTACK();
1398 } else {
1399 /* Argument is a Cons -> call SUBLIS recursively: */
1400 check_STACK(); check_SP();
1401 /* call recursively for the CDR: */
1402 var object new_cdr = sublis(Cdr(STACK_0),stackptr,pcall_test);
1403 pushSTACK(new_cdr); /* save CDR result */
1404 /* call recursively for the CAR: */
1405 var object new_car = sublis(Car(STACK_1),stackptr,pcall_test);
1406 if (eq(new_car,Car(STACK_1)) && eq(STACK_0,Cdr(STACK_1))) {
1407 /* both unchanged */
1408 skipSTACK(1); /* skip CDR result */
1409 return popSTACK();
1410 } else {
1411 STACK_1 = new_car; /* save CAR result */
1412 return cons_from_stack();
1413 }
1414 }
1415 }
1416
1417 LISPFUN(sublis,seclass_default,2,0,norest,key,3,
1418 (kw(test),kw(test_not),kw(key)) )
1419 { /* (SUBLIS alist tree :test :test-not :key), CLTL p. 274 */
1420 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1421 var gcv_object_t* stackptr = &STACK_1;
1422 var funarg_t* pcall_test = check_test_args(stackptr); /* Call with :TEST/:TEST-NOT arguments */
1423 /* on STACK_2,STACK_1 arguments. Returns true or false. */
1424 if (nullp(STACK_4)) { /* shortcut: nothing to do if alist = () */
1425 VALUES1(STACK_3);
1426 skipSTACK(5);
1427 } else {
1428 pushSTACK(NIL); /* Dummy */
1429 pushSTACK(NIL); /* Dummy */
1430 /* stack layout: alist, tree, test, test_not, key, dummy, dummy. */
1431 VALUES1(sublis(STACK_5,stackptr,pcall_test)); /* do the substitution */
1432 skipSTACK(7);
1433 }
1434 }
1435
1436 /* UP: Replaces in tree all x by its A-LIST representation (by ASSOC):
1437 x is replaced by the first v, so that (u . v) is a member in ALIST and
1438 (KEY x) and u pass the TESTFUNction. Destructively (in-place).
1439 nsublis(tree,stackptr)
1440 > tree: the Tree
1441 > stackptr: *(stackptr-1) = KEY, *(stackptr+3) = ALIST,
1442 *(stackptr-2) is free for (KEY x)
1443 < result: same Tree CAR
1444 can trigger GC */
nsublis(object tree,gcv_object_t * stackptr,funarg_t * pcall_test)1445 local maygc object nsublis (object tree, gcv_object_t* stackptr, funarg_t* pcall_test) {
1446 /* First calculate (KEY tree) and call ASSOC: */
1447 pushSTACK(tree); /* save tree */
1448 funcall_key(*(stackptr STACKop -1),tree); /* (KEY tree) */
1449 *(stackptr STACKop -2) = value1; /* save for sublis_assoc */
1450 var object assoc_erg = sublis_assoc(stackptr,pcall_test);
1451 if (consp(assoc_erg)) { /* Test ok */
1452 skipSTACK(1); return Cdr(assoc_erg); /* (CDR (ASSOC ...)) as value */
1453 } else { /* Test not ok */
1454 if (mconsp(STACK_0)) {
1455 /* Argument is a Cons -> call NSUBLIS recursively: */
1456 check_STACK(); check_SP();
1457 { /* call recursively for the CDR: */
1458 var object modified_cdr = nsublis(Cdr(STACK_0),stackptr,pcall_test);
1459 Cdr(STACK_0) = modified_cdr;
1460 }
1461 { /* call recursively for the CAR: */
1462 var object modified_car = nsublis(Car(STACK_0),stackptr,pcall_test);
1463 Car(STACK_0) = modified_car;
1464 }
1465 }
1466 return popSTACK(); /* return original tree address */
1467 }
1468 }
1469
1470 LISPFUN(nsublis,seclass_default,2,0,norest,key,3,
1471 (kw(test),kw(test_not),kw(key)) )
1472 { /* (NSUBLIS alist tree :test :test-not :key), CLTL p. 275 */
1473 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1474 var gcv_object_t* stackptr = &STACK_1;
1475 var funarg_t* pcall_test = check_test_args(stackptr); /* Call with :TEST/:TEST-NOT arguments */
1476 /* on STACK_2,STACK_1 arguments. Returns true or false. */
1477 if (nullp(STACK_4)) { /* shortcut: nothing to do if alist = () */
1478 VALUES1(STACK_3);
1479 skipSTACK(5);
1480 } else {
1481 pushSTACK(NIL); /* Dummy */
1482 pushSTACK(NIL); /* Dummy */
1483 /* Stackaufbau: alist, tree, test, test_not, key, dummy, dummy. */
1484 VALUES1(nsublis(STACK_5,stackptr,pcall_test)); /* do the substitution */
1485 skipSTACK(7);
1486 }
1487 }
1488
1489 /* UP: find OBJ in LIS: (MEMBER OBJ LIS :TEST #'EQ) */
memq(const object obj,const object lis)1490 modexp object memq (const object obj, const object lis) {
1491 var object l = lis;
1492 while (consp(l)) {
1493 if (eq(Car(l),obj)) return l;
1494 l = Cdr(l);
1495 }
1496 if (!nullp(l))
1497 error_proper_list_dotted(TheSubr(subr_self)->name,l);
1498 return NIL;
1499 }
1500
1501 /* (SYS::MEMQ OBJECT LIST) == (MEMBER OBJECT LIST :TEST #'EQ) */
1502 LISPFUNNR(memq,2) {
1503 var object lis = popSTACK();
1504 var object obj = popSTACK();
1505 VALUES1(memq(obj,lis));
1506 }
1507
1508 /* UP: Returns the rest of the list starting with the list element,
1509 which satisfies the TESTFUNction.
1510 member(list,stackptr,up_fun)
1511 > list: List
1512 > stackptr: *(stackptr-1) = KEY
1513 > up_fun: TESTFUN = Address of the test function,
1514 Called with same stackptr and with (KEY x) as argument.
1515 Returns true or false.
1516 < result: rest of list
1517 can trigger GC */
member(object list,gcv_object_t * stackptr,funarg_t * pcall_test)1518 local maygc object member (object list, gcv_object_t* stackptr,
1519 funarg_t* pcall_test) {
1520 while (!endp(list)) {
1521 pushSTACK(list); /* save rest of list */
1522 funcall_key(*(stackptr STACKop -1),Car(list)); /* (KEY x) */
1523 {
1524 var bool erg = CALL_TEST(stackptr); /* (funcall TESTFUN ...) */
1525 list = popSTACK();
1526 if (erg)
1527 return list; /* Test ok -> list as result */
1528 }
1529 /* Test not ok -> call (member ... (cdr list)): */
1530 list = Cdr(list); /* tail-end-recursively */
1531 }
1532 return list; /* NIL as result */
1533 }
1534
1535 LISPFUN(member,seclass_default,2,0,norest,key,3,
1536 (kw(test),kw(test_not),kw(key)) )
1537 { /* (MEMBER item list :test :test-not :key), CLTL p. 275 */
1538 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1539 var funarg_t* pcall_test = check_test_args(&STACK_1); /* :TEST/:TEST-NOT arguments on STACK_2,STACK_1 */
1540 VALUES1(member(STACK_3,&STACK_1,pcall_test)); /* do the search */
1541 skipSTACK(5);
1542 }
1543
1544 LISPFUN(member_if,seclass_default,2,0,norest,key,1, (kw(key)) )
1545 { /* (MEMBER-IF pred list :key), CLTL p. 275 */
1546 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1547 VALUES1(member(STACK_1,&STACK_1,&call_if)); /* do the search */
1548 skipSTACK(3);
1549 }
1550
1551 LISPFUN(member_if_not,seclass_default,2,0,norest,key,1, (kw(key)) )
1552 { /* (MEMBER-IF-NOT pred list :key), CLTL p. 275 */
1553 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1554 VALUES1(member(STACK_1,&STACK_1,&call_if_not)); /* do the search */
1555 skipSTACK(3);
1556 }
1557
1558 LISPFUNNR(tailp,2) /* (TAILP sublist list), CLTL p. 275 */
1559 #ifndef X3J13_175
1560 /* (defun tailp (sublist list)
1561 (do ((l list (rest l)))
1562 ((endp l) (null sublist))
1563 (when (eq l sublist) (return t)))) */
1564 #else
1565 /* (defun tailp (sublist list)
1566 (loop
1567 (when (eql sublist list) (return t))
1568 (when (atom list) (return nil))
1569 (setq list (cdr list)))) */
1570 #endif
1571 {
1572 var object list = popSTACK();
1573 var object sublist = popSTACK();
1574 #ifndef X3J13_175
1575 while (!endp(list)) {
1576 if (eq(list,sublist))
1577 goto yes;
1578 list = Cdr(list);
1579 }
1580 if (nullp(sublist))
1581 goto yes;
1582 #else
1583 while (1) {
1584 if (eql(list,sublist))
1585 goto yes;
1586 if (atomp(list))
1587 break;
1588 list = Cdr(list);
1589 }
1590 #endif
1591 VALUES1(NIL); return; /* NIL as value */
1592 yes:
1593 VALUES1(T); return; /* T as value */
1594 }
1595
1596 LISPFUN(adjoin,seclass_default,2,0,norest,key,3,
1597 (kw(test),kw(test_not),kw(key)) )
1598 { /* (ADJOIN item list :test :test-not :key), CLTL p. 276 */
1599 /* first test on (MEMBER (key item) list :test :test-not :key): */
1600 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1601 var funarg_t* pcall_test = check_test_args(&STACK_1); /* :TEST/:TEST-NOT arguments on STACK_2,STACK_1 */
1602 {
1603 var object item = STACK_4;
1604 pushSTACK(item); /* save item */
1605 funcall_key(STACK_1,item); STACK_5 = value1; /* item := (funcall key item) */
1606 }
1607 /* stack layout: (key item), list, test, test-not, key, item */
1608 if (nullp(member(STACK_4,&STACK_2,pcall_test))) { /* do search */
1609 /* item not yet found in list: must cons */
1610 var object new_cons = allocate_cons();
1611 Cdr(new_cons) = STACK_4; /* = list */
1612 Car(new_cons) = STACK_0; /* = item */
1613 VALUES1(new_cons);
1614 } else {
1615 VALUES1(STACK_4); /* list as value */
1616 }
1617 skipSTACK(6); return;
1618 }
1619
1620 LISPFUN(acons,seclass_no_se,3,0,norest,nokey,0,NIL)
1621 { /* (ACONS key val alist) = (CONS (CONS key val) alist), CLTL p. 279 */
1622 {
1623 var object new_cons = allocate_cons();
1624 Car(new_cons) = STACK_2; /* key */
1625 Cdr(new_cons) = STACK_1; /* value */
1626 STACK_1 = new_cons;
1627 }
1628 VALUES1(cons_from_stack());
1629 skipSTACK(1);
1630 }
1631
1632 LISPFUN(pairlis,seclass_read,2,1,norest,nokey,0,NIL)
1633 { /* (PAIRLIS keys data [alist]), CLTL p. 280 */
1634 if (!boundp(STACK_0))
1635 STACK_0=NIL; /* ALIST defaults to NIL */
1636 pushSTACK(STACK_2); /* keys */
1637 pushSTACK(STACK_(1+1)); /* data */
1638 while (1) { /* stack layout: keys, data, alist, keysr, datar. */
1639 if (endp(STACK_0)) /* data is over? */
1640 if (endp(STACK_1)) /* keys are over? */
1641 goto end;
1642 else
1643 goto error_lengths;
1644 else
1645 if (endp(STACK_1)) /* keys are over? */
1646 goto error_lengths;
1647 else {
1648 var object new_cons = allocate_cons();
1649 Car(new_cons) = Car(STACK_1); /* next key as CAR */
1650 Cdr(new_cons) = Car(STACK_0); /* next data as CDR */
1651 STACK_1 = Cdr(STACK_1); /* shorten keys */
1652 STACK_0 = Cdr(STACK_0); /* shorten data */
1653 pushSTACK(new_cons);
1654 new_cons = allocate_cons(); /* one more new Cons */
1655 Car(new_cons) = popSTACK(); /* with (key . data) as CAR */
1656 Cdr(new_cons) = STACK_2; /* and a-list as CDR */
1657 STACK_2 = new_cons; /* results in new a-list */
1658 }
1659 }
1660 error_lengths:
1661 skipSTACK(3);
1662 {
1663 var object data_list = popSTACK();
1664 var object keys_list = popSTACK();
1665 pushSTACK(data_list); pushSTACK(keys_list);
1666 pushSTACK(TheSubr(subr_self)->name);
1667 error(error_condition,GETTEXT("~S: lists ~S and ~S are not of same length"));
1668 }
1669 end:
1670 VALUES1(STACK_2); skipSTACK(5); /* a-list as value */
1671 }
1672
1673 /* UP: Returns the first list element, which CAR satisfies the TESTFUNction.
1674 assoc(alist,stackptr)
1675 > alist: A-list
1676 > stackptr: *(stackptr-1) = KEY
1677 > up_fun: TESTFUN = Address of the test function. Called for list elements
1678 (u . v) with same stackptr and with (KEY u) as argument.
1679 Returns true or false.
1680 < result: List element (a Cons) or NIL
1681 can trigger GC */
assoc(object alist,gcv_object_t * stackptr,funarg_t * pcall_test)1682 local maygc object assoc (object alist, gcv_object_t* stackptr,
1683 funarg_t* pcall_test) {
1684 start:
1685 if (endp(alist)) /* end of alist ==> NIL */
1686 return NIL;
1687 else {
1688 var object head = Car(alist);
1689 if (mconsp(head)) { /* skip atomic list elements */
1690 pushSTACK(alist); /* save rest of list ((u . v) ...) */
1691 funcall_key(*(stackptr STACKop -1),Car(head)); /* (KEY u) */
1692 var bool erg = CALL_TEST(stackptr); /* (funcall TESTFUN ...) */
1693 alist = popSTACK();
1694 if (erg)
1695 /* Test ok -> x = (u . v) = (CAR alist) as result */
1696 return Car(alist);
1697 /* Test not ok */
1698 } else if (!nullp(head))
1699 error_list(head);
1700 /* call tail-recursively (assoc ... (cdr alist)) */
1701 alist = Cdr(alist); goto start;
1702 }
1703 }
1704
1705 LISPFUN(assoc,seclass_default,2,0,norest,key,3,
1706 (kw(test),kw(test_not),kw(key)) )
1707 { /* (ASSOC item alist :test :test-not :key), CLTL p. 280 */
1708 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1709 var funarg_t* pcall_test = check_test_args(&STACK_1); /* :TEST/:TEST-NOT arguments on STACK_2,STACK_1 */
1710 VALUES1(assoc(STACK_3,&STACK_1,pcall_test)); /* do the search */
1711 skipSTACK(5);
1712 }
1713
1714 LISPFUN(assoc_if,seclass_default,2,0,norest,key,1, (kw(key)) )
1715 { /* (ASSOC-IF pred alist :key), CLTL p. 280 */
1716 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1717 VALUES1(assoc(STACK_1,&STACK_1,&call_if)); /* do the search */
1718 skipSTACK(3);
1719 }
1720
1721 LISPFUN(assoc_if_not,seclass_default,2,0,norest,key,1, (kw(key)) )
1722 { /* (ASSOC-IF-NOT pred alist :key), CLTL p. 280 */
1723 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1724 VALUES1(assoc(STACK_1,&STACK_1,&call_if_not)); /* do the search */
1725 skipSTACK(3);
1726 }
1727
1728 /* UP: Returns the first list element, which CDR satisfies the TESTFUNction.
1729 rassoc(alist,stackptr)
1730 > alist: A-list
1731 > stackptr: *(stackptr-1) = KEY
1732 > up_fun: TESTFUN = Address of the test function. Called for list elements
1733 (u . v) with same stackptr and with (KEY v) as argument.
1734 Returns true or false.
1735 < result: List element (a Cons) or NIL
1736 can trigger GC */
rassoc(object alist,gcv_object_t * stackptr,funarg_t * pcall_test)1737 local maygc object rassoc (object alist, gcv_object_t* stackptr,
1738 funarg_t* pcall_test) {
1739 start:
1740 if (endp(alist)) /* end of alist ==> NIL */
1741 return NIL;
1742 else {
1743 var object head = Car(alist);
1744 if (mconsp(head)) { /* skip atomic list elements */
1745 pushSTACK(alist); /* save rest of list ((u . v) ...) */
1746 funcall_key(*(stackptr STACKop -1),Cdr(head)); /* (KEY v) */
1747 var bool erg = CALL_TEST(stackptr); /* (funcall TESTFUN ...) */
1748 alist = popSTACK();
1749 if (erg)
1750 /* Test ok -> x = (u . v) = (CAR alist) as result */
1751 return Car(alist);
1752 /* Test not ok */
1753 } else if (!nullp(head))
1754 error_list(head);
1755 /* Call tail-recursively (rassoc ... (cdr alist)) */
1756 alist = Cdr(alist); goto start;
1757 }
1758 }
1759
1760 LISPFUN(rassoc,seclass_default,2,0,norest,key,3,
1761 (kw(test),kw(test_not),kw(key)) )
1762 { /* (RASSOC item alist :test :test-not :key), CLTL p. 281 */
1763 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1764 var funarg_t* pcall_test = check_test_args(&STACK_1); /* :TEST/:TEST-NOT arguments on STACK_2,STACK_1 */
1765 VALUES1(rassoc(STACK_3,&STACK_1,pcall_test)); /* do the search */
1766 skipSTACK(5);
1767 }
1768
1769 LISPFUN(rassoc_if,seclass_default,2,0,norest,key,1, (kw(key)) )
1770 { /* (RASSOC-IF pred alist :key), CLTL p. 281 */
1771 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1772 VALUES1(rassoc(STACK_1,&STACK_1,&call_if)); /* do the search */
1773 skipSTACK(3);
1774 }
1775
1776 LISPFUN(rassoc_if_not,seclass_default,2,0,norest,key,1, (kw(key)) )
1777 { /* (RASSOC-IF-NOT pred alist :key), CLTL p. 281 */
1778 check_key_arg(&STACK_0); /* :KEY argument on STACK_0 */
1779 VALUES1(rassoc(STACK_1,&STACK_1,&call_if_not)); /* do the search */
1780 skipSTACK(3);
1781 }
1782
1783 /* functions making lists sequences: */
1784
1785 LISPFUNN(list_upd,2)
1786 { /* #'(lambda (seq pointer) (cdr pointer)) */
1787 VALUES1(cdr(popSTACK())); skipSTACK(1);
1788 }
1789
1790 LISPFUNN(list_endtest,2)
1791 { /* #'(lambda (seq pointer) (endp pointer)) */
1792 VALUES_IF(endp(STACK_0)); skipSTACK(2);
1793 }
1794
1795 LISPFUNN(list_fe_init,1)
1796 { /* #'(lambda (seq) (revappend seq nil)) */
1797 pushSTACK(NIL); C_revappend();
1798 }
1799
1800 LISPFUNN(list_access,2)
1801 { /* #'(lambda (seq pointer) (car pointer)) */
1802 var object pointer = check_cons(STACK_0);
1803 VALUES1(Car(pointer));
1804 skipSTACK(2);
1805 }
1806
1807 LISPFUNN(list_access_set,3)
1808 { /* #'(lambda (seq pointer value) (rplaca pointer value)) */
1809 var object pointer = check_cons(STACK_1);
1810 var object value = STACK_0;
1811 Car(pointer) = value;
1812 VALUES1(value);
1813 skipSTACK(3);
1814 }
1815
1816 /* UP: get the list element at the given index
1817 elt_up(seq,index)
1818 > seq
1819 > index
1820 < result: list element at this index */
elt_up(object seq,object index)1821 local object elt_up (object seq, object index) {
1822 var object l = seq;
1823 var object n = Fixnum_0;
1824 while (1) {
1825 if (atomp(l))
1826 goto index_too_large;
1827 if (eq(n,index))
1828 break;
1829 l = Cdr(l);
1830 n = fixnum_inc(n,1);
1831 }
1832 return l;
1833 index_too_large:
1834 pushSTACK(index); /* TYPE-ERROR slot DATUM */
1835 pushSTACK(NIL);
1836 pushSTACK(seq); pushSTACK(index); pushSTACK(TheSubr(subr_self)->name);
1837 {
1838 var object tmp;
1839 pushSTACK(S(integer)); pushSTACK(Fixnum_0); pushSTACK(n);
1840 tmp = listof(1); pushSTACK(tmp); tmp = listof(3);
1841 STACK_3 = tmp; /* TYPE-ERROR slot EXPECTED-TYPE */
1842 }
1843 error(type_error,GETTEXT("~S: index ~S too large for ~S"));
1844 }
1845
1846 LISPFUNN(list_elt,2)
1847 { /* (lambda (seq index)
1848 (do ((L seq (cdr L)) (N 0 (1+ N)))
1849 (nil)
1850 (if (atom L) (error "index ~S too large for ~S" index seq))
1851 (if (= N index) (return (car L))))) */
1852 var object index = popSTACK();
1853 var object seq = popSTACK();
1854 VALUES1(Car(elt_up(seq,index)));
1855 }
1856
1857 LISPFUNN(list_set_elt,3)
1858 { /* (lambda (seq index value)
1859 (do ((L seq (cdr L)) (N 0 (1+ N)))
1860 (nil)
1861 (if (atom L) (error "index ~S too large for ~S" index seq))
1862 (if (= N index) (return (rplaca L value))))) */
1863 var object nthcdr = elt_up(STACK_2,STACK_1);
1864 VALUES1(Car(nthcdr) = popSTACK());
1865 skipSTACK(2);
1866 }
1867
1868 LISPFUNN(list_init_start,2)
1869 { /* (lambda (seq index)
1870 (do ((L seq (cdr L)) (N 0 (1+ N)))
1871 ((= N index) (return L))
1872 (if (atom L) (error "start index ~S too large for ~S" index seq)))) */
1873 var object index = popSTACK();
1874 var object seq = popSTACK();
1875 var object l = seq;
1876 var object n = Fixnum_0;
1877 while (!eq(n,index)) {
1878 if (atomp(l))
1879 goto index_too_large;
1880 l = Cdr(l);
1881 n = fixnum_inc(n,1);
1882 }
1883 VALUES1(l); return;
1884 index_too_large:
1885 pushSTACK(seq);
1886 pushSTACK(index); /* TYPE-ERROR slot DATUM */
1887 {
1888 var object tmp;
1889 pushSTACK(S(integer)); pushSTACK(Fixnum_0); pushSTACK(n);
1890 tmp = listof(3); pushSTACK(tmp); /* TYPE-ERROR slot EXPECTED-TYPE */
1891 }
1892 pushSTACK(STACK_2); /* seq */
1893 pushSTACK(STACK_2); /* index */
1894 pushSTACK(S(list_init_start));
1895 error(type_error,GETTEXT("~S: start index ~S too large for ~S"));
1896 }
1897
1898 LISPFUNN(list_fe_init_end,2)
1899 { /* (lambda (seq index)
1900 (if (<= 0 index)
1901 (do* ((L1 nil (cons (car L2) L1))
1902 (L2 seq (cdr L2))
1903 (i index (1- i)))
1904 ((zerop i) L1)
1905 (if (atom L2)
1906 (error "end index ~S too large for ~S" index seq)))
1907 (error "end index ~S too large for ~S" index seq))) */
1908 /* index is known to be an Integer >=0. */
1909 pushSTACK(NIL); /* L1 := nil */
1910 { var object seq = STACK_2; pushSTACK(seq); } /* L2 := seq */
1911 pushSTACK(Fixnum_0); /* i := 0 */
1912 while (1) {
1913 /* stack layout: seq, index, L1, L2, i */
1914 if (eq(STACK_0,STACK_3)) /* i=index ? */
1915 goto end;
1916 if (matomp(STACK_1)) /* (atom L2) ? */
1917 goto index_too_large;
1918 var object new_cons = allocate_cons(); /* new Cons */
1919 var object L2 = STACK_1; STACK_1 = Cdr(L2); /* (pop L2) */
1920 Car(new_cons) = Car(L2); /* as CAR */
1921 Cdr(new_cons) = STACK_2; /* L1 as CDR */
1922 STACK_2 = new_cons; /* L1 := new Cons */
1923 STACK_0 = fixnum_inc(STACK_0,1); /* i := i+1 */
1924 }
1925 index_too_large:
1926 pushSTACK(STACK_3); /* TYPE-ERROR slot DATUM */
1927 {
1928 var object tmp;
1929 pushSTACK(S(integer)); pushSTACK(Fixnum_0); pushSTACK(STACK_(0+3));
1930 tmp = listof(3); pushSTACK(tmp); /* TYPE-ERROR slot EXPECTED-TYPE */
1931 }
1932 { pushSTACK(STACK_(4+2));
1933 pushSTACK(STACK_(3+3));
1934 pushSTACK(S(list_fe_init_end));
1935 error(type_error,GETTEXT("~S: end index ~S too large for ~S"));
1936 }
1937 end:
1938 VALUES1(STACK_2); /* return L1 */
1939 skipSTACK(5);
1940 }
1941