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 int ul_uniqid_pool_init(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last)
  53 {
  54   ul_uniqid_pool_item_t *item;
  55
  56   ul_uniqid_pool_init_root_field(pool);
  57
  58   if(first>last)
  59     return -1;
  60
  61   pool->range.first=first;
  62   pool->range.last=last;
  63
  64   item=malloc(sizeof(ul_uniqid_pool_item_t));
  65   if(!item)
  66     return -1;
  67   item->range=pool->range;
  68
  69   ul_uniqid_pool_insert(pool, item);
  70
  71   return 0;
  72 }
  73
  74 int ul_uniqid_pool_done(ul_uniqid_pool_t *pool)
  75 {
  76   ul_uniqid_pool_item_t *item;
  77
  78   gavl_cust_for_each_cut(ul_uniqid_pool, pool, item){
  79     free(item);
  80   }
  81
  82   return 0;
  83 }
  84
  85 int ul_uniqid_pool_reserve(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last)
  86 {
  87   ul_uniqid_range_t range;
  88   ul_uniqid_t idsave;
  89   ul_uniqid_pool_item_t *item;
  90
  91   range.first=first;
  92   range.last=last;
  93
  94   if(range.first>range.last)
  95     return -1;
  96
  97   item=ul_uniqid_pool_find(pool, &range);
  98   if(!item)
  99     return -1;
 100
 101   if(range.first<item->range.first)
 102     return -1;
 103
 104   if(range.last>item->range.last)
 105     return -1;
 106
 107   if(range.first==item->range.first){
 108     if(range.last==item->range.last){
 109       ul_uniqid_pool_delete(pool, item);
 110     }else{
 111       item->range.first=range.last+1;
 112     }
 113   }else{
 114     idsave=item->range.last;
 115     item->range.last=range.first-1;
 116     if(range.last!=idsave){
 117       item=malloc(sizeof(ul_uniqid_pool_item_t));
 118       if(!item)
 119         return 1;
 120       item->range.last=idsave;
 121       item->range.first=range.last+1;
 122       ul_uniqid_pool_insert(pool, item);
 123     }
 124   }
 125
 126   return 0;
 127 }
 128
 129
 130 int ul_uniqid_pool_release(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last)
 131 {
 132   ul_uniqid_pool_item_t *post, *prev;
 133   ul_uniqid_range_t range;
 134
 135   range.first=first;
 136   range.last=last;
 137   post=ul_uniqid_pool_find_after(pool,&range);
 138
 139   if(post){
 140     prev=ul_uniqid_pool_prev(pool,post);
 141     if(post->range.first!=range.last+1)
 142       post=NULL;
 143     else
 144       post->range.first=range.first;
 145   }else{
 146     prev=ul_uniqid_pool_last(pool);
 147   }
 148
 149   if(prev){
 150     if(prev->range.last!=range.first-1)
 151       prev=NULL;
 152     else{
 153       if(post){
 154         post->range.first=prev->range.first;
 155         ul_uniqid_pool_delete(pool, prev);
 156       }else{
 157         prev->range.last=range.last;
 158       }
 159     }
 160   }
 161
 162   if(!prev && !post){
 163     post=malloc(sizeof(ul_uniqid_pool_item_t));
 164     if(!post)
 165       return -1;
 166     post->range=range;
 167     ul_uniqid_pool_insert(pool, post);
 168   }
 169   return 0;
 170 }
 171
 172 int ul_uniqid_pool_alloc_one(ul_uniqid_pool_t *pool, ul_uniqid_t *ptrid)
 173 {
 174   ul_uniqid_t id;
 175   ul_uniqid_pool_item_t *item;
 176
 177   item=ul_uniqid_pool_first(pool);
 178   if(!item) return -1;
 179   id=item->range.first;
 180   if(item->range.first!=item->range.last){
 181     item->range.first=id+1;
 182   }else{
 183     ul_uniqid_pool_delete(pool, item);
 184   }
 185   *ptrid=id;
 186
 187   return 0;
 188 }
 189
 190 int ul_uniqid_pool_alloc_one_after(ul_uniqid_pool_t *pool, ul_uniqid_t *ptrid, ul_uniqid_t afterid)
 191 {
 192   ul_uniqid_t id;
 193   ul_uniqid_pool_item_t *item;
 194
 195   if((afterid>=pool->range.last)||
 196      (afterid<=pool->range.first)){
 197     item=NULL;
 198   } else {
 199     ul_uniqid_range_t range;
 200     range.first=range.last=afterid;
 201     item=ul_uniqid_pool_find_after(pool,&range);
 202   }
 203
 204   if(!item)
 205     item=ul_uniqid_pool_first(pool);
 206
 207   if(!item)
 208     return -1;
 209
 210   id=item->range.first;
 211   if(item->range.first!=item->range.last){
 212     item->range.first=id+1;
 213   }else{
 214     ul_uniqid_pool_delete(pool, item);
 215   }
 216   *ptrid=id;
 217
 218   return 0;
 219 }
 220
 221
 222 int ul_uniqid_pool_free_one(ul_uniqid_pool_t *pool, ul_uniqid_t id)
 223 {
 224   return ul_uniqid_pool_release(pool, id, id);
 225 }