FrontISTR 5.2.0
Large-scale structural analysis program with finit element method
Loading...
Searching...
No Matches
hecmw_hash.c
Go to the documentation of this file.
1/*****************************************************************************
2 * Copyright (c) 2019 FrontISTR Commons
3 * This software is released under the MIT License, see LICENSE.txt
4 *****************************************************************************/
5
6#include "hecmw_hash.h"
7#include "hecmw_io_struct.h"
8
9typedef struct List List;
10typedef struct Bin Bin;
11
13static unsigned int hash_key(const char *str);
14static List *get_list(Bin *bin, const char *key);
15static unsigned int hecmw_hashsize_init_index = 0;
16
17struct List {
18 unsigned int hashkey;
19 char *key;
20 void *value;
21};
22
23struct Bin {
24 unsigned int n;
26};
27
29 unsigned int n;
30 unsigned int num_put;
32};
33
34hecmw_hash_p *hash_ng; /* node group */
35hecmw_hash_p *hash_eg; /* element group */
36hecmw_hash_p *hash_sg; /* surface group */
37hecmw_hash_p *hash_mat; /* material group */
38
39static const unsigned int hecmw_hashsize_template[] = {
40 1021, 2039, 4093, 8191, 16381, 32749,
41 65521, 131071, 262139, 524287, 1048573, 2097143,
42 4194301, 8388593, 16777213, 33554393, 67108859, 134217689,
43 268435399, 536870909, 1073741789, 2147483647 /* Maximum integer */
44};
45
46hecmw_hash_p *hecmw_hash_p_new(unsigned int index) {
47 unsigned int i, size;
48 Bin *bin;
49 hecmw_hash_p *hash;
50
51 hash = (hecmw_hash_p *)malloc(sizeof(hecmw_hash_p));
52 if (hash == NULL) return NULL;
53
54 hash->num_put = 0;
55 size = hecmw_hashsize_template[hecmw_hashsize_init_index];
56 hash->n = size;
57 hash->bin = (Bin *)malloc(hash->n * sizeof(Bin));
58 if (hash->bin == NULL) {
59 free(hash);
60 return NULL;
61 }
62
63 bin = hash->bin;
64 for (i = 0; i < size; i++) {
65 bin->n = 0;
66 bin->list = NULL;
67 bin++;
68 }
69
70 return hash;
71}
72
74 unsigned int i, j, k, l;
75 Bin *bin;
76 List *list;
77 if (hash == NULL) return;
78 k = hash->n;
79 bin = hash->bin;
80 for (i = 0; i < k; i++) {
81 l = bin->n;
82 list = bin->list;
83 for (j = 0; j < l; j++) {
84 free(list->key);
85 list++;
86 }
87 free(bin->list);
88 bin++;
89 }
90 free(hash->bin);
91 free(hash);
92}
93
94void *hecmw_hash_p_get(const hecmw_hash_p *hash, const char *key) {
95 unsigned int index;
96 List *list;
97
98 if (hash == NULL) return NULL;
99 if (key == NULL) return NULL;
100
101 index = hash_key(key) % hash->n;
102 list = get_list(&(hash->bin[index]), key);
103
104 if (list == NULL) return NULL;
105
106 return list->value;
107}
108
109int hecmw_hash_p_exist(const hecmw_hash_p *hash, const char *key) {
110 unsigned int index;
111 List *list;
112
113 if (hash == NULL) return 0;
114 if (key == NULL) return 0;
115
116 index = hash_key(key) % hash->n;
117 list = get_list(&(hash->bin[index]), key);
118
119 if (list == NULL) return 0;
120 return 1;
121}
122
123int hecmw_hash_p_put(hecmw_hash_p *hash, const char *key, void *value) {
124 unsigned int key_len, index, stat;
125 unsigned int hashkey, n;
126 Bin *bin;
127 List *tmp_list, *list;
128 char *new_key;
129
130 if (hash == NULL) return 0;
131 if (key == NULL) return 0;
132 if (value == NULL) return 0;
133
134 stat = 0.8 * hash->n;
135 if (hash->num_put >= stat) {
136 if (hecmw_hash_p_resize(hash) == 1) {
137 return 1;
138 }
139 }
140 hashkey = hash_key(key);
141 index = hashkey % hash->n;
142 key_len = strlen(key);
143
144 bin = &(hash->bin[index]);
145 list = get_list(bin, key);
146
147 if (list != NULL) {
148 return 1;
149 }
150
151 new_key = (char *)malloc((key_len + 1) * sizeof(char));
152 if (new_key == NULL) return 0;
153
154 n = bin->n;
155 if (n == 0) {
156 tmp_list = (List *)malloc(sizeof(List));
157 if (tmp_list == NULL) {
158 free(new_key);
159 return 0;
160 }
161 bin->list = tmp_list;
162 } else {
163 tmp_list = (List *)realloc(bin->list, (n + 1) * sizeof(List));
164 if (tmp_list == NULL) {
165 free(new_key);
166 return 0;
167 }
168 bin->list = tmp_list;
169 }
170
171 list = &(bin->list[n]);
172 list->key = new_key;
173 strcpy(list->key, key);
174 list->value = value;
175 list->hashkey = hashkey;
176 bin->n++;
177 hash->num_put++;
178
179 return 1;
180}
181
183 unsigned int i, j, n;
184 unsigned int newsize, index;
185 Bin *newbin, *bin, *tmp_bin;
186 List *newlist, *list, *tmp_list;
187
188 j = 0;
189 for (i = 0; i < 22; i++) {
190 if (hash->n == hecmw_hashsize_template[i]) {
191 j = i + 1;
192 break;
193 }
194 }
195
196 if (j == 0) {
197 printf("ERROR in hash table resize\n");
198 return 1;
199 }
200
201 newsize = hecmw_hashsize_template[j];
202 newbin = (Bin *)malloc(newsize * sizeof(Bin));
203 if (newbin == NULL) return 1;
204
205 tmp_bin = newbin;
206 for (i = 0; i < newsize; i++) {
207 tmp_bin->n = 0;
208 tmp_bin->list = NULL;
209 tmp_bin++;
210 }
211
212 bin = hash->bin;
213 for (i = 0; i < hash->n; i++) {
214 list = bin->list;
215 for (j = 0; j < bin->n; j++) {
216 index = list->hashkey % newsize;
217 tmp_bin = &(newbin[index]);
218
219 n = tmp_bin->n;
220 if (n == 0) {
221 newlist = (List *)malloc(sizeof(List));
222 if (newlist == NULL) return 1;
223 tmp_bin->list = newlist;
224 } else {
225 newlist = (List *)realloc(tmp_bin->list, (n + 1) * sizeof(List));
226 if (newlist == NULL) return 1;
227 tmp_bin->list = newlist;
228 }
229
230 tmp_list = &(tmp_bin->list[n]);
231 tmp_list->key = list->key;
232 tmp_list->value = list->value;
233 tmp_list->hashkey = list->hashkey;
234 tmp_bin->n++;
235 list++;
236 }
237 free(bin->list);
238 bin++;
239 }
240
241 free(hash->bin);
242 hash->bin = newbin;
243 hash->n = newsize;
244
245 return 0;
246}
247
248static List *get_list(Bin *bin, const char *key) {
249 unsigned int i, n;
250 List *list;
251
252 n = bin->n;
253 if (n == 0) return NULL;
254
255 list = bin->list;
256 for (i = 0; i < n; i++) {
257 if (list->key != NULL && list->value != NULL) {
258 if (strcmp(list->key, key) == 0) {
259 return list;
260 }
261 }
262 list++;
263 }
264 return NULL;
265}
266
268static unsigned int hash_key(const char *c) {
269 unsigned int hash_key = 5381;
270 int i;
271
272 while (*c != '\0') {
273 i = *c;
274 hash_key = ((hash_key << 5) + hash_key) + i;
275 ++c;
276 }
277
278 return hash_key;
279}
hecmw_hash_p * hash_mat
Definition: hecmw_hash.c:37
void * hecmw_hash_p_get(const hecmw_hash_p *hash, const char *key)
Definition: hecmw_hash.c:94
int hecmw_hash_p_resize(hecmw_hash_p *hash)
Definition: hecmw_hash.c:182
int hecmw_hash_p_exist(const hecmw_hash_p *hash, const char *key)
Definition: hecmw_hash.c:109
hecmw_hash_p * hash_ng
Definition: hecmw_hash.c:34
hecmw_hash_p * hash_sg
Definition: hecmw_hash.c:36
hecmw_hash_p * hecmw_hash_p_new(unsigned int index)
Definition: hecmw_hash.c:46
hecmw_hash_p * hash_eg
Definition: hecmw_hash.c:35
int hecmw_hash_p_put(hecmw_hash_p *hash, const char *key, void *value)
Definition: hecmw_hash.c:123
void hecmw_hash_p_delete(hecmw_hash_p *hash)
Definition: hecmw_hash.c:73
#define NULL
Definition: hecmw_hash.c:23
List * list
Definition: hecmw_hash.c:25
unsigned int n
Definition: hecmw_hash.c:24
void * value
Definition: hecmw_hash.c:20
unsigned int hashkey
Definition: hecmw_hash.c:18
char * key
Definition: hecmw_hash.c:19
unsigned int n
Definition: hecmw_hash.c:29
unsigned int num_put
Definition: hecmw_hash.c:30