ulut/ul_gsacust.h

   1 /*******************************************************************
   2   uLan Utilities Library - C library of basic reusable constructions
   3
   4   ul_gsacust.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_GSACUST_H
  25 #define _UL_GSACUST_H
  26
  27 #include "ul_gsa.h"
  28
  29 #ifdef __cplusplus
  30 extern "C" {
  31 #endif
  32
  33 /* Constant version of custom GSA arrays. It does not support runtime modifications. */
  34 #define GSA_CONST_CUST_IMP(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
  35                 cust_array_field, cust_item_key, cust_cmp_fnc, cust_ins_fl) \
  36 \
  37 int \
  38 cust_prefix##_bsearch_indx(const cust_array_t *array, cust_key_t const *key, \
  39                            int mode, unsigned *indx) \
  40 {\
  41   unsigned a, b, c;\
  42   int r;\
  43   if(!array->cust_array_field.items || !array->cust_array_field.count){\
  44     *indx=0;\
  45     return 0;\
  46   }\
  47   a=0;\
  48   b=array->cust_array_field.count;\
  49   while(1){\
  50     c=(a+b)/2;\
  51     r=cust_cmp_fnc(cust_prefix##_indx2key(array, c), key);\
  52     if(!r) if(!(mode&GSA_FAFTER)) break;\
  53     if(r<=0)\
  54       a=c+1;\
  55      else\
  56       b=c;\
  57     if(a==b){\
  58       *indx=a;\
  59       return mode&GSA_FAFTER;\
  60     }\
  61   }\
  62   if(mode&GSA_FFIRST){\
  63     /* equal items can be in range a to b-1 */\
  64     /* routine looks for first one */\
  65     b=c;\
  66     do{\
  67       c=(a+b)/2;\
  68       r=cust_cmp_fnc(cust_prefix##_indx2key(array, c), key);\
  69       if(r)\
  70         a=c+1;\
  71        else\
  72         b=c;\
  73     }while(a!=b);\
  74     c=b;\
  75   }\
  76   *indx=c;\
  77   return 1;\
  78 }
  79
  80
  81 /* Dynamic version with full support of insert and delete functions. */
  82 #define GSA_CUST_IMP(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
  83                 cust_array_field, cust_item_key, cust_cmp_fnc, cust_ins_fl) \
  84 \
  85 GSA_CONST_CUST_IMP(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
  86         cust_array_field, cust_item_key, cust_cmp_fnc, cust_ins_fl) \
  87 \
  88 int \
  89 cust_prefix##_insert(cust_array_t *array, cust_item_t *item)\
  90 {\
  91   unsigned indx;\
  92   if(cust_prefix##_bsearch_indx(array, &item->cust_item_key, cust_ins_fl, &indx))\
  93     if(!cust_ins_fl) return -1;\
  94   return cust_prefix##_insert_at(array,item,indx);\
  95 }\
  96 \
  97 int \
  98 cust_prefix##_delete(cust_array_t *array, const cust_item_t *item)\
  99 {\
 100   unsigned indx;\
 101   if(!cust_prefix##_bsearch_indx(array, &item->cust_item_key, GSA_FFIRST,&indx))\
 102     return -1;\
 103   while(cust_prefix##_indx2item(array, indx)!=item){\
 104     if(++indx>=array->cust_array_field.count) return -1;\
 105     if(cust_cmp_fnc(cust_prefix##_indx2key(array, indx),\
 106                     &item->cust_item_key))  return -1;\
 107   }\
 108   return cust_prefix##_delete_at(array,indx);\
 109 }
 110
 111
 112 /* Static version with limited support of insert and delete functions. */
 113 #define GSA_STATIC_CUST_IMP(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 114                 cust_array_field, cust_item_key, cust_cmp_fnc, cust_ins_fl) \
 115 \
 116 GSA_CUST_IMP(cust_prefix, cust_array_t, cust_item_t, cust_key_t,\
 117         cust_array_field, cust_item_key, cust_cmp_fnc, cust_ins_fl) \
 118 \
 119 void \
 120 cust_prefix##_init_array_field(cust_array_t *array)\
 121 {\
 122   array->cust_array_field.count=0;\
 123   array->cust_array_field.alloc_count=0;\
 124   array->cust_array_field.items=NULL;\
 125 }\
 126 \
 127 int \
 128 cust_prefix##_insert_at(cust_array_t *array, cust_item_t *item, unsigned indx)\
 129 {\
 130   unsigned cnt=array->cust_array_field.count; \
 131   cust_item_t **p; \
 132 \
 133   if(indx>cnt) indx=cnt;\
 134   if(cnt+1>=array->cust_array_field.alloc_count)\
 135     return -1;\
 136 \
 137   p=array->cust_array_field.items+indx;\
 138   memmove(p+1,p,(char*)(array->cust_array_field.items+cnt)-(char*)p);\
 139   array->cust_array_field.count=cnt+1;\
 140   *p=item;\
 141   return 0;\
 142 }\
 143 \
 144 int \
 145 cust_prefix##_delete_at(cust_array_t *array, unsigned indx)\
 146 {\
 147   unsigned cnt=array->cust_array_field.count;\
 148   cust_item_t **p;\
 149   if(indx>=cnt) return -1;\
 150   p=array->cust_array_field.items+indx;\
 151   array->cust_array_field.count=--cnt;\
 152   memmove(p,p+1,(array->cust_array_field.items+cnt-p)*sizeof(void *));\
 153   return 0;\
 154 }\
 155
 156
 157 #ifdef __cplusplus
 158 } /* extern "C"*/
 159 #endif
 160
 161 #endif /* _UL_GSACUST_H */