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 void
  34 gsa_struct_init(gsa_array_t *array, int key_offs,
  35                 gsa_cmp_fnc_t *cmp_fnc)
  36 {
  37   array->key_offs=key_offs;
  38   array->cmp_fnc=cmp_fnc;
  39   array->count=0;
  40   array->alloc_count=0;
  41   array->items=NULL;
  42 };
  43
  44 void
  45 gsa_delete_all(gsa_array_t *array)
  46 {
  47   if(array->items) free(array->items);
  48   array->items=NULL;
  49   array->count=0;
  50   array->alloc_count=0;
  51 }
  52
  53
  54 int
  55 gsa_bsearch_indx(gsa_array_t *array, void *key, int key_offs,
  56             gsa_cmp_fnc_t *cmp_fnc, int mode, unsigned *indx)
  57 {
  58   unsigned a, b, c;
  59   int r;
  60   if(!array->items || !array->count || !cmp_fnc){
  61     *indx=0;
  62     if(mode&GSA_FAFTER)
  63       *indx=array->count;
  64     return 0;
  65   }
  66   a=0;
  67   b=array->count;
  68   while(1){
  69     c=(a+b)/2;
  70     r=cmp_fnc((char*)array->items[c]+key_offs,key);
  71     if(!r) break;
  72     if(r<0)
  73       a=c+1;
  74      else
  75       b=c;
  76     if(a==b){
  77       *indx=a;
  78       return 0;
  79     }
  80   }
  81   if(mode&GSA_FFIRST){
  82     /* equal items can be in range a to b-1 */
  83     /* routine looks for first one */
  84     b=c;
  85     do{
  86       c=(a+b)/2;
  87       r=cmp_fnc((char*)array->items[c]+key_offs,key);
  88       if(r)
  89         a=c+1;
  90        else
  91         b=c;
  92     }while(a!=b);
  93     c=b;
  94   } else if(mode&GSA_FAFTER) {
  95     /* equal items can be in range a to b-1 */
  96     /* return index after last one */
  97     a=c+1;
  98     while(a!=b){
  99       c=(a+b)/2;
 100       r=cmp_fnc((char*)array->items[c]+key_offs,key);
 101       if(r)
 102         b=c;
 103        else
 104         a=c+1;
 105     }
 106     c=a;
 107   }
 108   *indx=c;
 109   return 1;
 110 }
 111
 112 void *
 113 gsa_find(gsa_array_t *array, void *key)
 114 {
 115   unsigned indx;
 116   if(gsa_bsearch_indx(array,key,array->key_offs,
 117                       array->cmp_fnc,0,&indx))
 118     return array->items[indx];
 119   else return NULL;
 120 }
 121
 122 void *
 123 gsa_find_first(gsa_array_t *array, void *key)
 124 {
 125   unsigned indx;
 126   if(gsa_bsearch_indx(array,key,array->key_offs,
 127                       array->cmp_fnc,GSA_FFIRST,&indx))
 128     return array->items[indx];
 129   else return NULL;
 130 }
 131
 132 void *
 133 gsa_find_indx(gsa_array_t *array, void *key, int *indx)
 134 {
 135   if(gsa_bsearch_indx(array,key,array->key_offs,
 136                       array->cmp_fnc,GSA_FFIRST,indx))
 137     return array->items[*indx];
 138   else return NULL;
 139 }
 140
 141 int
 142 gsa_insert_at(gsa_array_t *array, void *item, unsigned where)
 143 {
 144   unsigned acnt=array->alloc_count;
 145   unsigned cnt=array->count;
 146   void **items, **p;
 147   if(where>cnt) where=cnt;
 148   if((cnt+1>=acnt)||!array->items)
 149   {
 150     acnt+=GSA_ALLOC_STEP;
 151     if(!array->items)
 152       items=malloc(acnt*sizeof(void*));
 153      else
 154       items=realloc(array->items,acnt*sizeof(void*));
 155     if(!items) return -1;
 156     array->alloc_count=acnt;
 157     array->items=items;
 158   }
 159   else items=array->items;
 160   p=items+where;
 161   memmove(p+1,p,(char*)(items+cnt)-(char*)p);
 162   array->count=cnt+1;
 163   *p=item;
 164   return 0;
 165 }
 166
 167 int
 168 gsa_insert(gsa_array_t *array, void *item, int mode)
 169 {
 170   unsigned indx;
 171   int res;
 172   res=gsa_bsearch_indx(array,(char*)item+array->key_offs,
 173                 array->key_offs,array->cmp_fnc,mode,&indx);
 174   if(res){
 175     if(!mode) return -1;
 176   }
 177   if(gsa_insert_at(array,item,indx)<0)
 178     return -1;
 179   return res;
 180 }
 181
 182 int
 183 gsa_delete_at(gsa_array_t *array, unsigned indx)
 184 {
 185   unsigned acnt=array->alloc_count;
 186   unsigned cnt=array->count;
 187   void **items=array->items;
 188   void **p;
 189   if(indx>=cnt) return -1;
 190   p=items+indx;
 191   array->count=--cnt;
 192   memmove(p,p+1,(items+cnt-p)*sizeof(void *));
 193   if(acnt-cnt>GSA_DEALLOC_STEP+GSA_ALLOC_STEP)
 194   {
 195     acnt-=GSA_DEALLOC_STEP;
 196     items=realloc(array->items,acnt*sizeof(void*));
 197     if(items){
 198       array->alloc_count=acnt;
 199       array->items=items;
 200     }
 201   }
 202   return 0;
 203 }
 204
 205 int
 206 gsa_delete(gsa_array_t *array, void *item)
 207 {
 208   unsigned indx;
 209   int key_offs=array->key_offs;
 210   gsa_cmp_fnc_t *cmp_fnc=array->cmp_fnc;
 211   if(!gsa_bsearch_indx(array,(char*)item+key_offs,
 212         key_offs,cmp_fnc,GSA_FFIRST,&indx))
 213     return -1;
 214
 215   while(array->items[indx]!=item){
 216     if(++indx>=array->count) return -1;
 217     if(cmp_fnc){
 218       if(cmp_fnc((char*)(array->items[indx])+key_offs,
 219                (char*)item+key_offs))
 220         return -1;
 221     }
 222   }
 223   return gsa_delete_at(array,indx);
 224 }
 225
 226 int
 227 gsa_resort_buble(gsa_array_t *array, int key_offs,
 228                gsa_cmp_fnc_t *cmp_fnc)
 229 {
 230   char **a, **b, **p;
 231   char *k1, *k2;
 232   int m, m1;
 233   if(array->count<2) return 0;
 234   a=(char**)array->items; m=0;
 235   b=(char**)&array->items[array->count-1];
 236   do{
 237     /* upward run */
 238     p=a; m1=0;
 239     k1=*p+key_offs;
 240     do{
 241       k2=*(p+1)+key_offs;
 242       if(cmp_fnc(k1,k2)>0) {
 243         k2=*p;
 244         *p=*(p+1);
 245         *(p+1)=k2;
 246         m1=1;
 247       } else k1=k2;
 248     } while(++p!=b);
 249     m|=m1;
 250     if((a==--b)||!m1) return m;
 251     /* downward run */
 252     p=b; m1=0;
 253     k1=*p+key_offs;
 254     do{
 255       k2=*(p-1)+key_offs;
 256       if(cmp_fnc(k1,k2)<0) {
 257         k2=*p;
 258         *p=*(p-1);
 259         *(p-1)=k2;
 260         m1=1;
 261       } else k1=k2;
 262     } while(--p!=a);
 263     m|=m1;
 264     if((++a==b)||!m1) return m;
 265   }while(1);
 266 }
 267
 268 int
 269 gsa_setsort(gsa_array_t *array, int key_offs,
 270                gsa_cmp_fnc_t *cmp_fnc)
 271 {
 272   if(key_offs>=0) array->key_offs=key_offs;
 273   if(cmp_fnc!=NULL) array->cmp_fnc=cmp_fnc;
 274   return gsa_resort_buble(array,array->key_offs,array->cmp_fnc);
 275 }
 276
 277 int gsa_cmp_int(const void *a, const void *b)
 278 {
 279   return *(int*)a-*(int*)b;
 280 }
 281
 282 int gsa_cmp_ulong(const void *a, const void *b)
 283 {
 284   return *(unsigned long*)a-*(unsigned long*)b;
 285 }
 286