src/libopensrf/osrf_list.c

   1 /**
   2         @file osrf_list.c
   3         @brief Implementation of osrfList, sort of like a vector class.
   4 */
   5
   6 #include <opensrf/osrf_list.h>
   7 /** @brief The initial size of the array when none is specified */
   8 #define OSRF_LIST_DEFAULT_SIZE 48 /* most opensrf lists are small... */
   9 /** @brief How many slots to add at a time when the array grows */
  10 #define OSRF_LIST_INC_SIZE 256
  11 //#define OSRF_LIST_MAX_SIZE 10240
  12
  13 /**
  14         @brief  Create a new osrfList with OSRF_LIST_DEFAULT_SIZE slots.
  15         @return A pointer to the new osrfList.
  16
  17         The calling code is responsible for freeing the osrfList by calling osrfListFree().
  18 */
  19 osrfList* osrfNewList() {
  20         return osrfNewListSize( OSRF_LIST_DEFAULT_SIZE );
  21 }
  22
  23 /**
  24         @brief Create a new osrfList with a specified number of slots.
  25         @param size How many pointers to store initially.
  26         @return A pointer to the new osrfList.
  27
  28         The calling code is responsible for freeing the osrfList by calling osrfListFree().
  29 */
  30 osrfList* osrfNewListSize( unsigned int size ) {
  31         osrfList* list;
  32         OSRF_MALLOC(list, sizeof(osrfList));
  33         list->size = 0;
  34         list->freeItem = NULL;
  35         if( size <= 0 ) size = 16;
  36         list->arrsize = size;
  37         OSRF_MALLOC( list->arrlist, list->arrsize * sizeof(void*) );
  38
  39         // Nullify all pointers in the array
  40
  41         int i;
  42         for( i = 0; i < list->arrsize; ++i )
  43                 list->arrlist[ i ] = NULL;
  44
  45         return list;
  46 }
  47
  48
  49 /**
  50         @brief Add a pointer to the end of the array.
  51         @param list A pointer to the osrfList
  52         @param item A pointer to be added to the list.
  53         @return Zero if successful, or -1 if the list parameter is NULL.
  54
  55         The item pointer is stored one position past the last slot that might be in use.  The calling
  56         code should, in general, make no assumptions about where that position is.  See the discussion
  57         of osrfListGetCount() for the dirty details.
  58 */
  59 int osrfListPush( osrfList* list, void* item ) {
  60         if(!(list)) return -1;
  61         osrfListSet( list, item, list->size );
  62         return 0;
  63 }
  64
  65 /**
  66         @brief Store a pointer in the first unoccupied slot.
  67         @param list A pointer to the osrfList.
  68         @param item The pointer to be stored.
  69         @return If successful, the number of slots currently in use, or -1 if either of the
  70                 parameters is NULL.
  71
  72         Find the lowest-numbered position holding a NULL and overwrite it with the specified
  73         item pointer.
  74
  75         The meaning of the return value (other than -1) is fuzzy and probably not useful,
  76         because some of the slots counted as "in use" may in fact hold NULLs.
  77 */
  78 int osrfListPushFirst( osrfList* list, void* item ) {
  79         if(!(list && item)) return -1;
  80         unsigned int i;
  81         for( i = 0; i < list->size; i++ )
  82                 if(!list->arrlist[i]) break;
  83         osrfListSet( list, item, i );
  84         return list->size;
  85 }
  86
  87 /**
  88         @brief Store a pointer at a specified position in an osrfList.
  89         @param list A pointer to the osrfList.
  90         @param item The pointer to be stored.
  91         @param position Where to store it (a zero-based subscript).
  92         @return A pointer to the previous occupant of the specified slot, if any, or NULL if
  93                 it was unoccupied, or if we have freed the occupant.
  94
  95         If the pointer previously stored in the specified slot is not NULL, then the behavior
  96         depends on whether the calling code has provided a callback function for freeing stored
  97         items.  If there is such a callback function, we call it for the previously stored
  98         pointer, and return NULL.  Otherwise we return the previously stored pointer, so that
  99         the calling code can free it if it needs to.
 100
 101         If the specified position is beyond the physical bounds of the array, we replace the
 102         existing array with one that's big enough.  This replacement is transparent to the
 103         calling code.
 104 */
 105 void* osrfListSet( osrfList* list, void* item, unsigned int position ) {
 106         if(!list) return NULL;
 107
 108         int newsize = list->arrsize;
 109
 110         while( position >= newsize )
 111                 newsize += OSRF_LIST_INC_SIZE;
 112
 113         if( newsize > list->arrsize ) { /* expand the list if necessary */
 114                 void** newarr;
 115                 OSRF_MALLOC(newarr, newsize * sizeof(void*));
 116
 117                 // Copy the old pointers, and nullify the new ones
 118
 119                 int i;
 120                 for( i = 0; i < list->arrsize; i++ )
 121                         newarr[i] = list->arrlist[i];
 122                 for( ; i < newsize; i++ )
 123                         newarr[i] = NULL;
 124                 free(list->arrlist);
 125                 list->arrlist = newarr;
 126                 list->arrsize = newsize;
 127         }
 128
 129         void* olditem = osrfListRemove( list, position );
 130         list->arrlist[position] = item;
 131         if( list->size <= position ) list->size = position + 1;
 132         return olditem;
 133 }
 134
 135
 136 /**
 137         @brief Fetch the pointer stored at a specified position.
 138         @param list A pointer to an osrfList.
 139         @param position A zero-based index specifying which item to fetch.
 140         @return The pointer stored at the specified position, if any, or NULL.
 141
 142         The contents of the osrfList are unchanged.
 143
 144         If either parameter is invalid, the return value is NULL.
 145 */
 146 void* osrfListGetIndex( const osrfList* list, unsigned int position ) {
 147         if(!list || position >= list->size) return NULL;
 148         return list->arrlist[position];
 149 }
 150
 151 /**
 152         @brief Free an osrfList, and, optionally, everything in it.
 153         @param list A pointer to the osrfList to be freed.
 154
 155         If the calling code has specified a function for freeing items, it is called for every
 156         non-NULL pointer in the array.
 157 */
 158 void osrfListFree( osrfList* list ) {
 159         if(!list) return;
 160
 161         if( list->freeItem ) {
 162                 int i; void* val;
 163                 for( i = 0; i < list->size; i++ ) {
 164                         if( (val = list->arrlist[i]) )
 165                                 list->freeItem(val);
 166                 }
 167         }
 168
 169         free(list->arrlist);
 170         free(list);
 171 }
 172
 173 /**
 174         @brief Make an osrfList empty.
 175         @param list Pointer to the osrfList to be cleared.
 176
 177         Delete every item in the list.  If a callback function is defined for freeing the items,
 178         call it for every item.
 179 */
 180 void osrfListClear( osrfList* list ) {
 181         if(!list) return;
 182
 183         unsigned int i;
 184         for( i = 0; i < list->size; ++i ) {
 185                 if( list->freeItem && list->arrlist[ i ] )
 186                         list->freeItem( list->arrlist[ i ] );
 187                 list->arrlist[ i ] = NULL;
 188         }
 189
 190         list->size = 0;
 191 }
 192
 193 /**
 194         @brief Exchange the contents of two osrfLists.
 195         @param one Pointer to the first osrfList.
 196         @param two Pointer to the second osrfList.
 197
 198         After the call, the first list contains what had been the contents of the second,
 199         and vice versa.  This swap also works if the two parameters point to the same
 200         list; i.e. there is no net effect.
 201
 202         If either parameter is NULL, nothing happens.
 203 */
 204 void osrfListSwap( osrfList* one, osrfList* two ) {
 205         if( one && two ) {
 206                 osrfList temp = *one;
 207                 *one = *two;
 208                 *two = temp;
 209         }
 210 }
 211
 212 /**
 213         @brief Remove the pointer from a specified position.
 214         @param list A pointer to the osrfList.
 215         @param position A zero-based index identifying the pointer to be removed.
 216         @return A copy of the pointer removed, or NULL if the item was freed.
 217
 218         Returns NULL if either parameter is invalid.  Otherwise:
 219
 220         If a callback function has been installed for freeing the item to which the pointer
 221         points, it is called, and osrfListRemove returns NULL.  Otherwise it returns the pointer
 222         at the specified position in the array.  In either case it overwrites the pointer in
 223         the array with NULL.
 224
 225         Note that other positions in the array are not affected; i.e. osrfListRemove does NOT
 226         shift other pointers down to fill in the hole left by the removal.
 227 */
 228 void* osrfListRemove( osrfList* list, unsigned int position ) {
 229         if(!list || position >= list->size) return NULL;
 230
 231         void* olditem = list->arrlist[position];
 232         list->arrlist[position] = NULL;
 233         if( list->freeItem ) {
 234                 list->freeItem(olditem);
 235                 olditem = NULL;
 236         }
 237
 238         if( position == list->size - 1 ) list->size--;
 239         return olditem;
 240 }
 241
 242 /**
 243         @brief Remove a pointer from a specified position and return it.
 244         @param list A pointer to the osrfList.
 245         @param position A zero-based subscript identifying the pointer to be extracted.
 246         @return The pointer at the specified position.
 247
 248         This function is identical to osrfListRemove(), except that it never frees the item
 249         to which the pointer points, even if an item-freeing function has been designated.
 250 */
 251 void* osrfListExtract( osrfList* list, unsigned int position ) {
 252         if(!list || position >= list->size) return NULL;
 253
 254         void* olditem = list->arrlist[position];
 255         list->arrlist[position] = NULL;
 256
 257         if( position == list->size - 1 ) list->size--;
 258         return olditem;
 259 }
 260
 261
 262 /**
 263         @brief Find the position where a given pointer is stored.
 264         @param list A pointer to the osrfList.
 265         @param addr A void pointer possibly stored in the osrfList.
 266         @return A zero-based index indicating where the specified pointer resides in the array,
 267                 or -1 if no such pointer is found.
 268
 269         If either parameter is NULL, osrfListFind returns -1.
 270
 271         If the pointer in question is stored in more than one slot, osrfListFind returns the
 272                 lowest applicable index.
 273 */
 274 int osrfListFind( const osrfList* list, void* addr ) {
 275         if(!(list && addr)) return -1;
 276         int index;
 277         for( index = 0; index < list->size; index++ ) {
 278                 if( list->arrlist[index] == addr )
 279                         return index;
 280         }
 281         return -1;
 282 }
 283
 284
 285 /**
 286         @brief Return the number of slots in use.
 287         @param list A pointer to an osrfList.
 288         @return The number of slots in use.
 289
 290         The concept of "in use" is highly counter-intuitive and not, in general, very useful for the
 291         calling code.  It is an internal optimization trick: it keeps track of how many slots *might*
 292         contain non-NULL pointers, not how many slots *do* contain non_NULL pointers.  It
 293         represents how many slots certain operations need to look at before they can safely stop.
 294
 295         Extreme example: starting with an empty osrfList, call osrfListSet()
 296         to add a pointer at slot 15.  If you then call osrfListGetCount(),
 297         it returns 16, because you installed the pointer in the sixteenth slot (counting from 1),
 298         even though the array contains only one non-NULL pointer.
 299
 300         Now call osrfListRemove() to remove the pointer you just added. If you then call
 301         osrfListGetCount(), it returns 15, even though all the pointers in the array are NULL,
 302         because osrfListRemove() simply decremented the counter from its previous value of 16.
 303
 304         Conclusion: osrfListGetCount() tells you next to nothing about the contents of the array.
 305         The value returned reflects not only the current state of the array but also the history
 306         and sequence of previous operations.
 307
 308         If you have changed the contents of the array only by calls to osrfListPush() and/or
 309         osrfListPushFirst(), thereby leaving no holes in the array at any time, then
 310         osrfListGetCount() will return the answer you expect.  Otherwise all bets are off.
 311 */
 312 unsigned int osrfListGetCount( const osrfList* list ) {
 313         if(!list) return -1;
 314         return list->size;
 315 }
 316
 317
 318 /**
 319         @brief Remove the last pointer from the array.
 320         @param list A pointer to an osrfList.
 321         @return The pointer so removed, or NULL.
 322
 323         As with osrfListRemove(), if a callback function has been defined, osrfListPop() calls it
 324         for the pointer it removes, and returns NULL.  Otherwise it returns the removed pointer.
 325
 326         The concept of "last pointer" is non-intuitive.  It reflects, in part, the history and
 327         sequence of previous operations on the osrfList.  The pointer removed is the one with
 328         subscript n - 1, where n is the value returned by osrfListGetCount().  See the discussion
 329         of the latter function for the dirty details.
 330
 331         In brief, osrfListPop() will behave in the obvious and expected way as long as you never
 332         create holes in the array via calls to osrfListSet(), osrfListRemove(), or osrfListExtract().
 333 */
 334 void* osrfListPop( osrfList* list ) {
 335         if(!list) return NULL;
 336         return osrfListRemove( list, list->size - 1 );
 337 }
 338
 339
 340 /**
 341         @brief Create and initialize an osrfListIterator for a given osrfList.
 342         @param list A pointer to an osrfList.
 343         @return A pointer to the newly constructed osrfListIterator.
 344
 345         The calling code is responsible for freeing the osrfListIterator by calling
 346                 osrfListIteratorFree().
 347 */
 348 osrfListIterator* osrfNewListIterator( const osrfList* list ) {
 349         if(!list) return NULL;
 350         osrfListIterator* itr;
 351         OSRF_MALLOC(itr, sizeof(osrfListIterator));
 352         itr->list = list;
 353         itr->current = 0;
 354         return itr;
 355 }
 356
 357 /**
 358         @brief Advance an osrfListIterator to the next position in the array.
 359         @param itr A pointer to the osrfListIterator to be advanced.
 360         @return The pointer at the next position in the array; or NULL, if the osrfIterator
 361                 is already past the end.
 362
 363         The first call to osrfListIteratorNext() for a given osrfListIterator returns the first
 364         pointer in the array (i.e slot zero, counting from zero).  Subsequent calls return successive
 365         pointers from the array.  Once it has returned the last pointer, the iterator responds to
 366         subsequent calls by returning NULL, unless it is restored to an initial state by a call to
 367         osrfListIteratorReset().
 368
 369         A return value of NULL does not necessarily indicate that the iterator has reached the end
 370         of the array.  Depending on the history and sequence of previous operations, the array may
 371         include NULLs that are regarded as part of the array.  See the discussions of osrfListPop()
 372         and osrfListGetCount().
 373 */
 374 void* osrfListIteratorNext( osrfListIterator* itr ) {
 375         if(!(itr && itr->list)) return NULL;
 376         if(itr->current >= itr->list->size) return NULL;
 377         return itr->list->arrlist[itr->current++];
 378 }
 379
 380 /**
 381         @brief Free an osrfListIterator.
 382         @param itr A pointer to the osrfListIterator to be freed.
 383 */
 384 void osrfListIteratorFree( osrfListIterator* itr ) {
 385         if(!itr) return;
 386         free(itr);
 387 }
 388
 389
 390 /**
 391         @brief Reset an osrfListIterator to the beginning of the associated osrfList.
 392         @param itr A pointer to the osrfListIterator to be reset.
 393 */
 394 void osrfListIteratorReset( osrfListIterator* itr ) {
 395         if(!itr) return;
 396         itr->current = 0;
 397 }
 398
 399
 400 /**
 401         @brief Install a default item-freeing callback function (the ANSI standard free() function).
 402         @param list A pointer to the osrfList where the callback function will be installed.
 403 */
 404 void osrfListSetDefaultFree( osrfList* list ) {
 405         if(!list) return;
 406         list->freeItem = free;
 407 }