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-2001 Ullrich von Bassewitz                                       */
  10 /*               Wacholderweg 14                                             */
  11 /*               D-70597 Stuttgart                                           */
  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 CollInsert (Collection* C, void* Item, unsigned Index)
 112 /* Insert the data at the given position in the collection */
 113 {
 114     /* Check for invalid indices */
 115     PRECONDITION (Index <= C->Count);
 116
 117     /* Grow the array if necessary */
 118     if (C->Count >= C->Size) {
 119         /* Must grow */
 120         void** NewItems;
 121         if (C->Size > 0) {
 122             C->Size *= 2;
 123         } else {
 124             C->Size = 8;
 125         }
 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     /* Move the existing elements if needed */
 133     if (C->Count != Index) {
 134         memmove (C->Items+Index+1, C->Items+Index, (C->Count-Index) * sizeof (void*));
 135     }
 136     ++C->Count;
 137
 138     /* Store the new item */
 139     C->Items[Index] = Item;
 140 }
 141
 142
 143
 144 #if !defined(HAVE_INLINE)
 145 void CollAppend (Collection* C, void* Item)
 146 /* Append an item to the end of the collection */
 147 {
 148     /* Insert the item at the end of the current list */
 149     CollInsert (C, Item, C->Count);
 150 }
 151 #endif
 152
 153
 154
 155 #if !defined(HAVE_INLINE)
 156 void* CollAt (Collection* C, unsigned Index)
 157 /* Return the item at the given index */
 158 {
 159     /* Check the index */
 160     PRECONDITION (Index < C->Count);
 161
 162     /* Return the element */
 163     return C->Items[Index];
 164 }
 165 #endif
 166
 167
 168
 169 #if !defined(HAVE_INLINE)
 170 const void* CollConstAt (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 void* CollLast (Collection* C)
 185 /* Return the last item in a collection */
 186 {
 187     /* We must have at least one entry */
 188     PRECONDITION (C->Count > 0);
 189
 190     /* Return the element */
 191     return C->Items[C->Count-1];
 192 }
 193 #endif
 194
 195
 196
 197 #if !defined(HAVE_INLINE)
 198 const void* CollConstLast (const 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 void* CollPop (Collection* C)
 213 /* Remove the last segment from the stack and return it. Calls FAIL if the
 214  * collection is empty.
 215  */
 216 {
 217     /* We must have at least one entry */
 218     PRECONDITION (C->Count > 0);
 219
 220     /* Return the element */
 221     return C->Items[--C->Count];
 222 }
 223 #endif
 224
 225
 226
 227 int CollIndex (Collection* C, const void* Item)
 228 /* Return the index of the given item in the collection. Return -1 if the
 229  * item was not found in the collection.
 230  */
 231 {
 232     /* Linear search */
 233     unsigned I;
 234     for (I = 0; I < C->Count; ++I) {
 235         if (Item == C->Items[I]) {
 236             /* Found */
 237             return (int)I;
 238         }
 239     }
 240
 241     /* Not found */
 242     return -1;
 243 }
 244
 245
 246
 247 void CollDelete (Collection* C, unsigned Index)
 248 /* Remove the item with the given index from the collection. This will not
 249  * free the item itself, just the pointer. All items with higher indices
 250  * will get moved to a lower position.
 251  */
 252 {
 253     /* Check the index */
 254     PRECONDITION (Index < C->Count);
 255
 256     /* Remove the item pointer */
 257     --C->Count;
 258     memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
 259 }
 260
 261
 262
 263 void CollDeleteItem (Collection* C, const void* Item)
 264 /* Delete the item pointer from the collection. The item must be in the
 265  * collection, otherwise FAIL will be called.
 266  */
 267 {
 268     /* Get the index of the entry */
 269     int Index = CollIndex (C, Item);
 270     CHECK (Index >= 0);
 271
 272     /* Delete the item with this index */
 273     --C->Count;
 274     memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
 275 }
 276
 277
 278
 279 #if !defined(HAVE_INLINE)
 280 void CollReplace (Collection* C, void* Item, unsigned Index)
 281 /* Replace the item at the given position. The old item will not be freed,
 282  * just the pointer will get replaced.
 283  */
 284 {
 285     /* Check the index */
 286     PRECONDITION (Index < C->Count);
 287
 288     /* Replace the item pointer */
 289     C->Items[Index] = Item;
 290 }
 291 #endif
 292
 293
 294
 295 void CollMove (Collection* C, unsigned OldIndex, unsigned NewIndex)
 296 /* Move an item from one position in the collection to another. OldIndex
 297  * is the current position of the item, NewIndex is the new index after
 298  * the function has done it's work. Existing entries with indices NewIndex
 299  * and up are moved one position upwards.
 300  */
 301 {
 302     /* Get the item and remove it from the collection */
 303     void* Item = CollAt (C, OldIndex);
 304     CollDelete (C, OldIndex);
 305
 306     /* Correct NewIndex if needed */
 307     if (NewIndex >= OldIndex) {
 308         /* Position has changed with removal */
 309         --NewIndex;
 310     }
 311
 312     /* Now insert it at the new position */
 313     CollInsert (C, Item, NewIndex);
 314 }
 315
 316
 317
 318 void CollMoveMultiple (Collection* C, unsigned Start, unsigned Count, unsigned Target)
 319 /* Move a range of items from one position to another. Start is the index
 320  * of the first item to move, Count is the number of items and Target is
 321  * the index of the target item. The item with the index Start will later
 322  * have the index Target. All items with indices Target and above are moved
 323  * to higher indices.
 324  */
 325 {
 326     void** TmpItems;
 327     unsigned Bytes;
 328
 329     /* Check the range */
 330     PRECONDITION (Start < C->Count && Start + Count <= C->Count && Target <= C->Count);
 331
 332     /* Check for trivial parameters */
 333     if (Count == 0 || Start == Target) {
 334         return;
 335     }
 336
 337     /* Calculate the raw memory space used by the items to move */
 338     Bytes = Count * sizeof (void*);
 339
 340     /* Allocate temporary storage for the items */
 341     TmpItems = xmalloc (Bytes);
 342
 343     /* Copy the items we have to move to the temporary storage */
 344     memcpy (TmpItems, C->Items + Start, Bytes);
 345
 346     /* Check if the range has to be moved upwards or downwards. Move the
 347      * existing items to their final location, so that the space needed
 348      * for the items now in temporary storage is unoccupied.
 349      */
 350     if (Target < Start) {
 351
 352         /* Move downwards */
 353         unsigned BytesToMove = (Start - Target) * sizeof (void*);
 354         memmove (C->Items+Target+Count, C->Items+Target, BytesToMove);
 355
 356     } else if (Target < Start + Count) {
 357
 358         /* Target is inside range */
 359         FAIL ("Not supported");
 360
 361     } else {
 362
 363         /* Move upwards */
 364         unsigned ItemsToMove = (Target - Start - Count);
 365         unsigned BytesToMove = ItemsToMove * sizeof (void*);
 366         memmove (C->Items+Start, C->Items+Target-ItemsToMove, BytesToMove);
 367
 368         /* Adjust the target index */
 369         Target -= Count;
 370     }
 371
 372     /* Move the old items to their final location */
 373     memcpy (C->Items + Target, TmpItems, Bytes);
 374
 375     /* Delete the temporary item space */
 376     xfree (TmpItems);
 377 }
 378
 379
 380
 381 static void QuickSort (Collection* C, int Lo, int Hi,
 382                        int (*Compare) (void*, const void*, const void*),
 383                        void* Data)
 384 /* Internal recursive sort function. */
 385 {
 386     /* Get a pointer to the items */
 387     void** Items = C->Items;
 388
 389     /* Quicksort */
 390     while (Hi > Lo) {
 391         int I = Lo + 1;
 392         int J = Hi;
 393         while (I <= J) {
 394             while (I <= J && Compare (Data, Items[Lo], Items[I]) >= 0) {
 395                 ++I;
 396             }
 397             while (I <= J && Compare (Data, Items[Lo], Items[J]) < 0) {
 398                 --J;
 399             }
 400             if (I <= J) {
 401                 /* Swap I and J */
 402                 void* Tmp = Items[I];
 403                 Items[I]  = Items[J];
 404                 Items[J]  = Tmp;
 405                 ++I;
 406                 --J;
 407             }
 408         }
 409         if (J != Lo) {
 410             /* Swap J and Lo */
 411             void* Tmp = Items[J];
 412             Items[J]  = Items[Lo];
 413             Items[Lo] = Tmp;
 414         }
 415         if (J > (Hi + Lo) / 2) {
 416             QuickSort (C, J + 1, Hi, Compare, Data);
 417             Hi = J - 1;
 418         } else {
 419             QuickSort (C, Lo, J - 1, Compare, Data);
 420             Lo = J + 1;
 421         }
 422     }
 423 }
 424
 425
 426
 427 void CollSort (Collection* C,
 428                int (*Compare) (void*, const void*, const void*),
 429                void* Data)
 430 /* Sort the collection using the given compare function. The data pointer is
 431  * passed as *first* element to the compare function, it's not used by the
 432  * sort function itself. The other two pointer passed to the Compare function
 433  * are pointers to objects.
 434  */
 435 {
 436     if (C->Count > 1) {
 437         QuickSort (C, 0, C->Count-1, Compare, Data);
 438     }
 439 }
 440
 441
 442