common/lists.c

   1 #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
  31 Handle 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
  50 void DisposeHandle (Handle handle)
  51 {
  52         if (handle) {
  53                 free (*handle);
  54                 free ((void *) handle);
  55         }
  56 }
  57 /********************************************************************/
  58
  59 unsigned int GetHandleSize (Handle handle)
  60 {
  61         return ((HandleRecord *) handle)->size;
  62 }
  63 /********************************************************************/
  64
  65 int 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 */
  96 static 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  */
 114 int 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 */
 155 static 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  */
 182 void 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
 198 list_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
 218 void ListSetAllocationPolicy (list_t list, int minItemsPerAlloc,
 219                               int percentIncreasePerAlloc)
 220 {
 221         (*list)->percentIncrease = percentIncreasePerAlloc;
 222         (*list)->minNumItemsIncrease = minItemsPerAlloc;
 223 }
 224
 225 /*******************************/
 226
 227 void ListDispose (list_t list)
 228 {
 229         DisposeHandle ((Handle) list);
 230 }
 231 /*******************************/
 232
 233 #ifdef  CFG_ALL_LIST_FUNCTIONS
 234
 235 void 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  */
 255 void 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  */
 267 list_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  */
 305 int 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  */
 347 int ListInsertItem (list_t list, void *ptrToItem, int itemPosition)
 348 {
 349         return ListInsertItems (list, ptrToItem, itemPosition, 1);
 350 }
 351
 352 /*******************************/
 353
 354 int 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
 409 int 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  */
 433 void 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  */
 444 void 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
 459 void 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
 470 void ListRemoveItem (list_t list, void *itemDestination, int itemPosition)
 471 {
 472         ListRemoveItems (list, itemDestination, itemPosition, 1);
 473 }
 474
 475 /*******************************/
 476
 477 void 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
 509 void 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  */
 529 void *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  */
 545 void *ListGetDataPtr (list_t list)
 546 {
 547         return &((*list)->itemList[0]);
 548 }
 549
 550 /********************************/
 551
 552 #ifdef  CFG_ALL_LIST_FUNCTIONS
 553
 554 int 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
 583 Error:
 584         return result;
 585 }
 586
 587 #endif /* CFG_ALL_LIST_FUNCTIONS */
 588
 589 /********************************/
 590
 591 int ListGetItemSize (list_t list)
 592 {
 593         return (*list)->itemSize;
 594 }
 595
 596 /********************************/
 597
 598 int ListNumItems (list_t list)
 599 {
 600         return (*list)->numItems;
 601 }
 602
 603 /*******************************/
 604
 605 #ifdef  CFG_ALL_LIST_FUNCTIONS
 606
 607 void 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
 637 int 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
 667 int 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
 678 int 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
 689 int CStringCompare (void *a, void *b)
 690 {
 691         return strcmp (*(char **) a, *(char **) b);
 692 }
 693
 694 /*******************************/
 695
 696
 697 int 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  */
 723 int 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 */