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 void CollSort (Collection* C, int (*Compare) (const void*, const void*))
 229 /* Sort the collection using the given compare function.
 230  * BEWARE: The function uses qsort internally, so the Compare function does
 231  * actually get pointers to the object pointers, not just object pointers!
 232  */
 233 {
 234     /* Use qsort */
 235     qsort (C->Items, C->Count, sizeof (void*), Compare);
 236 }
 237
 238
 239