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 /*                                   Code                                    */
  50 /*****************************************************************************/
  51
  52
  53
  54 Collection* InitCollection (Collection* C)
  55 /* Initialize a collection and return it. */
  56 {
  57     /* Intialize the fields. */
  58     C->Count = 0;
  59     C->Size  = 0;
  60     C->Items = 0;
  61
  62     /* Return the new struct */
  63     return C;
  64 }
  65
  66
  67
  68 void DoneCollection (Collection* C)
  69 /* Free the data for a collection. This will not free the data contained in
  70  * the collection.
  71  */
  72 {
  73     /* Free the pointer array */
  74     xfree (C->Items);
  75 }
  76
  77
  78
  79 Collection* NewCollection (void)
  80 /* Create and return a new collection with the given initial size */
  81 {
  82     /* Allocate memory, intialize the collection and return it */
  83     return InitCollection (xmalloc (sizeof (Collection)));
  84 }
  85
  86
  87
  88 void FreeCollection (Collection* C)
  89 /* Free a collection */
  90 {
  91     /* Free the data */
  92     DoneCollection (C);
  93
  94     /* Free the structure itself */
  95     xfree (C);
  96 }
  97
  98
  99
 100 unsigned CollCount (const Collection* C)
 101 /* Return the number of items in the collection */
 102 {
 103     return C->Count;
 104 }
 105
 106
 107
 108 void CollInsert (Collection* C, void* Item, unsigned Index)
 109 /* Insert the data at the given position in the collection */
 110 {
 111     /* Check for invalid indices */
 112     PRECONDITION (Index <= C->Count);
 113
 114     /* Grow the array if necessary */
 115     if (C->Count >= C->Size) {
 116         /* Must grow */
 117         void** NewItems;
 118         if (C->Size > 0) {
 119             C->Size *= 2;
 120         } else {
 121             C->Size = 8;
 122         }
 123         NewItems = xmalloc (C->Size * sizeof (void*));
 124         memcpy (NewItems, C->Items, C->Count * sizeof (void*));
 125         xfree (C->Items);
 126         C->Items = NewItems;
 127     }
 128
 129     /* Move the existing elements if needed */
 130     if (C->Count != Index) {
 131         memmove (C->Items+Index+1, C->Items+Index, (C->Count-Index) * sizeof (void*));
 132     }
 133     ++C->Count;
 134
 135     /* Store the new item */
 136     C->Items[Index] = Item;
 137 }
 138
 139
 140
 141 void CollAppend (Collection* C, void* Item)
 142 /* Append an item to the end of the collection */
 143 {
 144     /* Insert the item at the end of the current list */
 145     CollInsert (C, Item, C->Count);
 146 }
 147
 148
 149
 150 void* CollAt (Collection* C, unsigned Index)
 151 /* Return the item at the given index */
 152 {
 153     /* Check the index */
 154     PRECONDITION (Index < C->Count);
 155
 156     /* Return the element */
 157     return C->Items[Index];
 158 }
 159
 160
 161
 162 const void* CollConstAt (const Collection* C, unsigned Index)
 163 /* Return the item at the given index */
 164 {
 165     /* Check the index */
 166     PRECONDITION (Index < C->Count);
 167
 168     /* Return the element */
 169     return C->Items[Index];
 170 }
 171
 172
 173
 174 void* CollLast (Collection* C)
 175 /* Return the last item in a collection */
 176 {
 177     /* We must have at least one entry */
 178     PRECONDITION (C->Count > 0);
 179
 180     /* Return the element */
 181     return C->Items[C->Count-1];
 182 }
 183
 184
 185
 186 const void* CollConstLast (const Collection* C)
 187 /* Return the last item in a collection */
 188 {
 189     /* We must have at least one entry */
 190     PRECONDITION (C->Count > 0);
 191
 192     /* Return the element */
 193     return C->Items[C->Count-1];
 194 }
 195
 196
 197
 198 void* CollPop (Collection* C)
 199 /* Remove the last segment from the stack and return it. Calls FAIL if the
 200  * collection is empty.
 201  */
 202 {
 203     /* We must have at least one entry */
 204     PRECONDITION (C->Count > 0);
 205
 206     /* Return the element */
 207     return C->Items[--C->Count];
 208 }
 209
 210
 211
 212 int CollIndex (Collection* C, const void* Item)
 213 /* Return the index of the given item in the collection. Return -1 if the
 214  * item was not found in the collection.
 215  */
 216 {
 217     /* Linear search */
 218     unsigned I;
 219     for (I = 0; I < C->Count; ++I) {
 220         if (Item == C->Items[I]) {
 221             /* Found */
 222             return (int)I;
 223         }
 224     }
 225
 226     /* Not found */
 227     return -1;
 228 }
 229
 230
 231
 232 void CollDelete (Collection* C, unsigned Index)
 233 /* Remove the item with the given index from the collection. This will not
 234  * free the item itself, just the pointer. All items with higher indices
 235  * will get moved to a lower position.
 236  */
 237 {
 238     /* Check the index */
 239     PRECONDITION (Index < C->Count);
 240
 241     /* Remove the item pointer */
 242     --C->Count;
 243     memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
 244 }
 245
 246
 247
 248 void CollDeleteItem (Collection* C, const void* Item)
 249 /* Delete the item pointer from the collection. The item must be in the
 250  * collection, otherwise FAIL will be called.
 251  */
 252 {
 253     /* Get the index of the entry */
 254     int Index = CollIndex (C, Item);
 255     CHECK (Index >= 0);
 256
 257     /* Delete the item with this index */
 258     --C->Count;
 259     memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
 260 }
 261
 262
 263
 264 void CollDeleteAll (Collection* C)
 265 /* Delete all items from the given collection. This will not free the items
 266  * itself, it will only remove the pointers.
 267  */
 268 {
 269     /* This one is easy... */
 270     C->Count = 0;
 271 }
 272
 273
 274
 275 void CollReplace (Collection* C, void* Item, unsigned Index)
 276 /* Replace the item at the given position. The old item will not be freed,
 277  * just the pointer will et replaced.
 278  */
 279 {
 280     /* Check the index */
 281     PRECONDITION (Index < C->Count);
 282
 283     /* Replace the item pointer */
 284     C->Items[Index] = Item;
 285 }
 286
 287
 288
 289 static void QuickSort (Collection* C, int Lo, int Hi,
 290                        int (*Compare) (void*, const void*, const void*),
 291                        void* Data)
 292 /* Internal recursive sort function. */
 293 {
 294     /* Get a pointer to the items */
 295     void** Items = C->Items;
 296
 297     /* Quicksort */
 298     while (Hi > Lo) {
 299         int I = Lo + 1;
 300         int J = Hi;
 301         while (I <= J) {
 302             while (I <= J && Compare (Data, Items[Lo], Items[I]) >= 0) {
 303                 ++I;
 304             }
 305             while (I <= J && Compare (Data, Items[Lo], Items[J]) < 0) {
 306                 --J;
 307             }
 308             if (I <= J) {
 309                 /* Swap I and J */
 310                 void* Tmp = Items[I];
 311                 Items[I]  = Items[J];
 312                 Items[J]  = Tmp;
 313                 ++I;
 314                 --J;
 315             }
 316         }
 317         if (J != Lo) {
 318             /* Swap J and Lo */
 319             void* Tmp = Items[J];
 320             Items[J]  = Items[Lo];
 321             Items[Lo] = Tmp;
 322         }
 323         if (J > (Hi + Lo) / 2) {
 324             QuickSort (C, J + 1, Hi, Compare, Data);
 325             Hi = J - 1;
 326         } else {
 327             QuickSort (C, Lo, J - 1, Compare, Data);
 328             Lo = J + 1;
 329         }
 330     }
 331 }
 332
 333
 334
 335 void CollSort (Collection* C,
 336                int (*Compare) (void*, const void*, const void*),
 337                void* Data)
 338 /* Sort the collection using the given compare function. The data pointer is
 339  * passed as *first* element to the compare function, it's not used by the
 340  * sort function itself. The other two pointer passed to the Compare function
 341  * are pointers to objects.
 342  */
 343 {
 344     if (C->Count > 1) {
 345         QuickSort (C, 0, C->Count-1, Compare, Data);
 346     }
 347 }
 348
 349
 350