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      Ullrich von Bassewitz                                       */
  10 /*               Wacholderweg 14                                             */
  11 /*               D-70597 Stuttgart                                           */
  12 /* EMail:        uz@musoftware.de                                            */
  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  = 8;
  60     C->Items = xmalloc (8 * sizeof (void*));
  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 CollDelete (Collection* C, unsigned Index)
 199 /* Remove the item with the given index from the collection. This will not
 200  * free the item itself, just the pointer. All items with higher indices
 201  * will get moved to a lower position.
 202  */
 203 {
 204     /* Check the index */
 205     PRECONDITION (Index < C->Count);
 206
 207     /* Remove the item pointer */
 208     --C->Count;
 209     memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
 210 }
 211
 212
 213
 214 void CollReplace (Collection* C, void* Item, unsigned Index)
 215 /* Replace the item at the given position. The old item will not be freed,
 216  * just the pointer will et replaced.
 217  */
 218 {
 219     /* Check the index */
 220     PRECONDITION (Index < C->Count);
 221
 222     /* Replace the item pointer */
 223     C->Items[Index] = Item;
 224 }
 225
 226
 227
 228 static void QuickSort (Collection* C, int Lo, int Hi,
 229                        int (*Compare) (void*, const void*, const void*),
 230                        void* Data)
 231 /* Internal recursive sort function. */
 232 {
 233     /* Get a pointer to the items */
 234     void** Items = C->Items;
 235
 236     /* Quicksort */
 237     while (Hi > Lo) {
 238         int I = Lo + 1;
 239         int J = Hi;
 240         while (I <= J) {
 241             while (I <= J && Compare (Data, Items[Lo], Items[I]) >= 0) {
 242                 ++I;
 243             }
 244             while (I <= J && Compare (Data, Items[Lo], Items[J]) < 0) {
 245                 --J;
 246             }
 247             if (I <= J) {
 248                 /* Swap I and J */
 249                 void* Tmp = Items[I];
 250                 Items[I]  = Items[J];
 251                 Items[J]  = Tmp;
 252                 ++I;
 253                 --J;
 254             }
 255         }
 256         if (J != Lo) {
 257             /* Swap J and Lo */
 258             void* Tmp = Items[J];
 259             Items[J]  = Items[Lo];
 260             Items[Lo] = Tmp;
 261         }
 262         if (J > (Hi + Lo) / 2) {
 263             QuickSort (C, J + 1, Hi, Compare, Data);
 264             Hi = J - 1;
 265         } else {
 266             QuickSort (C, Lo, J - 1, Compare, Data);
 267             Lo = J + 1;
 268         }
 269     }
 270 }
 271
 272
 273
 274 void CollSort (Collection* C,
 275                int (*Compare) (void*, const void*, const void*),
 276                void* Data)
 277 /* Sort the collection using the given compare function. The data pointer is
 278  * passed as *first* element to the compare function, it's not used by the
 279  * sort function itself. The other two pointer passed to the Compare function
 280  * are pointers to objects.
 281  */
 282 {
 283     if (C->Count > 1) {
 284         QuickSort (C, 0, C->Count-1, Compare, Data);
 285     }
 286 }
 287
 288
 289