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
 150
 151 /* User must provide his/her own compare routine with
 152     int cust_cmp_fnc(cust_key_t *a, cust_key_t *b) */
 153
 154 /*** Base declaration of custom GSA array  ***/
 155 #define GSA_BASE_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 156                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 157 \
 158 static inline cust_item_t * \
 159 cust_prefix##_indx2item(const cust_array_t *array, unsigned indx) \
 160 {\
 161   if(indx>=array->cust_array_field.count) return NULL;\
 162   return (cust_item_t*)array->cust_array_field.items[indx];\
 163 }\
 164 \
 165 static inline cust_key_t *\
 166 cust_prefix##_indx2key(const cust_array_t *array, unsigned indx)\
 167   { return &(cust_prefix##_indx2item(array, indx)->cust_item_key);}\
 168 \
 169 int cust_prefix##_bsearch_indx(const cust_array_t *array, const cust_key_t *key, int mode, unsigned *indxp);\
 170 \
 171 static inline  cust_item_t *\
 172 cust_prefix##_at(const cust_array_t *array, unsigned indx)\
 173 {\
 174   return cust_prefix##_indx2item(array, indx);\
 175 }\
 176 \
 177 static inline cust_item_t *\
 178 cust_prefix##_find(const cust_array_t *array, cust_key_t *key)\
 179 {\
 180   unsigned indx;\
 181   if(!cust_prefix##_bsearch_indx(array, key, 0, &indx)) return NULL;\
 182   return cust_prefix##_indx2item(array, indx);\
 183 }\
 184 \
 185 static inline cust_item_t *\
 186 cust_prefix##_find_first(const cust_array_t *array, cust_key_t *key)\
 187 {\
 188   unsigned indx;\
 189   if(!cust_prefix##_bsearch_indx(array, key, GSA_FFIRST, &indx)) return NULL;\
 190   return cust_prefix##_indx2item(array, indx);\
 191 }\
 192 \
 193 static inline unsigned \
 194 cust_prefix##_find_first_indx(const cust_array_t *array, cust_key_t *key)\
 195 {\
 196   unsigned indx;\
 197   if(!cust_prefix##_bsearch_indx(array, key, GSA_FFIRST, &indx)) return -1;\
 198   return indx;\
 199 }\
 200 \
 201 static inline cust_item_t *\
 202 cust_prefix##_find_after(const cust_array_t *array, cust_key_t *key)\
 203 {\
 204   unsigned indx;\
 205   if(!cust_prefix##_bsearch_indx(array, key, GSA_FAFTER, &indx)) return NULL;\
 206   return cust_prefix##_indx2item(array, indx);\
 207 }\
 208 \
 209 static inline unsigned \
 210 cust_prefix##_find_after_indx(const cust_array_t *array, cust_key_t *key)\
 211 {\
 212   unsigned indx;\
 213   cust_prefix##_bsearch_indx(array, key, GSA_FAFTER, &indx);\
 214   return indx;\
 215 }\
 216 \
 217 static inline int \
 218 cust_prefix##_is_empty(const cust_array_t *array)\
 219 {\
 220   return !array->cust_array_field.count;\
 221 }\
 222 \
 223 static inline cust_item_t *\
 224 cust_prefix##_first(const cust_array_t *array)\
 225 {\
 226   return cust_prefix##_indx2item(array, 0);\
 227 }\
 228 \
 229 static inline unsigned \
 230 cust_prefix##_first_indx(const cust_array_t *array)\
 231 {\
 232   return 0;\
 233 }\
 234 \
 235 static inline cust_item_t *\
 236 cust_prefix##_last(const cust_array_t *array)\
 237 {\
 238   return cust_prefix##_indx2item(array, array->cust_array_field.count-1);\
 239 }\
 240 \
 241 static inline unsigned \
 242 cust_prefix##_last_indx(const cust_array_t *array)\
 243 {\
 244   return array->cust_array_field.count-1;\
 245 }
 246
 247 /*** Iterators for GSA arrays ***/
 248 #define GSA_IT_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t) \
 249 \
 250 typedef struct {\
 251   cust_array_t *container;\
 252   unsigned indx;\
 253 } cust_prefix##_it_t;\
 254 \
 255 static inline cust_item_t *\
 256 cust_prefix##_it2item(const cust_prefix##_it_t *it)\
 257 {\
 258   return cust_prefix##_indx2item(it->container,it->indx);\
 259 }\
 260 \
 261 static inline void \
 262 cust_prefix##_first_it(cust_array_t *container, cust_prefix##_it_t *it)\
 263 {\
 264   it->container=container;\
 265   it->indx=cust_prefix##_first_indx(container);\
 266 }\
 267 \
 268 static inline void \
 269 cust_prefix##_last_it(cust_array_t *container, cust_prefix##_it_t *it)\
 270 {\
 271   it->container=container;\
 272   it->indx=cust_prefix##_last_indx(container);\
 273 }\
 274 \
 275 static inline void \
 276 cust_prefix##_next_it(cust_prefix##_it_t *it)\
 277 {\
 278   if(it->indx<=cust_prefix##_last_indx(it->container)) it->indx++;\
 279   else it->indx=cust_prefix##_first_indx(it->container);\
 280 }\
 281 \
 282 static inline void \
 283 cust_prefix##_prev_it(cust_prefix##_it_t *it)\
 284 {\
 285   if(it->indx<=cust_prefix##_last_indx(it->container)) it->indx--;\
 286   else it->indx=cust_prefix##_first_indx(it->container);\
 287 }\
 288 \
 289 static inline int \
 290 cust_prefix##_is_end_it(cust_prefix##_it_t *it)\
 291 {\
 292   if(!it->container) return 1;\
 293   return it->indx>cust_prefix##_last_indx(it->container);\
 294 }\
 295 \
 296 static inline int \
 297 cust_prefix##_find_it(cust_array_t *container, cust_key_t *key, cust_prefix##_it_t *it)\
 298 {\
 299   it->container=container;\
 300   return (it->indx=cust_prefix##_find_first_indx(container, key))!=(unsigned)-1;\
 301 }\
 302 \
 303 static inline int \
 304 cust_prefix##_find_first_it(cust_array_t *container, cust_key_t *key, cust_prefix##_it_t *it)\
 305 {\
 306   it->container=container;\
 307   return (it->indx=cust_prefix##_find_first_indx(container, key))!=(unsigned)-1;\
 308 }\
 309 \
 310 static inline int \
 311 cust_prefix##_find_after_it(cust_array_t *container, cust_key_t *key, cust_prefix##_it_t *it)\
 312 {\
 313   it->container=container;\
 314   return (it->indx=cust_prefix##_find_after_indx(container, key))!=(unsigned)-1;\
 315 }
 316
 317 /* Declaration of new static custom array without support of runtime modifications */
 318 #define GSA_STATIC_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 319                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 320 \
 321 GSA_BASE_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 322                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 323 \
 324 GSA_IT_CUST_DEC(cust_prefix, const cust_array_t, cust_item_t, cust_key_t)
 325
 326 /*** Declaration of dynamic custom array with  ***/
 327 #define GSA_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 328                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 329 \
 330 GSA_BASE_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 331                 cust_array_field, cust_item_key, cust_cmp_fnc) \
 332 \
 333 int cust_prefix##_insert(cust_array_t *array, cust_item_t *item);\
 334 int cust_prefix##_delete(cust_array_t *array, const cust_item_t *item);\
 335 \
 336 static inline void \
 337 cust_prefix##_init_array_field(cust_array_t *array)\
 338 {\
 339   gsa_cust_init_array_field(&array->cust_array_field);\
 340 }\
 341 \
 342 static inline int \
 343 cust_prefix##_insert_at(cust_array_t *array, cust_item_t *item, unsigned indx)\
 344 {\
 345   return gsa_cust_insert_at(&array->cust_array_field, item, indx);\
 346 }\
 347 \
 348 static inline int \
 349 cust_prefix##_delete_at(cust_array_t *array, unsigned indx)\
 350 {\
 351   return gsa_cust_delete_at(&array->cust_array_field, indx);\
 352 }\
 353 \
 354 static inline cust_item_t *\
 355 cust_prefix##_cut_last(cust_array_t *array)\
 356 {\
 357   if(cust_prefix##_is_empty(array)) return NULL;\
 358   return (cust_item_t *)array->cust_array_field.items\
 359                           [--array->cust_array_field.count];\
 360 }\
 361 /*** Iterators ***/\
 362 GSA_IT_CUST_DEC(cust_prefix, cust_array_t, cust_item_t, cust_key_t) \
 363 \
 364 static inline void \
 365 cust_prefix##_delete_it(cust_prefix##_it_t *it)\
 366 {\
 367   cust_prefix##_delete_at(it->container,it->indx);\
 368 }\
 369
 370
 371 /* The next implementation of foreaach is elegant, but can not
 372    be used in C99 non-conformant C compiler */
 373 #ifdef WITH_C99
 374
 375 #define gsa_cust_for_each(cust_prefix, array, ptr) \
 376         for(unsigned __fe_indx=cust_prefix##_first_indx(array);\
 377             (ptr=cust_prefix##_indx2item(array,__fe_indx));\
 378             __fe_indx++)
 379
 380 #define gsa_cust_for_each_rev(cust_prefix, array, ptr) \
 381         for(unsigned __fe_indx=cust_prefix##_last_indx(array);\
 382             (ptr=cust_prefix##_indx2item(array,__fe_indx));\
 383             __fe_indx--)
 384
 385 #define gsa_cust_for_each_from(cust_prefix, array, key, ptr) \
 386         for(unsigned __fe_indx=cust_prefix##_find_first_indx(array, key); \
 387             (ptr=cust_prefix##_indx2item(array,__fe_indx)); \
 388             __fe_indx++)
 389
 390 #define gsa_cust_for_each_after(cust_prefix, array, key, ptr) \
 391         for(unsigned __fe_indx=cust_prefix##_find_after_indx(array, key); \
 392             (ptr=cust_prefix##_indx2item(array,__fe_indx)); \
 393             __fe_indx++)
 394
 395 #endif /*WITH_C99*/
 396
 397 #define gsa_cust_for_each_cut(cust_prefix, array, ptr) \
 398         for(;(ptr=cust_prefix##_cut_last(array));)
 399
 400
 401 #ifdef __cplusplus
 402 } /* extern "C"*/
 403 #endif
 404
 405 #endif /* _UL_GSA_H */