home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / fax-3.2.1 / lib / libutil / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-31  |  7.0 KB  |  358 lines
  1. /*
  2.   This file is part of the NetFax system.
  3.  
  4.   (c) Copyright 1989 by David M. Siegel and Sundar Narasimhan.
  5.       All rights reserved.
  6.  
  7.     This program is free software; you can redistribute it and/or modify
  8.     it under the terms of the GNU General Public License as published by
  9.     the Free Software Foundation.
  10.  
  11.     This program is distributed in the hope that it will be useful, 
  12.     but WITHOUT ANY WARRANTY; without even the implied warranty of 
  13.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.     GNU General Public License for more details.
  15.  
  16.     You should have received a copy of the GNU General Public License
  17.     along with this program; if not, write to the Free Software
  18.     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19. */
  20.  
  21. #include <stdio.h>
  22. #include <strings.h>
  23. #include <malloc.h>
  24.  
  25. #include "alloc.h"
  26. #include "hash.h"
  27.  
  28. /*
  29.   The main initialization function. Use a size that is appropriate for 
  30.   your application.
  31. */
  32. HTTABLE *
  33. htinit(size, keysize)
  34. int size;
  35. int keysize;
  36. {
  37.     HTTABLE *ht;
  38.     HTENTRY **hte;
  39.  
  40.     if (((ht = salloc(1, HTTABLE))) == NULL ||
  41.     (hte = salloc(size, HTENTRY *)) == NULL) {
  42.     printf("htinit: out of memory\n");
  43.     return (NULL);
  44.     }
  45.  
  46.     ht->ht_entries = hte;
  47.     ht->ht_size = size;
  48.     ht->ht_keysize = keysize;
  49.  
  50.     return (ht);
  51. }
  52.  
  53. /* 
  54.   Deletes all the elements and deallocates a table - use with care.
  55. */  
  56. void htfree(table)
  57. HTTABLE *table;
  58. {
  59.     register int i;
  60.     HTENTRY *hte, *temp;
  61.  
  62.     for (i=0; i<table->ht_size; i++) {
  63.     hte = table->ht_entries[i];
  64.     while (hte != NULL) {
  65.         temp = hte;
  66.         hte = hte->ht_next;
  67.         free(temp->ht_key);
  68.         free((char *)temp);
  69.     }
  70.     }
  71.  
  72.     free((char *)table->ht_entries);
  73.     free((char *)table);
  74. }
  75.  
  76. /*
  77.   Takes a hash table and a pointer to a function, and calls function 
  78.   successively with elements found in the hash table. Notice that if you 
  79.   are using the data field to be a pointer to your own data structure 
  80.   you should do a htmap(table, free); before you do a htfree(table);
  81. */
  82. /*VARARGS*/
  83. int
  84. htmap(table, function, data)
  85. HTTABLE *table;
  86. int (*function)();
  87. char *data;
  88. {
  89.     register int i;
  90.     HTENTRY *hte;
  91.  
  92.     for (i=0;i<table->ht_size;i++) {
  93.     hte = (table->ht_entries)[i];
  94.     while (hte != NULL) {
  95.         (*function)(hte->ht_data, hte->ht_key, data);
  96.         hte = hte->ht_next;
  97.     }
  98.     }
  99.  
  100.     return (0);
  101. }
  102.  
  103. /*
  104.   Prints out statistics about the table if it contains any entries.
  105. */
  106. void
  107. htstat(fp, table)
  108. FILE *fp;
  109. HTTABLE *table;
  110. {
  111.     if (table->ht_noe != 0)
  112.       fprintf(fp,
  113.           "size=%d, entries=%d, colls=%d, %%full=%f, %%coll=%f\n",
  114.           table->ht_size, table->ht_noe, table->ht_noc,
  115.           (float)((table->ht_noe * 100)/(table->ht_size)),
  116.           (float)((table->ht_noc * 100)/table->ht_noe));
  117.     else
  118.       fprintf(fp,
  119.           "size=%d, entries=%d, colls=%d, %%full=%f, %%coll=%f\n",
  120.           table->ht_size, table->ht_noe, table->ht_noc, 0.0, 0.0);
  121. }
  122.  
  123. #define rotl(x) (x && (1 << 8*sizeof(x)-1) ? (x << 1) & 1 : x << 1)
  124.  
  125. /*
  126.   Takes a string key value, and a table and returns an offset number into 
  127.   the table of entries.
  128. */
  129. int
  130. hthash(s, table)
  131. char *s;
  132. HTTABLE *table;
  133. {
  134.     register int total = 0;
  135.     register int c;
  136.     register int i;
  137.  
  138.     if (table->ht_keysize == 0) {
  139.     while (*s != '\0') {
  140.         c = *s++;
  141.         total = (total<<3) + (total>>28) + c;
  142.     }
  143.     if (total < 0)
  144.       total = -total;
  145.     } else {
  146.     for (total = i = 0; i < table->ht_keysize; i++, s++) {
  147.         total ^= *s * 23;
  148.         total = rotl(total);
  149.     }
  150.     }
  151.  
  152.     return (total % table->ht_size);
  153. }
  154.  
  155. HTENTRY *
  156. htlookup(str, table)
  157. char *str;
  158. HTTABLE *table;
  159. {
  160.     HTENTRY *hte;
  161.     int offset;
  162.  
  163.     if ((offset = hthash(str, table)) < 0)
  164.       return (NULL);
  165.  
  166.     hte = table->ht_entries[offset];
  167.  
  168.     if (hte == NULL) 
  169.       return (NULL);
  170.  
  171.     while (hte != NULL) {
  172.     if (table->ht_keysize == 0) {
  173.         if (strcmp(hte->ht_key, str) == 0) 
  174.           return (hte);
  175.     } else {
  176.         if (bcmp(hte->ht_key, str, table->ht_keysize) == 0)
  177.           return (hte);
  178.     }
  179.     hte = hte->ht_next;
  180.     }
  181.  
  182.     return (NULL);
  183. }
  184.  
  185. char *
  186. htgetdata(str, table)
  187. char *str;
  188. HTTABLE *table;
  189. {
  190.     HTENTRY *hte;
  191.  
  192.     if ((hte = htlookup(str, table)) == NULL) 
  193.       return (NULL);
  194.     else 
  195.       return (hte->ht_data);
  196. }
  197.  
  198. HTENTRY *
  199. htadd_hte(str, table, hte, data)
  200. char *str;
  201. HTTABLE *table;
  202. HTENTRY *hte;
  203. char *data;
  204. {
  205.     int value = hthash(str, table);
  206.  
  207.     /* add hte to table */
  208.     hte->ht_key = str;
  209.     hte->ht_data = data;
  210.     hte->ht_next = table->ht_entries[value];
  211.     table->ht_entries[value] = hte;
  212.  
  213.     /* update stats */
  214.     table->ht_noe++;
  215.     if (hte->ht_next != NULL)
  216.       table->ht_noc++;
  217.  
  218.     return (hte);
  219. }
  220.  
  221. HTENTRY *
  222. htadd(str, table, data)
  223. char *str;
  224. HTTABLE *table;
  225. char *data;
  226. {
  227.     HTENTRY *hte = htlookup(str, table);
  228.     char *str_copy;
  229.  
  230.     if (hte == NULL) {
  231.     /* not found in the table */
  232.     if ((hte = salloc(1, HTENTRY)) == NULL)
  233.       return (NULL);
  234.  
  235.     if (table->ht_keysize == 0) {
  236.         if ((str_copy = salloc(strlen(str)+1, char)) == NULL) {
  237.         free(hte);
  238.         return (NULL);
  239.         } else
  240.           strcpy(str_copy, str);
  241.     } else {
  242.         if ((str_copy = salloc(table->ht_keysize, char)) == NULL) {
  243.         free(hte);
  244.         return (NULL);
  245.         } else
  246.           bcopy(str, str_copy, table->ht_keysize);
  247.     }
  248.  
  249.     return (htadd_hte(str_copy, table, hte, data));
  250.     } else {
  251.     /* update the previous data item by the current one */
  252.     hte->ht_data = data;
  253.     return (hte);
  254.     }
  255. }
  256.  
  257. HTENTRY *
  258. htdelete_hte(str, table)
  259. char *str;
  260. HTTABLE *table;
  261. {
  262.     int value = hthash(str, table);
  263.     HTENTRY *hte = table->ht_entries[value];
  264.     HTENTRY *prev = hte;
  265.     int found = 0;
  266.  
  267.     while (hte != NULL) {
  268.     if (table->ht_keysize == 0) {
  269.         if (strcmp(hte->ht_key, str) == 0) {
  270.         found++; 
  271.         break;
  272.         }
  273.     } else {
  274.         if (bcmp(hte->ht_key, str, table->ht_keysize) == 0) {
  275.         found++; 
  276.         break;
  277.         }
  278.     }
  279.     prev = hte;
  280.     hte = hte->ht_next;
  281.     }
  282.  
  283.     if (found == 0) 
  284.       return (NULL);
  285.  
  286.     if (prev == hte) 
  287.       table->ht_entries[value] = hte->ht_next;
  288.     else 
  289.       prev->ht_next = hte->ht_next;
  290.  
  291.     /* update stats */
  292.     table->ht_noe--;
  293.     if (table->ht_entries[value] != NULL)
  294.       table->ht_noc--;
  295.  
  296.     return (hte);
  297. }
  298.  
  299. int
  300. htdelete(str, table)
  301. char *str;
  302. HTTABLE *table;
  303. {
  304.     HTENTRY *hte = htdelete_hte(str, table);
  305.  
  306.     if (hte == NULL)
  307.       return (0);
  308.  
  309.     free(hte->ht_key);
  310.     free((char *)hte);
  311.  
  312.     return (1);
  313. }
  314.  
  315. #ifdef DEBUG
  316. main()
  317. {
  318.     HTTABLE *ht;
  319.     char cmd[20];
  320.     char data[20];
  321.     int val;
  322.  
  323.     ht = htinit(257);
  324.  
  325.     for (;;) {
  326.     htstat(stdout, ht);
  327.     printf("? ");
  328.     gets(cmd);
  329.     switch (cmd[0]) {
  330.       case 'i':
  331.         printf("data string: ");
  332.         gets(data);
  333.         printf("value: ");
  334.         scanf("%d", &val);
  335.         htadd(data, ht, (char *)val);
  336.         break;
  337.       case 'l':
  338.         printf("data string: ");
  339.         gets(data);
  340.         val = (int) htgetdata(data, ht);
  341.         if (val == 0) printf("not found!\r\n");
  342.         else printf("value: %d\r\n", val);
  343.         break;
  344.       case 'd':
  345.         printf("data string: ");
  346.         gets(data);
  347.         if (htdelete(data, ht)< 0)
  348.           printf("not found!\r\n");
  349.         else printf("deleted!\r\n");
  350.         break;
  351.       default:
  352.         printf("i-insert, l-lookup, d-delete\r\n");
  353.         break;
  354.     }
  355.     }
  356. }
  357. #endif
  358.