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 void CollInsert (Collection* C, void* Item, unsigned Index)
 101 /* Insert the data at the given position in the collection */
 102 {
 103     /* Check for invalid indices */
 104     PRECONDITION (Index <= C->Count);
 105
 106     /* Grow the array if necessary */
 107     if (C->Count >= C->Size) {
 108         /* Must grow */
 109         void** NewItems;
 110         if (C->Size > 0) {
 111             C->Size *= 2;
 112         } else {
 113             C->Size = 8;
 114         }
 115         NewItems = xmalloc (C->Size * sizeof (void*));
 116         memcpy (NewItems, C->Items, C->Count * sizeof (void*));
 117         xfree (C->Items);
 118         C->Items = NewItems;
 119     }
 120
 121     /* Move the existing elements if needed */
 122     if (C->Count != Index) {
 123         memmove (C->Items+Index+1, C->Items+Index, (C->Count-Index) * sizeof (void*));
 124     }
 125     ++C->Count;
 126
 127     /* Store the new item */
 128     C->Items[Index] = Item;
 129 }
 130
 131
 132
 133 int CollIndex (Collection* C, const void* Item)
 134 /* Return the index of the given item in the collection. Return -1 if the
 135  * item was not found in the collection.
 136  */
 137 {
 138     /* Linear search */
 139     unsigned I;
 140     for (I = 0; I < C->Count; ++I) {
 141         if (Item == C->Items[I]) {
 142             /* Found */
 143             return (int)I;
 144         }
 145     }
 146
 147     /* Not found */
 148     return -1;
 149 }
 150
 151
 152
 153 void CollDelete (Collection* C, unsigned Index)
 154 /* Remove the item with the given index from the collection. This will not
 155  * free the item itself, just the pointer. All items with higher indices
 156  * will get moved to a lower position.
 157  */
 158 {
 159     /* Check the index */
 160     PRECONDITION (Index < C->Count);
 161
 162     /* Remove the item pointer */
 163     --C->Count;
 164     memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
 165 }
 166
 167
 168
 169 void CollDeleteItem (Collection* C, const void* Item)
 170 /* Delete the item pointer from the collection. The item must be in the
 171  * collection, otherwise FAIL will be called.
 172  */
 173 {
 174     /* Get the index of the entry */
 175     int Index = CollIndex (C, Item);
 176     CHECK (Index >= 0);
 177
 178     /* Delete the item with this index */
 179     --C->Count;
 180     memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
 181 }
 182
 183
 184
 185 void CollMove (Collection* C, unsigned OldIndex, unsigned NewIndex)
 186 /* Move an item from one position in the collection to another. OldIndex
 187  * is the current position of the item, NewIndex is the new index after
 188  * the function has done it's work. Existing entries with indices NewIndex
 189  * and up are moved one position upwards.
 190  */
 191 {
 192     /* Get the item and remove it from the collection */
 193     void* Item = CollAt (C, OldIndex);
 194     CollDelete (C, OldIndex);
 195
 196     /* Correct NewIndex if needed */
 197     if (NewIndex >= OldIndex) {
 198         /* Position has changed with removal */
 199         --NewIndex;
 200     }
 201
 202     /* Now insert it at the new position */
 203     CollInsert (C, Item, NewIndex);
 204 }
 205
 206
 207
 208 static void QuickSort (Collection* C, int Lo, int Hi,
 209                        int (*Compare) (void*, const void*, const void*),
 210                        void* Data)
 211 /* Internal recursive sort function. */
 212 {
 213     /* Get a pointer to the items */
 214     void** Items = C->Items;
 215
 216     /* Quicksort */
 217     while (Hi > Lo) {
 218         int I = Lo + 1;
 219         int J = Hi;
 220         while (I <= J) {
 221             while (I <= J && Compare (Data, Items[Lo], Items[I]) >= 0) {
 222                 ++I;
 223             }
 224             while (I <= J && Compare (Data, Items[Lo], Items[J]) < 0) {
 225                 --J;
 226             }
 227             if (I <= J) {
 228                 /* Swap I and J */
 229                 void* Tmp = Items[I];
 230                 Items[I]  = Items[J];
 231                 Items[J]  = Tmp;
 232                 ++I;
 233                 --J;
 234             }
 235         }
 236         if (J != Lo) {
 237             /* Swap J and Lo */
 238             void* Tmp = Items[J];
 239             Items[J]  = Items[Lo];
 240             Items[Lo] = Tmp;
 241         }
 242         if (J > (Hi + Lo) / 2) {
 243             QuickSort (C, J + 1, Hi, Compare, Data);
 244             Hi = J - 1;
 245         } else {
 246             QuickSort (C, Lo, J - 1, Compare, Data);
 247             Lo = J + 1;
 248         }
 249     }
 250 }
 251
 252
 253
 254 void CollSort (Collection* C,
 255                int (*Compare) (void*, const void*, const void*),
 256                void* Data)
 257 /* Sort the collection using the given compare function. The data pointer is
 258  * passed as *first* element to the compare function, it's not used by the
 259  * sort function itself. The other two pointer passed to the Compare function
 260  * are pointers to objects.
 261  */
 262 {
 263     if (C->Count > 1) {
 264         QuickSort (C, 0, C->Count-1, Compare, Data);
 265     }
 266 }
 267
 268
 269