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) UL_ATTR_REENTRANT;
  40
  41 /* compare two integer fields */
  42 int gsa_cmp_int(const void *a, const void *b) UL_ATTR_REENTRANT;
  43
  44 /* compare two unsigned long fields */
  45 int gsa_cmp_ulong(const void *a, const void *b) UL_ATTR_REENTRANT;
  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 custom 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_SCOPE(cust_scope, 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 cust_scope int cust_prefix##_bsearch_indx(const cust_array_t *array, cust_key_t const *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 const *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 const *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 const *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 const *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 const *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   (void)array;\
 234   return 0;\
 235 }\
 236 \
 237 static inline cust_item_t *\
 238 cust_prefix##_last(const cust_array_t *array)\
 239 {\
 240   return cust_prefix##_indx2item(array, array->cust_array_field.count-1);\
 241 }\
 242 \
 243 static inline unsigned \
 244 cust_prefix##_last_indx(const cust_array_t *array)\
 245 {\
 246   return array->cust_array_field.count-1;\
 247 }
 248
 249 /*** Iterators for GSA arrays ***/
 250 #define GSA_IT_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t) \
 251 \
 252 typedef struct {\
 253   cust_array_t *container;\
 254   unsigned indx;\
 255 } cust_prefix##_it_t;\
 256 \
 257 static inline cust_item_t *\
 258 cust_prefix##_it2item(const cust_prefix##_it_t *it)\
 259 {\
 260   return cust_prefix##_indx2item(it->container,it->indx);\
 261 }\
 262 \
 263 static inline void \
 264 cust_prefix##_first_it(cust_array_t *container, cust_prefix##_it_t *it)\
 265 {\
 266   it->container=container;\
 267   it->indx=cust_prefix##_first_indx(container);\
 268 }\
 269 \
 270 static inline void \
 271 cust_prefix##_last_it(cust_array_t *container, cust_prefix##_it_t *it)\
 272 {\
 273   it->container=container;\
 274   it->indx=cust_prefix##_last_indx(container);\
 275 }\
 276 \
 277 static inline void \
 278 cust_prefix##_next_it(cust_prefix##_it_t *it)\
 279 {\
 280   if(it->indx<=cust_prefix##_last_indx(it->container)) it->indx++;\
 281   else it->indx=cust_prefix##_first_indx(it->container);\
 282 }\
 283 \
 284 static inline void \
 285 cust_prefix##_prev_it(cust_prefix##_it_t *it)\
 286 {\
 287   if(it->indx<=cust_prefix##_last_indx(it->container)) it->indx--;\
 288   else it->indx=cust_prefix##_first_indx(it->container);\
 289 }\
 290 \
 291 static inline int \
 292 cust_prefix##_is_end_it(cust_prefix##_it_t *it)\
 293 {\
 294   if(!it->container) return 1;\
 295   return it->indx>cust_prefix##_last_indx(it->container);\
 296 }\
 297 \
 298 static inline int \
 299 cust_prefix##_find_it(cust_array_t *container, cust_key_t const *key, cust_prefix##_it_t *it)\
 300 {\
 301   it->container=container;\
 302   return (it->indx=cust_prefix##_find_first_indx(container, key))!=(unsigned)-1;\
 303 }\
 304 \
 305 static inline int \
 306 cust_prefix##_find_first_it(cust_array_t *container, cust_key_t const *key, cust_prefix##_it_t *it)\
 307 {\
 308   it->container=container;\
 309   return (it->indx=cust_prefix##_find_first_indx(container, key))!=(unsigned)-1;\
 310 }\
 311 \
 312 static inline int \
 313 cust_prefix##_find_after_it(cust_array_t *container, cust_key_t const *key, cust_prefix##_it_t *it)\
 314 {\
 315   it->container=container;\
 316   return (it->indx=cust_prefix##_find_after_indx(container, key))!=(unsigned)-1;\
 317 }
 318
 319 /* Declaration of new const custom array without support of runtime modifications */
 320 #define GSA_CONST_CUST_DEC_SCOPE(cust_scope, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 321                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 322 \
 323 GSA_BASE_CUST_DEC_SCOPE(cust_scope, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 324                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 325 \
 326 GSA_IT_CUST_DEC(cust_prefix, const cust_array_t, cust_item_t, cust_key_t)
 327
 328 #define GSA_CONST_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 329                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 330         GSA_CONST_CUST_DEC_SCOPE(extern, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 331                 cust_array_field, cust_item_key, cust_cmp_fnc)
 332
 333 /*** Declaration of dynamic custom array with full functions ***/
 334 #define GSA_CUST_DEC_SCOPE(cust_scope, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 335                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 336 \
 337 GSA_BASE_CUST_DEC_SCOPE(cust_scope, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 338                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 339 \
 340 cust_scope int cust_prefix##_insert(cust_array_t *array, cust_item_t *item);\
 341 cust_scope int cust_prefix##_delete(cust_array_t *array, const cust_item_t *item);\
 342 \
 343 static inline void \
 344 cust_prefix##_init_array_field(cust_array_t *array)\
 345 {\
 346   gsa_cust_init_array_field(&array->cust_array_field);\
 347 }\
 348 \
 349 static inline int \
 350 cust_prefix##_insert_at(cust_array_t *array, cust_item_t *item, unsigned indx)\
 351 {\
 352   return gsa_cust_insert_at(&array->cust_array_field, item, indx);\
 353 }\
 354 \
 355 static inline int \
 356 cust_prefix##_delete_at(cust_array_t *array, unsigned indx)\
 357 {\
 358   return gsa_cust_delete_at(&array->cust_array_field, indx);\
 359 }\
 360 \
 361 static inline void \
 362 cust_prefix##_delete_all(cust_array_t *array)\
 363 {\
 364   gsa_cust_delete_all(&array->cust_array_field);\
 365 }\
 366 \
 367 static inline cust_item_t *\
 368 cust_prefix##_cut_last(cust_array_t *array)\
 369 {\
 370   if(cust_prefix##_is_empty(array)) return NULL;\
 371   return (cust_item_t *)array->cust_array_field.items\
 372                           [--array->cust_array_field.count];\
 373 }\
 374 /*** Iterators ***/\
 375 GSA_IT_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t) \
 376 \
 377 static inline void \
 378 cust_prefix##_delete_it(cust_prefix##_it_t *it)\
 379 {\
 380   cust_prefix##_delete_at(it->container,it->indx);\
 381 }
 382
 383 #define GSA_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 384                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 385         GSA_CUST_DEC_SCOPE(extern, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 386                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 387
 388 /*** Declaration of static custom array with limited functions ***/
 389 #define GSA_STATIC_CUST_DEC_SCOPE(cust_scope, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 390                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 391 \
 392 GSA_BASE_CUST_DEC_SCOPE(cust_scope, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 393                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 394 \
 395 cust_scope int cust_prefix##_insert(cust_array_t *array, cust_item_t *item);\
 396 cust_scope int cust_prefix##_delete(cust_array_t *array, const cust_item_t *item);\
 397 cust_scope void cust_prefix##_init_array_field(cust_array_t *array);\
 398 cust_scope int cust_prefix##_insert_at(cust_array_t *array, cust_item_t *item, unsigned indx);\
 399 cust_scope int cust_prefix##_delete_at(cust_array_t *array, unsigned indx); \
 400 \
 401 static inline void \
 402 cust_prefix##_delete_all(cust_array_t *array)\
 403 {\
 404   array->cust_array_field.count=0;\
 405 }\
 406 \
 407 static inline cust_item_t *\
 408 cust_prefix##_cut_last(cust_array_t *array)\
 409 {\
 410   if(cust_prefix##_is_empty(array)) return NULL;\
 411   return (cust_item_t *)array->cust_array_field.items\
 412                           [--array->cust_array_field.count];\
 413 }\
 414 /*** Iterators ***/\
 415 GSA_IT_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t) \
 416 \
 417 static inline void \
 418 cust_prefix##_delete_it(cust_prefix##_it_t *it)\
 419 {\
 420   cust_prefix##_delete_at(it->container,it->indx);\
 421 }
 422
 423 #define GSA_STATIC_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 424                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 425         GSA_STATIC_CUST_DEC_SCOPE(extern, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 426                 cust_array_field, cust_item_key, cust_cmp_fnc)
 427
 428 /* The next implementation of foreaach is elegant, but can not
 429    be used in C99 non-conformant C compiler */
 430 #ifdef WITH_C99
 431
 432 #define gsa_cust_for_each(cust_prefix, array, ptr) \
 433         for(unsigned __fe_indx=cust_prefix##_first_indx(array);\
 434             (ptr=cust_prefix##_indx2item(array,__fe_indx));\
 435             __fe_indx++)
 436
 437 #define gsa_cust_for_each_rev(cust_prefix, array, ptr) \
 438         for(unsigned __fe_indx=cust_prefix##_last_indx(array);\
 439             (ptr=cust_prefix##_indx2item(array,__fe_indx));\
 440             __fe_indx--)
 441
 442 #define gsa_cust_for_each_from(cust_prefix, array, key, ptr) \
 443         for(unsigned __fe_indx=cust_prefix##_find_first_indx(array, key); \
 444             (ptr=cust_prefix##_indx2item(array,__fe_indx)); \
 445             __fe_indx++)
 446
 447 #define gsa_cust_for_each_after(cust_prefix, array, key, ptr) \
 448         for(unsigned __fe_indx=cust_prefix##_find_after_indx(array, key); \
 449             (ptr=cust_prefix##_indx2item(array,__fe_indx)); \
 450             __fe_indx++)
 451
 452 #endif /*WITH_C99*/
 453
 454 #define gsa_cust_for_each_cut(cust_prefix, array, ptr) \
 455         for(;(ptr=cust_prefix##_cut_last(array));)
 456
 457
 458 #ifdef __cplusplus
 459 } /* extern "C"*/
 460 #endif
 461
 462 #endif /* _UL_GSA_H */