ulut/ul_hptree.h

   1 /*******************************************************************
   2   uLan Utilities Library - C library of basic reusable constructions
   3
   4   ul_hptree.h  - heap tree implementation
   5
   6   (C) Copyright 2003-2004 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_HPTREE_H
  25 #define _UL_HPTREE_H
  26
  27 #ifdef __cplusplus
  28 extern "C" {
  29 #endif
  30
  31 typedef struct ul_hpt_node {
  32   long index;
  33 } ul_hpt_node_t;
  34
  35 typedef struct{
  36   ul_hpt_node_t **heaparr;
  37   long count;
  38   long capacity;
  39 } ul_hpt_root_field_t;
  40
  41 #define ul_hpt_first_i     (1)
  42 #define ul_hpt_parent_i(i) ((i)/2)
  43 #define ul_hpt_left_i(i)   ((i)*2)
  44 #define ul_hpt_right_i(i)  ((i)*2+1)
  45
  46 /* Declaration of heap tree */
  47 #define UL_HPTREE_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
  48                 cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
  49 \
  50 static inline cust_item_t * \
  51 cust_prefix##_node2item(const cust_root_t *root, const ul_hpt_node_t *node) \
  52   {return (cust_item_t*)((char*)node-(long)&((cust_item_t*)0)->cust_item_node);}\
  53 \
  54 static inline cust_key_t *\
  55 cust_prefix##_node2key(const cust_root_t *root, ul_hpt_node_t *node)\
  56   { return &(cust_prefix##_node2item(root, node)->cust_item_key);}\
  57 \
  58 int cust_prefix##_init_root_field(cust_root_t *root);\
  59 \
  60 static inline void \
  61 cust_prefix##_init_detached(cust_item_t *item){;}\
  62 \
  63 int cust_prefix##_insert(cust_root_t *root, cust_item_t *item);\
  64 cust_item_t *cust_prefix##_cut_first(cust_root_t *root);\
  65 int cust_prefix##_delete(cust_root_t *root, cust_item_t *item);\
  66 \
  67 static inline cust_item_t *\
  68 cust_prefix##_first(const cust_root_t *root)\
  69 {\
  70   ul_hpt_node_t *n;\
  71   if(!root->cust_root_field.count)\
  72     return NULL;\
  73   n=root->cust_root_field.heaparr[ul_hpt_first_i];\
  74   return cust_prefix##_node2item(root,n);\
  75 }\
  76 static inline int \
  77 cust_prefix##_is_empty(const cust_root_t *root)\
  78 {\
  79   return !root->cust_root_field.count;\
  80 }
  81
  82 #define UL_HPTREE_IMP(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
  83                 cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc,\
  84                 cust_ins_fl, cust_first_change, cust_empty_state) \
  85 \
  86 int cust_prefix##_init_root_field(cust_root_t *root)\
  87   { return ul_hpt_init_root_hpt(&root->cust_root_field, 64);}\
  88 \
  89 static inline int \
  90 cust_prefix##_cmp_hpt_i(cust_root_t *root, ul_hpt_node_t *p, ul_hpt_node_t *r)\
  91 {\
  92   return cust_cmp_fnc(cust_prefix##_node2key(root,p),\
  93                       cust_prefix##_node2key(root,r));\
  94 }\
  95 \
  96 int cust_prefix##_insert(cust_root_t *root, cust_item_t *item)\
  97 {\
  98   long i, j; \
  99   ul_hpt_node_t *p, *r;\
 100   i=root->cust_root_field.count+1;\
 101   if(i>root->cust_root_field.capacity)\
 102     if(ul_hpt_enlarge_hpt(&root->cust_root_field)<0)\
 103       return -1;\
 104   root->cust_root_field.count=i;\
 105   p=&item->cust_item_node;\
 106   while(i>ul_hpt_first_i){\
 107     j=ul_hpt_parent_i(i);\
 108     r=root->cust_root_field.heaparr[j];\
 109     if(cust_prefix##_cmp_hpt_i(root,p,r)>=0)\
 110       break;\
 111     r->index=i;\
 112     root->cust_root_field.heaparr[i]=r;\
 113     i=j;\
 114   }\
 115   p->index=i;\
 116   root->cust_root_field.heaparr[i]=p;\
 117   if(i<=ul_hpt_first_i){\
 118     cust_first_change;\
 119   }\
 120   return 1;\
 121 }\
 122 \
 123 cust_item_t *cust_prefix##_cut_first(cust_root_t *root)\
 124 {\
 125   long i, j;\
 126   ul_hpt_node_t *n, *p, *r;\
 127   if(!(i=root->cust_root_field.count))\
 128     return NULL;\
 129   \
 130   n=root->cust_root_field.heaparr[ul_hpt_first_i];\
 131   if((root->cust_root_field.count=i-1)){\
 132     p=root->cust_root_field.heaparr[i];\
 133     i=ul_hpt_first_i;\
 134     while((j=ul_hpt_left_i(i))<=root->cust_root_field.count){\
 135       r=root->cust_root_field.heaparr[j];\
 136       if(j!=root->cust_root_field.count)\
 137         if(cust_prefix##_cmp_hpt_i(root,r,root->cust_root_field.heaparr[j+1])>0)\
 138           {j++; r=root->cust_root_field.heaparr[j];}\
 139       if(cust_prefix##_cmp_hpt_i(root,p,r)<=0)\
 140         break;\
 141       r->index=i;\
 142       root->cust_root_field.heaparr[i]=r;\
 143       i=j;\
 144     }\
 145     p->index=i;\
 146     root->cust_root_field.heaparr[i]=p;\
 147     cust_first_change;\
 148   }else{\
 149     cust_empty_state;\
 150   }\
 151   return cust_prefix##_node2item(root,n);\
 152 }\
 153 \
 154 int cust_prefix##_delete(cust_root_t *root, cust_item_t *item)\
 155 {\
 156   long i, j;\
 157   ul_hpt_node_t *p, *r;\
 158   p=&item->cust_item_node;\
 159   i=p->index;\
 160   if(i>root->cust_root_field.count) return -1;\
 161   if(root->cust_root_field.heaparr[i]!=p) return -1;\
 162   if(i==ul_hpt_first_i){\
 163     cust_prefix##_cut_first(root);\
 164     return 1;\
 165   }\
 166   if(i==(j=root->cust_root_field.count--))\
 167     return 0;\
 168   p=root->cust_root_field.heaparr[j];\
 169   j=ul_hpt_parent_i(i);\
 170   r=root->cust_root_field.heaparr[j];\
 171   if(cust_prefix##_cmp_hpt_i(root,p,r)<0){\
 172     do{\
 173       r->index=i;\
 174       root->cust_root_field.heaparr[i]=r;\
 175       i=j;\
 176       j=ul_hpt_parent_i(i);\
 177       r=root->cust_root_field.heaparr[j];\
 178       if(cust_prefix##_cmp_hpt_i(root,p,r)>=0)\
 179         break;\
 180     }while(1);\
 181   }else{\
 182     while((j=ul_hpt_left_i(i))<=root->cust_root_field.count){\
 183       r=root->cust_root_field.heaparr[j];\
 184       if(j!=root->cust_root_field.count)\
 185         if(cust_prefix##_cmp_hpt_i(root,r,root->cust_root_field.heaparr[j+1])>0)\
 186           {j++; r=root->cust_root_field.heaparr[j];}\
 187       if(cust_prefix##_cmp_hpt_i(root,p,r)<=0)\
 188         break;\
 189       r->index=i;\
 190       root->cust_root_field.heaparr[i]=r;\
 191       i=j;\
 192     }\
 193   }\
 194   p->index=i;\
 195   root->cust_root_field.heaparr[i]=p;\
 196   return 1;\
 197 }
 198
 199 int ul_hpt_init_root_hpt(ul_hpt_root_field_t *hpt_root, int acapacity);
 200 int ul_hpt_enlarge_hpt(ul_hpt_root_field_t *hpt_root);
 201
 202 #ifdef __cplusplus
 203 } /* extern "C"*/
 204 #endif
 205
 206 #endif /* _UL_HPTREE_H */