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 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   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 const *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 const *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 const *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 const custom array without support of runtime modifications */
 319 #define GSA_CONST_CUST_DEC_SCOPE(cust_scope, 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_SCOPE(cust_scope, 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 #define GSA_CONST_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 328                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 329         GSA_CONST_CUST_DEC_SCOPE(extern, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 330                 cust_array_field, cust_item_key, cust_cmp_fnc)
 331
 332 /*** Declaration of dynamic custom array with full functions ***/
 333 #define GSA_CUST_DEC_SCOPE(cust_scope, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 334                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 335 \
 336 GSA_BASE_CUST_DEC_SCOPE(cust_scope, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 337                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 338 \
 339 cust_scope int cust_prefix##_insert(cust_array_t *array, cust_item_t *item);\
 340 cust_scope int cust_prefix##_delete(cust_array_t *array, const cust_item_t *item);\
 341 \
 342 static inline void \
 343 cust_prefix##_init_array_field(cust_array_t *array)\
 344 {\
 345   gsa_cust_init_array_field(&array->cust_array_field);\
 346 }\
 347 \
 348 static inline int \
 349 cust_prefix##_insert_at(cust_array_t *array, cust_item_t *item, unsigned indx)\
 350 {\
 351   return gsa_cust_insert_at(&array->cust_array_field, item, indx);\
 352 }\
 353 \
 354 static inline int \
 355 cust_prefix##_delete_at(cust_array_t *array, unsigned indx)\
 356 {\
 357   return gsa_cust_delete_at(&array->cust_array_field, indx);\
 358 }\
 359 \
 360 static inline void \
 361 cust_prefix##_delete_all(cust_array_t *array)\
 362 {\
 363   gsa_cust_delete_all(&array->cust_array_field);\
 364 }\
 365 \
 366 static inline cust_item_t *\
 367 cust_prefix##_cut_last(cust_array_t *array)\
 368 {\
 369   if(cust_prefix##_is_empty(array)) return NULL;\
 370   return (cust_item_t *)array->cust_array_field.items\
 371                           [--array->cust_array_field.count];\
 372 }\
 373 /*** Iterators ***/\
 374 GSA_IT_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t) \
 375 \
 376 static inline void \
 377 cust_prefix##_delete_it(cust_prefix##_it_t *it)\
 378 {\
 379   cust_prefix##_delete_at(it->container,it->indx);\
 380 }
 381
 382 #define GSA_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 383                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 384         GSA_CUST_DEC_SCOPE(extern, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 385                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 386
 387 /*** Declaration of static custom array with limited functions ***/
 388 #define GSA_STATIC_CUST_DEC_SCOPE(cust_scope, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 389                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 390 \
 391 GSA_BASE_CUST_DEC_SCOPE(cust_scope, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 392                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 393 \
 394 cust_scope int cust_prefix##_insert(cust_array_t *array, cust_item_t *item);\
 395 cust_scope int cust_prefix##_delete(cust_array_t *array, const cust_item_t *item);\
 396 cust_scope void cust_prefix##_init_array_field(cust_array_t *array);\
 397 cust_scope int cust_prefix##_insert_at(cust_array_t *array, cust_item_t *item, unsigned indx);\
 398 cust_scope int cust_prefix##_delete_at(cust_array_t *array, unsigned indx); \
 399 \
 400 static inline void \
 401 cust_prefix##_delete_all(cust_array_t *array)\
 402 {\
 403   array->cust_array_field.count=0;\
 404 }\
 405 \
 406 static inline cust_item_t *\
 407 cust_prefix##_cut_last(cust_array_t *array)\
 408 {\
 409   if(cust_prefix##_is_empty(array)) return NULL;\
 410   return (cust_item_t *)array->cust_array_field.items\
 411                           [--array->cust_array_field.count];\
 412 }\
 413 /*** Iterators ***/\
 414 GSA_IT_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t) \
 415 \
 416 static inline void \
 417 cust_prefix##_delete_it(cust_prefix##_it_t *it)\
 418 {\
 419   cust_prefix##_delete_at(it->container,it->indx);\
 420 }
 421
 422 #define GSA_STATIC_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 423                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 424         GSA_STATIC_CUST_DEC_SCOPE(extern, cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 425                 cust_array_field, cust_item_key, cust_cmp_fnc)
 426
 427 /* The next implementation of foreaach is elegant, but can not
 428    be used in C99 non-conformant C compiler */
 429 #ifdef WITH_C99
 430
 431 #define gsa_cust_for_each(cust_prefix, array, ptr) \
 432         for(unsigned __fe_indx=cust_prefix##_first_indx(array);\
 433             (ptr=cust_prefix##_indx2item(array,__fe_indx));\
 434             __fe_indx++)
 435
 436 #define gsa_cust_for_each_rev(cust_prefix, array, ptr) \
 437         for(unsigned __fe_indx=cust_prefix##_last_indx(array);\
 438             (ptr=cust_prefix##_indx2item(array,__fe_indx));\
 439             __fe_indx--)
 440
 441 #define gsa_cust_for_each_from(cust_prefix, array, key, ptr) \
 442         for(unsigned __fe_indx=cust_prefix##_find_first_indx(array, key); \
 443             (ptr=cust_prefix##_indx2item(array,__fe_indx)); \
 444             __fe_indx++)
 445
 446 #define gsa_cust_for_each_after(cust_prefix, array, key, ptr) \
 447         for(unsigned __fe_indx=cust_prefix##_find_after_indx(array, key); \
 448             (ptr=cust_prefix##_indx2item(array,__fe_indx)); \
 449             __fe_indx++)
 450
 451 #endif /*WITH_C99*/
 452
 453 #define gsa_cust_for_each_cut(cust_prefix, array, ptr) \
 454         for(;(ptr=cust_prefix##_cut_last(array));)
 455
 456
 457 #ifdef __cplusplus
 458 } /* extern "C"*/
 459 #endif
 460
 461 #endif /* _UL_GSA_H */