1 //metadoc List category Core
2 //metadoc List copyright Steve Dekorte 2002
3 //metadoc List license BSD revised
4 /*metadoc List description
5 A mutable array of values. The first index is 0.
6 */
7
8 #include <math.h>
9 #include "IoList.h"
10 #include "IoObject.h"
11 #include "IoState.h"
12 #include "IoCFunction.h"
13 #include "IoSeq.h"
14 #include "IoState.h"
15 #include "IoNumber.h"
16 #include "IoBlock.h"
17
18 static const char *protoId = "List";
19
20 #define DATA(self) ((List *)(IoObject_dataPointer(self)))
21
IoList_newTag(void * state)22 IoTag *IoList_newTag(void *state)
23 {
24 IoTag *tag = IoTag_newWithName_(protoId);
25 IoTag_state_(tag, state);
26 IoTag_freeFunc_(tag, (IoTagFreeFunc *)IoList_free);
27 IoTag_cloneFunc_(tag, (IoTagCloneFunc *)IoList_rawClone);
28 IoTag_markFunc_(tag, (IoTagMarkFunc *)IoList_mark);
29 IoTag_compareFunc_(tag, (IoTagCompareFunc *)IoList_compare);
30 //IoTag_writeToStreamFunc_(tag, (IoTagWriteToStreamFunc *)IoList_writeToStream_);
31 //IoTag_readFromStreamFunc_(tag, (IoTagReadFromStreamFunc *)IoList_readFromStream_);
32 return tag;
33 }
34
35 /*
36 void IoList_writeToStream_(IoList *self, BStream *stream)
37 {
38 List *list = DATA(self);
39
40 BStream_writeTaggedInt32_(stream, List_size(list));
41
42 LIST_FOREACH(list, i, v,
43 BStream_writeTaggedInt32_(stream, IoObject_pid((IoObject *)v));
44 );
45 }
46
47 void IoList_readFromStream_(IoList *self, BStream *stream)
48 {
49 List *list = DATA(self);
50 int i, max = BStream_readTaggedInt32(stream);
51
52 for (i = 0; i < max; i ++)
53 {
54 int pid = BStream_readTaggedInt32(stream);
55 IoObject *v = IoState_objectWithPid_(IOSTATE, pid);
56 List_append_(list, v);
57 }
58 }
59 */
60
IoList_proto(void * state)61 IoList *IoList_proto(void *state)
62 {
63 IoMethodTable methodTable[] = {
64 {"with", IoList_with},
65
66 // access
67
68 {"indexOf", IoList_indexOf},
69 {"contains", IoList_contains},
70 {"containsIdenticalTo", IoList_containsIdenticalTo},
71 {"capacity", IoList_capacity},
72 {"size", IoList_size},
73
74 // mutation
75
76 {"setSize", IoList_setSize},
77 {"removeAll", IoList_removeAll},
78 {"appendSeq", IoList_appendSeq},
79 {"append", IoList_append},
80 {"prepend", IoList_prepend},
81 {"push", IoList_append},
82
83 {"appendIfAbsent", IoList_appendIfAbsent},
84
85 {"remove", IoList_remove},
86 {"pop", IoList_pop},
87
88 {"atInsert", IoList_atInsert},
89 {"at", IoList_at},
90 {"atPut", IoList_atPut},
91
92 {"removeAt", IoList_removeAt},
93 {"swapIndices", IoList_swapIndices},
94
95 {"preallocateToSize", IoList_preallocateToSize},
96
97 {"first", IoList_first},
98 {"last", IoList_last},
99 {"slice", IoList_slice},
100 {"sliceInPlace", IoList_sliceInPlace},
101
102
103 {"sortInPlace", IoList_sortInPlace},
104 {"sortInPlaceBy", IoList_sortInPlaceBy},
105 {"foreach", IoList_foreach},
106 {"reverseInPlace", IoList_reverseInPlace},
107 {"reverseForeach", IoList_reverseForeach},
108
109 {"asEncodedList", IoList_asEncodedList},
110 {"fromEncodedList", IoList_fromEncodedList},
111 {"join", IoList_join},
112 {NULL, NULL},
113 };
114
115 IoObject *self = IoObject_new(state);
116 IoObject_tag_(self, IoList_newTag(state));
117
118 IoObject_setDataPointer_(self, List_new());
119 IoState_registerProtoWithId_((IoState *)state, self, protoId);
120
121 IoObject_addMethodTable_(self, methodTable);
122 return self;
123 }
124
IoList_rawClone(IoList * proto)125 IoList *IoList_rawClone(IoList *proto)
126 {
127 IoObject *self = IoObject_rawClonePrimitive(proto);
128 IoObject_tag_(self, IoObject_tag(proto));
129 IoObject_setDataPointer_(self, List_clone(DATA(proto)));
130 return self;
131 }
132
IoList_new(void * state)133 IoList *IoList_new(void *state)
134 {
135 IoObject *proto = IoState_protoWithId_((IoState *)state, protoId);
136 return IOCLONE(proto);
137 }
138
IoList_newWithList_(void * state,List * list)139 IoList *IoList_newWithList_(void *state, List *list)
140 {
141 IoList *self = IoList_new(state);
142 //printf("IoList_newWithList_ %p %p\n", (void *)self, (void *)list);
143 List_free(IoObject_dataPointer(self));
144 IoObject_setDataPointer_(self, list);
145 return self;
146 }
147
IoList_free(IoList * self)148 void IoList_free(IoList *self)
149 {
150 if (NULL == DATA(self))
151 {
152 printf("IoList_free(%p) already freed\n", (void *)self);
153 exit(1);
154 }
155 //printf("IoList_free(%p) List_free(%p)\n", (void *)self, (void *)DATA(self));
156
157 List_free(DATA(self));
158 IoObject_setDataPointer_(self, NULL);
159
160 }
161
IoList_mark(IoList * self)162 void IoList_mark(IoList *self)
163 {
164 LIST_FOREACH(DATA(self), i, item, IoObject_shouldMark(item));
165 }
166
IoList_compare(IoList * self,IoList * otherList)167 int IoList_compare(IoList *self, IoList *otherList)
168 {
169 if (!ISLIST(otherList))
170 {
171 return IoObject_defaultCompare(self, otherList);
172 }
173 else
174 {
175 size_t s1 = List_size(DATA(self));
176 size_t s2 = List_size(DATA(otherList));
177 size_t i;
178
179 if (s1 != s2)
180 {
181 return s1 > s2 ? 1 : -1;
182 }
183
184 for (i = 0; i < s1; i ++)
185 {
186 IoObject *v1 = LIST_AT_(DATA(self), i);
187 IoObject *v2 = LIST_AT_(DATA(otherList), i);
188 int c = IoObject_compare(v1, v2);
189
190 if (c)
191 {
192 return c;
193 }
194 }
195 }
196 return 0;
197 }
198
IoList_rawList(IoList * self)199 List *IoList_rawList(IoList *self)
200 {
201 return DATA(self);
202 }
203
IoList_rawAt_(IoList * self,int i)204 IoObject *IoList_rawAt_(IoList *self, int i)
205 {
206 return List_at_(DATA(self), i);
207 }
208
IoList_rawAt_put_(IoList * self,int i,IoObject * v)209 void IoList_rawAt_put_(IoList *self, int i, IoObject *v)
210 {
211 List_at_put_(DATA(self), i, IOREF(v));
212 IoObject_isDirty_(self, 1);
213 }
214
IoList_rawAppend_(IoList * self,IoObject * v)215 void IoList_rawAppend_(IoList *self, IoObject *v)
216 {
217 List_append_(DATA(self), IOREF(v));
218 IoObject_isDirty_(self, 1);
219 }
220
IoList_rawRemove_(IoList * self,IoObject * v)221 void IoList_rawRemove_(IoList *self, IoObject *v)
222 {
223 List_remove_(DATA(self), IOREF(v));
224 IoObject_isDirty_(self, 1);
225 }
226
IoList_rawAddBaseList_(IoList * self,List * otherList)227 void IoList_rawAddBaseList_(IoList *self, List *otherList)
228 {
229 List *list = DATA(self);
230 LIST_FOREACH(otherList, i, v, List_append_(list, IOREF((IoObject *)v)); );
231 IoObject_isDirty_(self, 1);
232 }
233
IoList_rawAddIoList_(IoList * self,IoList * other)234 void IoList_rawAddIoList_(IoList *self, IoList *other)
235 {
236 IoList_rawAddBaseList_(self, DATA(other));
237 IoObject_isDirty_(self, 1);
238 }
239
IoList_rawSize(IoList * self)240 size_t IoList_rawSize(IoList *self)
241 {
242 return List_size(DATA(self));
243 }
244
IoList_rawIndexOf_(IoList * self,IoObject * v)245 long IoList_rawIndexOf_(IoList *self, IoObject *v)
246 {
247 List *list = DATA(self);
248
249 LIST_FOREACH(list, i, item,
250 if (IoObject_compare(v, (IoObject *)item) == 0)
251 {
252 return i;
253 }
254 );
255
256 return -1;
257 }
258
IoList_checkIndex(IoList * self,IoMessage * m,char allowsExtending,int index,const char * methodName)259 void IoList_checkIndex(IoList *self, IoMessage *m, char allowsExtending, int index, const char *methodName)
260 {
261 size_t max = List_size(DATA(self));
262
263 if (allowsExtending)
264 {
265 max += 1;
266 }
267
268 if (index < 0 || index >= max)
269 {
270 IoState_error_(IOSTATE, m, "index out of bounds\n");
271 }
272 }
273
274 // immutable --------------------------------------------------------
275
IO_METHOD(IoList,with)276 IO_METHOD(IoList, with)
277 {
278 /*doc List with(anObject, ...)
279 Returns a new List containing the arguments.
280 */
281
282 int n, argCount = (int)IoMessage_argCount(m);
283 IoList *ioList = IOCLONE(self);
284
285 for (n = 0; n < argCount; n ++)
286 {
287 IoObject *v = IoMessage_locals_valueArgAt_(m, locals, n);
288 IoList_rawAppend_(ioList, v);
289 }
290
291 return ioList;
292 }
293
294
IO_METHOD(IoList,indexOf)295 IO_METHOD(IoList, indexOf)
296 {
297 /*doc List indexOf(anObject)
298 Returns the index of the first occurrence of anObject
299 in the receiver. Returns Nil if the receiver doesn't contain anObject.
300 */
301
302 int count = IoMessage_argCount(m);
303
304 IOASSERT(count, "indexOf requires at least one argument");
305
306 {
307 IoObject *v = IoMessage_locals_valueArgAt_(m, locals, 0);
308 size_t i = IoList_rawIndexOf_(self, v);
309
310 return i == -1 ? IONIL(self) :
311 (IoObject *)IONUMBER(IoList_rawIndexOf_(self, v));
312 }
313 }
314
IO_METHOD(IoList,contains)315 IO_METHOD(IoList, contains)
316 {
317 /*doc List contains(anObject)
318 Returns true if the receiver contains anObject, otherwise returns false.
319 */
320
321 IoObject *v = IoMessage_locals_valueArgAt_(m, locals, 0);
322 return IOBOOL(self, IoList_rawIndexOf_(self, v) != -1);
323 }
324
IO_METHOD(IoList,containsIdenticalTo)325 IO_METHOD(IoList, containsIdenticalTo)
326 {
327 /*doc List containsIdenticalTo(anObject)
328 Returns true if the receiver contains a value identical to anObject, otherwise returns false.
329 */
330
331 IoObject *v = IoMessage_locals_valueArgAt_(m, locals, 0);
332 return IOBOOL(self, List_contains_(DATA(self), v) != 0);
333 }
334
IO_METHOD(IoList,capacity)335 IO_METHOD(IoList, capacity)
336 {
337 /*doc List capacity
338 Returns the number of potential elements the receiver can hold before it needs to grow.
339 */
340
341 return IONUMBER(DATA(self)->memSize / sizeof(void *));
342 }
343
IO_METHOD(IoList,size)344 IO_METHOD(IoList, size)
345 {
346 /*doc List size
347 Returns the number of items in the receiver.
348 */
349
350 return IONUMBER(List_size(DATA(self)));
351 }
352
IO_METHOD(IoList,at)353 IO_METHOD(IoList, at)
354 {
355 /*doc List at(index)
356 Returns the value at index. Returns Nil if the index is out of bounds.
357 */
358
359 int index = IoMessage_locals_intArgAt_(m, locals, 0);
360 IoObject *v;
361 /*IoList_checkIndex(self, m, 0, index, "Io List at");*/
362 v = List_at_(DATA(self), index);
363 return (v) ? v : IONIL(self);
364 }
365
IO_METHOD(IoList,first)366 IO_METHOD(IoList, first)
367 {
368 /*doc List first(optionalSize)
369 Returns the first item or Nil if the list is empty.
370 If optionalSize is provided, that number of the first items in the list are returned.
371 */
372
373 IoObject *result = List_at_(DATA(self), 0);
374 return result ? result : IONIL(self);
375 }
376
IO_METHOD(IoList,last)377 IO_METHOD(IoList, last)
378 {
379 /*doc List last(optionalSize)
380 Returns the last item or Nil if the list is empty.
381 If optionalSize is provided, that number of the last items in the list are returned.
382 */
383
384 IoObject *result = List_at_(DATA(self), List_size(DATA(self)) - 1);
385 return result ? result : IONIL(self);
386 }
387
IoList_sliceIndex(int * index,int step,int size)388 void IoList_sliceIndex(int *index, int step, int size)
389 {
390 /* The following code mimics Python's slicing behaviour. */
391 if (*index < 0)
392 {
393 *index += size;
394 if (*index < 0)
395 {
396 *index = (step < 0) ? -1 : 0;
397 }
398 }
399 else if (*index >= size)
400 {
401 *index = (step < 0) ? size - 1 : size;
402 }
403 }
404
IoList_sliceArguments(IoList * self,IoObject * locals,IoMessage * m,int * start,int * end,int * step)405 void IoList_sliceArguments(IoList *self, IoObject *locals, IoMessage *m, int *start, int *end, int *step)
406 {
407 size_t size = IoList_rawSize(self);
408 /* Checking step, before any other arguments. */
409 *step = (IoMessage_argCount(m) == 3) ? IoMessage_locals_intArgAt_(m, locals, 2) : 1;
410 IOASSERT(step != 0, "step cannot be equal to zero");
411
412 *start = IoMessage_locals_intArgAt_(m, locals, 0);
413 *end = (IoMessage_argCount(m) >= 2) ? IoMessage_locals_intArgAt_(m, locals, 1) : (int)size;
414
415 /* Fixing slice index values. */
416 IoList_sliceIndex(start, *step, (int)size);
417 IoList_sliceIndex(end, *step, (int)size);
418 }
419
IO_METHOD(IoList,slice)420 IO_METHOD(IoList, slice)
421 {
422 /*doc List slice(startIndex, endIndex, step)
423 Returns a new string containing the subset of the receiver
424 from the startIndex to the endIndex. The endIndex argument
425 is optional. If not given, it is assumed to be the end of the string.
426 Step argument is also optional and defaults to 1, if not given.
427 However, since Io supports positional arguments only, you need to
428 explicitly specify endIndex, if you need a custom step.
429 */
430 List *list;
431 int start, end, step;
432
433 IoList_sliceArguments(self, locals, m, &start, &end, &step);
434
435 if ((step > 0 && end < start) ||
436 (step < 0 && end > start))
437 {
438 return IoList_new(IOSTATE);
439 }
440 else
441 {
442 list = List_cloneSlice(DATA(self), start, end, step);
443 return IoList_newWithList_(IOSTATE, list);
444 }
445 }
446
IO_METHOD(IoList,sliceInPlace)447 IO_METHOD(IoList, sliceInPlace)
448 {
449 /*doc List sliceInPlace(startIndex, endIndex, step)
450 Returns the receiver containing the subset of the
451 receiver from the startIndex to the endIndex. The endIndex argument
452 is optional. If not given, it is assumed to be the end of the string.
453 Step argument is also optional and defaults to 1.
454 */
455
456 int start, end, step;
457
458 IoList_sliceArguments(self, locals, m, &start, &end, &step);
459
460 if ((step > 0 && end < start) ||
461 (step < 0 && end > start))
462 {
463 return IoList_new(IOSTATE);
464 }
465 else
466 {
467 List_sliceInPlace(DATA(self), start, end, step);
468 }
469
470 IoObject_isDirty_(self, 1);
471
472 return self;
473 }
474
IO_METHOD(IoList,each)475 IO_METHOD(IoList, each)
476 {
477 IoState *state = IOSTATE;
478 IoObject *result = IONIL(self);
479 IoMessage *doMessage = IoMessage_rawArgAt_(m, 0);
480 List *list = DATA(self);
481
482 IoState_pushRetainPool(state);
483
484 LIST_SAFEFOREACH(list, i, v,
485 IoState_clearTopPool(state);
486 result = IoMessage_locals_performOn_(doMessage, locals, (IoObject *)v);
487 if (IoState_handleStatus(IOSTATE)) goto done;
488 );
489
490 done:
491 IoState_popRetainPoolExceptFor_(state, result);
492 return result;
493 }
494
495
IO_METHOD(IoList,foreach)496 IO_METHOD(IoList, foreach)
497 {
498 /*doc List foreach(optionalIndex, value, message)
499 Loops over the list values setting the specified index and
500 value slots and executing the message. Returns the result of the last
501 execution of the message. Example:
502 <p>
503 <pre>
504 list(1, 2, 3) foreach(i, v, writeln(i, " = ", v))
505 list(1, 2, 3) foreach(v, writeln(v))</pre>
506 */
507
508 IoState *state = IOSTATE;
509 IoObject *result = IONIL(self);
510 IoSymbol *slotName = NULL;
511 IoSymbol *valueName;
512 IoMessage *doMessage;
513 List *list = DATA(self);
514
515 if (IoMessage_argCount(m) == 1)
516 {
517 return IoList_each(self, locals, m);
518 }
519
520 IoMessage_foreachArgs(m, self, &slotName, &valueName, &doMessage);
521
522 IoState_pushRetainPool(state);
523
524 if (slotName)
525 {
526 LIST_SAFEFOREACH(list, i, value,
527 IoState_clearTopPool(state);
528 IoObject_setSlot_to_(locals, slotName, IONUMBER(i));
529 IoObject_setSlot_to_(locals, valueName, (IoObject *)value);
530 result = IoMessage_locals_performOn_(doMessage, locals, locals);
531 if (IoState_handleStatus(IOSTATE)) goto done;
532 );
533 }
534 else
535 {
536 LIST_SAFEFOREACH(list, i, value,
537 IoState_clearTopPool(state);
538 IoObject_setSlot_to_(locals, valueName, (IoObject *)value);
539 result = IoMessage_locals_performOn_(doMessage, locals, locals);
540 if (IoState_handleStatus(IOSTATE)) goto done;
541 );
542 }
543
544 done:
545 IoState_popRetainPoolExceptFor_(state, result);
546 return result;
547 }
548
IO_METHOD(IoList,reverseForeach)549 IO_METHOD(IoList, reverseForeach)
550 {
551 /*doc List reverseForeach(index, value, message)
552 Same as foreach, but in reverse order.
553 */
554
555 IoState *state = IOSTATE;
556 IoObject *result = IONIL(self);
557 IoSymbol *slotName, *valueName;
558 IoMessage *doMessage;
559 long i;
560
561 IoMessage_foreachArgs(m, self, &slotName, &valueName, &doMessage);
562
563 IoState_pushRetainPool(state);
564
565 for (i = List_size(DATA(self)) - 1; i >= 0; i --)
566 {
567 IoState_clearTopPool(state);
568 {
569 IoObject *value = (IoObject *)LIST_AT_(DATA(self), i);
570
571 if (slotName)
572 {
573 IoObject_setSlot_to_(locals, slotName, IONUMBER(i));
574 }
575
576 IoObject_setSlot_to_(locals, valueName, value);
577 result = IoMessage_locals_performOn_(doMessage, locals, locals);
578
579 if (IoState_handleStatus(IOSTATE))
580 {
581 goto done;
582 }
583 }
584 if(i > List_size(DATA(self)) - 1) { i = List_size(DATA(self)) - 1; }
585 }
586 done:
587 IoState_popRetainPoolExceptFor_(state, result);
588 return result;
589 }
590
591 // mutable --------------------------------------------------------
592
IO_METHOD(IoList,appendIfAbsent)593 IO_METHOD(IoList, appendIfAbsent)
594 {
595 /*doc List appendIfAbsent(anObject)
596 Adds each value not already contained by the receiver. Returns self.
597 */
598
599 int n;
600
601 for (n = 0; n < IoMessage_argCount(m); n ++)
602 {
603 IoObject *v = IoMessage_locals_valueArgAt_(m, locals, n);
604
605 if (IoList_rawIndexOf_(self, v) == -1)
606 {
607 IoState_stackRetain_(IOSTATE, v);
608 List_append_(DATA(self), IOREF(v));
609 IoObject_isDirty_(self, 1);
610 }
611 }
612
613 return self;
614 }
615
IO_METHOD(IoList,appendSeq)616 IO_METHOD(IoList, appendSeq)
617 {
618 /*doc List appendSeq(aList1, aList2, ...)
619 Add the items in the lists to the receiver. Returns self.
620 */
621
622 int i;
623
624 for (i = 0; i < IoMessage_argCount(m); i ++)
625 {
626 IoObject *other = IoMessage_locals_valueArgAt_(m, locals, i);
627
628 IOASSERT(ISLIST(other), "requires List objects as arguments");
629
630 if (other == self)
631 {
632 IoState_error_(IOSTATE, m, "can't add a list to itself\n");
633 }
634 else
635 {
636 List *selfList = DATA(self);
637 List *otherList = DATA(other);
638 size_t i, max = List_size(otherList);
639
640 for (i = 0; i < max; i ++)
641 {
642 IoObject *v = List_at_(otherList, i);
643 List_append_(selfList, IOREF(v));
644 }
645 IoObject_isDirty_(self, 1);
646 }
647 }
648
649 return self;
650 }
651
IO_METHOD(IoList,append)652 IO_METHOD(IoList, append)
653 {
654 /*doc List append(anObject1, anObject2, ...)
655 Appends the arguments to the end of the list. Returns self.
656 */
657
658 /*doc List push(anObject1, anObject2, ...)
659 Same as add(anObject1, anObject2, ...).
660 */
661
662 int n;
663
664 IOASSERT(IoMessage_argCount(m), "requires at least one argument");
665
666 for (n = 0; n < IoMessage_argCount(m); n ++)
667 {
668 IoObject *v = IoMessage_locals_valueArgAt_(m, locals, n);
669 List_append_(DATA(self), IOREF(v));
670 }
671
672 IoObject_isDirty_(self, 1);
673
674 return self;
675 }
676
IO_METHOD(IoList,prepend)677 IO_METHOD(IoList, prepend)
678 {
679 /*doc List prepend(anObject1, anObject2, ...)
680 Inserts the values at the beginning of the list. Returns self.
681 */
682
683 int n;
684
685 IOASSERT(IoMessage_argCount(m), "requires at least one argument");
686
687 for (n = 0; n < IoMessage_argCount(m); n ++)
688 {
689 IoObject *v = IoMessage_locals_valueArgAt_(m, locals, n);
690 List_at_insert_(DATA(self), 0, IOREF(v));
691 }
692
693 IoObject_isDirty_(self, 1);
694
695 return self;
696 }
697
698
IO_METHOD(IoList,remove)699 IO_METHOD(IoList, remove)
700 {
701 /*doc List remove(anObject, ...)
702 Removes all occurrences of the arguments from the receiver. Returns self.
703 */
704
705 int count = IoMessage_argCount(m);
706 int j;
707
708 IOASSERT(count, "requires at least one argument");
709
710 for (j = 0; j < count; j++)
711 {
712 IoObject *v = IoMessage_locals_valueArgAt_(m, locals, j);
713
714 // a quick pass to remove values with equal pointers
715 List_remove_(DATA(self), v);
716
717 // slow pass to remove values that match comparision test
718 for (;;)
719 {
720 long i = IoList_rawIndexOf_(self, v);
721
722 if (i == -1)
723 {
724 break;
725 }
726
727 List_removeIndex_(DATA(self), i);
728 }
729 }
730
731 IoObject_isDirty_(self, 1);
732
733 return self;
734 }
735
IO_METHOD(IoList,pop)736 IO_METHOD(IoList, pop)
737 {
738 /*doc List pop
739 Returns the last item in the list and removes it
740 from the receiver. Returns nil if the receiver is empty.
741 */
742
743 IoObject *v = List_pop(DATA(self));
744 return (v) ? v : IONIL(self);
745 }
746
IO_METHOD(IoList,atInsert)747 IO_METHOD(IoList, atInsert)
748 {
749 /*doc List atInsert(index, anObject)
750 Inserts anObject at the index specified by index.
751 Adds anObject if the index equals the current count of the receiver.
752 Raises an exception if the index is out of bounds. Returns self.
753 */
754
755 int index = IoMessage_locals_intArgAt_(m, locals, 0);
756 IoObject *v = IoMessage_locals_valueArgAt_(m, locals, 1);
757
758 IoList_checkIndex(self, m, 1, index, "List atInsert");
759 List_at_insert_(DATA(self), index, IOREF(v));
760 IoObject_isDirty_(self, 1);
761 return self;
762 }
763
IO_METHOD(IoList,removeAt)764 IO_METHOD(IoList, removeAt)
765 {
766 /*doc List removeAt(index)
767 Removes the item at the specified index and returns the value removed.
768 Raises an exception if the index is out of bounds.
769 */
770
771 int index = IoMessage_locals_intArgAt_(m, locals, 0);
772 IoObject *v = List_at_(DATA(self), index);
773
774 IoList_checkIndex(self, m, 0, index, "Io List atInsert");
775 List_removeIndex_(DATA(self), index);
776 IoObject_isDirty_(self, 1);
777 return (v) ? v : IONIL(self);
778 }
779
IoList_rawAtPut(IoList * self,int i,IoObject * v)780 void IoList_rawAtPut(IoList *self, int i, IoObject *v)
781 {
782 while (List_size(DATA(self)) < i) /* not efficient */
783 {
784 List_append_(DATA(self), IONIL(self));
785 }
786
787 List_at_put_(DATA(self), i, IOREF(v));
788 IoObject_isDirty_(self, 1);
789 }
790
IO_METHOD(IoList,atPut)791 IO_METHOD(IoList, atPut)
792 {
793 /*doc List atPut(index, anObject)
794 Replaces the existing value at index with anObject.
795 Raises an exception if the index is out of bounds. Returns self.
796 */
797
798 int index = IoMessage_locals_intArgAt_(m, locals, 0);
799 IoObject *v = IoMessage_locals_valueArgAt_(m, locals, 1);
800
801 IoList_checkIndex(self, m, 0, index, "Io List atPut");
802 IoList_rawAtPut(self, index, v);
803 IoObject_isDirty_(self, 1);
804 return self;
805 }
806
IO_METHOD(IoList,setSize)807 IO_METHOD(IoList, setSize)
808 {
809 /*doc List setSize(newSize)
810 Sets the size of the receiver by either removing excess items or adding nils as needed.
811 */
812
813 List *list = DATA(self);
814 size_t newSize = IoMessage_locals_sizetArgAt_(m, locals, 0);
815 size_t oldSize = List_size(list);
816
817 if(newSize < oldSize)
818 {
819 List_setSize_(list, newSize);
820 }
821 else
822 {
823 size_t i, max = newSize - oldSize;
824 IoObject *nilObject = IONIL(self);
825
826 for(i = 0; i < max; i ++)
827 {
828 List_append_(list, nilObject);
829 }
830 }
831
832 IoObject_isDirty_(self, 1);
833 return self;
834 }
835
IO_METHOD(IoList,removeAll)836 IO_METHOD(IoList, removeAll)
837 {
838 /*doc List empty
839 Removes all items from the receiver.
840 */
841
842 List_removeAll(DATA(self));
843 IoObject_isDirty_(self, 1);
844 return self;
845 }
846
IO_METHOD(IoList,swapIndices)847 IO_METHOD(IoList, swapIndices)
848 {
849 /*doc List swapIndices(index1, index2)
850 Exchanges the object at index1 with the object at index2.
851 Raises an exception if either index is out of bounds. Returns self.
852 */
853
854 int i = IoMessage_locals_intArgAt_(m, locals, 0);
855 int j = IoMessage_locals_intArgAt_(m, locals, 1);
856
857 IoList_checkIndex(self, m, 0, i, "List swapIndices");
858 IoList_checkIndex(self, m, 0, j, "List swapIndices");
859 List_swap_with_(DATA(self), i, j);
860 IoObject_isDirty_(self, 1);
861 return self;
862 }
863
IO_METHOD(IoList,reverseInPlace)864 IO_METHOD(IoList, reverseInPlace)
865 {
866 /*doc List reverseInPlace
867 Reverses the ordering of all the items in the receiver. Returns self.
868 */
869 List_reverseInPlace(DATA(self));
870 IoObject_isDirty_(self, 1);
871 return self;
872 }
873
IO_METHOD(IoList,preallocateToSize)874 IO_METHOD(IoList, preallocateToSize)
875 {
876 /*doc List preallocateToSize(aNumber)
877 Preallocates array memory to hold aNumber number of items.
878 */
879
880 int newSize = IoMessage_locals_intArgAt_(m, locals, 0);
881 List_preallocateToSize_(DATA(self), newSize);
882 return self;
883 }
884
885 // sorting -----------------------------------------------
886
887 typedef struct
888 {
889 IoState *state;
890 IoObject *locals;
891 IoMessage *exp;
892 List *list;
893 } MSortContext;
894
MSortContext_compareForSort(MSortContext * self,void * ap,void * bp)895 int MSortContext_compareForSort(MSortContext *self, void *ap, void *bp)
896 {
897 IoObject *a = *(void **)ap;
898 IoObject *b = *(void **)bp;
899 int r;
900
901 IoState_pushRetainPool(self->state);
902
903 a = IoMessage_locals_performOn_(self->exp, self->locals, a);
904 b = IoMessage_locals_performOn_(self->exp, self->locals, b);
905 r = IoObject_compare(a, b);
906
907 IoState_popRetainPool(self->state);
908 return r;
909 }
910
IO_METHOD(IoList,sortInPlace)911 IO_METHOD(IoList, sortInPlace)
912 {
913 /*doc List sortInPlace(optionalExpression)
914 Sorts the list using the compare method on the items. Returns self.
915 If an optionalExpression is provided, the sort is done on the result of the evaluation
916 of the optionalExpression on each value.
917 */
918
919 if (IoMessage_argCount(m) == 0)
920 {
921 List_qsort(DATA(self), (ListSortCallback *)IoObject_sortCompare);
922 }
923 else
924 {
925 MSortContext sc;
926 MSortContext *sortContext = ≻
927 sortContext->state = IOSTATE;
928 sortContext->locals = locals;
929 sortContext->exp = IoMessage_rawArgAt_(m, 0);
930
931 List_qsort_r(DATA(self), sortContext, (ListSortRCallback *)MSortContext_compareForSort);
932
933 }
934
935 IoObject_isDirty_(self, 1);
936 return self;
937 }
938
939 typedef struct
940 {
941 IoState *state;
942 IoObject *locals;
943 IoBlock *block;
944 IoMessage *blockMsg;
945 IoMessage *argMsg1;
946 IoMessage *argMsg2;
947 List *list;
948 } SortContext;
949
SortContext_compareForSort(SortContext * self,void * ap,void * bp)950 int SortContext_compareForSort(SortContext *self, void *ap, void *bp)
951 {
952 IoObject *a = *(void **)ap;
953 IoObject *b = *(void **)bp;
954 IoObject *cr;
955 IoState_pushRetainPool(self->state);
956
957 IoMessage_rawSetCachedResult_(self->argMsg1, a);
958 IoMessage_rawSetCachedResult_(self->argMsg2, b);
959 cr = IoBlock_activate(self->block, self->locals, self->locals, self->blockMsg, self->locals);
960
961 IoState_popRetainPool(self->state);
962 return ISFALSE(cr) ? 1 : -1;
963 }
964
IO_METHOD(IoList,sortInPlaceBy)965 IO_METHOD(IoList, sortInPlaceBy)
966 {
967 /*doc List sortInPlaceBy(aBlock)
968 Sort the list using aBlock as the compare function. Returns self.
969 */
970
971 SortContext sc;
972 SortContext *sortContext = ≻
973 sc.state = IOSTATE;
974 sc.locals = locals;
975 sc.block = IoMessage_locals_blockArgAt_(m, locals, 0);
976 sc.blockMsg = IoMessage_new(IOSTATE);
977 sc.argMsg1 = IoMessage_new(IOSTATE);
978 sc.argMsg2 = IoMessage_new(IOSTATE);
979
980 IoMessage_addArg_(sortContext->blockMsg, sortContext->argMsg1);
981 IoMessage_addArg_(sortContext->blockMsg, sortContext->argMsg2);
982
983 List_qsort_r(DATA(self), &sc, (ListSortRCallback *)SortContext_compareForSort);
984 IoObject_isDirty_(self, 1);
985 return self;
986 }
987
988 typedef enum
989 {
990 IOLIST_ENCODING_TYPE_NIL,
991 IOLIST_ENCODING_TYPE_NUMBER,
992 IOLIST_ENCODING_TYPE_SYMBOL,
993 IOLIST_ENCODING_TYPE_REFERENCE,
994
995 } IOLIST_ENCODING_TYPE;
996
997
IO_METHOD(IoList,asEncodedList)998 IO_METHOD(IoList, asEncodedList)
999 {
1000 /*doc List asEncodedList
1001 Returns a Sequence with an encoding of the list.
1002 Nil, Number and Symbol objects are copied into the encoding, for other object
1003 types, referenceIdForObject(item) will be called to request a reference id for
1004 the object.
1005
1006 Also see: List fromEncodedList.
1007 */
1008
1009 UArray *u = UArray_new();
1010 List *list = IoList_rawList(self);
1011 size_t i, max = List_size(list);
1012 IoMessage *rm = IOSTATE->referenceIdForObjectMessage;
1013
1014 UArray_setItemType_(u, CTYPE_uint8_t);
1015 UArray_setEncoding_(u, CENCODING_NUMBER);
1016
1017 //UArray_appendBytes_size_(u, " ", 4); // placeholder until we know the size
1018
1019 for(i = 0; i < max; i ++)
1020 {
1021 IoObject *item = List_at_(list, i);
1022
1023 if(ISNIL(item))
1024 {
1025 UArray_appendLong_(u, IOLIST_ENCODING_TYPE_NIL);
1026 UArray_appendLong_(u, 0);
1027 UArray_appendLong_(u, 0);
1028 }
1029 else if(ISNUMBER(item))
1030 {
1031 float32_t f = CNUMBER(item);
1032
1033 UArray_appendLong_(u, IOLIST_ENCODING_TYPE_NUMBER);
1034 UArray_appendLong_(u, CENCODING_NUMBER);
1035 UArray_appendLong_(u, CTYPE_float32_t);
1036 UArray_appendBytes_size_(u, (const uint8_t *)(&f), sizeof(float32_t));
1037 }
1038 else if(ISSEQ(item))
1039 {
1040 UArray *s = IoSeq_rawUArray(item);
1041 uint32_t size = (uint32_t)UArray_size(s);
1042
1043 UArray_appendLong_(u, IOLIST_ENCODING_TYPE_SYMBOL);
1044 UArray_appendLong_(u, UArray_encoding(s));
1045 UArray_appendLong_(u, UArray_itemType(s));
1046 UArray_appendBytes_size_(u, (const uint8_t *)(&size), sizeof(uint32_t));
1047 UArray_appendBytes_size_(u, (const uint8_t *)UArray_bytes(s), UArray_sizeInBytes(s));
1048 }
1049 else
1050 {
1051 IoObject *result;
1052
1053 IoMessage_setCachedArg_to_(rm, 0, item);
1054 result = IoObject_perform(locals, locals, rm);
1055 IoMessage_setCachedArg_to_(rm, 0, IONIL(self));
1056
1057 IOASSERT(ISNUMBER(result), "referenceIdForObject() must return a Number");
1058
1059 {
1060 uint32_t id = CNUMBER(result);
1061
1062 UArray_appendLong_(u, IOLIST_ENCODING_TYPE_REFERENCE);
1063 UArray_appendLong_(u, 0);
1064 UArray_appendLong_(u, 0);
1065 UArray_appendBytes_size_(u, (const uint8_t *)(&id), sizeof(uint32_t));
1066 }
1067 }
1068 }
1069
1070 return IoSeq_newWithUArray_copy_(IOSTATE, u, 0);
1071 }
1072
1073
IO_METHOD(IoList,fromEncodedList)1074 IO_METHOD(IoList, fromEncodedList)
1075 {
1076 /*doc List fromEncodedList(aSeq)
1077 Returns a List with the decoded Nils, Symbols and Numbers from the input raw array.
1078 For each object reference encounters, objectForReferenceId(id) will be called to
1079 allow the reference to be resolved.
1080
1081 Also see: List asEncodedList.
1082 */
1083
1084 IoMessage *rm = IOSTATE->objectForReferenceIdMessage;
1085 IoSeq *s = IoMessage_locals_seqArgAt_(m, locals, 0);
1086 UArray *u = IoSeq_rawUArray(s);
1087 List *list = List_new();
1088 const uint8_t *d = UArray_bytes(u);
1089 size_t uSize = UArray_sizeInBytes(u);
1090 size_t index = 0;
1091
1092 // add bounds checks
1093
1094 while (index < uSize)
1095 {
1096 if (index + 3 > uSize)
1097 {
1098 break;
1099 }
1100 uint8_t type = d[index + 0];
1101 uint8_t encoding = d[index + 1];
1102 uint8_t itemType = d[index + 2];
1103 index += 3;
1104
1105 if(type == IOLIST_ENCODING_TYPE_NIL)
1106 {
1107 List_append_(list, IONIL(self));
1108 }
1109 else if(type == IOLIST_ENCODING_TYPE_NUMBER)
1110 {
1111 if (index + sizeof(float32_t) > uSize)
1112 {
1113 break;
1114 }
1115 float32_t f = *((float32_t *)(d + index));
1116
1117 index += sizeof(float32_t);
1118 List_append_(list, IONUMBER(f));
1119 }
1120 else if(type == IOLIST_ENCODING_TYPE_SYMBOL)
1121 {
1122 if (index + sizeof(uint32_t) > uSize)
1123 {
1124 break;
1125 }
1126 uint32_t size = *((uint32_t *)(d + index));
1127 UArray *o;
1128
1129 index += sizeof(uint32_t);
1130
1131 if (index + size > uSize)
1132 {
1133 break;
1134 }
1135
1136 o = UArray_newWithData_type_size_copy_((void *)(d + index), itemType, size, 1);
1137 UArray_setEncoding_(o, encoding);
1138 List_append_(list, IoSeq_newWithUArray_copy_(IOSTATE, o, 0));
1139
1140 index += size;
1141 }
1142 else if(type == IOLIST_ENCODING_TYPE_REFERENCE)
1143 {
1144 // should we have a Number reference encoding?
1145 if (index + sizeof(uint32_t) > uSize)
1146 {
1147 break;
1148 }
1149 uint32_t id= *((uint32_t *)(d + index));
1150 IoMessage_setCachedArg_to_(rm, 0, IONUMBER(id));
1151 IoMessage_setCachedArg_to_(rm, 0, IONIL(self));
1152
1153 index += sizeof(uint32_t);
1154
1155 {
1156 IoObject *result = IoObject_perform(locals, locals, rm);
1157 List_append_(list, result);
1158 }
1159 }
1160 else
1161 {
1162 IOASSERT(0, "unrecognized encoded type");
1163 }
1164 }
1165 if (index == uSize)
1166 {
1167 return IoList_newWithList_(IOSTATE, list);
1168 }
1169 else
1170 {
1171 /* Decode error for some reason */
1172 List_free(list);
1173 return IONIL(self);
1174 }
1175 }
1176
IO_METHOD(IoList,join)1177 IO_METHOD(IoList, join)
1178 {
1179 /*doc List join(optionalSeparator)
1180 Returns a String with the elements of the receiver concatenated into one String.
1181 If optionalSeparator is provided, it is used to separate the concatenated strings.
1182 This operation does not respect string encodings.
1183 */
1184
1185 List *items = IoList_rawList(self);
1186 size_t itemCount = List_size(items);
1187 IoSeq *separator = IoMessage_locals_seqArgAt_(m, locals, 0);
1188 UArray *out = UArray_new();
1189 int totalSize = 0;
1190 int hasSeparator = !ISNIL(separator);
1191 size_t separatorSize = hasSeparator ? IOSEQ_LENGTH(separator) : 0;
1192 uint8_t *bytes;
1193 IOASSERT(ISSEQ(separator), "separator must be of type Sequence");
1194
1195 LIST_FOREACH(items, i, v,
1196 if(!ISSEQ(v))
1197 {
1198 //printf("type: %s\n", IoObject_name(v));
1199 IOASSERT(ISSEQ(v), "values must be of type Sequence");
1200 }
1201 totalSize += IoSeq_rawSizeInBytes(v);
1202 //printf("UArray_sizeInBytes(v): %i\n", (int) IoSeq_rawSizeInBytes(v));
1203 if(hasSeparator) totalSize += separatorSize;
1204 )
1205
1206 if(hasSeparator) totalSize -= separatorSize;
1207
1208 //printf("separatorSize: %i\n", (int) separatorSize);
1209 //printf("totalSize: %i\n", (int) totalSize);
1210 UArray_sizeTo_(out, totalSize+1);
1211
1212 bytes = UArray_mutableBytes(out);
1213
1214 LIST_FOREACH(items, i, v,
1215 size_t vsize = IoSeq_rawSizeInBytes(v);
1216 memcpy((char *)bytes, (char *)IoSeq_rawBytes(v), (int)vsize);
1217 bytes += vsize;
1218
1219 if(hasSeparator && i != itemCount-1)
1220 {
1221 memcpy(bytes, (char *)IoSeq_rawBytes(separator), separatorSize);
1222 bytes += separatorSize;
1223 }
1224 )
1225
1226 return IoSeq_newWithUArray_copy_(IOSTATE, out, 0);
1227 }
1228
1229