ulut/ul_gsa.h

   1 /*******************************************************************
   2   uLan Utilities Library - C library of basic reusable constructions
   3
   4   ul_gsa.h      - generic sorted arrays
   5
   6   (C) Copyright 2001 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 #ifndef _UL_GSA_H
  25 #define _UL_GSA_H
  26
  27 #include "ul_utdefs.h"
  28 #include "ul_itbase.h"
  29
  30 #ifdef __cplusplus
  31 extern "C" {
  32 #endif
  33
  34 #define GSA_FANY 0
  35 #define GSA_FFIRST 1
  36 #define GSA_FAFTER 2
  37
  38 /* function to compare fields of two array items */
  39 typedef int gsa_cmp_fnc_t(const void *a, const void *b);
  40
  41 /* compare two integer fields */
  42 int gsa_cmp_int(const void *a, const void *b);
  43
  44 /* compare two unsigned long fields */
  45 int gsa_cmp_ulong(const void *a, const void *b);
  46
  47 /* define structure representing head of array */
  48 #define GSA_ARRAY_FOR(_type) \
  49   struct { \
  50     _type **items; \
  51     unsigned count; \
  52     unsigned alloc_count; \
  53     int key_offs; \
  54     gsa_cmp_fnc_t *cmp_fnc; \
  55   }
  56
  57 /* array type for functions independent on stored type */
  58 typedef GSA_ARRAY_FOR(void) gsa_array_t;
  59
  60 /* initialize array head structure */
  61 void
  62 gsa_struct_init(gsa_array_t *array, int key_offs,
  63                 gsa_cmp_fnc_t *cmp_fnc);
  64
  65 /* delete all pointers from array */
  66 void
  67 gsa_delete_all(gsa_array_t *array);
  68
  69 /* Core binary search routine for GSA arrays
  70    searches in "array" for index "indx" of item
  71    with value of item field at offset "key_offs"
  72    equal to "*key". Values are compared by function
  73    "*cmp_fnc".
  74    Integer "mode" modifies search algorithm
  75      0 .. finds index of any item with field value "*key"
  76      1 .. finds index of first item with "*key"
  77      2 .. index points after last item with "*key" value
  78           reworded - index points at first item with higher
  79           value of field or after last item
  80    Return of nonzerro value indicates match found.
  81  */
  82 int
  83 gsa_bsearch_indx(gsa_array_t *array, void *key, int key_offs,
  84             gsa_cmp_fnc_t *cmp_fnc, int mode, unsigned *indx);
  85
  86 /* returns item with key field value equal to "*key" or NULL */
  87 void *
  88 gsa_find(gsa_array_t *array, void *key);
  89
  90 /* same as above, but first matching item is found */
  91 void *
  92 gsa_find_first(gsa_array_t *array, void *key);
  93
  94 /* find index "indx" of the first matching item */
  95 void *
  96 gsa_find_indx(gsa_array_t *array, void *key, int *indx);
  97
  98 /* insert new item at index "where" */
  99 int
 100 gsa_insert_at(gsa_array_t *array, void *item, unsigned where);
 101
 102 /* insert new item at the right index,
 103    "mode" has same meaning as in "gsa_bsearch_indx"
 104    if mode==0 then strict sorting is required
 105    and violation result in ignore of new item
 106    and return value <0
 107  */
 108 int
 109 gsa_insert(gsa_array_t *array, void *item, int mode);
 110
 111 /* delete item at index */
 112 int
 113 gsa_delete_at(gsa_array_t *array, unsigned indx);
 114
 115 /* delete item from array */
 116 int
 117 gsa_delete(gsa_array_t *array, void *item);
 118
 119 /* set new sorting field and function
 120    returns 0 if no change needed */
 121 int
 122 gsa_setsort(gsa_array_t *array, int key_offs,
 123                gsa_cmp_fnc_t *cmp_fnc);
 124
 125 /*===========================================================*/
 126 /* Macrodefinitions to prepare custom GSA arrays with */
 127
 128 /**
 129  * struct gsa_array_field_t - Structure Representing Anchor of ustom GSA Array
 130  * @items:      pointer to array of pointers to individual items
 131  * @count:      number of items in the sorted array
 132  * @alloc_count: allocated pointer array capacity
 133  */
 134
 135 typedef struct gsa_array_field_t{
 136   void **items;
 137   unsigned count;
 138   unsigned alloc_count;
 139 } gsa_array_field_t;
 140
 141 typedef struct gsa_static_array_field_t{
 142   void * const *items;
 143   unsigned count;
 144 } gsa_static_array_field_t;
 145
 146 void gsa_cust_init_array_field(gsa_array_field_t *array);
 147 int gsa_cust_insert_at(gsa_array_field_t *array, void *item, unsigned where);
 148 int gsa_cust_delete_at(gsa_array_field_t *array, unsigned indx);
 149 void gsa_cust_delete_all(gsa_array_field_t *array);
 150
 151
 152 /* User must provide his/her own compare routine with
 153     int cust_cmp_fnc(cust_key_t *a, cust_key_t *b) */
 154
 155 /*** Base declaration of custom GSA array  ***/
 156 #define GSA_BASE_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 157                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 158 \
 159 static inline cust_item_t * \
 160 cust_prefix##_indx2item(const cust_array_t *array, unsigned indx) \
 161 {\
 162   if(indx>=array->cust_array_field.count) return NULL;\
 163   return (cust_item_t*)array->cust_array_field.items[indx];\
 164 }\
 165 \
 166 static inline cust_key_t *\
 167 cust_prefix##_indx2key(const cust_array_t *array, unsigned indx)\
 168   { return &(cust_prefix##_indx2item(array, indx)->cust_item_key);}\
 169 \
 170 int cust_prefix##_bsearch_indx(const cust_array_t *array, const cust_key_t *key, int mode, unsigned *indxp);\
 171 \
 172 static inline  cust_item_t *\
 173 cust_prefix##_at(const cust_array_t *array, unsigned indx)\
 174 {\
 175   return cust_prefix##_indx2item(array, indx);\
 176 }\
 177 \
 178 static inline cust_item_t *\
 179 cust_prefix##_find(const cust_array_t *array, cust_key_t *key)\
 180 {\
 181   unsigned indx;\
 182   if(!cust_prefix##_bsearch_indx(array, key, 0, &indx)) return NULL;\
 183   return cust_prefix##_indx2item(array, indx);\
 184 }\
 185 \
 186 static inline cust_item_t *\
 187 cust_prefix##_find_first(const cust_array_t *array, cust_key_t *key)\
 188 {\
 189   unsigned indx;\
 190   if(!cust_prefix##_bsearch_indx(array, key, GSA_FFIRST, &indx)) return NULL;\
 191   return cust_prefix##_indx2item(array, indx);\
 192 }\
 193 \
 194 static inline unsigned \
 195 cust_prefix##_find_first_indx(const cust_array_t *array, cust_key_t *key)\
 196 {\
 197   unsigned indx;\
 198   if(!cust_prefix##_bsearch_indx(array, key, GSA_FFIRST, &indx)) return -1;\
 199   return indx;\
 200 }\
 201 \
 202 static inline cust_item_t *\
 203 cust_prefix##_find_after(const cust_array_t *array, cust_key_t *key)\
 204 {\
 205   unsigned indx;\
 206   if(!cust_prefix##_bsearch_indx(array, key, GSA_FAFTER, &indx)) return NULL;\
 207   return cust_prefix##_indx2item(array, indx);\
 208 }\
 209 \
 210 static inline unsigned \
 211 cust_prefix##_find_after_indx(const cust_array_t *array, cust_key_t *key)\
 212 {\
 213   unsigned indx;\
 214   cust_prefix##_bsearch_indx(array, key, GSA_FAFTER, &indx);\
 215   return indx;\
 216 }\
 217 \
 218 static inline int \
 219 cust_prefix##_is_empty(const cust_array_t *array)\
 220 {\
 221   return !array->cust_array_field.count;\
 222 }\
 223 \
 224 static inline cust_item_t *\
 225 cust_prefix##_first(const cust_array_t *array)\
 226 {\
 227   return cust_prefix##_indx2item(array, 0);\
 228 }\
 229 \
 230 static inline unsigned \
 231 cust_prefix##_first_indx(const cust_array_t *array)\
 232 {\
 233   return 0;\
 234 }\
 235 \
 236 static inline cust_item_t *\
 237 cust_prefix##_last(const cust_array_t *array)\
 238 {\
 239   return cust_prefix##_indx2item(array, array->cust_array_field.count-1);\
 240 }\
 241 \
 242 static inline unsigned \
 243 cust_prefix##_last_indx(const cust_array_t *array)\
 244 {\
 245   return array->cust_array_field.count-1;\
 246 }
 247
 248 /*** Iterators for GSA arrays ***/
 249 #define GSA_IT_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t) \
 250 \
 251 typedef struct {\
 252   cust_array_t *container;\
 253   unsigned indx;\
 254 } cust_prefix##_it_t;\
 255 \
 256 static inline cust_item_t *\
 257 cust_prefix##_it2item(const cust_prefix##_it_t *it)\
 258 {\
 259   return cust_prefix##_indx2item(it->container,it->indx);\
 260 }\
 261 \
 262 static inline void \
 263 cust_prefix##_first_it(cust_array_t *container, cust_prefix##_it_t *it)\
 264 {\
 265   it->container=container;\
 266   it->indx=cust_prefix##_first_indx(container);\
 267 }\
 268 \
 269 static inline void \
 270 cust_prefix##_last_it(cust_array_t *container, cust_prefix##_it_t *it)\
 271 {\
 272   it->container=container;\
 273   it->indx=cust_prefix##_last_indx(container);\
 274 }\
 275 \
 276 static inline void \
 277 cust_prefix##_next_it(cust_prefix##_it_t *it)\
 278 {\
 279   if(it->indx<=cust_prefix##_last_indx(it->container)) it->indx++;\
 280   else it->indx=cust_prefix##_first_indx(it->container);\
 281 }\
 282 \
 283 static inline void \
 284 cust_prefix##_prev_it(cust_prefix##_it_t *it)\
 285 {\
 286   if(it->indx<=cust_prefix##_last_indx(it->container)) it->indx--;\
 287   else it->indx=cust_prefix##_first_indx(it->container);\
 288 }\
 289 \
 290 static inline int \
 291 cust_prefix##_is_end_it(cust_prefix##_it_t *it)\
 292 {\
 293   if(!it->container) return 1;\
 294   return it->indx>cust_prefix##_last_indx(it->container);\
 295 }\
 296 \
 297 static inline int \
 298 cust_prefix##_find_it(cust_array_t *container, cust_key_t *key, cust_prefix##_it_t *it)\
 299 {\
 300   it->container=container;\
 301   return (it->indx=cust_prefix##_find_first_indx(container, key))!=(unsigned)-1;\
 302 }\
 303 \
 304 static inline int \
 305 cust_prefix##_find_first_it(cust_array_t *container, cust_key_t *key, cust_prefix##_it_t *it)\
 306 {\
 307   it->container=container;\
 308   return (it->indx=cust_prefix##_find_first_indx(container, key))!=(unsigned)-1;\
 309 }\
 310 \
 311 static inline int \
 312 cust_prefix##_find_after_it(cust_array_t *container, cust_key_t *key, cust_prefix##_it_t *it)\
 313 {\
 314   it->container=container;\
 315   return (it->indx=cust_prefix##_find_after_indx(container, key))!=(unsigned)-1;\
 316 }
 317
 318 /* Declaration of new static custom array without support of runtime modifications */
 319 #define GSA_STATIC_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 320                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 321 \
 322 GSA_BASE_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 323                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 324 \
 325 GSA_IT_CUST_DEC(cust_prefix, const cust_array_t, cust_item_t, cust_key_t)
 326
 327 /*** Declaration of dynamic custom array with  ***/
 328 #define GSA_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 329                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 330 \
 331 GSA_BASE_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 332                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 333 \
 334 int cust_prefix##_insert(cust_array_t *array, cust_item_t *item);\
 335 int cust_prefix##_delete(cust_array_t *array, const cust_item_t *item);\
 336 \
 337 static inline void \
 338 cust_prefix##_init_array_field(cust_array_t *array)\
 339 {\
 340   gsa_cust_init_array_field(&array->cust_array_field);\
 341 }\
 342 \
 343 static inline int \
 344 cust_prefix##_insert_at(cust_array_t *array, cust_item_t *item, unsigned indx)\
 345 {\
 346   return gsa_cust_insert_at(&array->cust_array_field, item, indx);\
 347 }\
 348 \
 349 static inline int \
 350 cust_prefix##_delete_at(cust_array_t *array, unsigned indx)\
 351 {\
 352   return gsa_cust_delete_at(&array->cust_array_field, indx);\
 353 }\
 354 \
 355 static inline void \
 356 cust_prefix##_delete_all(cust_array_t *array)\
 357 {\
 358   gsa_cust_delete_all(&array->cust_array_field);\
 359 }\
 360 \
 361 static inline cust_item_t *\
 362 cust_prefix##_cut_last(cust_array_t *array)\
 363 {\
 364   if(cust_prefix##_is_empty(array)) return NULL;\
 365   return (cust_item_t *)array->cust_array_field.items\
 366                           [--array->cust_array_field.count];\
 367 }\
 368 /*** Iterators ***/\
 369 GSA_IT_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t) \
 370 \
 371 static inline void \
 372 cust_prefix##_delete_it(cust_prefix##_it_t *it)\
 373 {\
 374   cust_prefix##_delete_at(it->container,it->indx);\
 375 }\
 376
 377
 378 /* The next implementation of foreaach is elegant, but can not
 379    be used in C99 non-conformant C compiler */
 380 #ifdef WITH_C99
 381
 382 #define gsa_cust_for_each(cust_prefix, array, ptr) \
 383         for(unsigned __fe_indx=cust_prefix##_first_indx(array);\
 384             (ptr=cust_prefix##_indx2item(array,__fe_indx));\
 385             __fe_indx++)
 386
 387 #define gsa_cust_for_each_rev(cust_prefix, array, ptr) \
 388         for(unsigned __fe_indx=cust_prefix##_last_indx(array);\
 389             (ptr=cust_prefix##_indx2item(array,__fe_indx));\
 390             __fe_indx--)
 391
 392 #define gsa_cust_for_each_from(cust_prefix, array, key, ptr) \
 393         for(unsigned __fe_indx=cust_prefix##_find_first_indx(array, key); \
 394             (ptr=cust_prefix##_indx2item(array,__fe_indx)); \
 395             __fe_indx++)
 396
 397 #define gsa_cust_for_each_after(cust_prefix, array, key, ptr) \
 398         for(unsigned __fe_indx=cust_prefix##_find_after_indx(array, key); \
 399             (ptr=cust_prefix##_indx2item(array,__fe_indx)); \
 400             __fe_indx++)
 401
 402 #endif /*WITH_C99*/
 403
 404 #define gsa_cust_for_each_cut(cust_prefix, array, ptr) \
 405         for(;(ptr=cust_prefix##_cut_last(array));)
 406
 407
 408 #ifdef __cplusplus
 409 } /* extern "C"*/
 410 #endif
 411
 412 #endif /* _UL_GSA_H */