git.sur5r.net Git - cc65/blob - src/common/coll.c

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                  coll.c                                   */
   4 /*                                                                           */
   5 /*                        Collection (dynamic array)                         */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 2000-2011, Ullrich von Bassewitz                                      */
  10 /*                Roemerstrasse 52                                           */
  11 /*                D-70794 Filderstadt                                        */
  12 /* EMail:         uz@cc65.org                                                */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 #include <stdlib.h>
  37 #include <string.h>
  38
  39 /* common */
  40 #include "check.h"
  41 #include "xmalloc.h"
  42
  43 /* cc65 */
  44 #include "coll.h"
  45
  46
  47
  48 /*****************************************************************************/
  49 /*                                   Data                                    */
  50 /*****************************************************************************/
  51
  52
  53
  54 /* An empty collection */
  55 const Collection EmptyCollection = STATIC_COLLECTION_INITIALIZER;
  56
  57
  58
  59 /*****************************************************************************/
  60 /*                                   Code                                    */
  61 /*****************************************************************************/
  62
  63
  64
  65 Collection* InitCollection (Collection* C)
  66 /* Initialize a collection and return it. */
  67 {
  68     /* Intialize the fields. */
  69     C->Count = 0;
  70     C->Size  = 0;
  71     C->Items = 0;
  72
  73     /* Return the new struct */
  74     return C;
  75 }
  76
  77
  78
  79 void DoneCollection (Collection* C)
  80 /* Free the data for a collection. This will not free the data contained in
  81 ** the collection.
  82 */
  83 {
  84     /* Free the pointer array */
  85     xfree (C->Items);
  86 }
  87
  88
  89
  90 Collection* NewCollection (void)
  91 /* Create and return a new collection with the given initial size */
  92 {
  93     /* Allocate memory, intialize the collection and return it */
  94     return InitCollection (xmalloc (sizeof (Collection)));
  95 }
  96
  97
  98
  99 void FreeCollection (Collection* C)
 100 /* Free a collection */
 101 {
 102     /* Free the data */
 103     DoneCollection (C);
 104
 105     /* Free the structure itself */
 106     xfree (C);
 107 }
 108
 109
 110
 111 void CollGrow (Collection* C, unsigned Size)
 112 /* Grow the collection C so it is able to hold Size items without a resize
 113 ** being necessary. This can be called for performance reasons if the number
 114 ** of items to be placed in the collection is known in advance.
 115 */
 116 {
 117     void** NewItems;
 118
 119     /* Ignore the call if the collection is already large enough */
 120     if (Size <= C->Size) {
 121         return;
 122     }
 123
 124     /* Grow the collection */
 125     C->Size = Size;
 126     NewItems = xmalloc (C->Size * sizeof (void*));
 127     memcpy (NewItems, C->Items, C->Count * sizeof (void*));
 128     xfree (C->Items);
 129     C->Items = NewItems;
 130 }
 131
 132
 133
 134 void CollInsert (Collection* C, void* Item, unsigned Index)
 135 /* Insert the data at the given position in the collection */
 136 {
 137     /* Check for invalid indices */
 138     PRECONDITION (Index <= C->Count);
 139
 140     /* Grow the array if necessary */
 141     if (C->Count >= C->Size) {
 142         /* Must grow */
 143         CollGrow (C, (C->Size == 0)? 4 : C->Size * 2);
 144     }
 145
 146     /* Move the existing elements if needed */
 147     if (C->Count != Index) {
 148         memmove (C->Items+Index+1, C->Items+Index, (C->Count-Index) * sizeof (void*));
 149     }
 150     ++C->Count;
 151
 152     /* Store the new item */
 153     C->Items[Index] = Item;
 154 }
 155
 156
 157
 158 #if !defined(HAVE_INLINE)
 159 void CollAppend (Collection* C, void* Item)
 160 /* Append an item to the end of the collection */
 161 {
 162     /* Insert the item at the end of the current list */
 163     CollInsert (C, Item, C->Count);
 164 }
 165 #endif
 166
 167
 168
 169 #if !defined(HAVE_INLINE)
 170 void* CollAt (const Collection* C, unsigned Index)
 171 /* Return the item at the given index */
 172 {
 173     /* Check the index */
 174     PRECONDITION (Index < C->Count);
 175
 176     /* Return the element */
 177     return C->Items[Index];
 178 }
 179 #endif
 180
 181
 182
 183 #if !defined(HAVE_INLINE)
 184 const void* CollConstAt (const Collection* C, unsigned Index)
 185 /* Return the item at the given index */
 186 {
 187     /* Check the index */
 188     PRECONDITION (Index < C->Count);
 189
 190     /* Return the element */
 191     return C->Items[Index];
 192 }
 193 #endif
 194
 195
 196
 197 #if !defined(HAVE_INLINE)
 198 void* CollLast (Collection* C)
 199 /* Return the last item in a collection */
 200 {
 201     /* We must have at least one entry */
 202     PRECONDITION (C->Count > 0);
 203
 204     /* Return the element */
 205     return C->Items[C->Count-1];
 206 }
 207 #endif
 208
 209
 210
 211 #if !defined(HAVE_INLINE)
 212 const void* CollConstLast (const Collection* C)
 213 /* Return the last item in a collection */
 214 {
 215     /* We must have at least one entry */
 216     PRECONDITION (C->Count > 0);
 217
 218     /* Return the element */
 219     return C->Items[C->Count-1];
 220 }
 221 #endif
 222
 223
 224
 225 #if !defined(HAVE_INLINE)
 226 void* CollPop (Collection* C)
 227 /* Remove the last segment from the stack and return it. Calls FAIL if the
 228 ** collection is empty.
 229 */
 230 {
 231     /* We must have at least one entry */
 232     PRECONDITION (C->Count > 0);
 233
 234     /* Return the element */
 235     return C->Items[--C->Count];
 236 }
 237 #endif
 238
 239
 240
 241 int CollIndex (Collection* C, const void* Item)
 242 /* Return the index of the given item in the collection. Return -1 if the
 243 ** item was not found in the collection.
 244 */
 245 {
 246     /* Linear search */
 247     unsigned I;
 248     for (I = 0; I < C->Count; ++I) {
 249         if (Item == C->Items[I]) {
 250             /* Found */
 251             return (int)I;
 252         }
 253     }
 254
 255     /* Not found */
 256     return -1;
 257 }
 258
 259
 260
 261 void CollDelete (Collection* C, unsigned Index)
 262 /* Remove the item with the given index from the collection. This will not
 263 ** free the item itself, just the pointer. All items with higher indices
 264 ** will get moved to a lower position.
 265 */
 266 {
 267     /* Check the index */
 268     PRECONDITION (Index < C->Count);
 269
 270     /* Remove the item pointer */
 271     --C->Count;
 272     memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
 273 }
 274
 275
 276
 277 void CollDeleteItem (Collection* C, const void* Item)
 278 /* Delete the item pointer from the collection. The item must be in the
 279 ** collection, otherwise FAIL will be called.
 280 */
 281 {
 282     /* Get the index of the entry */
 283     int Index = CollIndex (C, Item);
 284     CHECK (Index >= 0);
 285
 286     /* Delete the item with this index */
 287     --C->Count;
 288     memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
 289 }
 290
 291
 292
 293 #if !defined(HAVE_INLINE)
 294 void CollReplace (Collection* C, void* Item, unsigned Index)
 295 /* Replace the item at the given position. The old item will not be freed,
 296 ** just the pointer will get replaced.
 297 */
 298 {
 299     /* Check the index */
 300     PRECONDITION (Index < C->Count);
 301
 302     /* Replace the item pointer */
 303     C->Items[Index] = Item;
 304 }
 305 #endif
 306
 307
 308
 309 void CollReplaceExpand (Collection* C, void* Item, unsigned Index)
 310 /* If Index is a valid index for the collection, replace the item at this
 311 ** position by the one passed. If the collection is too small, expand it,
 312 ** filling unused pointers with NULL, then add the new item at the given
 313 ** position.
 314 */
 315 {
 316     if (Index < C->Count) {
 317         /* Collection is already large enough */
 318         C->Items[Index] = Item;
 319     } else {
 320         /* Must expand the collection */
 321         unsigned Size = C->Size;
 322         if (Size == 0) {
 323             Size = 4;
 324         }
 325         while (Index >= Size) {
 326             Size *= 2;
 327         }
 328         CollGrow (C, Size);
 329
 330         /* Fill up unused slots with NULL */
 331         while (C->Count < Index) {
 332             C->Items[C->Count++] = 0;
 333         }
 334
 335         /* Fill in the item */
 336         C->Items[C->Count++] = Item;
 337     }
 338 }
 339
 340
 341
 342 void CollMove (Collection* C, unsigned OldIndex, unsigned NewIndex)
 343 /* Move an item from one position in the collection to another. OldIndex
 344 ** is the current position of the item, NewIndex is the new index before
 345 ** the function has done it's work. Existing entries with indices NewIndex
 346 ** and up might be moved one position upwards.
 347 */
 348 {
 349     /* Get the item; and, remove it from the collection */
 350     void* Item = CollAt (C, OldIndex);
 351
 352     CollDelete (C, OldIndex);
 353
 354     /* Correct NewIndex if needed */
 355     if (NewIndex > OldIndex) {
 356         /* Position has changed with removal */
 357         --NewIndex;
 358     }
 359
 360     /* Now, insert it at the new position */
 361     CollInsert (C, Item, NewIndex);
 362 }
 363
 364
 365
 366 void CollMoveMultiple (Collection* C, unsigned Start, unsigned Count, unsigned Target)
 367 /* Move a range of items from one position to another. Start is the index
 368 ** of the first item to move, Count is the number of items and Target is
 369 ** the index of the target item. The item with the index Start will later
 370 ** have the index Target. All items with indices Target and above are moved
 371 ** to higher indices.
 372 */
 373 {
 374     void** TmpItems;
 375     unsigned Bytes;
 376
 377     /* Check the range */
 378     PRECONDITION (Start < C->Count && Start + Count <= C->Count && Target <= C->Count);
 379
 380     /* Check for trivial parameters */
 381     if (Count == 0 || Start == Target) {
 382         return;
 383     }
 384
 385     /* Calculate the raw memory space used by the items to move */
 386     Bytes = Count * sizeof (void*);
 387
 388     /* Allocate temporary storage for the items */
 389     TmpItems = xmalloc (Bytes);
 390
 391     /* Copy the items we have to move to the temporary storage */
 392     memcpy (TmpItems, C->Items + Start, Bytes);
 393
 394     /* Check if the range has to be moved upwards or downwards. Move the
 395     ** existing items to their final location, so that the space needed
 396     ** for the items now in temporary storage is unoccupied.
 397     */
 398     if (Target < Start) {
 399
 400         /* Move downwards */
 401         unsigned BytesToMove = (Start - Target) * sizeof (void*);
 402         memmove (C->Items+Target+Count, C->Items+Target, BytesToMove);
 403
 404     } else if (Target < Start + Count) {
 405
 406         /* Target is inside range */
 407         FAIL ("Not supported");
 408
 409     } else {
 410
 411         /* Move upwards */
 412         unsigned ItemsToMove = (Target - Start - Count);
 413         unsigned BytesToMove = ItemsToMove * sizeof (void*);
 414         memmove (C->Items+Start, C->Items+Target-ItemsToMove, BytesToMove);
 415
 416         /* Adjust the target index */
 417         Target -= Count;
 418     }
 419
 420     /* Move the old items to their final location */
 421     memcpy (C->Items + Target, TmpItems, Bytes);
 422
 423     /* Delete the temporary item space */
 424     xfree (TmpItems);
 425 }
 426
 427
 428
 429 static void QuickSort (Collection* C, int Lo, int Hi,
 430                        int (*Compare) (void*, const void*, const void*),
 431                        void* Data)
 432 /* Internal recursive sort function. */
 433 {
 434     /* Get a pointer to the items */
 435     void** Items = C->Items;
 436
 437     /* Quicksort */
 438     while (Hi > Lo) {
 439         int I = Lo + 1;
 440         int J = Hi;
 441         while (I <= J) {
 442             while (I <= J && Compare (Data, Items[Lo], Items[I]) >= 0) {
 443                 ++I;
 444             }
 445             while (I <= J && Compare (Data, Items[Lo], Items[J]) < 0) {
 446                 --J;
 447             }
 448             if (I <= J) {
 449                 /* Swap I and J */
 450                 void* Tmp = Items[I];
 451                 Items[I]  = Items[J];
 452                 Items[J]  = Tmp;
 453                 ++I;
 454                 --J;
 455             }
 456         }
 457         if (J != Lo) {
 458             /* Swap J and Lo */
 459             void* Tmp = Items[J];
 460             Items[J]  = Items[Lo];
 461             Items[Lo] = Tmp;
 462         }
 463         if (J > (Hi + Lo) / 2) {
 464             QuickSort (C, J + 1, Hi, Compare, Data);
 465             Hi = J - 1;
 466         } else {
 467             QuickSort (C, Lo, J - 1, Compare, Data);
 468             Lo = J + 1;
 469         }
 470     }
 471 }
 472
 473
 474
 475 void CollTransfer (Collection* Dest, const Collection* Source)
 476 /* Transfer all items from Source to Dest. Anything already in Dest is left
 477 ** untouched. The items in Source are not changed and are therefore in both
 478 ** Collections on return.
 479 */
 480 {
 481     /* Be sure there's enough room in Dest */
 482     CollGrow (Dest, Dest->Count + Source->Count);
 483
 484     /* Copy the items */
 485     memcpy (Dest->Items + Dest->Count,
 486             Source->Items,
 487             Source->Count * sizeof (Source->Items[0]));
 488
 489     /* Bump the counter */
 490     Dest->Count += Source->Count;
 491 }
 492
 493
 494
 495 void CollSort (Collection* C,
 496                int (*Compare) (void*, const void*, const void*),
 497                void* Data)
 498 /* Sort the collection using the given compare function. The data pointer is
 499 ** passed as *first* element to the compare function, it's not used by the
 500 ** sort function itself. The other two pointer passed to the Compare function
 501 ** are pointers to objects.
 502 */
 503 {
 504     if (C->Count > 1) {
 505         QuickSort (C, 0, C->Count-1, Compare, Data);
 506     }
 507 }