1 /*******************************************************************
2 uLan Utilities Library - C library of basic reusable constructions
4 ul_uniqid.h - unique ID generator
6 (C) Copyright 2003-2004 by Pavel Pisa - Originator
8 The uLan utilities library can be used, copied and modified under
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.
20 See files COPYING and README for details.
22 *******************************************************************/
27 #include "ul_gavlflesint.h"
28 #include "ul_uniqid.h"
29 #include "ul_utmalloc.h"
31 typedef struct ul_uniqid_pool_item {
33 ul_uniqid_range_t range;
34 } ul_uniqid_pool_item_t;
37 ul_uniqid_pool_cmp_fnc( const ul_uniqid_range_t *a, const ul_uniqid_range_t *b)
39 if (a->first>b->last) return 1;
40 if (a->last<b->first) return -1;
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)
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, , , )
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
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.
62 int ul_uniqid_pool_init(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last)
64 ul_uniqid_pool_item_t *item;
66 ul_uniqid_pool_init_root_field(pool);
71 pool->range.first=first;
72 pool->range.last=last;
74 item=malloc(sizeof(ul_uniqid_pool_item_t));
77 item->range=pool->range;
79 ul_uniqid_pool_insert(pool, item);
85 * ul_uniqid_pool_done - Finalize Unique IDs Pool
86 * @pool: the pointer to the unique IDs pool
88 * Return Value: The zero value indicates success.
90 int ul_uniqid_pool_done(ul_uniqid_pool_t *pool)
92 ul_uniqid_pool_item_t *item;
94 gavl_cust_for_each_cut(ul_uniqid_pool, pool, item){
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
107 * The function checks if specified range @first..@last is free
108 * and reserves it from free pool.
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.
115 int ul_uniqid_pool_reserve(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last)
117 ul_uniqid_range_t range;
119 ul_uniqid_pool_item_t *item;
124 if(range.first>range.last)
127 item=ul_uniqid_pool_find(pool, &range);
131 if(range.first<item->range.first)
134 if(range.last>item->range.last)
137 if(range.first==item->range.first){
138 if(range.last==item->range.last){
139 ul_uniqid_pool_delete(pool, item);
142 item->range.first=range.last+1;
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));
151 item->range.last=idsave;
152 item->range.first=range.last+1;
153 ul_uniqid_pool_insert(pool, item);
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
167 * The range @first..@last is returned to the pool for subsequent reuse.
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.
173 int ul_uniqid_pool_release(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last)
175 ul_uniqid_pool_item_t *post, *prev;
176 ul_uniqid_range_t range;
180 post=ul_uniqid_pool_find_after(pool,&range);
183 prev=ul_uniqid_pool_prev(pool,post);
184 if(post->range.first!=range.last+1)
187 post->range.first=range.first;
189 prev=ul_uniqid_pool_last(pool);
193 if(prev->range.last!=range.first-1)
197 post->range.first=prev->range.first;
198 ul_uniqid_pool_delete(pool, prev);
201 prev->range.last=range.last;
207 post=malloc(sizeof(ul_uniqid_pool_item_t));
211 ul_uniqid_pool_insert(pool, post);
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
221 * The function allocates lowest available ID from the pool and assigns
222 * its value to the space pointed by @ptrid.
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.
228 int ul_uniqid_pool_alloc_one(ul_uniqid_pool_t *pool, ul_uniqid_t *ptrid)
231 ul_uniqid_pool_item_t *item;
233 item=ul_uniqid_pool_first(pool);
235 id=item->range.first;
236 if(item->range.first!=item->range.last){
237 item->range.first=id+1;
239 ul_uniqid_pool_delete(pool, item);
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
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.
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.
262 int ul_uniqid_pool_alloc_one_after(ul_uniqid_pool_t *pool, ul_uniqid_t *ptrid, ul_uniqid_t afterid)
265 ul_uniqid_pool_item_t *item;
267 if((afterid>=pool->range.last)||
268 (afterid<=pool->range.first)){
271 ul_uniqid_range_t range;
272 range.first=range.last=afterid;
273 item=ul_uniqid_pool_find_after(pool,&range);
277 item=ul_uniqid_pool_first(pool);
282 id=item->range.first;
283 if(item->range.first!=item->range.last){
284 item->range.first=id+1;
286 ul_uniqid_pool_delete(pool, item);
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
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.
304 int ul_uniqid_pool_free_one(ul_uniqid_pool_t *pool, ul_uniqid_t id)
306 return ul_uniqid_pool_release(pool, id, id);