1
2 #include <stdlib.h>
3 #include <string.h>
4 #include "lp_lib.h"
5 #include "lp_utils.h"
6 #include "lp_report.h"
7 #include "lp_Hash.h"
8
9 #ifdef FORTIFY
10 # include "lp_fortify.h"
11 #endif
12
13
14 #define HASH_START_SIZE 5000 /* Hash table size for row and column name storage */
15 #define NUMHASHPRIMES 45
16
create_hash_table(int size,int base)17 STATIC hashtable *create_hash_table(int size, int base)
18 {
19 int i;
20 int HashPrimes[ ] = {
21 29, 229, 883, 1671, 2791, 4801, 8629, 10007,
22 15289, 25303, 34843, 65269, 99709, 129403, 147673, 166669,
23 201403, 222163, 242729, 261431, 303491, 320237, 402761, 501131,
24 602309, 701507, 800999, 900551, 1000619, 1100837, 1200359, 1300021,
25 1400017, 1500007, 1750009, 2000003, 2500009, 3000017, 4000037, 5000011,
26 6000011, 7000003, 8000009, 9000011, 9999991};
27 hashtable *ht;
28
29 /* Find a good size for the hash table */
30 if(size < HASH_START_SIZE)
31 size = HASH_START_SIZE;
32 for(i = 0; i < NUMHASHPRIMES-1; i++)
33 if(HashPrimes[i] > size)
34 break;
35 size = HashPrimes[i];
36
37 /* Then allocate and initialize memory */
38 ht = (hashtable *) calloc(1 , sizeof(*ht));
39 ht->table = (hashelem **) calloc(size, sizeof(*(ht->table)));
40 ht->size = size;
41 ht->base = base;
42 ht->count = base-1;
43
44 return(ht);
45 }
46
free_hash_item(hashelem ** hp)47 STATIC void free_hash_item(hashelem **hp)
48 {
49 free((*hp)->name);
50 free(*hp);
51 *hp = NULL;
52 }
53
free_hash_table(hashtable * ht)54 STATIC void free_hash_table(hashtable *ht)
55 {
56 hashelem *hp, *thp;
57
58 hp = ht->first;
59 while(hp != NULL) {
60 thp = hp;
61 hp = hp->nextelem;
62 free_hash_item(&thp);
63 }
64 free(ht->table);
65 free(ht);
66 }
67
68
69 /* make a good hash function for any int size */
70 /* inspired by Aho, Sethi and Ullman, Compilers ..., p436 */
71 #define HASH_1 sizeof(unsigned int)
72 #define HASH_2 (sizeof(unsigned int) * 6)
73 #define HASH_3 (((unsigned int)0xF0) << ((sizeof(unsigned int) - 1) * CHAR_BIT))
74
hashval(const char * string,int size)75 STATIC int hashval(const char *string, int size)
76 {
77 unsigned int result = 0, tmp;
78
79 for(; *string; string++) {
80 result = (result << HASH_1) + *string;
81 if((tmp = result & HASH_3) != 0) {
82 /* if any of the most significant bits is on */
83 result ^= tmp >> HASH_2; /* xor them in in a less significant part */
84 result ^= tmp; /* and reset the most significant bits to 0 */
85 }
86 }
87 return(result % size);
88 } /* hashval */
89
90
findhash(const char * name,hashtable * ht)91 STATIC hashelem *findhash(const char *name, hashtable *ht)
92 {
93 hashelem *h_tab_p;
94 for(h_tab_p = ht->table[hashval(name, ht->size)];
95 h_tab_p != NULL;
96 h_tab_p = h_tab_p->next)
97 if(strcmp(name, h_tab_p->name) == 0) /* got it! */
98 break;
99 return(h_tab_p);
100 } /* findhash */
101
102
puthash(const char * name,int index,hashelem ** list,hashtable * ht)103 STATIC hashelem *puthash(const char *name, int index, hashelem **list, hashtable *ht)
104 {
105 hashelem *hp = NULL;
106 int hashindex;
107
108 if(list != NULL) {
109 hp = list[index];
110 if(hp != NULL)
111 list[index] = NULL;
112 }
113
114 if((hp = findhash(name, ht)) == NULL) {
115
116 hashindex = hashval(name, ht->size);
117 hp = (hashelem *) calloc(1, sizeof(*hp));
118 allocCHAR(NULL, &hp->name, (int) (strlen(name) + 1), FALSE);
119 strcpy(hp->name, name);
120 hp->index = index;
121 ht->count++;
122 if(list != NULL)
123 list[index] = hp;
124
125 hp->next = ht->table[hashindex];
126 ht->table[hashindex] = hp;
127 if(ht->first == NULL)
128 ht->first = hp;
129 if(ht->last != NULL)
130 ht->last->nextelem = hp;
131 ht->last = hp;
132
133 }
134 return(hp);
135 }
136
drophash(const char * name,hashelem ** list,hashtable * ht)137 STATIC void drophash(const char *name, hashelem **list, hashtable *ht) {
138 hashelem *hp, *hp1, *hp2;
139 int hashindex;
140
141 if((hp = findhash(name, ht)) != NULL) {
142 hashindex = hashval(name, ht->size);
143 if((hp1 = ht->table[hashindex]) != NULL) {
144 hp2 = NULL;
145 while((hp1 != NULL) && (hp1 != hp)) {
146 hp2 = hp1;
147 hp1 = hp1->next;
148 }
149 if(hp1 == hp) {
150 if(hp2 != NULL)
151 hp2->next = hp->next;
152 else
153 ht->table[hashindex] = hp->next;
154 }
155
156 hp1 = ht->first;
157 hp2 = NULL;
158 while((hp1 != NULL) && (hp1 != hp)) {
159 hp2 = hp1;
160 hp1 = hp1->nextelem;
161 }
162 if(hp1 == hp) {
163 if(hp2 != NULL)
164 hp2->nextelem = hp->nextelem;
165 else
166 ht->first = hp->nextelem;
167 }
168 if(list != NULL)
169 list[hp->index] = NULL;
170 free_hash_item(&hp);
171 ht->count--;
172 }
173 }
174 }
175
copy_hash_table(hashtable * ht,hashelem ** list,int newsize)176 STATIC hashtable *copy_hash_table(hashtable *ht, hashelem **list, int newsize)
177 {
178 hashtable *copy;
179 hashelem *elem, *new_elem;
180
181 if(newsize < ht->size)
182 newsize = ht->size;
183
184 copy = create_hash_table(newsize, ht->base);
185 if (copy != NULL) {
186 elem = ht->first;
187 while (elem != NULL) {
188 if((new_elem = puthash(elem->name, elem->index, list, copy)) == NULL) {
189 free_hash_table(copy);
190 return(NULL);
191 }
192 elem = elem ->nextelem;
193 }
194 }
195
196 return(copy);
197 }
198
find_row(lprec * lp,char * name,MYBOOL Unconstrained_rows_found)199 STATIC int find_row(lprec *lp, char *name, MYBOOL Unconstrained_rows_found)
200 {
201 hashelem *hp;
202
203 if (lp->rowname_hashtab != NULL)
204 hp = findhash(name, lp->rowname_hashtab);
205 else
206 hp = NULL;
207
208 if (hp == NULL) {
209 if(Unconstrained_rows_found) { /* just ignore them in this case */
210 return(-1);
211 }
212 else {
213 return(-1);
214 }
215 }
216 return(hp->index);
217 }
218
find_var(lprec * lp,char * name,MYBOOL verbose)219 STATIC int find_var(lprec *lp, char *name, MYBOOL verbose)
220 {
221 hashelem *hp;
222
223 if (lp->colname_hashtab != NULL)
224 hp = findhash(name, lp->colname_hashtab);
225 else
226 hp = NULL;
227
228 if (hp == NULL) {
229 if(verbose)
230 report(lp, SEVERE, "find_var: Unknown variable name '%s'\n", name);
231 return(-1);
232 }
233 return(hp->index);
234 }
235
236