blob: 3f117b568ee2aa29cd9c54ad2118b6f5e7e7529b [file] [log] [blame]
wdenkaffae2b2002-08-17 09:36:01 +00001#include <common.h>
2#include <malloc.h>
3#include <lists.h>
4
5#define MAX(a,b) (((a)>(b)) ? (a) : (b))
6#define MIN(a,b) (((a)<(b)) ? (a) : (b))
7#define CAT4CHARS(a,b,c,d) ((a<<24) | (b<<16) | (c<<8) | d)
8
9/* increase list size by 10% every time it is full */
10#define kDefaultAllocationPercentIncrease 10
11
12/* always increase list size by 4 items when it is full */
13#define kDefaultAllocationminNumItemsIncrease 4
14
15/*
16 * how many items to expand the list by when it becomes full
17 * = current listSize (in items) + (hiword percent of list size) + loword
18 */
19#define NUMITEMSPERALLOC(list) MAX(((*list)->listSize * \
20 ((*list)->percentIncrease + 100)) / 100, \
21 (*list)->minNumItemsIncrease )
22
23#define ITEMPTR(list,item) &(((char *)&(*list)->itemList)[(*(list))->itemSize * (item)])
24
25#define LIST_SIGNATURE CAT4CHARS('L', 'I', 'S', 'T');
26
27#define calloc(size,num) malloc(size*num)
28
29/********************************************************************/
30
31Handle NewHandle (unsigned int numBytes)
32{
33 void *memPtr;
34 HandleRecord *hanPtr;
35
36 memPtr = calloc (numBytes, 1);
37 hanPtr = (HandleRecord *) calloc (sizeof (HandleRecord), 1);
38 if (hanPtr && (memPtr || numBytes == 0)) {
39 hanPtr->ptr = memPtr;
40 hanPtr->size = numBytes;
41 return (Handle) hanPtr;
42 } else {
43 free (memPtr);
44 free (hanPtr);
45 return NULL;
46 }
47}
48/********************************************************************/
49
50void DisposeHandle (Handle handle)
51{
52 if (handle) {
53 free (*handle);
54 free ((void *) handle);
55 }
56}
57/********************************************************************/
58
59unsigned int GetHandleSize (Handle handle)
60{
61 return ((HandleRecord *) handle)->size;
62}
63/********************************************************************/
64
65int SetHandleSize (Handle handle, unsigned int newSize)
66{
67 HandleRecord *hanRecPtr = (HandleRecord *) handle;
68 void *newPtr, *oldPtr;
69 unsigned int oldSize;
70
71
72 oldPtr = hanRecPtr->ptr;
73 oldSize = hanRecPtr->size;
74
75 if (oldSize == newSize)
76 return 1;
77
78 if (oldPtr == NULL) {
79 newPtr = malloc (newSize);
80 } else {
81 newPtr = realloc (oldPtr, newSize);
82 }
83 if (newPtr || (newSize == 0)) {
84 hanRecPtr->ptr = newPtr;
85 hanRecPtr->size = newSize;
86 if (newSize > oldSize)
87 memset ((char *) newPtr + oldSize, 0, newSize - oldSize);
88 return 1;
89 } else
90 return 0;
91}
92
93#ifdef CFG_ALL_LIST_FUNCTIONS
94
95/* Used to compare list elements by their raw data contents */
96static int ListMemBlockCmp (void *a, void *b, int size)
97{
98 return memcmp (a, b, size);
99}
100
101/***************************************************************************/
102
103/*
104 * Binary search numElements of size elementSize in array for a match
105 * to the. item. Return the index of the element that matches
106 * (0 - numElements - 1). If no match is found return the -i-1 where
107 * i is the index (0 - numElements) where the item should be placed.
108 * (*theCmp)(a,b) should return <0 if a<b, 0 if a==b, >0 if a>b.
109 *
110 * This function is like the C-Library function bsearch() except that
111 * this function returns the index where the item should be placed if
112 * it is not found.
113 */
114int BinSearch ( void *array, int numElements, int elementSize,
115 void *itemPtr, CompareFunction compareFunction)
116{
117 int low, high, mid, cmp;
118 void *arrayItemPtr;
119
120 for (low = 0, high = numElements - 1, mid = 0, cmp = -1; low <= high;) {
121 mid = (low + high) >> 1;
122
123 arrayItemPtr = (void *) (((char *) array) + (mid * elementSize));
124 cmp = compareFunction
125 ? compareFunction (itemPtr, arrayItemPtr)
126 : ListMemBlockCmp (itemPtr, arrayItemPtr, elementSize);
127 if (cmp == 0) {
128 return mid;
129 } else if (cmp < 0) {
130 high = mid - 1;
131 } else {
132 low = mid + 1;
133 }
134 }
135 if (cmp > 0)
136 mid++;
137
138 return -mid - 1;
139}
140
141#endif /* CFG_ALL_LIST_FUNCTIONS */
142
143/*******************************************************************************/
144
145/*
146 * If numNewItems == 0 then expand the list by the number of items
147 * indicated by its allocation policy.
148 * If numNewItems > 0 then expand the list by exactly the number of
149 * items indicated.
150 * If numNewItems < 0 then expand the list by the absolute value of
151 * numNewItems plus the number of items indicated by its allocation
152 * policy.
153 * Returns 1 for success, 0 if out of memory
154*/
155static int ExpandListSpace (list_t list, int numNewItems)
156{
157 if (numNewItems == 0) {
158 numNewItems = NUMITEMSPERALLOC (list);
159 } else if (numNewItems < 0) {
160 numNewItems = (-numNewItems) + NUMITEMSPERALLOC (list);
161 }
162
163 if (SetHandleSize ((Handle) list,
164 sizeof (ListStruct) +
165 ((*list)->listSize +
166 numNewItems) * (*list)->itemSize)) {
167 (*list)->listSize += numNewItems;
168 return 1;
169 } else {
170 return 0;
171 }
172}
173
174/*******************************/
175
176#ifdef CFG_ALL_LIST_FUNCTIONS
177
178/*
179 * This function reallocate the list, minus any currently unused
180 * portion of its allotted memory.
181 */
182void ListCompact (list_t list)
183{
184
185 if (!SetHandleSize ((Handle) list,
186 sizeof (ListStruct) +
187 (*list)->numItems * (*list)->itemSize)) {
188 return;
189 }
190
191 (*list)->listSize = (*list)->numItems;
192}
193
194#endif /* CFG_ALL_LIST_FUNCTIONS */
195
196/*******************************/
197
198list_t ListCreate (int elementSize)
199{
200 list_t list;
201
202 list = (list_t) (NewHandle (sizeof (ListStruct))); /* create empty list */
203 if (list) {
204 (*list)->signature = LIST_SIGNATURE;
205 (*list)->numItems = 0;
206 (*list)->listSize = 0;
207 (*list)->itemSize = elementSize;
208 (*list)->percentIncrease = kDefaultAllocationPercentIncrease;
209 (*list)->minNumItemsIncrease =
210 kDefaultAllocationminNumItemsIncrease;
211 }
212
213 return list;
214}
215
216/*******************************/
217
218void ListSetAllocationPolicy (list_t list, int minItemsPerAlloc,
219 int percentIncreasePerAlloc)
220{
221 (*list)->percentIncrease = percentIncreasePerAlloc;
222 (*list)->minNumItemsIncrease = minItemsPerAlloc;
223}
224
225/*******************************/
226
227void ListDispose (list_t list)
228{
229 DisposeHandle ((Handle) list);
230}
231/*******************************/
232
233#ifdef CFG_ALL_LIST_FUNCTIONS
234
235void ListDisposePtrList (list_t list)
236{
237 int index;
238 int numItems;
239
240 if (list) {
241 numItems = ListNumItems (list);
242
243 for (index = 1; index <= numItems; index++)
244 free (*(void **) ListGetPtrToItem (list, index));
245
246 ListDispose (list);
247 }
248}
249
250/*******************************/
251
252/*
253 * keeps memory, resets the number of items to 0
254 */
255void ListClear (list_t list)
256{
257 if (!list)
258 return;
259 (*list)->numItems = 0;
260}
261
262/*******************************/
263
264/*
265 * copy is only as large as necessary
266 */
267list_t ListCopy (list_t originalList)
268{
269 list_t tempList = NULL;
270 int numItems;
271
272 if (!originalList)
273 return NULL;
274
275 tempList = ListCreate ((*originalList)->itemSize);
276 if (tempList) {
277 numItems = ListNumItems (originalList);
278
279 if (!SetHandleSize ((Handle) tempList,
280 sizeof (ListStruct) +
281 numItems * (*tempList)->itemSize)) {
282 ListDispose (tempList);
283 return NULL;
284 }
285
286 (*tempList)->numItems = (*originalList)->numItems;
287 (*tempList)->listSize = (*originalList)->numItems;
288 (*tempList)->itemSize = (*originalList)->itemSize;
289 (*tempList)->percentIncrease = (*originalList)->percentIncrease;
290 (*tempList)->minNumItemsIncrease =
291 (*originalList)->minNumItemsIncrease;
292
293 memcpy (ITEMPTR (tempList, 0), ITEMPTR (originalList, 0),
294 numItems * (*tempList)->itemSize);
295 }
296
297 return tempList;
298}
299
300/********************************/
301
302/*
303 * list1 = list1 + list2
304 */
305int ListAppend (list_t list1, list_t list2)
306{
307 int numItemsL1, numItemsL2;
308
309 if (!list2)
310 return 1;
311
312 if (!list1)
313 return 0;
314 if ((*list1)->itemSize != (*list2)->itemSize)
315 return 0;
316
317 numItemsL1 = ListNumItems (list1);
318 numItemsL2 = ListNumItems (list2);
319
320 if (numItemsL2 == 0)
321 return 1;
322
323 if (!SetHandleSize ((Handle) list1,
324 sizeof (ListStruct) + (numItemsL1 + numItemsL2) *
325 (*list1)->itemSize)) {
326 return 0;
327 }
328
329 (*list1)->numItems = numItemsL1 + numItemsL2;
330 (*list1)->listSize = numItemsL1 + numItemsL2;
331
332 memmove (ITEMPTR (list1, numItemsL1),
333 ITEMPTR (list2, 0),
334 numItemsL2 * (*list2)->itemSize);
335
336 return 1;
337}
338
339#endif /* CFG_ALL_LIST_FUNCTIONS */
340
341/*******************************/
342
343/*
344 * returns 1 if the item is inserted, returns 0 if out of memory or
345 * bad arguments were passed.
346 */
347int ListInsertItem (list_t list, void *ptrToItem, int itemPosition)
348{
349 return ListInsertItems (list, ptrToItem, itemPosition, 1);
350}
351
352/*******************************/
353
354int ListInsertItems (list_t list, void *ptrToItems, int firstItemPosition,
355 int numItemsToInsert)
356{
357 int numItems = (*list)->numItems;
358
359 if (firstItemPosition == numItems + 1)
360 firstItemPosition = LIST_END;
361 else if (firstItemPosition > numItems)
362 return 0;
363
364 if ((*list)->numItems >= (*list)->listSize) {
365 if (!ExpandListSpace (list, -numItemsToInsert))
366 return 0;
367 }
368
369 if (firstItemPosition == LIST_START) {
370 if (numItems == 0) {
371 /* special case for empty list */
372 firstItemPosition = LIST_END;
373 } else {
374 firstItemPosition = 1;
375 }
376 }
377
378 if (firstItemPosition == LIST_END) { /* add at the end of the list */
379 if (ptrToItems)
380 memcpy (ITEMPTR (list, numItems), ptrToItems,
381 (*list)->itemSize * numItemsToInsert);
382 else
383 memset (ITEMPTR (list, numItems), 0,
384 (*list)->itemSize * numItemsToInsert);
385
386 (*list)->numItems += numItemsToInsert;
387 } else { /* move part of list up to make room for new item */
388 memmove (ITEMPTR (list, firstItemPosition - 1 + numItemsToInsert),
389 ITEMPTR (list, firstItemPosition - 1),
390 (numItems + 1 - firstItemPosition) * (*list)->itemSize);
391
392 if (ptrToItems)
393 memmove (ITEMPTR (list, firstItemPosition - 1), ptrToItems,
394 (*list)->itemSize * numItemsToInsert);
395 else
396 memset (ITEMPTR (list, firstItemPosition - 1), 0,
397 (*list)->itemSize * numItemsToInsert);
398
399 (*list)->numItems += numItemsToInsert;
400 }
401
402 return 1;
403}
404
405#ifdef CFG_ALL_LIST_FUNCTIONS
406
407/*******************************/
408
409int ListEqual (list_t list1, list_t list2)
410{
411 if (list1 == list2)
412 return 1;
413
414 if (list1 == NULL || list2 == NULL)
415 return 0;
416
417 if ((*list1)->itemSize == (*list1)->itemSize) {
418 if ((*list1)->numItems == (*list2)->numItems) {
419 return (memcmp (ITEMPTR (list1, 0), ITEMPTR (list2, 0),
420 (*list1)->itemSize * (*list1)->numItems) == 0);
421 }
422 }
423
424 return 0;
425}
426
427/*******************************/
428
429/*
430 * The item pointed to by ptrToItem is copied over the current item
431 * at itemPosition
432 */
433void ListReplaceItem (list_t list, void *ptrToItem, int itemPosition)
434{
435 ListReplaceItems (list, ptrToItem, itemPosition, 1);
436}
437
438/*******************************/
439
440/*
441 * The item pointed to by ptrToItems is copied over the current item
442 * at itemPosition
443 */
444void ListReplaceItems ( list_t list, void *ptrToItems,
445 int firstItemPosition, int numItemsToReplace)
446{
447
448 if (firstItemPosition == LIST_END)
449 firstItemPosition = (*list)->numItems;
450 else if (firstItemPosition == LIST_START)
451 firstItemPosition = 1;
452
453 memmove (ITEMPTR (list, firstItemPosition - 1), ptrToItems,
454 (*list)->itemSize * numItemsToReplace);
455}
456
457/*******************************/
458
459void ListGetItem (list_t list, void *itemDestination, int itemPosition)
460{
461 ListGetItems (list, itemDestination, itemPosition, 1);
462}
463
464#endif /* CFG_ALL_LIST_FUNCTIONS */
465
466/*******************************/
467
468#if defined(CFG_ALL_LIST_FUNCTIONS) || defined(CFG_DEVICE_DEREGISTER)
469
470void ListRemoveItem (list_t list, void *itemDestination, int itemPosition)
471{
472 ListRemoveItems (list, itemDestination, itemPosition, 1);
473}
474
475/*******************************/
476
477void ListRemoveItems (list_t list, void *itemsDestination,
478 int firstItemPosition, int numItemsToRemove)
479{
480 int firstItemAfterChunk, numToMove;
481
482 if (firstItemPosition == LIST_START)
483 firstItemPosition = 1;
484 else if (firstItemPosition == LIST_END)
485 firstItemPosition = (*list)->numItems;
486
487 if (itemsDestination != NULL)
488 memcpy (itemsDestination, ITEMPTR (list, firstItemPosition - 1),
489 (*list)->itemSize * numItemsToRemove);
490
491 firstItemAfterChunk = firstItemPosition + numItemsToRemove;
492 numToMove = (*list)->numItems - (firstItemAfterChunk - 1);
493
494 if (numToMove > 0) {
495 /*
496 * move part of list down to cover hole left by removed item
497 */
498 memmove (ITEMPTR (list, firstItemPosition - 1),
499 ITEMPTR (list, firstItemAfterChunk - 1),
500 (*list)->itemSize * numToMove);
501 }
502
503 (*list)->numItems -= numItemsToRemove;
504}
505#endif /* CFG_ALL_LIST_FUNCTIONS || CFG_DEVICE_DEREGISTER */
506
507/*******************************/
508
509void ListGetItems (list_t list, void *itemsDestination,
510 int firstItemPosition, int numItemsToGet)
511{
512
513 if (firstItemPosition == LIST_START)
514 firstItemPosition = 1;
515 else if (firstItemPosition == LIST_END)
516 firstItemPosition = (*list)->numItems;
517
518 memcpy (itemsDestination,
519 ITEMPTR (list, firstItemPosition - 1),
520 (*list)->itemSize * numItemsToGet);
521}
522
523/*******************************/
524
525/*
526 * Returns a pointer to the item at itemPosition. returns null if an
527 * errors occurred.
528 */
529void *ListGetPtrToItem (list_t list, int itemPosition)
530{
531 if (itemPosition == LIST_START)
532 itemPosition = 1;
533 else if (itemPosition == LIST_END)
534 itemPosition = (*list)->numItems;
535
536 return ITEMPTR (list, itemPosition - 1);
537}
538
539/*******************************/
540
541/*
542 * returns a pointer the lists data (abstraction violation for
543 * optimization)
544 */
545void *ListGetDataPtr (list_t list)
546{
547 return &((*list)->itemList[0]);
548}
549
550/********************************/
551
552#ifdef CFG_ALL_LIST_FUNCTIONS
553
554int ListApplyToEach (list_t list, int ascending,
555 ListApplicationFunc funcToApply,
556 void *callbackData)
557{
558 int result = 0, index;
559
560 if (!list || !funcToApply)
561 goto Error;
562
563 if (ascending) {
564 for (index = 1; index <= ListNumItems (list); index++) {
565 result = funcToApply (index,
566 ListGetPtrToItem (list, index),
567 callbackData);
568 if (result < 0)
569 goto Error;
570 }
571 } else {
572 for (index = ListNumItems (list);
573 index > 0 && index <= ListNumItems (list);
574 index--) {
575 result = funcToApply (index,
576 ListGetPtrToItem (list, index),
577 callbackData);
578 if (result < 0)
579 goto Error;
580 }
581 }
582
583Error:
584 return result;
585}
586
587#endif /* CFG_ALL_LIST_FUNCTIONS */
588
589/********************************/
590
591int ListGetItemSize (list_t list)
592{
593 return (*list)->itemSize;
594}
595
596/********************************/
597
598int ListNumItems (list_t list)
599{
600 return (*list)->numItems;
601}
602
603/*******************************/
604
605#ifdef CFG_ALL_LIST_FUNCTIONS
606
607void ListRemoveDuplicates (list_t list, CompareFunction compareFunction)
608{
609 int numItems, index, startIndexForFind, duplicatesIndex;
610
611 numItems = ListNumItems (list);
612
613 for (index = 1; index < numItems; index++) {
614 startIndexForFind = index + 1;
615 while (startIndexForFind <= numItems) {
616 duplicatesIndex =
617 ListFindItem (list,
618 ListGetPtrToItem (list, index),
619 startIndexForFind,
620 compareFunction);
621 if (duplicatesIndex > 0) {
622 ListRemoveItem (list, NULL, duplicatesIndex);
623 numItems--;
624 startIndexForFind = duplicatesIndex;
625 } else {
626 break;
627 }
628 }
629 }
630}
631
632/*******************************/
633
634
635/*******************************/
636
637int ListFindItem (list_t list, void *ptrToItem, int startingPosition,
638 CompareFunction compareFunction)
639{
640 int numItems, size, index, cmp;
641 void *listItemPtr;
642
643 if ((numItems = (*list)->numItems) == 0)
644 return 0;
645
646 size = (*list)->itemSize;
647
648 if (startingPosition == LIST_START)
649 startingPosition = 1;
650 else if (startingPosition == LIST_END)
651 startingPosition = numItems;
652
653 for (index = startingPosition; index <= numItems; index++) {
654 listItemPtr = ITEMPTR (list, index - 1);
655 cmp = compareFunction
656 ? compareFunction (ptrToItem, listItemPtr)
657 : ListMemBlockCmp (ptrToItem, listItemPtr, size);
658 if (cmp == 0)
659 return index;
660 }
661
662 return 0;
663}
664
665/*******************************/
666
667int ShortCompare (void *a, void *b)
668{
669 if (*(short *) a < *(short *) b)
670 return -1;
671 if (*(short *) a > *(short *) b)
672 return 1;
673 return 0;
674}
675
676/*******************************/
677
678int IntCompare (void *a, void *b)
679{
680 if (*(int *) a < *(int *) b)
681 return -1;
682 if (*(int *) a > *(int *) b)
683 return 1;
684 return 0;
685}
686
687/*******************************/
688
689int CStringCompare (void *a, void *b)
690{
691 return strcmp (*(char **) a, *(char **) b);
692}
693
694/*******************************/
695
696
697int ListBinSearch (list_t list, void *ptrToItem,
698 CompareFunction compareFunction)
699{
700 int index;
701
702 index = BinSearch (ITEMPTR (list, 0),
703 (int) (*list)->numItems,
704 (int) (*list)->itemSize, ptrToItem,
705 compareFunction);
706
707 if (index >= 0)
708 index++; /* lists start from 1 */
709 else
710 index = 0; /* item not found */
711
712 return index;
713}
714
715/**************************************************************************/
716
717/*
718 * Reserves memory for numItems in the list. If it succeeds then
719 * numItems items can be inserted without possibility of an out of
720 * memory error (useful to simplify error recovery in complex
721 * functions). Returns 1 if success, 0 if out of memory.
722 */
723int ListPreAllocate (list_t list, int numItems)
724{
725 if ((*list)->listSize - (*list)->numItems < numItems) {
726 return ExpandListSpace (list,
727 numItems - ((*list)->listSize -
728 (*list)->numItems));
729 } else {
730 return 1; /* enough items are already pre-allocated */
731 }
732}
733
734#endif /* CFG_ALL_LIST_FUNCTIONS */