From 0d30649e03110bbf0763aaa412d189d7a431e278 Mon Sep 17 00:00:00 2001 From: ppisa Date: Sun, 8 May 2005 13:19:21 +0000 Subject: [PATCH] Added support for unique ID generator based on GAVL --- ulut/Makefile.omk | 5 +- ulut/ul_hptree.c | 1 + ulut/ul_uniqid.c | 225 ++++++++++++++++++++++++++++++++++++++++++++++ ulut/ul_uniqid.h | 51 +++++++++++ 4 files changed, 280 insertions(+), 2 deletions(-) create mode 100644 ulut/ul_uniqid.c create mode 100644 ulut/ul_uniqid.h diff --git a/ulut/Makefile.omk b/ulut/Makefile.omk index 89e8c89..95d3feb 100644 --- a/ulut/Makefile.omk +++ b/ulut/Makefile.omk @@ -9,12 +9,13 @@ endif include_HEADERS = ul_dbuff.h ul_evcbase.h ul_gavl.h ul_gavlcust.h \ ul_gavlflesint.h ul_gavlrepcust.h ul_gsa.h ul_gsacust.h \ ul_hptree.h ul_htimdefs.h ul_htimer.h ul_itbase.h \ - ul_list.h ul_listbase.h ul_utdefs.h ul_utmalloc.h + ul_list.h ul_listbase.h ul_utdefs.h ul_utmalloc.h \ + ul_uniqid.h ulut_SOURCES = ul_dbufbase.c ul_dbufmore.c ul_gsa.c ul_gsacust.c \ ul_gavlprim.c ul_gavl.c ul_hptree.c \ ul_htimer.c ul_htimbase.c ul_htimmstime.c \ - ul_evcbase.c + ul_evcbase.c ul_uniqid.c lib_LOADLIBES = ulut diff --git a/ulut/ul_hptree.c b/ulut/ul_hptree.c index 26fd334..fa62926 100644 --- a/ulut/ul_hptree.c +++ b/ulut/ul_hptree.c @@ -21,6 +21,7 @@ *******************************************************************/ +#include #include "ul_utmalloc.h" #include "ul_hptree.h" diff --git a/ulut/ul_uniqid.c b/ulut/ul_uniqid.c new file mode 100644 index 0000000..64ad4f9 --- /dev/null +++ b/ulut/ul_uniqid.c @@ -0,0 +1,225 @@ +/******************************************************************* + uLan Utilities Library - C library of basic reusable constructions + + ul_uniqid.h - unique ID generator + + (C) Copyright 2003-2004 by Pavel Pisa - Originator + + The uLan utilities library can be used, copied and modified under + next licenses + - GPL - GNU General Public License + - LGPL - GNU Lesser General Public License + - MPL - Mozilla Public License + - and other licenses added by project originators + Code can be modified and re-distributed under any combination + of the above listed licenses. If contributor does not agree with + some of the licenses, he/she can delete appropriate line. + Warning, if you delete all lines, you are not allowed to + distribute source code and/or binaries utilizing code. + + See files COPYING and README for details. + + *******************************************************************/ + +#include + +#include "ul_gavl.h" +#include "ul_gavlflesint.h" +#include "ul_uniqid.h" +#include "ul_utmalloc.h" + +typedef struct ul_uniqid_pool_item { + gavl_node_t node; + ul_uniqid_range_t range; +} ul_uniqid_pool_item_t; + +static inline int +ul_uniqid_pool_cmp_fnc( const ul_uniqid_range_t *a, const ul_uniqid_range_t *b) +{ + if (a->first>b->last) return 1; + if (a->lastfirst) return -1; + return 0; +} + +GAVL_FLES_INT_DEC(ul_uniqid_pool, ul_uniqid_pool_t, ul_uniqid_pool_item_t, ul_uniqid_range_t, + items, node, range, ul_uniqid_pool_cmp_fnc) + + +GAVL_FLES_INT_IMP(ul_uniqid_pool, ul_uniqid_pool_t, ul_uniqid_pool_item_t, ul_uniqid_range_t, + items, node, range, ul_uniqid_pool_cmp_fnc, GAVL_FANY, , , ) + + +int ul_uniqid_pool_init(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last) +{ + ul_uniqid_pool_item_t *item; + + ul_uniqid_pool_init_root_field(pool); + + if(first>last) + return -1; + + pool->range.first=first; + pool->range.last=last; + + item=malloc(sizeof(ul_uniqid_pool_item_t)); + if(!item) + return -1; + item->range=pool->range; + + ul_uniqid_pool_insert(pool, item); + + return 0; +} + +int ul_uniqid_pool_done(ul_uniqid_pool_t *pool) +{ + ul_uniqid_pool_item_t *item; + + gavl_cust_for_each_cut(ul_uniqid_pool, pool, item){ + free(item); + } + + return 0; +} + +int ul_uniqid_pool_reserve(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last) +{ + ul_uniqid_range_t range; + ul_uniqid_t idsave; + ul_uniqid_pool_item_t *item; + + range.first=first; + range.last=last; + + if(range.first>range.last) + return -1; + + item=ul_uniqid_pool_find(pool, &range); + if(!item) + return -1; + + if(range.firstrange.first) + return -1; + + if(range.last>item->range.last) + return -1; + + if(range.first==item->range.first){ + if(range.last==item->range.last){ + ul_uniqid_pool_delete(pool, item); + }else{ + item->range.first=range.last+1; + } + }else{ + idsave=item->range.last; + item->range.last=range.first-1; + if(range.last!=idsave){ + item=malloc(sizeof(ul_uniqid_pool_item_t)); + if(!item) + return 1; + item->range.last=idsave; + item->range.first=range.last+1; + ul_uniqid_pool_insert(pool, item); + } + } + + return 0; +} + + +int ul_uniqid_pool_release(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last) +{ + ul_uniqid_pool_item_t *post, *prev; + ul_uniqid_range_t range; + + range.first=first; + range.last=last; + post=ul_uniqid_pool_find_after(pool,&range); + + if(post){ + prev=ul_uniqid_pool_prev(pool,post); + if(post->range.first!=range.last+1) + post=NULL; + else + post->range.first=range.first; + }else{ + prev=ul_uniqid_pool_last(pool); + } + + if(prev){ + if(prev->range.last!=range.first-1) + prev=NULL; + else{ + if(post){ + post->range.first=prev->range.first; + ul_uniqid_pool_delete(pool, prev); + }else{ + prev->range.last=range.last; + } + } + } + + if(!prev && !post){ + post=malloc(sizeof(ul_uniqid_pool_item_t)); + if(!post) + return -1; + post->range=range; + ul_uniqid_pool_insert(pool, post); + } + return 0; +} + +int ul_uniqid_pool_alloc_one(ul_uniqid_pool_t *pool, ul_uniqid_t *ptrid) +{ + ul_uniqid_t id; + ul_uniqid_pool_item_t *item; + + item=ul_uniqid_pool_first(pool); + if(!item) return -1; + id=item->range.first; + if(item->range.first!=item->range.last){ + item->range.first=id+1; + }else{ + ul_uniqid_pool_delete(pool, item); + } + *ptrid=id; + + return 0; +} + +int ul_uniqid_pool_alloc_one_after(ul_uniqid_pool_t *pool, ul_uniqid_t *ptrid, ul_uniqid_t afterid) +{ + ul_uniqid_t id; + ul_uniqid_pool_item_t *item; + + if((afterid>=pool->range.last)|| + (afterid<=pool->range.first)){ + item=NULL; + } else { + ul_uniqid_range_t range; + range.first=range.last=afterid; + item=ul_uniqid_pool_find_after(pool,&range); + } + + if(!item) + item=ul_uniqid_pool_first(pool); + + if(!item) + return -1; + + id=item->range.first; + if(item->range.first!=item->range.last){ + item->range.first=id+1; + }else{ + ul_uniqid_pool_delete(pool, item); + } + *ptrid=id; + + return 0; +} + + +int ul_uniqid_pool_free_one(ul_uniqid_pool_t *pool, ul_uniqid_t id) +{ + return ul_uniqid_pool_release(pool, id, id); +} diff --git a/ulut/ul_uniqid.h b/ulut/ul_uniqid.h new file mode 100644 index 0000000..b19ab02 --- /dev/null +++ b/ulut/ul_uniqid.h @@ -0,0 +1,51 @@ +/******************************************************************* + uLan Utilities Library - C library of basic reusable constructions + + ul_uniqid.h - unique ID generator + + (C) Copyright 2003-2004 by Pavel Pisa - Originator + + The uLan utilities library can be used, copied and modified under + next licenses + - GPL - GNU General Public License + - LGPL - GNU Lesser General Public License + - MPL - Mozilla Public License + - and other licenses added by project originators + Code can be modified and re-distributed under any combination + of the above listed licenses. If contributor does not agree with + some of the licenses, he/she can delete appropriate line. + Warning, if you delete all lines, you are not allowed to + distribute source code and/or binaries utilizing code. + + See files COPYING and README for details. + + *******************************************************************/ + +#ifndef _UL_UNIQID_H +#define _UL_UNIQID_H + +#include "ul_gavl.h" + + +typedef unsigned long ul_uniqid_t; + +typedef struct ul_uniqid_range { + ul_uniqid_t first; + ul_uniqid_t last; +} ul_uniqid_range_t; + +typedef struct ul_uniqid_pool { + gavl_fles_int_root_field_t items; + ul_uniqid_range_t range; +} ul_uniqid_pool_t; + +int ul_uniqid_pool_init(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last); +int ul_uniqid_pool_done(ul_uniqid_pool_t *pool); +int ul_uniqid_pool_reserve(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last); +int ul_uniqid_pool_release(ul_uniqid_pool_t *pool, ul_uniqid_t first, ul_uniqid_t last); +int ul_uniqid_pool_alloc_one(ul_uniqid_pool_t *pool, ul_uniqid_t *ptrid); +int ul_uniqid_pool_alloc_one_after(ul_uniqid_pool_t *pool, ul_uniqid_t *ptrid, ul_uniqid_t afterid); +int ul_uniqid_pool_free_one(ul_uniqid_pool_t *pool, ul_uniqid_t id); + + +#endif /*_UL_UNIQID_H*/ -- 2.39.2