1 /*
2
3 BOOSTER: BOOtstrap Support by TransfER:
4 BOOSTER is an alternative method to compute bootstrap branch supports
5 in large trees. It uses transfer distance between bipartitions, instead
6 of perfect match.
7
8 Copyright (C) 2017 Frederic Lemoine, Jean-Baka Domelevo Entfellner, Olivier Gascuel
9
10 This program is free software; you can redistribute it and/or
11 modify it under the terms of the GNU General Public License
12 as published by the Free Software Foundation; either version 2
13 of the License, or (at your option) any later version.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
23
24 */
25
26 /*
27 * Generic map implementation.
28 */
29 #include "hashmap.h"
30
31 #include <stdlib.h>
32 #include <stdio.h>
33 #include <string.h>
34
35 #define INITIAL_SIZE (256)
36 #define MAX_CHAIN_LENGTH (8)
37
38 /* We need to keep keys and values */
39 typedef struct _hashmap_element{
40 char* key;
41 int in_use;
42 any_t data;
43 } hashmap_element;
44
45 /* A hashmap has some maximum size and current size,
46 * as well as the data to hold. */
47 typedef struct _hashmap_map{
48 int table_size;
49 int size;
50 hashmap_element *data;
51 } hashmap_map;
52
53 /*
54 * Return an empty hashmap, or NULL on failure.
55 */
hashmap_new()56 map_t hashmap_new() {
57 hashmap_map* m = (hashmap_map*) malloc(sizeof(hashmap_map));
58 if(!m) goto err;
59
60 m->data = (hashmap_element*) calloc(INITIAL_SIZE, sizeof(hashmap_element));
61 if(!m->data) goto err;
62
63 m->table_size = INITIAL_SIZE;
64 m->size = 0;
65
66 return m;
67 err:
68 if (m)
69 hashmap_free(m);
70 return NULL;
71 }
72
73 /* The implementation here was originally done by Gary S. Brown. I have
74 borrowed the tables directly, and made some minor changes to the
75 crc32-function (including changing the interface). //ylo */
76
77 /* ============================================================= */
78 /* COPYRIGHT (C) 1986 Gary S. Brown. You may use this program, or */
79 /* code or tables extracted from it, as desired without restriction. */
80 /* */
81 /* First, the polynomial itself and its table of feedback terms. The */
82 /* polynomial is */
83 /* X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0 */
84 /* */
85 /* Note that we take it "backwards" and put the highest-order term in */
86 /* the lowest-order bit. The X^32 term is "implied"; the LSB is the */
87 /* X^31 term, etc. The X^0 term (usually shown as "+1") results in */
88 /* the MSB being 1. */
89 /* */
90 /* Note that the usual hardware shift register implementation, which */
91 /* is what we're using (we're merely optimizing it by doing eight-bit */
92 /* chunks at a time) shifts bits into the lowest-order term. In our */
93 /* implementation, that means shifting towards the right. Why do we */
94 /* do it this way? Because the calculated CRC must be transmitted in */
95 /* order from highest-order term to lowest-order term. UARTs transmit */
96 /* characters in order from LSB to MSB. By storing the CRC this way, */
97 /* we hand it to the UART in the order low-byte to high-byte; the UART */
98 /* sends each low-bit to hight-bit; and the result is transmission bit */
99 /* by bit from highest- to lowest-order term without requiring any bit */
100 /* shuffling on our part. Reception works similarly. */
101 /* */
102 /* The feedback terms table consists of 256, 32-bit entries. Notes: */
103 /* */
104 /* The table can be generated at runtime if desired; code to do so */
105 /* is shown later. It might not be obvious, but the feedback */
106 /* terms simply represent the results of eight shift/xor opera- */
107 /* tions for all combinations of data and CRC register values. */
108 /* */
109 /* The values must be right-shifted by eight bits by the "updcrc" */
110 /* logic; the shift must be unsigned (bring in zeroes). On some */
111 /* hardware you could probably optimize the shift in assembler by */
112 /* using byte-swap instructions. */
113 /* polynomial $edb88320 */
114 /* */
115 /* -------------------------------------------------------------------- */
116
117 static unsigned long crc32_tab[] = {
118 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
119 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
120 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
121 0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
122 0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
123 0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
124 0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
125 0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
126 0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
127 0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
128 0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
129 0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
130 0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
131 0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
132 0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
133 0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
134 0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
135 0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
136 0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
137 0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
138 0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
139 0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
140 0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
141 0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
142 0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
143 0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
144 0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
145 0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
146 0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
147 0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
148 0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
149 0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
150 0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
151 0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
152 0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
153 0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
154 0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
155 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
156 0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
157 0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
158 0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
159 0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
160 0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
161 0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
162 0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
163 0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
164 0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
165 0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
166 0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
167 0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
168 0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
169 0x2d02ef8dL
170 };
171
172 /* Return a 32-bit CRC of the contents of the buffer. */
173
crc32_booster(const unsigned char * s,unsigned int len)174 unsigned long crc32_booster(const unsigned char *s, unsigned int len)
175 {
176 unsigned int i;
177 unsigned long crc32val;
178
179 crc32val = 0;
180 for (i = 0; i < len; i ++)
181 {
182 crc32val =
183 crc32_tab[(crc32val ^ s[i]) & 0xff] ^
184 (crc32val >> 8);
185 }
186 return crc32val;
187 }
188
189 /*
190 * Hashing function for a string
191 */
hashmap_hash_int(hashmap_map * m,char * keystring)192 unsigned int hashmap_hash_int(hashmap_map * m, char* keystring){
193
194 unsigned long key = crc32_booster((unsigned char*)(keystring), strlen(keystring));
195
196 /* Robert Jenkins' 32 bit Mix Function */
197 key += (key << 12);
198 key ^= (key >> 22);
199 key += (key << 4);
200 key ^= (key >> 9);
201 key += (key << 10);
202 key ^= (key >> 2);
203 key += (key << 7);
204 key ^= (key >> 12);
205
206 /* Knuth's Multiplicative Method */
207 key = (key >> 3) * 2654435761;
208
209 return key % m->table_size;
210 }
211
212 /*
213 * Return the integer of the location in data
214 * to store the point to the item, or MAP_FULL.
215 */
hashmap_hash(map_t in,char * key)216 int hashmap_hash(map_t in, char* key){
217 int curr;
218 int i;
219
220 /* Cast the hashmap */
221 hashmap_map* m = (hashmap_map *) in;
222
223 /* If full, return immediately */
224 if(m->size >= (m->table_size/2)) return MAP_FULL;
225
226 /* Find the best index */
227 curr = hashmap_hash_int(m, key);
228
229 /* Linear probing */
230 for(i = 0; i< MAX_CHAIN_LENGTH; i++){
231 if(m->data[curr].in_use == 0)
232 return curr;
233
234 if(m->data[curr].in_use == 1 && (strcmp(m->data[curr].key,key)==0))
235 return curr;
236
237 curr = (curr + 1) % m->table_size;
238 }
239
240 return MAP_FULL;
241 }
242
243 /*
244 * Doubles the size of the hashmap, and rehashes all the elements
245 */
hashmap_rehash(map_t in)246 int hashmap_rehash(map_t in){
247 int i;
248 int old_size;
249 hashmap_element* curr;
250
251 /* Setup the new elements */
252 hashmap_map *m = (hashmap_map *) in;
253 hashmap_element* temp = (hashmap_element *)
254 calloc(2 * m->table_size, sizeof(hashmap_element));
255 if(!temp) return MAP_OMEM;
256
257 /* Update the array */
258 curr = m->data;
259 m->data = temp;
260
261 /* Update the size */
262 old_size = m->table_size;
263 m->table_size = 2 * m->table_size;
264 m->size = 0;
265
266 /* Rehash the elements */
267 for(i = 0; i < old_size; i++){
268 int status;
269
270 if (curr[i].in_use == 0)
271 continue;
272
273 status = hashmap_put(m, curr[i].key, curr[i].data);
274 if (status != MAP_OK)
275 return status;
276 }
277
278 free(curr);
279
280 return MAP_OK;
281 }
282
283 /*
284 * Add a pointer to the hashmap with some key
285 */
hashmap_put(map_t in,char * key,any_t value)286 int hashmap_put(map_t in, char* key, any_t value){
287 int index;
288 hashmap_map* m;
289
290 /* Cast the hashmap */
291 m = (hashmap_map *) in;
292
293 /* Find a place to put our value */
294 index = hashmap_hash(in, key);
295 while(index == MAP_FULL){
296 if (hashmap_rehash(in) == MAP_OMEM) {
297 return MAP_OMEM;
298 }
299 index = hashmap_hash(in, key);
300 }
301
302 /* Set the data */
303 m->data[index].data = value;
304 m->data[index].key = key;
305 m->data[index].in_use = 1;
306 m->size++;
307
308 return MAP_OK;
309 }
310
311 /*
312 * Get your pointer out of the hashmap with a key
313 */
hashmap_get(map_t in,char * key,any_t * arg)314 int hashmap_get(map_t in, char* key, any_t *arg){
315 int curr;
316 int i;
317 hashmap_map* m;
318
319 /* Cast the hashmap */
320 m = (hashmap_map *) in;
321
322 /* Find data location */
323 curr = hashmap_hash_int(m, key);
324
325 /* Linear probing, if necessary */
326 for(i = 0; i<MAX_CHAIN_LENGTH; i++){
327
328 int in_use = m->data[curr].in_use;
329 if (in_use == 1){
330 if (strcmp(m->data[curr].key,key)==0){
331 *arg = (m->data[curr].data);
332 return MAP_OK;
333 }
334 }
335
336 curr = (curr + 1) % m->table_size;
337 }
338
339 *arg = NULL;
340
341 /* Not found */
342 return MAP_MISSING;
343 }
344
345 /*
346 * Iterate the function parameter over each element in the hashmap. The
347 * additional any_t argument is passed to the function as its first
348 * argument and the hashmap element is the second.
349 */
hashmap_iterate(map_t in,PFany f,any_t item)350 int hashmap_iterate(map_t in, PFany f, any_t item) {
351 int i;
352
353 /* Cast the hashmap */
354 hashmap_map* m = (hashmap_map*) in;
355
356 /* On empty hashmap, return immediately */
357 if (hashmap_length(m) <= 0)
358 return MAP_MISSING;
359
360 /* Linear probing */
361 for(i = 0; i< m->table_size; i++)
362 if(m->data[i].in_use != 0) {
363 any_t data = (any_t) (m->data[i].data);
364 any_t key = (any_t) (m->data[i].key);
365 int status = f(item, key, data);
366 if (status != MAP_OK) {
367 return status;
368 }
369 }
370
371 return MAP_OK;
372 }
373
374 /*
375 * Remove an element with that key from the map
376 */
hashmap_remove(map_t in,char * key)377 int hashmap_remove(map_t in, char* key){
378 int i;
379 int curr;
380 hashmap_map* m;
381
382 /* Cast the hashmap */
383 m = (hashmap_map *) in;
384
385 /* Find key */
386 curr = hashmap_hash_int(m, key);
387
388 /* Linear probing, if necessary */
389 for(i = 0; i<MAX_CHAIN_LENGTH; i++){
390
391 int in_use = m->data[curr].in_use;
392 if (in_use == 1){
393 if (strcmp(m->data[curr].key,key)==0){
394 /* Blank out the fields */
395 m->data[curr].in_use = 0;
396 m->data[curr].data = NULL;
397 m->data[curr].key = NULL;
398
399 /* Reduce the size */
400 m->size--;
401 return MAP_OK;
402 }
403 }
404 curr = (curr + 1) % m->table_size;
405 }
406
407 /* Data not found */
408 return MAP_MISSING;
409 }
410
411 /* Deallocate the hashmap */
hashmap_free(map_t in)412 void hashmap_free(map_t in){
413 hashmap_map* m = (hashmap_map*) in;
414 free(m->data);
415 free(m);
416 }
417
418 /* Return the length of the hashmap */
hashmap_length(map_t in)419 int hashmap_length(map_t in){
420 hashmap_map* m = (hashmap_map *) in;
421 if(m != NULL) return m->size;
422 else return 0;
423 }
424