git.sur5r.net Git - cc65/blob - src/common/coll.h

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                  coll.h                                   */
   4 /*                                                                           */
   5 /*                        Collection (dynamic array)                         */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 2000-2011, Ullrich von Bassewitz                                      */
  10 /*                Roemerstrasse 52                                           */
  11 /*                D-70794 Filderstadt                                        */
  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 #ifndef COLL_H
  37 #define COLL_H
  38
  39
  40
  41 /* common */
  42 #include "attrib.h"
  43 #include "check.h"
  44 #include "inline.h"
  45
  46
  47
  48 /*****************************************************************************/
  49 /*                                   Data                                    */
  50 /*****************************************************************************/
  51
  52
  53
  54 /* An array of pointers that grows if needed */
  55 typedef struct Collection Collection;
  56 struct Collection {
  57     unsigned            Count;          /* Number of items in the list */
  58     unsigned            Size;           /* Size of allocated array */
  59     void**              Items;          /* Array with dynamic size */
  60 };
  61
  62 /* An empty collection */
  63 extern const Collection EmptyCollection;
  64
  65 /* Initializer for static collections */
  66 #define STATIC_COLLECTION_INITIALIZER   { 0, 0, 0 }
  67
  68 /* Initializer for auto collections */
  69 #define AUTO_COLLECTION_INITIALIZER     EmptyCollection
  70
  71
  72
  73 /*****************************************************************************/
  74 /*                                   Code                                    */
  75 /*****************************************************************************/
  76
  77
  78
  79 Collection* InitCollection (Collection* C);
  80 /* Initialize a collection and return it. */
  81
  82 void DoneCollection (Collection* C);
  83 /* Free the data for a collection. This will not free the data contained in
  84  * the collection.
  85  */
  86
  87 Collection* NewCollection (void);
  88 /* Create and return a new collection */
  89
  90 void FreeCollection (Collection* C);
  91 /* Free a collection */
  92
  93 void CollGrow (Collection* C, unsigned Size);
  94 /* Grow the collection C so it is able to hold Size items without a resize
  95  * being necessary. This can be called for performance reasons if the number
  96  * of items to be placed in the collection is known in advance.
  97  */
  98
  99 #if defined(HAVE_INLINE)
 100 INLINE unsigned CollCount (const Collection* C)
 101 /* Return the number of items in the collection */
 102 {
 103     return C->Count;
 104 }
 105 #else
 106 #  define CollCount(C)  (C)->Count
 107 #endif
 108
 109 void CollInsert (Collection* C, void* Item, unsigned Index);
 110 /* Insert the data at the given position in the collection */
 111
 112 #if defined(HAVE_INLINE)
 113 INLINE void CollAppend (Collection* C, void* Item)
 114 /* Append an item to the end of the collection */
 115 {
 116     /* Insert the item at the end of the current list */
 117     CollInsert (C, Item, C->Count);
 118 }
 119 #else
 120 void CollAppend (Collection* C, void* Item);
 121 /* Append an item to the end of the collection */
 122 #endif
 123
 124 #if defined(HAVE_INLINE)
 125 INLINE void* CollAt (const Collection* C, unsigned Index)
 126 /* Return the item at the given index */
 127 {
 128     /* Check the index */
 129     PRECONDITION (Index < C->Count);
 130
 131     /* Return the element */
 132     return C->Items[Index];
 133 }
 134 #else
 135 void* CollAt (const Collection* C, unsigned Index);
 136 /* Return the item at the given index */
 137 #endif
 138
 139 #if defined(HAVE_INLINE)
 140 INLINE void* CollAtUnchecked (const Collection* C, unsigned Index)
 141 /* Return the item at the given index */
 142 {
 143     /* Return the element */
 144     return C->Items[Index];
 145 }
 146 #else
 147 #  define CollAtUnchecked(C, Index)     ((C)->Items[(Index)])
 148 #endif
 149
 150 #if defined(HAVE_INLINE)
 151 INLINE const void* CollConstAt (const Collection* C, unsigned Index)
 152 /* Return the item at the given index */
 153 {
 154     /* Check the index */
 155     PRECONDITION (Index < C->Count);
 156
 157     /* Return the element */
 158     return C->Items[Index];
 159 }
 160 #else
 161 const void* CollConstAt (const Collection* C, unsigned Index);
 162 /* Return the item at the given index */
 163 #endif
 164
 165 #if defined(HAVE_INLINE)
 166 INLINE void* CollLast (Collection* C)
 167 /* Return the last item in a collection */
 168 {
 169     /* We must have at least one entry */
 170     PRECONDITION (C->Count > 0);
 171
 172     /* Return the element */
 173     return C->Items[C->Count-1];
 174 }
 175 #else
 176 void* CollLast (Collection* C);
 177 /* Return the last item in a collection */
 178 #endif
 179
 180 #if defined(HAVE_INLINE)
 181 INLINE const void* CollConstLast (const Collection* C)
 182 /* Return the last item in a collection */
 183 {
 184     /* We must have at least one entry */
 185     PRECONDITION (C->Count > 0);
 186
 187     /* Return the element */
 188     return C->Items[C->Count-1];
 189 }
 190 #else
 191 const void* CollConstLast (const Collection* C);
 192 /* Return the last item in a collection */
 193 #endif
 194
 195 #if defined(HAVE_INLINE)
 196 INLINE void* CollPop (Collection* C)
 197 /* Remove the last segment from the stack and return it. Calls FAIL if the
 198  * collection is empty.
 199  */
 200 {
 201     /* We must have at least one entry */
 202     PRECONDITION (C->Count > 0);
 203
 204     /* Return the element */
 205     return C->Items[--C->Count];
 206 }
 207 #else
 208 void* CollPop (Collection* C);
 209 /* Remove the last segment from the stack and return it. Calls FAIL if the
 210  * collection is empty.
 211  */
 212 #endif
 213
 214 int CollIndex (Collection* C, const void* Item);
 215 /* Return the index of the given item in the collection. Return -1 if the
 216  * item was not found in the collection.
 217  */
 218
 219 void CollDelete (Collection* C, unsigned Index);
 220 /* Remove the item with the given index from the collection. This will not
 221  * free the item itself, just the pointer. All items with higher indices
 222  * will get moved to a lower position.
 223  */
 224
 225 void CollDeleteItem (Collection* C, const void* Item);
 226 /* Delete the item pointer from the collection. The item must be in the
 227  * collection, otherwise FAIL will be called.
 228  */
 229
 230 #if defined(HAVE_INLINE)
 231 INLINE void CollDeleteAll (Collection* C)
 232 /* Delete all items from the given collection. This will not free the items
 233  * itself, it will only remove the pointers.
 234  */
 235 {
 236     /* This one is easy... */
 237     C->Count = 0;
 238 }
 239 #else
 240 #  define CollDeleteAll(C)      ((C)->Count = 0)
 241 #endif
 242
 243 #if defined(HAVE_INLINE)
 244 INLINE void CollReplace (Collection* C, void* Item, unsigned Index)
 245 /* Replace the item at the given position. The old item will not be freed,
 246  * just the pointer will get replaced.
 247  */
 248 {
 249     /* Check the index */
 250     PRECONDITION (Index < C->Count);
 251
 252     /* Replace the item pointer */
 253     C->Items[Index] = Item;
 254 }
 255 #else
 256 void CollReplace (Collection* C, void* Item, unsigned Index);
 257 /* Replace the item at the given position. The old item will not be freed,
 258  * just the pointer will get replaced.
 259  */
 260 #endif
 261
 262 void CollReplaceExpand (Collection* C, void* Item, unsigned Index);
 263 /* If Index is a valid index for the collection, replace the item at this
 264  * position by the one passed. If the collection is too small, expand it,
 265  * filling unused pointers with NULL, then add the new item at the given
 266  * position.
 267  */
 268
 269 void CollMove (Collection* C, unsigned OldIndex, unsigned NewIndex);
 270 /* Move an item from one position in the collection to another. OldIndex
 271  * is the current position of the item, NewIndex is the new index after
 272  * the function has done it's work. Existing entries with indices NewIndex
 273  * and up are moved one position upwards.
 274  */
 275
 276 void CollMoveMultiple (Collection* C, unsigned Start, unsigned Count, unsigned Target);
 277 /* Move a range of items from one position to another. Start is the index
 278  * of the first item to move, Count is the number of items and Target is
 279  * the index of the target item. The item with the index Start will later
 280  * have the index Target. All items with indices Target and above are moved
 281  * to higher indices.
 282  */
 283
 284 void CollTransfer (Collection* Dest, const Collection* Source);
 285 /* Transfer all items from Source to Dest. Anything already in Dest is left
 286  * untouched. The items in Source are not changed and are therefore in both
 287  * Collections on return.
 288  */
 289
 290 void CollSort (Collection* C,
 291                int (*Compare) (void*, const void*, const void*),
 292                void* Data);
 293 /* Sort the collection using the given compare function. The data pointer is
 294  * passed as *first* element to the compare function, it's not used by the
 295  * sort function itself. The other two pointer passed to the Compare function
 296  * are pointers to objects.
 297  */
 298
 299
 300
 301 /* End of coll.h */
 302
 303 #endif
 304
 305
 306
 307