src/libopensrf/osrf_list.c

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