removed mistaken divid by 1Meg for predicted cost.
[dyninst.git] / pdutil / src / stringPool.C
1 /*
2  * 
3  * $Log: stringPool.C,v $
4  * Revision 1.3  1994/07/14 23:43:14  hollings
5  * added abort for malloc failure.
6  *
7  * Revision 1.2  1994/01/26  04:53:43  hollings
8  * Change to using <module>/h/*.h
9  *
10  * Revision 1.1  1994/01/25  20:50:27  hollings
11  * First real version of utility library.
12  *
13  * Revision 1.4  1993/08/05  18:58:08  hollings
14  * new includes
15  *
16  * Revision 1.3  1993/05/07  20:19:17  hollings
17  * Upgrade to use dyninst interface.
18  *
19  * Revision 1.2  1993/01/28  19:32:44  hollings
20  * bzero changed to memset.
21  *
22  * Revision 1.1  1992/08/03  20:42:59  hollings
23  * Initial revision
24  *
25  *
26  */
27 #include <stdlib.h>
28 #include <string.h>
29
30 #include "util/h/list.h"
31 #include "util/h/stringPool.h"
32
33 /*
34  * Hash Function from Aho, Sethi, Ulman _Compilers_ (Second Edition)
35  *   page 436.
36  *
37  */
38 static int hash(char *ch, int size)
39 {
40     register unsigned int h = 0, g;
41
42     for (; *ch != '\0'; ch++) {
43         h = (h << 4) + (*ch);
44         if (g = (h & 0xf0000000)) {
45             h = h ^ (g >> 24);
46             h = h ^ g;
47         }
48     }
49     return(h % size);
50 }
51
52 stringPool::stringPool()
53 {
54     memset(table, '\0', sizeof(table));
55     currPage = (stringHandle) malloc(4090);;
56     currPos = currPage;
57 }
58
59 stringHandle stringPool::find(char *data)
60 {
61     int hid;
62     stringEntry *curr;
63
64     hid = hash(data, TAB_SIZE);
65     for (curr=table[hid]; curr; curr=curr->next) {
66         if (!strcmp(data, curr->data)) {
67             return(curr->data);
68         }
69     }
70     return(NULL);
71 }
72
73 char *stringPool::getSpace(int size)
74 {
75     stringHandle ret;
76
77     if ((int)(currPos - currPage) + size > PAGE_SIZE) {
78         // create a new page.
79         currPage = (stringHandle) malloc(4090);
80         if (!currPage) abort();
81         currPos = currPage;
82     }
83     ret = currPos;
84     currPos += size;
85     return(ret);
86 }
87
88 stringHandle stringPool::findAndAdd(char *data)
89 {
90     int hid;
91     stringHandle val;
92     stringEntry *temp;
93
94     val = find(data);
95     if (!val) {
96         // add it.
97         hid = hash(data, TAB_SIZE);
98         temp = (stringEntry *) malloc(sizeof(stringEntry));
99         temp->data = getSpace(strlen(data)+1);
100         strcpy(temp->data, data);
101         temp->next = this->table[hid];
102         table[hid] = temp;
103         val = temp->data;
104     }
105     return(val);
106 }