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 int CollIndex (Collection* C, const void* Item)
 145 /* Return the index of the given item in the collection. Return -1 if the
 146  * item was not found in the collection.
 147  */
 148 {
 149     /* Linear search */
 150     unsigned I;
 151     for (I = 0; I < C->Count; ++I) {
 152         if (Item == C->Items[I]) {
 153             /* Found */
 154             return (int)I;
 155         }
 156     }
 157
 158     /* Not found */
 159     return -1;
 160 }
 161
 162
 163
 164 void CollDelete (Collection* C, unsigned Index)
 165 /* Remove the item with the given index from the collection. This will not
 166  * free the item itself, just the pointer. All items with higher indices
 167  * will get moved to a lower position.
 168  */
 169 {
 170     /* Check the index */
 171     PRECONDITION (Index < C->Count);
 172
 173     /* Remove the item pointer */
 174     --C->Count;
 175     memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
 176 }
 177
 178
 179
 180 void CollDeleteItem (Collection* C, const void* Item)
 181 /* Delete the item pointer from the collection. The item must be in the
 182  * collection, otherwise FAIL will be called.
 183  */
 184 {
 185     /* Get the index of the entry */
 186     int Index = CollIndex (C, Item);
 187     CHECK (Index >= 0);
 188
 189     /* Delete the item with this index */
 190     --C->Count;
 191     memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
 192 }
 193
 194
 195
 196 void CollMove (Collection* C, unsigned OldIndex, unsigned NewIndex)
 197 /* Move an item from one position in the collection to another. OldIndex
 198  * is the current position of the item, NewIndex is the new index after
 199  * the function has done it's work. Existing entries with indices NewIndex
 200  * and up are moved one position upwards.
 201  */
 202 {
 203     /* Get the item and remove it from the collection */
 204     void* Item = CollAt (C, OldIndex);
 205     CollDelete (C, OldIndex);
 206
 207     /* Correct NewIndex if needed */
 208     if (NewIndex >= OldIndex) {
 209         /* Position has changed with removal */
 210         --NewIndex;
 211     }
 212
 213     /* Now insert it at the new position */
 214     CollInsert (C, Item, NewIndex);
 215 }
 216
 217
 218
 219 void CollMoveMultiple (Collection* C, unsigned Start, unsigned Count, unsigned Target)
 220 /* Move a range of items from one position to another. Start is the index
 221  * of the first item to move, Count is the number of items and Target is
 222  * the index of the target item. The item with the index Start will later
 223  * have the index Target. All items with indices Target and above are moved
 224  * to higher indices.
 225  */
 226 {
 227     void** TmpItems;
 228     unsigned Bytes;
 229
 230     /* Check the range */
 231     PRECONDITION (Start < C->Count && Start + Count <= C->Count && Target <= C->Count);
 232
 233     /* Check for trivial parameters */
 234     if (Count == 0 || Start == Target) {
 235         return;
 236     }
 237
 238     /* Calculate the raw memory space used by the items to move */
 239     Bytes = Count * sizeof (void*);
 240
 241     /* Allocate temporary storage for the items */
 242     TmpItems = xmalloc (Bytes);
 243
 244     /* Copy the items we have to move to the temporary storage */
 245     memcpy (TmpItems, C->Items + Start, Bytes);
 246
 247     /* Check if the range has to be moved upwards or downwards. Move the
 248      * existing items to their final location, so that the space needed
 249      * for the items now in temporary storage is unoccupied.
 250      */
 251     if (Target < Start) {
 252
 253         /* Move downwards */
 254         unsigned BytesToMove = (Start - Target) * sizeof (void*);
 255         memmove (C->Items+Target+Count, C->Items+Target, BytesToMove);
 256
 257     } else if (Target < Start + Count) {
 258
 259         /* Target is inside range */
 260         FAIL ("Not supported");
 261
 262     } else {
 263
 264         /* Move upwards */
 265         unsigned ItemsToMove = (Target - Start - Count);
 266         unsigned BytesToMove = ItemsToMove * sizeof (void*);
 267         memmove (C->Items+Start, C->Items+Target-ItemsToMove, BytesToMove);
 268
 269         /* Adjust the target index */
 270         Target -= Count;
 271     }
 272
 273     /* Move the old items to their final location */
 274     memcpy (C->Items + Target, TmpItems, Bytes);
 275
 276     /* Delete the temporary item space */
 277     xfree (TmpItems);
 278 }
 279
 280
 281
 282 static void QuickSort (Collection* C, int Lo, int Hi,
 283                        int (*Compare) (void*, const void*, const void*),
 284                        void* Data)
 285 /* Internal recursive sort function. */
 286 {
 287     /* Get a pointer to the items */
 288     void** Items = C->Items;
 289
 290     /* Quicksort */
 291     while (Hi > Lo) {
 292         int I = Lo + 1;
 293         int J = Hi;
 294         while (I <= J) {
 295             while (I <= J && Compare (Data, Items[Lo], Items[I]) >= 0) {
 296                 ++I;
 297             }
 298             while (I <= J && Compare (Data, Items[Lo], Items[J]) < 0) {
 299                 --J;
 300             }
 301             if (I <= J) {
 302                 /* Swap I and J */
 303                 void* Tmp = Items[I];
 304                 Items[I]  = Items[J];
 305                 Items[J]  = Tmp;
 306                 ++I;
 307                 --J;
 308             }
 309         }
 310         if (J != Lo) {
 311             /* Swap J and Lo */
 312             void* Tmp = Items[J];
 313             Items[J]  = Items[Lo];
 314             Items[Lo] = Tmp;
 315         }
 316         if (J > (Hi + Lo) / 2) {
 317             QuickSort (C, J + 1, Hi, Compare, Data);
 318             Hi = J - 1;
 319         } else {
 320             QuickSort (C, Lo, J - 1, Compare, Data);
 321             Lo = J + 1;
 322         }
 323     }
 324 }
 325
 326
 327
 328 void CollSort (Collection* C,
 329                int (*Compare) (void*, const void*, const void*),
 330                void* Data)
 331 /* Sort the collection using the given compare function. The data pointer is
 332  * passed as *first* element to the compare function, it's not used by the
 333  * sort function itself. The other two pointer passed to the Compare function
 334  * are pointers to objects.
 335  */
 336 {
 337     if (C->Count > 1) {
 338         QuickSort (C, 0, C->Count-1, Compare, Data);
 339     }
 340 }
 341
 342
 343