home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume24 / yabbawhap / part03 / huptrie.h < prev    next >
C/C++ Source or Header  |  1991-10-09  |  7KB  |  240 lines
  1. /* Placed into the public domain by Daniel J. Bernstein. */
  2.  
  3. #ifndef HUPTRIE_H
  4. #define HUPTRIE_H
  5.  
  6. /* Ever seen an efficient data structure library? You're about to. */
  7.  
  8. /* Yes, folks, I have some documentation for this; I'm just not sure */
  9. /* that the library is ready for general release yet. If you're */
  10. /* desperate for huptries in an application and *need* to use this */
  11. /* library *now*, let me know. */
  12.  
  13. /*#defines: PTRS, TYPE, HASHTYPE, ZEROFILLED, BZERO, MEMZERO, OPTCANT{1,2,5}.*/
  14. /* HASHPTRS. */
  15.  
  16. #ifndef HASHTYPE
  17. #define HASHTYPE TYPE
  18. #endif
  19.  
  20. typedef unsigned TYPE pos;
  21.  
  22. #ifdef PTRS
  23. typedef struct nod { struct nod *p; struct nod *n; } *node;
  24. typedef struct nod *next;
  25. typedef int * /*XXX: irrelevant*/ parent;
  26. #else
  27. typedef pos node;
  28. typedef node *next;
  29. typedef node *parent;
  30. #endif
  31.  
  32. #ifdef HASHPTRS
  33. typedef struct hod { node n; struct hod *h; } htt;
  34. typedef struct hod *hash;
  35. #define HASHP 255
  36. #define HANO(h,sh) ((sh)->n)
  37. #else
  38. typedef node htt;
  39. typedef unsigned HASHTYPE hash;
  40. #define HASHP 0
  41. #define HANO(h,sh) ((h)[sh])
  42. #endif
  43.  
  44. typedef htt *hashtable;
  45. typedef pos ipos;
  46.  
  47. /* A huptrie consists of:
  48.    next n; parent p; hashtable h;
  49.    ipos m; pos sm; pos l1; hash h1; 
  50. */
  51.  
  52. #define TOPHASH 5381
  53.  
  54. #ifdef HASHPTRS
  55. #define hh(sh,sch,h1) (please do not use this yet, XXX)
  56. #define hc(sh,c,h1) (sh[(unsigned char) c].h)
  57. #else
  58. #define hh(sh,sch,h1) (((sch) - (((sh) << 5) + (sh))) & (h1))
  59. #define hc(sh,c,h1) ((((sh) << 5) + (sh) + ((hash) (unsigned char) (c))) & (h1))
  60. #endif
  61.  
  62. #ifdef PTRS
  63. #define NEXT(ne,no) ((no)->n)
  64. #define PARENT(pa,no) ((no)->p)
  65. #define AVAIL(ne) ((ne)[0].n)
  66. #define NODEBYN(ne,po) ((ne) + (po))
  67. #else
  68. #define NEXT(ne,no) ((ne)[no])
  69. #define PARENT(pa,no) ((pa)[no])
  70. #define AVAIL(ne) ((ne)[0])
  71. #define NODEBYN(ne,po) (po)
  72. #endif
  73.  
  74. /* INIT, HUP_DELETE, DOWN are block statements. */
  75.  
  76. /* n,p,h,m,sm are by address */
  77. #ifdef PTRS
  78. #define INIT(n,p,h,m,sm,l1,h1) \
  79. { (n) = malloc(sizeof(struct nod) * ((l1) + 1)); AVAIL(n) = 0; \
  80.  (h) = (hashtable) malloc(sizeof(htt) * ((h1) + HASHP + 1)); \
  81.  CLEARHASH(h,h1); FIRSTHASH(h,h1); (m) = (l1) + 1; (sm) = -1; }
  82. #define STATICDECLARE(n,p,h,l1,h1) \
  83.   struct nod (n)[(l1) + 1]; parent (p); htt (h)[(h1) + HASHP + 1];
  84. #else
  85. #define INIT(n,p,h,m,sm,l1,h1) \
  86. { (n) = (next) malloc(sizeof(node) * ((l1) + 1)); AVAIL(n) = 0; \
  87.  (p) = (parent) malloc(sizeof(node) * ((l1) + 1)); \
  88.  (h) = (hashtable) malloc(sizeof(htt) * ((h1) + HASHP + 1)); \
  89.  CLEARHASH(h,h1); FIRSTHASH(h,h1); (m) = (l1) + 1; (sm) = -1; }
  90. #define STATICDECLARE(n,p,h,l1,h1) \
  91.   node (n)[(l1) + 1]; node (p)[(l1) + 1]; htt (h)[(h1) + HASHP + 1];
  92. #endif
  93.  
  94. #define STATICINIT(n,p,h,m,sm,l1,h1) \
  95. { INITHASH(h,h1); AVAIL(n) = 0; (m) = (l1) + 1; (sm) = -1; }
  96. /* FIRSTHASH(h,h1)  XXX*/
  97.  
  98. #ifdef HASHPTRS
  99. #define FIRSTHASH(h,h1) { hash ha; ha = (h) + ((h1) + HASHP + 1); \
  100. do { --ha; ha->h = (h) + ((((ha - h) << 5) + (ha - h)) & (h1)); } \
  101. while (ha != (h)); }
  102. #else
  103. #define FIRSTHASH(h,h1) ;
  104. #endif
  105.  
  106. #ifdef ZEROFILLED
  107. #define INITHASH(h,h1) ;
  108. #else
  109. #define INITHASH(h,h1) CLEARHASH(h,h1);
  110. #endif
  111.  
  112. #ifdef HASHPTRS
  113. #define CLEARHASH(h,h1) { hash ha; ha = (h) + ((h1) + 1); do HANO(h,--ha) = 0; while (ha != (h)); }
  114. /* XXX: if -UZEROFILLED, this is unnecessarily inefficient on the first CLEARHASH */
  115. #else
  116. #ifdef BZERO
  117. #define CLEARHASH(h,h1) (void) bzero((char *) (h),sizeof(node) * ((h1) + 1));
  118. #else
  119. #ifdef MEMZERO
  120. #define CLEARHASH(h,h1) (void) memset((char *) (h),0,sizeof(node) * ((h1) + 1));
  121. #else
  122. #define CLEARHASH(h,h1) { hash ha; ha = (h1) + 1; do HANO(h,--ha) = 0; while (ha); }
  123. #endif
  124. #endif
  125. #endif
  126.  
  127.  
  128. /* sm and newnode are by address */
  129. #define ADDAVAIL(n,p,h,sm,sp,sch,newnode) \
  130. ( --(sm), (newnode = AVAIL(n)), (AVAIL(n) = NEXT(n,newnode)), \
  131.  (PARENT(p,newnode) = (sp)), \
  132.  (NEXT(n,newnode) = HANO(h,sch)), (HANO(h,sch) = (newnode)) )
  133.  
  134. /* m, sm, newnode are by address */
  135. #define WASTEMAX(n,p,h,m,sm,newnode) \
  136. ( (++(sm)), (newnode = NODEBYN(n,--(m))), (PARENT(p,newnode) = 0), \
  137.  (NEXT(n,newnode) = AVAIL(n)), (AVAIL(n) = (newnode)) )
  138.  
  139. /* m and newnode are by address */
  140. #define ADDMAX(n,p,h,m,sp,sch,newnode) \
  141. ( (newnode = NODEBYN(n,--(m))), (PARENT(p,newnode) = (sp)), \
  142.  (NEXT(n,newnode) = HANO(h,sch)), (HANO(h,sch) = (newnode)) )
  143.  
  144. /* sm and noptr are by address */
  145. #define HUP_DELETE(n,p,h,sm,sp,sh,noptr) \
  146. { (noptr) = &(HANO(h,sh)); while (*(noptr) != (sp)) (noptr) = &(NEXT(n,*(noptr))); \
  147.  *(noptr) = NEXT(n,sp); PARENT(p,sp) = 0; NEXT(n,sp) = AVAIL(n); \
  148.  AVAIL(n) = (sp); ++(sm); }
  149.  
  150. /* no is by address, FOUND and NOTFOUND are formal */
  151. /* XXX: Reorganize hash lists? */
  152. #define DOWN2(n,p,h,sp,sch,no,FOUND,NOTFOUND) { \
  153.  if ((no) = HANO(h,sch)) { if (PARENT(p,no) != (sp)) { \
  154.  if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
  155.  if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
  156.    do (no) = NEXT(n,no); while ((no) && (PARENT(p,no) != (sp))); \
  157.    if (no) { FOUND } else { NOTFOUND } \
  158.  } else { FOUND } } else { NOTFOUND } \
  159.  } else { FOUND } } else { NOTFOUND } \
  160.  } else { FOUND } } else { NOTFOUND } \
  161. }
  162.  
  163. #define DOWN1(n,p,h,sp,sch,no,FOUND,NOTFOUND) { \
  164.  if ((no) = HANO(h,sch)) { if (PARENT(p,no) != (sp)) { \
  165.  if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
  166.    do (no) = NEXT(n,no); while ((no) && (PARENT(p,no) != (sp))); \
  167.    if (no) { FOUND } else { NOTFOUND } \
  168.  } else { FOUND } } else { NOTFOUND } \
  169.  } else { FOUND } } else { NOTFOUND } \
  170. }
  171.  
  172. #define DOWN0(n,p,h,sp,sch,no,FOUND,NOTFOUND) { \
  173.  if ((no) = HANO(h,sch)) { if (PARENT(p,no) != (sp)) { \
  174.    do (no) = NEXT(n,no); while ((no) && (PARENT(p,no) != (sp))); \
  175.    if (no) { FOUND } else { NOTFOUND } \
  176.  } else { FOUND } } else { NOTFOUND } \
  177. }
  178.  
  179. #define DOWN5(n,p,h,sp,sch,no,FOUND,NOTFOUND) { \
  180.  if ((no) = HANO(h,sch)) { if (PARENT(p,no) != (sp)) { \
  181.  if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
  182.  if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
  183.  if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
  184.  if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
  185.  if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
  186.    do (no) = NEXT(n,no); while ((no) && (PARENT(p,no) != (sp))); \
  187.    if (no) { FOUND } else { NOTFOUND } \
  188.  } else { FOUND } } else { NOTFOUND } \
  189.  } else { FOUND } } else { NOTFOUND } \
  190.  } else { FOUND } } else { NOTFOUND } \
  191.  } else { FOUND } } else { NOTFOUND } \
  192.  } else { FOUND } } else { NOTFOUND } \
  193.  } else { FOUND } } else { NOTFOUND } \
  194. }
  195.  
  196. #ifdef OPTCANT1
  197. #define DOWN DOWN0
  198. #define DOWNI DOWN0
  199. #else
  200. #ifdef OPTCANT2
  201. #define DOWN DOWN1
  202. #define DOWNI DOWN1
  203. #else
  204. #ifdef OPTCANT5
  205. #define DOWN DOWN2
  206. #define DOWNI DOWN2
  207. #else
  208. #define DOWN DOWN5
  209. #define DOWNI DOWN2
  210. #endif
  211. #endif
  212. #endif
  213.  
  214. #define hup_parent(p,no) PARENT(p,no)
  215. #define setparent(p,scp,sp) (PARENT(p,scp) = (sp))
  216. #ifdef HASHPTRS
  217. #define tophash(h,h1) ((h) + (TOPHASH & (h1)))
  218. #else
  219. #define tophash(h,h1) (TOPHASH & (h1))
  220. #endif
  221. #define topnode(n,l1) (NODEBYN(n,(l1) + 1))
  222. #define Hmax(m,l1) ((l1) - (m))
  223. #define size(m,sm,l1) (((l1) - (m)) - (sm))
  224. #define limitm1(l1) (l1)
  225. #define ipos2pos(n,ip,l1) ((l1) - (ip))
  226. #define pos2ipos(n,po,l1) ((l1) - (po))
  227.  
  228. #ifdef PTRS
  229. #define node2pos(n,no,l1) ((l1) - ((no) - (n)))
  230. #define node2ipos(n,no,l1) ((no) - (n))
  231. #else
  232. #define node2pos(n,no,l1) ((l1) - (no))
  233. #define node2ipos(n,no,l1) (no)
  234. #endif
  235.  
  236. #define ipos2node(n,ip,l1) (NODEBYN(n,ip))
  237. #define pos2node(n,po,l1) (NODEBYN(n,(l1) - (po)))
  238.  
  239. #endif
  240.