ulan/host/libs4c/ulut/ul_uniqid.c

   1 /*******************************************************************
   2   uLan Utilities Library - C library of basic reusable constructions
   3
   4   ul_uniqid.h  - unique ID generator
   5
   6   (C) Copyright 2003-2004 by Pavel Pisa - Originator
   7
   8   The uLan utilities library can be used, copied and modified under
   9   next licenses
  10     - GPL - GNU General Public License
  11     - LGPL - GNU Lesser General Public License
  12     - MPL - Mozilla Public License
  13     - and other licenses added by project originators
  14   Code can be modified and re-distributed under any combination
  15   of the above listed licenses. If contributor does not agree with
  16   some of the licenses, he/she can delete appropriate line.
  17   Warning, if you delete all lines, you are not allowed to
  18   distribute source code and/or binaries utilizing code.
  19
  20   See files COPYING and README for details.
  21
  22  *******************************************************************/
  23
  24 #include <string.h>
  25
  26 #include "ul_gavl.h"
  27 #include "ul_gavlflesint.h"
  28 #include "ul_uniqid.h"
  29 #include "ul_utmalloc.h"
  30
  31 typedef struct ul_uniqid_pool_item {
  32   gavl_node_t    node;
  33   ul_uniqid_range_t range;
  34 } ul_uniqid_pool_item_t;
  35
  36 static inline int
  37 ul_uniqid_pool_cmp_fnc( const ul_uniqid_range_t *a, const ul_uniqid_range_t *b)
  38 {
  39         if (a->first>b->last) return 1;
  40         if (a->last<b->first) return -1;
  41         return 0;
  42 }
  43
  44 GAVL_FLES_INT_DEC(ul_uniqid_pool, ul_uniqid_pool_t, ul_uniqid_pool_item_t, ul_uniqid_range_t,
  45         items, node, range, ul_uniqid_pool_cmp_fnc)
  46
  47
  48 GAVL_FLES_INT_IMP(ul_uniqid_pool, ul_uniqid_pool_t, ul_uniqid_pool_item_t, ul_uniqid_range_t,
  49         items, node, range, ul_uniqid_pool_cmp_fnc, GAVL_FANY, , , )
  50
  51
  52 /**
  53  * ul_uniqid_pool_init - Initialize Unique IDs Pool
  54  * @pool:       the pointer to the unique IDs pool
  55  * @first:      the start of the available numeric range
  56  * @last:       the end of the available numeric range
  57  *
  58  * Return Value: The function returns -1 if the @first>@last or if there
  59  *      is not enough memory to allocate item for initial range representation.
  60  *      The zero value indicates successful initialization.
  61  */
  62 int ul_uniqid_pool_init(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last)
  63 {
  64   ul_uniqid_pool_item_t *item;
  65
  66   ul_uniqid_pool_init_root_field(pool);
  67
  68   if(first>last)
  69     return -1;
  70
  71   pool->range.first=first;
  72   pool->range.last=last;
  73
  74   item=malloc(sizeof(ul_uniqid_pool_item_t));
  75   if(!item)
  76     return -1;
  77   item->range=pool->range;
  78
  79   ul_uniqid_pool_insert(pool, item);
  80
  81   return 0;
  82 }
  83
  84 /**
  85  * ul_uniqid_pool_done - Finalize Unique IDs Pool
  86  * @pool:       the pointer to the unique IDs pool
  87  *
  88  * Return Value: The zero value indicates success.
  89  */
  90 int ul_uniqid_pool_done(ul_uniqid_pool_t *pool)
  91 {
  92   ul_uniqid_pool_item_t *item;
  93
  94   gavl_cust_for_each_cut(ul_uniqid_pool, pool, item){
  95     free(item);
  96   }
  97
  98   return 0;
  99 }
 100
 101 /**
 102  * ul_uniqid_pool_reserve - Reserve Range from the Unique IDs Pool
 103  * @pool:       the pointer to the unique IDs pool
 104  * @first:      the start value of the range
 105  * @last:       the end value of the range
 106  *
 107  * The function checks if specified range @first..@last is free
 108  * and reserves it from free pool.
 109  *
 110  * Return Value: The zero value indicates success. The value of -1 indicates,
 111  *      that range overlaps with already reserved values or exceeds pool boundaries.
 112  *      The value 1 is returned in the case, that there is not enough free memory
 113  *      to represent new non-continuous ranges.
 114  */
 115 int ul_uniqid_pool_reserve(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last)
 116 {
 117   ul_uniqid_range_t range;
 118   ul_uniqid_t idsave;
 119   ul_uniqid_pool_item_t *item;
 120
 121   range.first=first;
 122   range.last=last;
 123
 124   if(range.first>range.last)
 125     return -1;
 126
 127   item=ul_uniqid_pool_find(pool, &range);
 128   if(!item)
 129     return -1;
 130
 131   if(range.first<item->range.first)
 132     return -1;
 133
 134   if(range.last>item->range.last)
 135     return -1;
 136
 137   if(range.first==item->range.first){
 138     if(range.last==item->range.last){
 139       ul_uniqid_pool_delete(pool, item);
 140       free(item);
 141     }else{
 142       item->range.first=range.last+1;
 143     }
 144   }else{
 145     idsave=item->range.last;
 146     item->range.last=range.first-1;
 147     if(range.last!=idsave){
 148       item=malloc(sizeof(ul_uniqid_pool_item_t));
 149       if(!item)
 150         return 1;
 151       item->range.last=idsave;
 152       item->range.first=range.last+1;
 153       ul_uniqid_pool_insert(pool, item);
 154     }
 155   }
 156
 157   return 0;
 158 }
 159
 160
 161 /**
 162  * ul_uniqid_pool_release - Release Range Back to the Unique IDs Pool
 163  * @pool:       the pointer to the unique IDs pool
 164  * @first:      the start value of the range
 165  * @last:       the end value of the range
 166  *
 167  * The range @first..@last is returned to the pool for subsequent reuse.
 168  *
 169  * Return Value: The zero value indicates success. The value of -1 indicates,
 170  *      that range cannot be return back, because there is no free memory
 171  *      to allocate space for returned range.
 172  */
 173 int ul_uniqid_pool_release(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last)
 174 {
 175   ul_uniqid_pool_item_t *post, *prev;
 176   ul_uniqid_range_t range;
 177
 178   range.first=first;
 179   range.last=last;
 180   post=ul_uniqid_pool_find_after(pool,&range);
 181
 182   if(post){
 183     prev=ul_uniqid_pool_prev(pool,post);
 184     if(post->range.first!=range.last+1)
 185       post=NULL;
 186     else
 187       post->range.first=range.first;
 188   }else{
 189     prev=ul_uniqid_pool_last(pool);
 190   }
 191
 192   if(prev){
 193     if(prev->range.last!=range.first-1)
 194       prev=NULL;
 195     else{
 196       if(post){
 197         post->range.first=prev->range.first;
 198         ul_uniqid_pool_delete(pool, prev);
 199         free(prev);
 200       }else{
 201         prev->range.last=range.last;
 202       }
 203     }
 204   }
 205
 206   if(!prev && !post){
 207     post=malloc(sizeof(ul_uniqid_pool_item_t));
 208     if(!post)
 209       return -1;
 210     post->range=range;
 211     ul_uniqid_pool_insert(pool, post);
 212   }
 213   return 0;
 214 }
 215
 216 /**
 217  * ul_uniqid_pool_alloc_one - Allocate/Generate One Unique ID from the Pool
 218  * @pool:       the pointer to the unique IDs pool
 219  * @ptrid:      pointer to ul_uniqid_t variable where unique ID is returned
 220  *
 221  * The function allocates lowest available ID from the pool and assigns
 222  * its value to the space pointed by @ptrid.
 223  *
 224  * Return Value: The zero value indicates success. The value of -1 indicates,
 225  *      that all IDs from the pool are taken. No other reason is possible,
 226  *      because function does not call any memory allocation function.
 227  */
 228 int ul_uniqid_pool_alloc_one(ul_uniqid_pool_t *pool, ul_uniqid_t *ptrid)
 229 {
 230   ul_uniqid_t id;
 231   ul_uniqid_pool_item_t *item;
 232
 233   item=ul_uniqid_pool_first(pool);
 234   if(!item) return -1;
 235   id=item->range.first;
 236   if(item->range.first!=item->range.last){
 237     item->range.first=id+1;
 238   }else{
 239     ul_uniqid_pool_delete(pool, item);
 240     free(item);
 241   }
 242   *ptrid=id;
 243
 244   return 0;
 245 }
 246
 247 /**
 248  * ul_uniqid_pool_alloc_one_after - Allocate One Unique ID Greater Than Value Specified
 249  * @pool:       the pointer to the unique IDs pool
 250  * @ptrid:      pointer to ul_uniqid_t variable where unique ID is returned
 251  * @afterid:    the ID value after which free ID is searched
 252  *
 253  * The function allocates the first available ID after @afterid from the
 254  * pool and assigns its value to the space pointed by @ptrid.
 255  * If there is no available ID with value greater than @afterid, the first free ID
 256  * from the whole pool is returned.
 257  *
 258  * Return Value: The zero value indicates success. The value of -1 indicates,
 259  *      that all IDs from the pool are taken. No other reason is possible,
 260  *      because function does not call any memory allocation function.
 261  */
 262 int ul_uniqid_pool_alloc_one_after(ul_uniqid_pool_t *pool, ul_uniqid_t *ptrid, ul_uniqid_t afterid)
 263 {
 264   ul_uniqid_t id;
 265   ul_uniqid_pool_item_t *item;
 266
 267   if((afterid>=pool->range.last)||
 268      (afterid<=pool->range.first)){
 269     item=NULL;
 270   } else {
 271     ul_uniqid_range_t range;
 272     range.first=range.last=afterid;
 273     item=ul_uniqid_pool_find_after(pool,&range);
 274   }
 275
 276   if(!item)
 277     item=ul_uniqid_pool_first(pool);
 278
 279   if(!item)
 280     return -1;
 281
 282   id=item->range.first;
 283   if(item->range.first!=item->range.last){
 284     item->range.first=id+1;
 285   }else{
 286     ul_uniqid_pool_delete(pool, item);
 287     free(item);
 288   }
 289   *ptrid=id;
 290
 291   return 0;
 292 }
 293
 294
 295 /**
 296  * ul_uniqid_pool_free_one - Release One Previously Allocated Unique ID
 297  * @pool:       the pointer to the unique IDs pool
 298  * @id:         the released ID value
 299  *
 300  * Return Value: The zero value indicates success. The value of -1 indicates,
 301  *      that ID cannot be return back, because there is no free memory
 302  *      to allocate space for range representing returned ID.
 303  */
 304 int ul_uniqid_pool_free_one(ul_uniqid_pool_t *pool, ul_uniqid_t id)
 305 {
 306   return ul_uniqid_pool_release(pool, id, id);
 307 }