hash.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583
  1. /* -----------------------------------------------------------------------------
  2. * This file is part of SWIG, which is licensed as a whole under version 3
  3. * (or any later version) of the GNU General Public License. Some additional
  4. * terms also apply to certain portions of SWIG. The full details of the SWIG
  5. * license and copyrights can be found in the LICENSE and COPYRIGHT files
  6. * included with the SWIG source code as distributed by the SWIG developers
  7. * and at https://www.swig.org/legal.html.
  8. *
  9. * hash.c
  10. *
  11. * Implements a simple hash table object.
  12. * ----------------------------------------------------------------------------- */
  13. #include "dohint.h"
  14. extern DohObjInfo DohHashType;
  15. /* Hash node */
  16. typedef struct HashNode {
  17. DOH *key;
  18. DOH *object;
  19. struct HashNode *next;
  20. } HashNode;
  21. /* Hash object */
  22. typedef struct Hash {
  23. DOH *file;
  24. int line;
  25. HashNode **hashtable;
  26. int hashsize;
  27. int nitems;
  28. } Hash;
  29. /* Key interning structure */
  30. typedef struct KeyValue {
  31. char *cstr;
  32. DOH *sstr;
  33. struct KeyValue *left;
  34. struct KeyValue *right;
  35. } KeyValue;
  36. static KeyValue *root = 0;
  37. static int max_expand = 1;
  38. /* Find or create a key in the interned key table */
  39. static DOH *find_key(DOH *doh_c) {
  40. char *c = (char *) doh_c;
  41. KeyValue *r, *s;
  42. int d = 0;
  43. /* OK, sure, we use a binary tree for maintaining interned
  44. symbols. Then we use their hash values for accessing secondary
  45. hash tables. */
  46. r = root;
  47. s = 0;
  48. while (r) {
  49. s = r;
  50. d = strcmp(r->cstr, c);
  51. if (d == 0)
  52. return r->sstr;
  53. if (d < 0)
  54. r = r->left;
  55. else
  56. r = r->right;
  57. }
  58. /* fprintf(stderr,"Interning '%s'\n", c); */
  59. r = (KeyValue *) DohMalloc(sizeof(KeyValue));
  60. r->cstr = (char *) DohMalloc(strlen(c) + 1);
  61. strcpy(r->cstr, c);
  62. r->sstr = NewString(c);
  63. DohIntern(r->sstr);
  64. r->left = 0;
  65. r->right = 0;
  66. if (!s) {
  67. root = r;
  68. } else {
  69. if (d < 0)
  70. s->left = r;
  71. else
  72. s->right = r;
  73. }
  74. return r->sstr;
  75. }
  76. #define HASH_INIT_SIZE 7
  77. /* Create a new hash node */
  78. static HashNode *NewNode(DOH *k, void *obj) {
  79. HashNode *hn = (HashNode *) DohMalloc(sizeof(HashNode));
  80. hn->key = k;
  81. Incref(hn->key);
  82. hn->object = obj;
  83. Incref(obj);
  84. hn->next = 0;
  85. return hn;
  86. }
  87. /* Delete a hash node */
  88. static void DelNode(HashNode *hn) {
  89. Delete(hn->key);
  90. Delete(hn->object);
  91. DohFree(hn);
  92. }
  93. /* -----------------------------------------------------------------------------
  94. * DelHash()
  95. *
  96. * Delete a hash table.
  97. * ----------------------------------------------------------------------------- */
  98. static void DelHash(DOH *ho) {
  99. Hash *h = (Hash *) ObjData(ho);
  100. HashNode *n, *next;
  101. int i;
  102. for (i = 0; i < h->hashsize; i++) {
  103. n = h->hashtable[i];
  104. while (n) {
  105. next = n->next;
  106. DelNode(n);
  107. n = next;
  108. }
  109. }
  110. DohFree(h->hashtable);
  111. h->hashtable = 0;
  112. h->hashsize = 0;
  113. DohFree(h);
  114. }
  115. /* -----------------------------------------------------------------------------
  116. * Hash_clear()
  117. *
  118. * Clear all of the entries in the hash table.
  119. * ----------------------------------------------------------------------------- */
  120. static void Hash_clear(DOH *ho) {
  121. Hash *h = (Hash *) ObjData(ho);
  122. HashNode *n, *next;
  123. int i;
  124. for (i = 0; i < h->hashsize; i++) {
  125. n = h->hashtable[i];
  126. while (n) {
  127. next = n->next;
  128. DelNode(n);
  129. n = next;
  130. }
  131. h->hashtable[i] = 0;
  132. }
  133. h->nitems = 0;
  134. }
  135. /* resize the hash table */
  136. static void resize(Hash *h) {
  137. HashNode *n, *next, **table;
  138. int oldsize, newsize;
  139. int i, p, hv;
  140. if (h->nitems < 2 * h->hashsize)
  141. return;
  142. /* Too big. We have to rescale everything now */
  143. oldsize = h->hashsize;
  144. /* Calculate a new size */
  145. newsize = 2 * oldsize + 1;
  146. p = 3;
  147. while (p < (newsize >> 1)) {
  148. if (((newsize / p) * p) == newsize) {
  149. newsize += 2;
  150. p = 3;
  151. continue;
  152. }
  153. p = p + 2;
  154. }
  155. table = (HashNode **) DohCalloc(newsize, sizeof(HashNode *));
  156. /* Walk down the old set of nodes and re-place */
  157. h->hashsize = newsize;
  158. for (i = 0; i < oldsize; i++) {
  159. n = h->hashtable[i];
  160. while (n) {
  161. hv = Hashval(n->key) % newsize;
  162. next = n->next;
  163. n->next = table[hv];
  164. table[hv] = n;
  165. n = next;
  166. }
  167. }
  168. DohFree(h->hashtable);
  169. h->hashtable = table;
  170. }
  171. /* -----------------------------------------------------------------------------
  172. * Hash_setattr()
  173. *
  174. * Set an attribute in the hash table. Deletes the existing entry if it already
  175. * exists.
  176. * ----------------------------------------------------------------------------- */
  177. static int Hash_setattr(DOH *ho, DOH *k, DOH *obj) {
  178. int hv;
  179. HashNode *n, *prev;
  180. Hash *h = (Hash *) ObjData(ho);
  181. if (!obj) {
  182. return DohDelattr(ho, k);
  183. }
  184. if (!DohCheck(k))
  185. k = find_key(k);
  186. if (!DohCheck(obj)) {
  187. obj = NewString((char *) obj);
  188. Decref(obj);
  189. }
  190. hv = (Hashval(k)) % h->hashsize;
  191. n = h->hashtable[hv];
  192. prev = 0;
  193. while (n) {
  194. if (Cmp(n->key, k) == 0) {
  195. /* Node already exists. Just replace its contents */
  196. if (n->object == obj) {
  197. /* Whoa. Same object. Do nothing */
  198. return 1;
  199. }
  200. Delete(n->object);
  201. n->object = obj;
  202. Incref(obj);
  203. return 1; /* Return 1 to indicate a replacement */
  204. } else {
  205. prev = n;
  206. n = n->next;
  207. }
  208. }
  209. /* Add this to the table */
  210. n = NewNode(k, obj);
  211. if (prev)
  212. prev->next = n;
  213. else
  214. h->hashtable[hv] = n;
  215. h->nitems++;
  216. resize(h);
  217. return 0;
  218. }
  219. /* -----------------------------------------------------------------------------
  220. * Hash_getattr()
  221. *
  222. * Get an attribute from the hash table. Returns 0 if it doesn't exist.
  223. * ----------------------------------------------------------------------------- */
  224. typedef int (*binop) (DOH *obj1, DOH *obj2);
  225. static DOH *Hash_getattr(DOH *h, DOH *k) {
  226. DOH *obj = 0;
  227. Hash *ho = (Hash *) ObjData(h);
  228. DOH *ko = DohCheck(k) ? k : find_key(k);
  229. int hv = Hashval(ko) % ho->hashsize;
  230. DohObjInfo *k_type = ((DohBase*)ko)->type;
  231. HashNode *n = ho->hashtable[hv];
  232. if (k_type->doh_equal) {
  233. binop equal = k_type->doh_equal;
  234. while (n) {
  235. DohBase *nk = (DohBase *)n->key;
  236. if ((k_type == nk->type) && equal(ko, nk)) obj = n->object;
  237. n = n->next;
  238. }
  239. } else {
  240. binop cmp = k_type->doh_cmp;
  241. while (n) {
  242. DohBase *nk = (DohBase *)n->key;
  243. if ((k_type == nk->type) && (cmp(ko, nk) == 0)) obj = n->object;
  244. n = n->next;
  245. }
  246. }
  247. return obj;
  248. }
  249. /* -----------------------------------------------------------------------------
  250. * Hash_delattr()
  251. *
  252. * Delete an object from the hash table.
  253. * ----------------------------------------------------------------------------- */
  254. static int Hash_delattr(DOH *ho, DOH *k) {
  255. HashNode *n, *prev;
  256. int hv;
  257. Hash *h = (Hash *) ObjData(ho);
  258. if (!DohCheck(k))
  259. k = find_key(k);
  260. hv = Hashval(k) % h->hashsize;
  261. n = h->hashtable[hv];
  262. prev = 0;
  263. while (n) {
  264. if (Cmp(n->key, k) == 0) {
  265. /* Found it, kill it */
  266. if (prev) {
  267. prev->next = n->next;
  268. } else {
  269. h->hashtable[hv] = n->next;
  270. }
  271. DelNode(n);
  272. h->nitems--;
  273. return 1;
  274. }
  275. prev = n;
  276. n = n->next;
  277. }
  278. return 0;
  279. }
  280. static DohIterator Hash_firstiter(DOH *ho) {
  281. DohIterator iter;
  282. Hash *h = (Hash *) ObjData(ho);
  283. iter.object = ho;
  284. iter._current = 0;
  285. iter.item = 0;
  286. iter.key = 0;
  287. iter._index = 0; /* Index in hash table */
  288. while ((iter._index < h->hashsize) && !h->hashtable[iter._index])
  289. iter._index++;
  290. if (iter._index >= h->hashsize) {
  291. return iter;
  292. }
  293. iter._current = h->hashtable[iter._index];
  294. iter.item = ((HashNode *) iter._current)->object;
  295. iter.key = ((HashNode *) iter._current)->key;
  296. /* Actually save the next slot in the hash. This makes it possible to
  297. delete the item being iterated over without trashing the universe */
  298. iter._current = ((HashNode *) iter._current)->next;
  299. return iter;
  300. }
  301. static DohIterator Hash_nextiter(DohIterator iter) {
  302. Hash *h = (Hash *) ObjData(iter.object);
  303. if (!iter._current) {
  304. iter._index++;
  305. while ((iter._index < h->hashsize) && !h->hashtable[iter._index]) {
  306. iter._index++;
  307. }
  308. if (iter._index >= h->hashsize) {
  309. iter.item = 0;
  310. iter.key = 0;
  311. iter._current = 0;
  312. return iter;
  313. }
  314. iter._current = h->hashtable[iter._index];
  315. }
  316. iter.key = ((HashNode *) iter._current)->key;
  317. iter.item = ((HashNode *) iter._current)->object;
  318. /* Store the next node to iterator on */
  319. iter._current = ((HashNode *) iter._current)->next;
  320. return iter;
  321. }
  322. /* -----------------------------------------------------------------------------
  323. * Hash_keys()
  324. *
  325. * Return a list of keys
  326. * ----------------------------------------------------------------------------- */
  327. static DOH *Hash_keys(DOH *so) {
  328. DOH *keys;
  329. Iterator i;
  330. keys = NewList();
  331. for (i = First(so); i.key; i = Next(i)) {
  332. Append(keys, i.key);
  333. }
  334. return keys;
  335. }
  336. /* -----------------------------------------------------------------------------
  337. * DohSetMaxHashExpand()
  338. *
  339. * Controls how many Hash objects are displayed in full in Hash_str
  340. * ----------------------------------------------------------------------------- */
  341. void DohSetMaxHashExpand(int count) {
  342. max_expand = count;
  343. }
  344. /* -----------------------------------------------------------------------------
  345. * DohGetMaxHashExpand()
  346. *
  347. * Returns how many Hash objects are displayed in full in Hash_str
  348. * ----------------------------------------------------------------------------- */
  349. int DohGetMaxHashExpand(void) {
  350. return max_expand;
  351. }
  352. /* -----------------------------------------------------------------------------
  353. * Hash_str()
  354. *
  355. * Create a string representation of a hash table (mainly for debugging).
  356. * ----------------------------------------------------------------------------- */
  357. static DOH *Hash_str(DOH *ho) {
  358. int i, j;
  359. HashNode *n;
  360. DOH *s;
  361. static int expanded = 0;
  362. static const char *tab = " ";
  363. Hash *h = (Hash *) ObjData(ho);
  364. s = NewStringEmpty();
  365. if (ObjGetMark(ho)) {
  366. Printf(s, "Hash(%p)", ho);
  367. return s;
  368. }
  369. if (expanded >= max_expand) {
  370. /* replace each hash attribute with a '.' */
  371. Printf(s, "Hash(%p) {", ho);
  372. for (i = 0; i < h->hashsize; i++) {
  373. n = h->hashtable[i];
  374. while (n) {
  375. Putc('.', s);
  376. n = n->next;
  377. }
  378. }
  379. Putc('}', s);
  380. return s;
  381. }
  382. ObjSetMark(ho, 1);
  383. Printf(s, "Hash(%p) {\n", ho);
  384. for (i = 0; i < h->hashsize; i++) {
  385. n = h->hashtable[i];
  386. while (n) {
  387. for (j = 0; j < expanded + 1; j++)
  388. Printf(s, tab);
  389. expanded += 1;
  390. Printf(s, "'%s' : %s, \n", n->key, n->object);
  391. expanded -= 1;
  392. n = n->next;
  393. }
  394. }
  395. for (j = 0; j < expanded; j++)
  396. Printf(s, tab);
  397. Printf(s, "}");
  398. ObjSetMark(ho, 0);
  399. return s;
  400. }
  401. /* -----------------------------------------------------------------------------
  402. * Hash_len()
  403. *
  404. * Return number of entries in the hash table.
  405. * ----------------------------------------------------------------------------- */
  406. static int Hash_len(DOH *ho) {
  407. Hash *h = (Hash *) ObjData(ho);
  408. return h->nitems;
  409. }
  410. /* -----------------------------------------------------------------------------
  411. * CopyHash()
  412. *
  413. * Make a copy of a hash table. Note: this is a shallow copy.
  414. * ----------------------------------------------------------------------------- */
  415. static DOH *CopyHash(DOH *ho) {
  416. Hash *h, *nh;
  417. HashNode *n;
  418. DOH *nho;
  419. int i;
  420. h = (Hash *) ObjData(ho);
  421. nh = (Hash *) DohMalloc(sizeof(Hash));
  422. nh->hashsize = h->hashsize;
  423. nh->hashtable = (HashNode **) DohMalloc(nh->hashsize * sizeof(HashNode *));
  424. for (i = 0; i < nh->hashsize; i++) {
  425. nh->hashtable[i] = 0;
  426. }
  427. nh->nitems = 0;
  428. nh->line = h->line;
  429. nh->file = h->file;
  430. if (nh->file)
  431. Incref(nh->file);
  432. nho = DohObjMalloc(&DohHashType, nh);
  433. for (i = 0; i < h->hashsize; i++) {
  434. n = h->hashtable[i];
  435. while (n) {
  436. Hash_setattr(nho, n->key, n->object);
  437. n = n->next;
  438. }
  439. }
  440. return nho;
  441. }
  442. static void Hash_setfile(DOH *ho, DOH *file) {
  443. DOH *fo;
  444. Hash *h = (Hash *) ObjData(ho);
  445. if (!DohCheck(file)) {
  446. fo = NewString(file);
  447. Decref(fo);
  448. } else
  449. fo = file;
  450. Incref(fo);
  451. Delete(h->file);
  452. h->file = fo;
  453. }
  454. static DOH *Hash_getfile(DOH *ho) {
  455. Hash *h = (Hash *) ObjData(ho);
  456. return h->file;
  457. }
  458. static void Hash_setline(DOH *ho, int line) {
  459. Hash *h = (Hash *) ObjData(ho);
  460. h->line = line;
  461. }
  462. static int Hash_getline(DOH *ho) {
  463. Hash *h = (Hash *) ObjData(ho);
  464. return h->line;
  465. }
  466. /* -----------------------------------------------------------------------------
  467. * type information
  468. * ----------------------------------------------------------------------------- */
  469. static DohHashMethods HashHashMethods = {
  470. Hash_getattr,
  471. Hash_setattr,
  472. Hash_delattr,
  473. Hash_keys,
  474. };
  475. DohObjInfo DohHashType = {
  476. "Hash", /* objname */
  477. DelHash, /* doh_del */
  478. CopyHash, /* doh_copy */
  479. Hash_clear, /* doh_clear */
  480. Hash_str, /* doh_str */
  481. 0, /* doh_data */
  482. 0, /* doh_dump */
  483. Hash_len, /* doh_len */
  484. 0, /* doh_hash */
  485. 0, /* doh_cmp */
  486. 0, /* doh_equal */
  487. Hash_firstiter, /* doh_first */
  488. Hash_nextiter, /* doh_next */
  489. Hash_setfile, /* doh_setfile */
  490. Hash_getfile, /* doh_getfile */
  491. Hash_setline, /* doh_setline */
  492. Hash_getline, /* doh_getline */
  493. &HashHashMethods, /* doh_mapping */
  494. 0, /* doh_sequence */
  495. 0, /* doh_file */
  496. 0, /* doh_string */
  497. 0, /* doh_positional */
  498. 0,
  499. };
  500. /* -----------------------------------------------------------------------------
  501. * NewHash()
  502. *
  503. * Create a new hash table.
  504. * ----------------------------------------------------------------------------- */
  505. DOH *DohNewHash(void) {
  506. Hash *h;
  507. int i;
  508. h = (Hash *) DohMalloc(sizeof(Hash));
  509. h->hashsize = HASH_INIT_SIZE;
  510. h->hashtable = (HashNode **) DohMalloc(h->hashsize * sizeof(HashNode *));
  511. for (i = 0; i < h->hashsize; i++) {
  512. h->hashtable[i] = 0;
  513. }
  514. h->nitems = 0;
  515. h->file = 0;
  516. h->line = 0;
  517. return DohObjMalloc(&DohHashType, h);
  518. }