src/ulut/ulut/ul_gsa.c

   1 /*******************************************************************
   2   uLan Utilities Library - C library of basic reusable constructions
   3
   4   ul_gsa.c      - generic sorted arrays
   5
   6   (C) Copyright 2001-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 #include "ul_utmalloc.h"
  26 #include "ul_gsa.h"
  27
  28 #undef DEBUG
  29
  30 #define GSA_ALLOC_STEP 8
  31 #define GSA_DEALLOC_STEP 32
  32
  33 /**
  34  * gsa_struct_init - Initialize GSA Structure
  35  * @array:      pointer to the array structure declared through %GSA_ARRAY_FOR
  36  * @key_offs:   offset to the order controlling field obtained by %UL_OFFSETOF
  37  * @cmp_fnc:    function defining order of items by comparing fields at offset
  38  *              @key_offs.
  39  */
  40 void
  41 gsa_struct_init(gsa_array_t *array, int key_offs,
  42                 gsa_cmp_fnc_t *cmp_fnc)
  43 {
  44   array->key_offs=key_offs;
  45   array->cmp_fnc=cmp_fnc;
  46   array->count=0;
  47   array->alloc_count=0;
  48   array->items=NULL;
  49 }
  50
  51 /**
  52  * gsa_delete_all - Delete Pointers to the All Items in the Array
  53  * @array:      pointer to the array structure declared through %GSA_ARRAY_FOR
  54  *
  55  * This function releases all internally allocated memory,
  56  * but does not release memory of the @array structure
  57  */
  58 void
  59 gsa_delete_all(gsa_array_t *array)
  60 {
  61   if(array->items) free(array->items);
  62   array->items=NULL;
  63   array->count=0;
  64   array->alloc_count=0;
  65 }
  66
  67
  68 /**
  69  * gsa_bsearch_indx - Search for Item or Place for Item by Key
  70  * @array:      pointer to the array structure declared through %GSA_ARRAY_FOR
  71  * @key:        key value searched for
  72  * @key_offs:   offset to the order controlling field obtained by %UL_OFFSETOF
  73  * @cmp_fnc:    function defining order of items by comparing fields
  74  * @mode:       mode of the search operation
  75  * @indx:       pointer to place, where store value of found item array index
  76  *              or index where new item should be inserted
  77  *
  78  * Core search routine for GSA arrays
  79  * binary searches for item with field at offset @key_off equal to @key value
  80  * Values are compared by function pointed by *@cmp_fnc field in the array
  81  * structure @array.
  82  * Integer @mode modifies search algorithm:
  83  *   %GSA_FANY   .. finds item with field value *@key,
  84  *   %GSA_FFIRST .. finds the first item with field value *@key,
  85  *   %GSA_FAFTER .. index points after last item with *@key value,
  86  *        reworded - index points at first item with higher
  87  *        value of field or after last item
  88  * Return Value: Return of nonzero value indicates match found.
  89  */
  90 int
  91 gsa_bsearch_indx(gsa_array_t *array, void *key, int key_offs,
  92             gsa_cmp_fnc_t *cmp_fnc, int mode, unsigned *indx)
  93 {
  94   unsigned a, b, c;
  95   int r;
  96   if(!array->items || !array->count || !cmp_fnc){
  97     *indx=0;
  98     if(mode&GSA_FAFTER)
  99       *indx=array->count;
 100     return 0;
 101   }
 102   a=0;
 103   b=array->count;
 104   while(1){
 105     c=(a+b)/2;
 106     r=cmp_fnc((char*)array->items[c]+key_offs,key);
 107     if(!r) break;
 108     if(r<0)
 109       a=c+1;
 110      else
 111       b=c;
 112     if(a==b){
 113       *indx=a;
 114       return 0;
 115     }
 116   }
 117   if(mode&GSA_FFIRST){
 118     /* equal items can be in range a to b-1 */
 119     /* routine looks for first one */
 120     b=c;
 121     do{
 122       c=(a+b)/2;
 123       r=cmp_fnc((char*)array->items[c]+key_offs,key);
 124       if(r)
 125         a=c+1;
 126        else
 127         b=c;
 128     }while(a!=b);
 129     c=b;
 130   } else if(mode&GSA_FAFTER) {
 131     /* equal items can be in range a to b-1 */
 132     /* return index after last one */
 133     a=c+1;
 134     while(a!=b){
 135       c=(a+b)/2;
 136       r=cmp_fnc((char*)array->items[c]+key_offs,key);
 137       if(r)
 138         b=c;
 139        else
 140         a=c+1;
 141     }
 142     c=a;
 143   }
 144   *indx=c;
 145   return 1;
 146 }
 147
 148 /**
 149  * gsa_find - Find Item for Provided Key
 150  * @array:      pointer to the array structure declared through %GSA_ARRAY_FOR
 151  * @key:        key value searched for
 152  *
 153  * Return Value: pointer to item associated to key value or %NULL.
 154  */
 155 void *
 156 gsa_find(gsa_array_t *array, void *key)
 157 {
 158   unsigned indx;
 159   if(gsa_bsearch_indx(array,key,array->key_offs,
 160                       array->cmp_fnc,0,&indx))
 161     return array->items[indx];
 162   else return NULL;
 163 }
 164
 165 /**
 166  * gsa_find_first - Find the First Item for Provided Key
 167  * @array:      pointer to the array structure declared through %GSA_ARRAY_FOR
 168  * @key:        key value searched for
 169  *
 170  * same as above, but first matching item is found.
 171  * Return Value: pointer to the first item associated to key value or %NULL.
 172  */
 173 void *
 174 gsa_find_first(gsa_array_t *array, void *key)
 175 {
 176   unsigned indx;
 177   if(gsa_bsearch_indx(array,key,array->key_offs,
 178                       array->cmp_fnc,GSA_FFIRST,&indx))
 179     return array->items[indx];
 180   else return NULL;
 181 }
 182
 183 /**
 184  * gsa_find_indx - Find the First Item with Key Value and Return Its Index
 185  * @array:      pointer to the array structure declared through %GSA_ARRAY_FOR
 186  * @key:        key value searched for
 187  * @indx:       pointer to place for index, at which new item should be inserted
 188  *
 189  * same as above, but additionally stores item index value.
 190  * Return Value: pointer to the first item associated to key value or %NULL.
 191  */
 192 void *
 193 gsa_find_indx(gsa_array_t *array, void *key, int *indx)
 194 {
 195   if(gsa_bsearch_indx(array,key,array->key_offs,
 196                       array->cmp_fnc,GSA_FFIRST,(unsigned*)indx))
 197     return array->items[*indx];
 198   else return NULL;
 199 }
 200
 201 /**
 202  * gsa_insert_at - Insert Existing Item to the Specified Array Index
 203  * @array:      pointer to the array structure declared through %GSA_ARRAY_FOR
 204  * @item:       pointer to inserted Item
 205  * @where:      at which index should be @item inserted
 206  *
 207  * Return Value: positive or zero value informs about success
 208  */
 209 int
 210 gsa_insert_at(gsa_array_t *array, void *item, unsigned where)
 211 {
 212   unsigned acnt=array->alloc_count;
 213   unsigned cnt=array->count;
 214   void **items, **p;
 215   if(where>cnt) where=cnt;
 216   if((cnt+1>=acnt)||!array->items)
 217   {
 218     acnt+=GSA_ALLOC_STEP;
 219     if(!array->items)
 220       items=malloc(acnt*sizeof(void*));
 221      else
 222       items=realloc(array->items,acnt*sizeof(void*));
 223     if(!items) return -1;
 224     array->alloc_count=acnt;
 225     array->items=items;
 226   }
 227   else items=array->items;
 228   p=items+where;
 229   memmove(p+1,p,(char*)(items+cnt)-(char*)p);
 230   array->count=cnt+1;
 231   *p=item;
 232   return 0;
 233 }
 234
 235 /**
 236  * gsa_insert - Insert Existing into Ordered Item Array
 237  * @array:      pointer to the array structure declared through %GSA_ARRAY_FOR
 238  * @item:       pointer to inserted Item
 239  * @mode:       if mode is %GSA_FAFTER, multiple items with same key can
 240  *              be stored into array, else strict ordering is required
 241  *
 242  * Return Value: positive or zero value informs about success
 243  */
 244 int
 245 gsa_insert(gsa_array_t *array, void *item, int mode)
 246 {
 247   unsigned indx;
 248   int res;
 249   res=gsa_bsearch_indx(array,(char*)item+array->key_offs,
 250                 array->key_offs,array->cmp_fnc,mode,&indx);
 251   if(res){
 252     if(!mode) return -1;
 253   }
 254   if(gsa_insert_at(array,item,indx)<0)
 255     return -1;
 256   return res;
 257 }
 258
 259 /**
 260  * gsa_delete_at - Delete Item from the Specified Array Index
 261  * @array:      pointer to the array structure declared through %GSA_ARRAY_FOR
 262  * @indx:       index of deleted item
 263  *
 264  * Return Value: positive or zero value informs about success
 265  */
 266 int
 267 gsa_delete_at(gsa_array_t *array, unsigned indx)
 268 {
 269   unsigned acnt=array->alloc_count;
 270   unsigned cnt=array->count;
 271   void **items=array->items;
 272   void **p;
 273   if(indx>=cnt) return -1;
 274   p=items+indx;
 275   array->count=--cnt;
 276   memmove(p,p+1,(items+cnt-p)*sizeof(void *));
 277   if(acnt-cnt>GSA_DEALLOC_STEP+GSA_ALLOC_STEP)
 278   {
 279     acnt-=GSA_DEALLOC_STEP;
 280     items=realloc(array->items,acnt*sizeof(void*));
 281     if(items){
 282       array->alloc_count=acnt;
 283       array->items=items;
 284     }
 285   }
 286   return 0;
 287 }
 288
 289 /**
 290  * gsa_delete - Delete Item from the Array
 291  * @array:      pointer to the array structure declared through %GSA_ARRAY_FOR
 292  * @item:       pointer to deleted Item
 293  *
 294  * Return Value: positive or zero value informs about success
 295  */
 296 int
 297 gsa_delete(gsa_array_t *array, void *item)
 298 {
 299   unsigned indx;
 300   int key_offs=array->key_offs;
 301   gsa_cmp_fnc_t *cmp_fnc=array->cmp_fnc;
 302   if(!gsa_bsearch_indx(array,(char*)item+key_offs,
 303         key_offs,cmp_fnc,GSA_FFIRST,&indx))
 304     return -1;
 305
 306   while(array->items[indx]!=item){
 307     if(++indx>=array->count) return -1;
 308     if(cmp_fnc){
 309       if(cmp_fnc((char*)(array->items[indx])+key_offs,
 310                (char*)item+key_offs))
 311         return -1;
 312     }
 313   }
 314   return gsa_delete_at(array,indx);
 315 }
 316
 317 /**
 318  * gsa_resort_buble - Sort Again Array If Sorting Criteria Are Changed
 319  * @array:      pointer to the array structure declared through %GSA_ARRAY_FOR
 320  * @key_offs:   offset to the order controlling field obtained by %UL_OFFSETOF
 321  * @cmp_fnc:    function defining order of items by comparing fields
 322  *
 323  * Return Value: non-zero value informs, that resorting changed order
 324  */
 325 int
 326 gsa_resort_buble(gsa_array_t *array, int key_offs,
 327                gsa_cmp_fnc_t *cmp_fnc)
 328 {
 329   char **a, **b, **p;
 330   char *k1, *k2;
 331   int m, m1;
 332   if(array->count<2) return 0;
 333   a=(char**)array->items; m=0;
 334   b=(char**)&array->items[array->count-1];
 335   do{
 336     /* upward run */
 337     p=a; m1=0;
 338     k1=*p+key_offs;
 339     do{
 340       k2=*(p+1)+key_offs;
 341       if(cmp_fnc(k1,k2)>0) {
 342         k2=*p;
 343         *p=*(p+1);
 344         *(p+1)=k2;
 345         m1=1;
 346       } else k1=k2;
 347     } while(++p!=b);
 348     m|=m1;
 349     if((a==--b)||!m1) return m;
 350     /* downward run */
 351     p=b; m1=0;
 352     k1=*p+key_offs;
 353     do{
 354       k2=*(p-1)+key_offs;
 355       if(cmp_fnc(k1,k2)<0) {
 356         k2=*p;
 357         *p=*(p-1);
 358         *(p-1)=k2;
 359         m1=1;
 360       } else k1=k2;
 361     } while(--p!=a);
 362     m|=m1;
 363     if((++a==b)||!m1) return m;
 364   }while(1);
 365 }
 366
 367 /**
 368  * gsa_setsort - Change Array Sorting Criterion
 369  * @array:      pointer to the array structure declared through %GSA_ARRAY_FOR
 370  * @key_offs:   new value of offset to the order controlling field
 371  * @cmp_fnc:    new function defining order of items by comparing fields at
 372  *              offset @key_offs
 373  *
 374  * Return Value: non-zero value informs, that resorting changed order
 375  */
 376 int
 377 gsa_setsort(gsa_array_t *array, int key_offs,
 378                gsa_cmp_fnc_t *cmp_fnc)
 379 {
 380   if(key_offs>=0) array->key_offs=key_offs;
 381   if(cmp_fnc!=NULL) array->cmp_fnc=cmp_fnc;
 382   return gsa_resort_buble(array,array->key_offs,array->cmp_fnc);
 383 }
 384
 385 int gsa_cmp_int(const void *a, const void *b) UL_ATTR_REENTRANT
 386 {
 387   return *(int*)a-*(int*)b;
 388 }
 389
 390 int gsa_cmp_ulong(const void *a, const void *b) UL_ATTR_REENTRANT
 391 {
 392   return *(unsigned long*)a-*(unsigned long*)b;
 393 }
 394