Вы не можете выбрать более 25 тем Темы должны начинаться с буквы или цифры, могут содержать дефисы(-) и должны содержать не более 35 символов.

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238
  1. /* $Header: hash.c,v 1.0 87/12/18 13:05:17 root Exp $
  2. *
  3. * $Log: hash.c,v $
  4. * Revision 1.0 87/12/18 13:05:17 root
  5. * Initial revision
  6. *
  7. */
  8. #include <stdio.h>
  9. #include "EXTERN.h"
  10. #include "handy.h"
  11. #include "util.h"
  12. #include "search.h"
  13. #include "perl.h"
  14. STR *
  15. hfetch(tb,key)
  16. register HASH *tb;
  17. char *key;
  18. {
  19. register char *s;
  20. register int i;
  21. register int hash;
  22. register HENT *entry;
  23. if (!tb)
  24. return Nullstr;
  25. for (s=key, i=0, hash = 0;
  26. /* while */ *s;
  27. s++, i++, hash *= 5) {
  28. hash += *s * coeff[i];
  29. }
  30. entry = tb->tbl_array[hash & tb->tbl_max];
  31. for (; entry; entry = entry->hent_next) {
  32. if (entry->hent_hash != hash) /* strings can't be equal */
  33. continue;
  34. if (strNE(entry->hent_key,key)) /* is this it? */
  35. continue;
  36. return entry->hent_val;
  37. }
  38. return Nullstr;
  39. }
  40. bool
  41. hstore(tb,key,val)
  42. register HASH *tb;
  43. char *key;
  44. STR *val;
  45. {
  46. register char *s;
  47. register int i;
  48. register int hash;
  49. register HENT *entry;
  50. register HENT **oentry;
  51. if (!tb)
  52. return FALSE;
  53. for (s=key, i=0, hash = 0;
  54. /* while */ *s;
  55. s++, i++, hash *= 5) {
  56. hash += *s * coeff[i];
  57. }
  58. oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  59. i = 1;
  60. for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
  61. if (entry->hent_hash != hash) /* strings can't be equal */
  62. continue;
  63. if (strNE(entry->hent_key,key)) /* is this it? */
  64. continue;
  65. safefree((char*)entry->hent_val);
  66. entry->hent_val = val;
  67. return TRUE;
  68. }
  69. entry = (HENT*) safemalloc(sizeof(HENT));
  70. entry->hent_key = savestr(key);
  71. entry->hent_val = val;
  72. entry->hent_hash = hash;
  73. entry->hent_next = *oentry;
  74. *oentry = entry;
  75. if (i) { /* initial entry? */
  76. tb->tbl_fill++;
  77. if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
  78. hsplit(tb);
  79. }
  80. return FALSE;
  81. }
  82. #ifdef NOTUSED
  83. bool
  84. hdelete(tb,key)
  85. register HASH *tb;
  86. char *key;
  87. {
  88. register char *s;
  89. register int i;
  90. register int hash;
  91. register HENT *entry;
  92. register HENT **oentry;
  93. if (!tb)
  94. return FALSE;
  95. for (s=key, i=0, hash = 0;
  96. /* while */ *s;
  97. s++, i++, hash *= 5) {
  98. hash += *s * coeff[i];
  99. }
  100. oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  101. entry = *oentry;
  102. i = 1;
  103. for (; entry; i=0, oentry = &entry->hent_next, entry = entry->hent_next) {
  104. if (entry->hent_hash != hash) /* strings can't be equal */
  105. continue;
  106. if (strNE(entry->hent_key,key)) /* is this it? */
  107. continue;
  108. safefree((char*)entry->hent_val);
  109. safefree(entry->hent_key);
  110. *oentry = entry->hent_next;
  111. safefree((char*)entry);
  112. if (i)
  113. tb->tbl_fill--;
  114. return TRUE;
  115. }
  116. return FALSE;
  117. }
  118. #endif
  119. hsplit(tb)
  120. HASH *tb;
  121. {
  122. int oldsize = tb->tbl_max + 1;
  123. register int newsize = oldsize * 2;
  124. register int i;
  125. register HENT **a;
  126. register HENT **b;
  127. register HENT *entry;
  128. register HENT **oentry;
  129. a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
  130. bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */
  131. tb->tbl_max = --newsize;
  132. tb->tbl_array = a;
  133. for (i=0; i<oldsize; i++,a++) {
  134. if (!*a) /* non-existent */
  135. continue;
  136. b = a+oldsize;
  137. for (oentry = a, entry = *a; entry; entry = *oentry) {
  138. if ((entry->hent_hash & newsize) != i) {
  139. *oentry = entry->hent_next;
  140. entry->hent_next = *b;
  141. if (!*b)
  142. tb->tbl_fill++;
  143. *b = entry;
  144. continue;
  145. }
  146. else
  147. oentry = &entry->hent_next;
  148. }
  149. if (!*a) /* everything moved */
  150. tb->tbl_fill--;
  151. }
  152. }
  153. HASH *
  154. hnew()
  155. {
  156. register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
  157. tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
  158. tb->tbl_fill = 0;
  159. tb->tbl_max = 7;
  160. hiterinit(tb); /* so each() will start off right */
  161. bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
  162. return tb;
  163. }
  164. #ifdef NOTUSED
  165. hshow(tb)
  166. register HASH *tb;
  167. {
  168. fprintf(stderr,"%5d %4d (%2d%%)\n",
  169. tb->tbl_max+1,
  170. tb->tbl_fill,
  171. tb->tbl_fill * 100 / (tb->tbl_max+1));
  172. }
  173. #endif
  174. hiterinit(tb)
  175. register HASH *tb;
  176. {
  177. tb->tbl_riter = -1;
  178. tb->tbl_eiter = Null(HENT*);
  179. return tb->tbl_fill;
  180. }
  181. HENT *
  182. hiternext(tb)
  183. register HASH *tb;
  184. {
  185. register HENT *entry;
  186. entry = tb->tbl_eiter;
  187. do {
  188. if (entry)
  189. entry = entry->hent_next;
  190. if (!entry) {
  191. tb->tbl_riter++;
  192. if (tb->tbl_riter > tb->tbl_max) {
  193. tb->tbl_riter = -1;
  194. break;
  195. }
  196. entry = tb->tbl_array[tb->tbl_riter];
  197. }
  198. } while (!entry);
  199. tb->tbl_eiter = entry;
  200. return entry;
  201. }
  202. char *
  203. hiterkey(entry)
  204. register HENT *entry;
  205. {
  206. return entry->hent_key;
  207. }
  208. STR *
  209. hiterval(entry)
  210. register HENT *entry;
  211. {
  212. return entry->hent_val;
  213. }