ARB
adhash.cxx
Go to the documentation of this file.
1 // =============================================================== //
2 // //
3 // File : adhash.cxx //
4 // Purpose : //
5 // //
6 // Institute of Microbiology (Technical University Munich) //
7 // http://www.arb-home.de/ //
8 // //
9 // =============================================================== //
10 
11 #include "gb_data.h"
12 #include "gb_tune.h"
13 #include "gb_hashindex.h"
14 
15 #include <arb_strbuf.h>
16 #include <arb_sort.h>
17 
18 #include <climits>
19 #include <cfloat>
20 #include <cctype>
21 
22 
24  char *key;
25  long val;
27 };
28 struct GB_HASH {
29  size_t size; // size of hashtable
30  size_t nelem; // number of elements inserted
32  gbs_hash_entry **entries; // the hash table (has 'size' entries)
33 
34  void (*freefun)(long val); // function to free hash values (see GBS_create_dynaval_hash)
35 
36 };
37 
38 struct numhash_entry {
39  long key;
40  long val;
42 };
43 
44 struct GB_NUMHASH {
45  long size; // size of hashtable
46  size_t nelem; // number of elements inserted
48 };
49 
50 // prime numbers
51 
52 #define KNOWN_PRIMES 279
53 static size_t sorted_primes[KNOWN_PRIMES] = {
54  3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 67, 71, 79, 89, 97, 103, 109, 127, 137, 149, 157, 167, 179, 191, 211,
55  223, 239, 257, 271, 293, 311, 331, 349, 373, 397, 419, 443, 467, 499, 541, 571, 607, 641, 677, 719, 757, 797, 839, 887, 937,
56  991, 1049, 1109, 1171, 1237, 1303, 1373, 1447, 1531, 1613, 1699, 1789, 1889, 1993, 2099, 2213, 2333, 2459, 2591, 2729, 2879,
57  3037, 3203, 3373, 3557, 3761, 3967, 4177, 4397, 4637, 4889, 5147, 5419, 5711, 6029, 6353, 6689, 7043, 7417, 7817, 8231, 8669,
58  9127, 9613, 10133, 10667, 11239, 11831, 12457, 13121, 13829, 14557, 15329, 16139, 16993, 17891, 18839, 19841, 20887, 21991, 23159,
59  24379, 25667, 27031, 28463, 29983, 31567, 33247, 35023, 36871, 38821, 40867, 43019, 45289, 47681, 50207, 52859, 55661, 58601,
60  61687, 64937, 68371, 71971, 75767, 79757, 83969, 88397, 93053, 97961, 103123, 108553, 114269, 120293, 126631, 133303, 140321,
61  147709, 155501, 163697, 172313, 181387, 190979, 201031, 211619, 222773, 234499, 246889, 259907, 273601, 288007, 303187, 319147,
62  335953, 353641, 372263, 391861, 412487, 434201, 457057, 481123, 506449, 533111, 561173, 590713, 621821, 654553, 689021, 725293,
63  763471, 803659, 845969, 890501, 937373, 986717, 1038671, 1093357, 1150909, 1211489, 1275269, 1342403, 1413077, 1487459, 1565747,
64  1648181, 1734937, 1826257, 1922383, 2023577, 2130101, 2242213, 2360243, 2484473, 2615243, 2752889, 2897789, 3050321, 3210871,
65  3379877, 3557773, 3745051, 3942209, 4149703, 4368113, 4598063, 4840103, 5094853, 5363011, 5645279, 5942399, 6255157, 6584377,
66  6930929, 7295719, 7679713, 8083919, 8509433, 8957309, 9428759, 9925021, 10447391, 10997279, 11576087, 12185359, 12826699, 13501819,
67  14212447, 14960471, 15747869, 16576727, 17449207, 18367597, 19334317, 20351927, 21423107, 22550639, 23737523, 24986867, 26301967,
68  27686291, 29143493, 30677363, 32291971, 33991597, 35780639, 37663841, 39646153, 41732809, 43929307, 46241389, 48675167, 51237019,
69  53933713, 56772371, 59760391, 62905681, 66216511, 69701591, 73370107, 77231711, 81296543, 85575313, 90079313, 94820347, 99810899
70 };
71 
72 // define CALC_PRIMES only to expand the above table
73 #if defined(DEBUG)
74 // #define CALC_PRIMES
75 #endif // DEBUG
76 
77 #ifdef CALC_PRIMES
78 
79 #define CALC_PRIMES_UP_TO 100000000U
80 #define PRIME_UNDENSITY 20U // the higher, the less primes are stored
81 
82 #warning "please don't define CALC_PRIMES permanently"
83 
84 static unsigned char bit_val[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };
85 
86 static int bit_value(const unsigned char *eratosthenes, long num) {
87  // 'num' is odd and lowest 'num' is 3
88  long bit_num = ((num-1) >> 1)-1; // 3->0 5->1 7->2 etc.
89  long byte_num = bit_num >> 3; // div 8
90  char byte = eratosthenes[byte_num];
91 
92  gb_assert(bit_num >= 0);
93  gb_assert((num&1) == 1); // has to odd
94 
95  bit_num = bit_num & 7;
96 
97  return (byte & bit_val[bit_num]) ? 1 : 0;
98 }
99 static void set_bit_value(unsigned char *eratosthenes, long num, int val) {
100  // 'num' is odd and lowest 'num' is 3; val is 0 or 1
101  long bit_num = ((num-1) >> 1)-1; // 3->0 5->1 7->2 etc.
102  long byte_num = bit_num >> 3; // div 8
103  char byte = eratosthenes[byte_num];
104 
105  gb_assert(bit_num >= 0);
106  gb_assert((num&1) == 1); // has to odd
107 
108  bit_num = bit_num & 7;
109 
110  if (val) {
111  byte |= bit_val[bit_num];
112  }
113  else {
114  byte &= (0xff - bit_val[bit_num]);
115  }
116  eratosthenes[byte_num] = byte;
117 }
118 
119 static void calculate_primes_upto() {
120  {
121  size_t bits_needed = CALC_PRIMES_UP_TO/2+1; // only need bits for odd numbers
122  size_t bytes_needed = (bits_needed/8)+1;
123  unsigned char *eratosthenes = ARB_calloc<unsigned char>(bytes_needed); // bit = 1 means "is not a prime"
124  size_t prime_count = 0;
125  size_t num;
126 
127  printf("eratosthenes' size = %zu\n", bytes_needed);
128  GBK_dump_backtrace(stderr, "calculate_primes_upto");
129 
130  for (num = 3; num <= CALC_PRIMES_UP_TO; num += 2) {
131  if (bit_value(eratosthenes, num) == 0) { // is a prime number
132  size_t num2;
133  prime_count++;
134  for (num2 = num*2; num2 <= CALC_PRIMES_UP_TO; num2 += num) { // with all multiples
135  if ((num2&1) == 1) { // skip even numbers
136  set_bit_value(eratosthenes, num2, 1);
137  }
138  }
139  }
140  // otherwise it is no prime and all multiples are already set to 1
141  }
142 
143  // thin out prime numbers (we don't need all of them)
144  {
145  size_t prime_count2 = 0;
146  size_t last_prime = 1;
147  size_t printed = 0;
148 
149  for (num = 3; num <= CALC_PRIMES_UP_TO; num += 2) {
150  if (bit_value(eratosthenes, num) == 0) { // is a prime number
151  size_t diff = num-last_prime;
152  if ((diff*PRIME_UNDENSITY)<num) {
153  set_bit_value(eratosthenes, num, 1); // delete unneeded prime
154  }
155  else {
156  prime_count2++; // count needed primes
157  last_prime = num;
158  }
159  }
160  }
161 
162  printf("\nUsing %zu prime numbers up to %zu:\n\n", prime_count2, CALC_PRIMES_UP_TO);
163  printf("#define KNOWN_PRIMES %zu\n", prime_count2);
164  printf("static size_t sorted_primes[KNOWN_PRIMES] = {\n ");
165  printed = 4;
166 
167  for (num = 3; num <= CALC_PRIMES_UP_TO; num += 2) {
168  if (bit_value(eratosthenes, num) == 0) { // is a prime number
169  if (printed>128) {
170  printf("\n ");
171  printed = 4;
172  }
173 
174  if (num>INT_MAX) {
175  printed += printf("%zuU, ", num);
176  }
177  else {
178  printed += printf("%zu, ", num);
179  }
180  }
181  }
182  printf("\n};\n\n");
183  }
184 
185  free(eratosthenes);
186  }
187  fflush(stdout);
188  exit(1);
189 }
190 
191 #endif // CALC_PRIMES
192 
193 size_t gbs_get_a_prime(size_t above_or_equal_this) {
194  // return a prime number above_or_equal_this
195  // NOTE: it is not necessarily the next prime number, because we don't calculate all prime numbers!
196 
197 #if defined(CALC_PRIMES)
198  calculate_primes_upto();
199 #endif // CALC_PRIMES
200 
201  if (sorted_primes[KNOWN_PRIMES-1] >= above_or_equal_this) {
202  int l = 0, h = KNOWN_PRIMES-1;
203 
204  while (l < h) {
205  int m = (l+h)/2;
206 #if defined(DEBUG) && 0
207  printf("l=%-3i m=%-3i h=%-3i above_or_equal_this=%li sorted_primes[%i]=%li sorted_primes[%i]=%li sorted_primes[%i]=%li\n",
208  l, m, h, above_or_equal_this, l, sorted_primes[l], m, sorted_primes[m], h, sorted_primes[h]);
209 #endif // DEBUG
210  gb_assert(l <= m);
211  gb_assert(m <= h);
212  if (sorted_primes[m] > above_or_equal_this) {
213  h = m-1;
214  }
215  else {
216  if (sorted_primes[m] < above_or_equal_this) {
217  l = m+1;
218  }
219  else {
220  h = l = m;
221  }
222  }
223  }
224 
225  if (sorted_primes[l] < above_or_equal_this) {
226  l++; // take next
228  }
229 
230  gb_assert(sorted_primes[l] >= above_or_equal_this);
231  gb_assert(l == 0 || sorted_primes[l-1] < above_or_equal_this);
232 
233  return sorted_primes[l];
234  }
235 
236  fprintf(stderr, "Warning: gbs_get_a_prime failed for value %zu (performance bleed)\n", above_or_equal_this);
237  gb_assert(0); // add more primes to sorted_primes[]
238 
239  return above_or_equal_this; // NEED_NO_COV
240 }
241 
242 // -----------------------------------------------
243 // Some Hash Procedures for [string,long]
244 
245 inline size_t hash_size(size_t estimated_elements) {
246  size_t min_hash_size = 2*estimated_elements; // -> fill rate ~ 50% -> collisions unlikely
247  size_t next_prime = gbs_get_a_prime(min_hash_size); // use next prime number
248 
249  return next_prime;
250 }
251 
252 
253 GB_HASH *GBS_create_hash(long estimated_elements, GB_CASE case_sens) {
259  long size = hash_size(estimated_elements);
260  GB_HASH *hs = ARB_calloc<GB_HASH>(1);
261 
262  hs->size = size;
263  hs->nelem = 0;
264  hs->case_sens = case_sens;
265  ARB_calloc(hs->entries, size);
266  hs->freefun = NULp;
267 
268  return hs;
269 }
270 
271 GB_HASH *GBS_create_dynaval_hash(long estimated_elements, GB_CASE case_sens, void (*freefun)(long)) {
273  GB_HASH *hs = GBS_create_hash(estimated_elements, case_sens);
274  hs->freefun = freefun;
275  return hs;
276 }
277 
278 void GBS_dynaval_free(long val) {
279  free((void*)val);
280 }
281 
282 #if defined(DEBUG)
283 inline void dump_access(const char *title, const GB_HASH *hs, double mean_access) {
284  fprintf(stderr,
285  "%s: size=%zu elements=%zu mean_access=%.2f hash-speed=%.1f%%\n",
286  title, hs->size, hs->nelem, mean_access, 100.0/mean_access);
287 }
288 
289 static double hash_mean_access_costs(const GB_HASH *hs) {
290  /* returns the mean access costs of the hash [1.0 .. inf[
291  * 1.0 is optimal
292  * 2.0 means: hash speed is 50% (1/2.0)
293  */
294  double mean_access = 1.0;
295 
296  if (hs->nelem) {
297  int strcmps_needed = 0;
298  size_t pos;
299 
300  for (pos = 0; pos<hs->size; pos++) {
301  int strcmps = 1;
302  gbs_hash_entry *e;
303 
304  for (e = hs->entries[pos]; e; e = e->next) {
305  strcmps_needed += strcmps++;
306  }
307  }
308 
309  mean_access = (double)strcmps_needed/hs->nelem;
310  }
311  return mean_access;
312 }
313 #endif // DEBUG
314 
315 
316 void GBS_optimize_hash(const GB_HASH *hs) {
317  if (hs->nelem > hs->size) { // hash is overfilled (Note: even 50% fillrate is slow)
318  size_t new_size = gbs_get_a_prime(hs->nelem*3);
319 
320 #if defined(DEBUG)
321  dump_access("Optimizing filled hash", hs, hash_mean_access_costs(hs));
322 #endif // DEBUG
323 
324  if (new_size>hs->size) { // avoid overflow
325  gbs_hash_entry **new_entries; ARB_calloc(new_entries, new_size);
326 
327  for (size_t pos = 0; pos<hs->size; ++pos) {
328  gbs_hash_entry *e;
329  gbs_hash_entry *next;
330 
331  for (e = hs->entries[pos]; e; e = next) {
332  long new_idx;
333  next = e->next;
334 
335  GB_CALC_HASH_INDEX(e->key, new_idx, new_size, hs->case_sens);
336 
337  e->next = new_entries[new_idx];
338  new_entries[new_idx] = e;
339  }
340  }
341 
342  free(hs->entries);
343 
344  {
345  GB_HASH *hs_mutable = const_cast<GB_HASH*>(hs);
346  hs_mutable->size = new_size;
347  hs_mutable->entries = new_entries;
348  }
349  }
350 #if defined(DEBUG)
351  dump_access("Optimized hash ", hs, hash_mean_access_costs(hs));
352 #endif // DEBUG
353 
354  }
355 }
356 
357 static void gbs_hash_to_strstruct(const char *key, long val, void *cd_out) {
358  GBS_strstruct& out = *(GBS_strstruct*)cd_out;
359 
360  for (size_t i = 0; key[i]; ++i) {
361  out.nput(key[i], (key[i] == ':')+1);
362  }
363  out.put(':');
364  out.putlong(val);
365  out.put(' ');
366 }
367 
369  GBS_strstruct out(1024);
371  return out.release();
372 }
373 
374 
375 static gbs_hash_entry *find_hash_entry(const GB_HASH *hs, const char *key, size_t *index) {
376  gbs_hash_entry *e;
377  if (hs->case_sens == GB_IGNORE_CASE) {
378  GB_CALC_HASH_INDEX_CASE_IGNORED(key, *index, hs->size);
379  for (e=hs->entries[*index]; e; e=e->next) {
380  if (!strcasecmp(e->key, key)) return e;
381  }
382  }
383  else {
384  GB_CALC_HASH_INDEX_CASE_SENSITIVE(key, *index, hs->size);
385  for (e=hs->entries[*index]; e; e=e->next) {
386  if (!strcmp(e->key, key)) return e;
387  }
388  }
389  return NULp;
390 }
391 
392 long GBS_read_hash(const GB_HASH *hs, const char *key) {
393  size_t i;
394  gbs_hash_entry *e = find_hash_entry(hs, key, &i);
395 
396  return e ? e->val : 0;
397 }
398 
399 static void delete_from_list(GB_HASH *hs, size_t i, gbs_hash_entry *e) {
400  // delete the hash entry 'e' from list at index 'i'
401  hs->nelem--;
402  if (hs->entries[i] == e) {
403  hs->entries[i] = e->next;
404  }
405  else {
406  gbs_hash_entry *ee;
407  for (ee = hs->entries[i]; ee->next != e; ee = ee->next) ;
408  if (ee->next == e) {
409  ee->next = e->next;
410  }
411  else {
412  GB_internal_error("Database may be corrupt, hash tables error"); // NEED_NO_COV
413  }
414  }
415  free(e->key);
416  if (hs->freefun) hs->freefun(e->val);
418 }
419 
420 static long write_hash(GB_HASH *hs, char *key, bool copyKey, long val) {
421  /* returns the old value (or 0 if key had no entry)
422  * if 'copyKey' == false, 'key' will be freed (now or later) and may be invalid!
423  * if 'copyKey' == true, 'key' will not be touched in any way!
424  */
425 
426  size_t i;
427  gbs_hash_entry *e = find_hash_entry(hs, key, &i);
428  long oldval = 0;
429 
430  if (e) {
431  oldval = e->val;
432 
433  if (!val) delete_from_list(hs, i, e); // (val == 0 is not stored, cause 0 is the default value)
434  else e->val = val;
435 
436  if (!copyKey) free(key); // already had an entry -> delete unused mem
437  }
438  else if (val != 0) { // don't store 0
439  // create new hash entry
441  e->next = hs->entries[i];
442  e->key = copyKey ? ARB_strdup(key) : key;
443  e->val = val;
444 
445  hs->entries[i] = e;
446  hs->nelem++;
447  }
448  else {
449  if (!copyKey) free(key); // don't need an entry -> delete unused mem
450  }
451  return oldval;
452 }
453 
454 long GBS_write_hash(GB_HASH *hs, const char *key, long val) {
455  // returns the old value (or 0 if key had no entry)
456  return write_hash(hs, (char*)key, true, val);
457 }
458 
459 long GBS_write_hash_no_strdup(GB_HASH *hs, char *key, long val) {
460  /* same as GBS_write_hash, but does no strdup. 'key' is freed later in GBS_free_hash,
461  * so the user has to 'malloc' the string and give control to the hash.
462  * Note: after calling this function 'key' may be invalid!
463  */
464  return write_hash(hs, key, false, val);
465 }
466 
467 long GBS_incr_hash(GB_HASH *hs, const char *key) {
468  // returns new value
469  size_t i;
470  gbs_hash_entry *e = find_hash_entry(hs, key, &i);
471  long result;
472 
473  if (e) {
474  result = ++e->val;
475  if (!result) delete_from_list(hs, i, e);
476  }
477  else {
479  e->next = hs->entries[i];
480  e->key = ARB_strdup(key);
481  e->val = result = 1;
482 
483  hs->entries[i] = e;
484  hs->nelem++;
485  }
486  return result;
487 }
488 
489 #if defined(DEVEL_RALF)
490 // #define DUMP_HASH_ENTRIES
491 #endif // DEVEL_RALF
492 
493 static void GBS_erase_hash(GB_HASH *hs) {
494  size_t hsize = hs->size;
495 
496 #if defined(DUMP_HASH_ENTRIES)
497  for (size_t i = 0; i < hsize; i++) {
498  printf("hash[%zu] =", i);
499  for (gbs_hash_entry *e = hs->entries[i]; e; e = e->next) {
500  printf(" '%s'", e->key);
501  }
502  printf("\n");
503  }
504 #endif // DUMP_HASH_ENTRIES
505 
506  // check hash size
507  if (hsize >= 10) { // ignore small hashes
508 #if defined(DEBUG)
509  double mean_access = hash_mean_access_costs(hs);
510  if (mean_access > 1.5) { // every 2nd access is a collision - increase hash size?
511  dump_access("hash-size-warning", hs, mean_access);
512 #if defined(DEVEL_RALF) && !defined(UNIT_TESTS)
513  gb_assert(mean_access<2.0); // hash with 50% speed or less
514 #endif // DEVEL_RALF
515  }
516 #else
517  if (hs->nelem >= (2*hsize)) {
518  GB_warningf("Performance leak - very slow hash detected (elems=%zu, size=%zu)\n", hs->nelem, hs->size);
519  GBK_dump_backtrace(stderr, "detected performance leak");
520  }
521 #endif // DEBUG
522  }
523 
524  for (size_t i = 0; i < hsize; i++) {
525  for (gbs_hash_entry *e = hs->entries[i]; e; ) {
526  free(e->key);
527  if (hs->freefun) hs->freefun(e->val);
528 
529  gbs_hash_entry *next = e->next;
531  e = next;
532  }
533  hs->entries[i] = NULp;
534  }
535  hs->nelem = 0;
536 }
537 
539  gb_assert(hs);
540  GBS_erase_hash(hs);
541  free(hs->entries);
542  free(hs);
543 }
544 
545 void GBS_hash_do_loop(GB_HASH *hs, gb_hash_loop_type func, void *client_data) {
546  size_t hsize = hs->size;
547  for (size_t i=0; i<hsize; i++) {
548  for (gbs_hash_entry *e = hs->entries[i]; e; ) {
549  gbs_hash_entry *next = e->next;
550  if (e->val) {
551  e->val = func(e->key, e->val, client_data);
552  if (!e->val) delete_from_list(hs, i, e);
553  }
554  e = next;
555  }
556  }
557 }
558 
559 void GBS_hash_do_const_loop(const GB_HASH *hs, gb_hash_const_loop_type func, void *client_data) {
560  size_t hsize = hs->size;
561  for (size_t i=0; i<hsize; i++) {
562  for (gbs_hash_entry *e = hs->entries[i]; e; ) {
563  gbs_hash_entry *next = e->next;
564  if (e->val) func(e->key, e->val, client_data);
565  e = next;
566  }
567  }
568 }
569 
570 size_t GBS_hash_elements(const GB_HASH *hs) {
571  return hs->nelem;
572 }
573 
574 const char *GBS_hash_next_element_that(const GB_HASH *hs, const char *last_key, bool (*condition)(const char *key, long val, void *cd), void *cd) {
575  /* Returns the key of the next element after 'last_key' matching 'condition' (i.e. where condition returns true).
576  * If 'last_key' is NULp, the first matching element is returned.
577  * Returns NULp if no (more) elements match the 'condition'.
578  */
579 
580  size_t size = hs->size;
581  size_t i = 0;
582  gbs_hash_entry *e = NULp;
583 
584  if (last_key) {
585  e = find_hash_entry(hs, last_key, &i);
586  if (!e) return NULp;
587 
588  e = e->next; // use next entry after 'last_key'
589  if (!e) i++;
590  }
591 
592  for (; i<size && !e; ++i) e = hs->entries[i]; // search first/next entry
593 
594  while (e) {
595  if ((*condition)(e->key, e->val, cd)) break;
596  e = e->next;
597  if (!e) {
598  for (i++; i<size && !e; ++i) e = hs->entries[i];
599  }
600  }
601 
602  return e ? e->key : NULp;
603 }
604 
605 static int wrap_hashCompare4gb_sort(const void *v0, const void *v1, void *sorter) {
606  const gbs_hash_entry *e0 = (const gbs_hash_entry*)v0;
607  const gbs_hash_entry *e1 = (const gbs_hash_entry*)v1;
608 
609  return ((gbs_hash_compare_function)sorter)(e0->key, e0->val, e1->key, e1->val);
610 }
611 
612 static size_t get_sorted_hash_values(const GB_HASH *hs, gbs_hash_compare_function sorter, gbs_hash_entry**& mtab) {
613  size_t hsize = hs->size;
614  ARB_calloc(mtab, hs->nelem);
615 
616  size_t values = 0;
617  for (size_t i = 0; i < hsize; i++) {
618  for (gbs_hash_entry *e = hs->entries[i]; e; e = e->next) {
619  if (e->val) {
620  mtab[values++] = e;
621  }
622  }
623  }
624 
625  GB_sort((void**)mtab, 0, values, wrap_hashCompare4gb_sort, (void*)sorter);
626  return values;
627 }
628 
630  gbs_hash_entry **mtab;
631  size_t values = get_sorted_hash_values(hs, sorter, mtab);
632 
633  for (size_t i = 0; i < values; i++) {
634  long new_val = func(mtab[i]->key, mtab[i]->val, client_data);
635  if (new_val != mtab[i]->val) GBS_write_hash(hs, mtab[i]->key, new_val);
636  }
637 
638  free(mtab);
639 }
640 
642  gbs_hash_entry **mtab;
643  size_t values = get_sorted_hash_values(hs, sorter, mtab);
644 
645  for (size_t i = 0; i < values; i++) {
646  func(mtab[i]->key, mtab[i]->val, client_data);
647  }
648 
649  free(mtab);
650 }
651 
652 
653 int GBS_HCF_sortedByKey(const char *k0, long /*v0*/, const char *k1, long /*v1*/) {
654  return strcmp(k0, k1);
655 }
656 
657 // ---------------------------------------------
658 // Some Hash Procedures for [long,long]
659 
660 inline long gbs_numhash_index(long key, long size) {
661  long x;
662  x = (key * (long long)97)%size; // make one multiplier a (long long) to avoid
663  if (x<0) x += size; // int overflow and abort if compiled with -ftrapv
664  return x;
665 }
666 
667 
668 GB_NUMHASH *GBS_create_numhash(size_t estimated_elements) {
669  size_t size = hash_size(estimated_elements);
670  GB_NUMHASH *hs = ARB_calloc<GB_NUMHASH>(1);
671 
672  hs->size = size;
673  hs->nelem = 0;
674  ARB_calloc(hs->entries, size);
675 
676  return hs;
677 }
678 
679 long GBS_read_numhash(GB_NUMHASH *hs, long key) {
680  size_t i = gbs_numhash_index(key, hs->size);
681  for (numhash_entry *e = hs->entries[i]; e; e = e->next) {
682  if (e->key==key) return e->val;
683  }
684  return 0;
685 }
686 
687 long GBS_write_numhash(GB_NUMHASH *hs, long key, long val) {
688  size_t i = gbs_numhash_index(key, hs->size);
689  long oldval = 0;
690 
691  if (val == 0) { // erase
692  numhash_entry **nextPtr = &(hs->entries[i]);
693 
694  for (numhash_entry *e = hs->entries[i]; e; e = e->next) {
695  if (e->key == key) {
696  *nextPtr = e->next; // unlink entry
697  gbm_free_mem(e, sizeof(*e), GBM_HASH_INDEX);
698  hs->nelem--;
699  return 0;
700  }
701  nextPtr = &(e->next);
702  }
703  }
704  else {
705  for (numhash_entry *e=hs->entries[i]; e; e=e->next) {
706  if (e->key==key) {
707  oldval = e->val; gb_assert(oldval);
708  e->val = val;
709  break;
710  }
711  }
712 
713  if (!oldval) {
715 
716  e->next = hs->entries[i];
717  e->key = key;
718  e->val = val;
719 
720  hs->nelem++;
721  hs->entries[i] = e;
722  }
723  }
724  return oldval;
725 }
726 
727 static void GBS_erase_numhash(GB_NUMHASH *hs) {
728  size_t hsize = hs->size;
729 
730  for (size_t i=0; i<hsize; i++) {
731  for (numhash_entry *e = hs->entries[i]; e; ) {
732  numhash_entry *next = e->next;
733 
734  gbm_free_mem(e, sizeof(*e), GBM_HASH_INDEX);
735  e = next;
736  }
737  }
738 
739  hs->nelem = 0;
740 }
741 
743  GBS_erase_numhash(hs);
744  free(hs->entries);
745  free(hs);
746 }
747 
748 // --------------------------------------------------------------------------------
749 
750 #ifdef UNIT_TESTS
751 
752 #include <test_unit.h>
753 
754 // determine hash quality
755 
756 struct gbs_hash_statistic_summary {
757  long count; // how many stats
758  long min_size, max_size, sum_size;
759  long min_nelem, max_nelem, sum_nelem;
760  long min_collisions, max_collisions, sum_collisions;
761  double min_fill_ratio, max_fill_ratio, sum_fill_ratio;
762  double min_hash_quality, max_hash_quality, sum_hash_quality;
763 
764  void init() {
765  count = 0;
766  min_size = min_nelem = min_collisions = LONG_MAX;
767  max_size = max_nelem = max_collisions = LONG_MIN;
768  min_fill_ratio = min_hash_quality = DBL_MAX;
769  max_fill_ratio = max_hash_quality = DBL_MIN;
770 
771  sum_size = sum_nelem = sum_collisions = 0;
772  sum_fill_ratio = sum_hash_quality = 0.0;
773  }
774 };
775 
776 class hash_statistic_manager : virtual Noncopyable {
777  GB_HASH *stat_hash;
778 public:
779  hash_statistic_manager() : stat_hash(NULp) { }
780  ~hash_statistic_manager() {
781  if (stat_hash) GBS_free_hash(stat_hash);
782  }
783 
784  gbs_hash_statistic_summary *get_stat_summary(const char *id) {
785  if (!stat_hash) stat_hash = GBS_create_dynaval_hash(10, GB_MIND_CASE, GBS_dynaval_free);
786 
787  long found = GBS_read_hash(stat_hash, id);
788  if (!found) {
789  gbs_hash_statistic_summary *stat; ARB_calloc(stat, 1);
790  stat->init();
791  found = (long)stat;
792  GBS_write_hash(stat_hash, id, found);
793  }
794 
795  return (gbs_hash_statistic_summary*)found;
796  }
797 };
798 
799 static void addto_hash_statistic_summary(gbs_hash_statistic_summary *stat, long size, long nelem, long collisions, double fill_ratio, double hash_quality) {
800  stat->count++;
801 
802  if (stat->min_size > size) stat->min_size = size;
803  if (stat->max_size < size) stat->max_size = size;
804 
805  if (stat->min_nelem > nelem) stat->min_nelem = nelem;
806  if (stat->max_nelem < nelem) stat->max_nelem = nelem;
807 
808  if (stat->min_collisions > collisions) stat->min_collisions = collisions;
809  if (stat->max_collisions < collisions) stat->max_collisions = collisions;
810 
811  if (stat->min_fill_ratio > fill_ratio) stat->min_fill_ratio = fill_ratio;
812  if (stat->max_fill_ratio < fill_ratio) stat->max_fill_ratio = fill_ratio;
813 
814  if (stat->min_hash_quality > hash_quality) stat->min_hash_quality = hash_quality;
815  if (stat->max_hash_quality < hash_quality) stat->max_hash_quality = hash_quality;
816 
817  stat->sum_size += size;
818  stat->sum_nelem += nelem;
819  stat->sum_collisions += collisions;
820  stat->sum_fill_ratio += fill_ratio;
821  stat->sum_hash_quality += hash_quality;
822 }
823 
824 static hash_statistic_manager hash_stat_man;
825 
826 static void test_clear_hash_statistic_summary(const char *id) {
827  hash_stat_man.get_stat_summary(id)->init();
828 }
829 
830 static void test_print_hash_statistic_summary(const char *id) {
831  gbs_hash_statistic_summary *stat = hash_stat_man.get_stat_summary(id);
832  long count = stat->count;
833  printf("Statistic summary for %li hashes of type '%s':\n", count, id);
834  printf("- size: min = %6li ; max = %6li ; mean = %6.1f\n", stat->min_size, stat->max_size, (double)stat->sum_size/count);
835  printf("- nelem: min = %6li ; max = %6li ; mean = %6.1f\n", stat->min_nelem, stat->max_nelem, (double)stat->sum_nelem/count);
836  printf("- fill_ratio: min = %5.1f%% ; max = %5.1f%% ; mean = %5.1f%%\n", stat->min_fill_ratio*100.0, stat->max_fill_ratio*100.0, (double)stat->sum_fill_ratio/count*100.0);
837  printf("- collisions: min = %6li ; max = %6li ; mean = %6.1f\n", stat->min_collisions, stat->max_collisions, (double)stat->sum_collisions/count);
838  printf("- hash_quality: min = %5.1f%% ; max = %5.1f%% ; mean = %5.1f%%\n", stat->min_hash_quality*100.0, stat->max_hash_quality*100.0, (double)stat->sum_hash_quality/count*100.0);
839 }
840 
841 static void test_calc_hash_statistic(const GB_HASH *hs, const char *id, int print) {
842  long queues = 0;
843  long collisions;
844  double fill_ratio = (double)hs->nelem/hs->size;
845  double hash_quality;
846 
847  for (size_t i = 0; i < hs->size; i++) {
848  if (hs->entries[i]) queues++;
849  }
850  collisions = hs->nelem - queues;
851 
852  hash_quality = (double)queues/hs->nelem; // no collisions means 100% quality
853 
854  if (print != 0) {
855  printf("Statistic for hash '%s':\n", id);
856  printf("- size = %zu\n", hs->size);
857  printf("- elements = %zu (fill ratio = %4.1f%%)\n", hs->nelem, fill_ratio*100.0);
858  printf("- collisions = %li (hash quality = %4.1f%%)\n", collisions, hash_quality*100.0);
859  }
860 
861  addto_hash_statistic_summary(hash_stat_man.get_stat_summary(id), hs->size, hs->nelem, collisions, fill_ratio, hash_quality);
862 }
863 
864 static long test_numhash_count_elems(GB_NUMHASH *hs) {
865  return hs->nelem;
866 }
867 
868 static void insert_into_hash(const char *key, long val, void *cl_toHash) {
869  GB_HASH *toHash = (GB_HASH*)cl_toHash;
870  GBS_write_hash(toHash, key, val);
871 }
872 static void erase_from_hash(const char *key, long val, void *cl_fromHash) {
873  GB_HASH *fromHash = (GB_HASH*)cl_fromHash;
874  long val2 = GBS_read_hash(fromHash, key);
875 
876  if (val2 == val) {
877  GBS_write_hash(fromHash, key, 0);
878  }
879  else {
880  printf("value mismatch in hashes_are_equal(): key='%s' val: %li != %li\n", key, val2, val); // NEED_NO_COV
881  }
882 }
883 
884 static bool hashes_are_equal(GB_HASH *h1, GB_HASH *h2) {
885  size_t count1 = GBS_hash_elements(h1);
886  size_t count2 = GBS_hash_elements(h2);
887 
888  bool equal = (count1 == count2);
889  if (equal) {
891 
892  GBS_hash_do_const_loop(h1, insert_into_hash, copy);
893  GBS_hash_do_const_loop(h2, erase_from_hash, copy);
894 
895  equal = (GBS_hash_elements(copy) == 0);
896  GBS_free_hash(copy);
897  }
898  return equal;
899 }
900 
901 struct TestData : virtual Noncopyable {
902  GB_HASH *mind;
903  GB_HASH *ignore;
904  GB_NUMHASH *num;
905 
906  TestData() {
907  mind = GBS_create_hash(100, GB_MIND_CASE);
908  ignore = GBS_create_hash(100, GB_IGNORE_CASE);
909  num = GBS_create_numhash(100);
910  }
911  ~TestData() {
912  GBS_free_numhash(num);
913  GBS_free_hash(ignore);
914  GBS_free_hash(mind);
915  }
916 
917  void reset() {
918  GBS_erase_hash(mind);
919  GBS_erase_hash(ignore);
920  GBS_erase_numhash(num);
921  }
922 
923  GB_HASH *get_hash(bool case_sens) {
924  return case_sens ? mind : ignore;
925  }
926 };
927 
928 static TestData TEST;
929 
930 static size_t test_hash_count_value(GB_HASH *hs, long val) {
931  size_t hsize = hs->size;
932  size_t count = 0;
933 
934  gb_assert(val != 0); // counting zero values makes no sense (cause these are not stored in the hash)
935 
936  for (size_t i = 0; i<hsize; ++i) {
937  for (gbs_hash_entry *e=hs->entries[i]; e; e=e->next) {
938  if (e->val == val) {
939  ++count;
940  }
941  }
942  }
943 
944  return count;
945 }
946 
947 void TEST_GBS_write_hash() {
948  TEST.reset();
949 
950  for (int case_sens = 0; case_sens <= 1; ++case_sens) {
951  GB_HASH *hash = TEST.get_hash(case_sens);
952 
953  GBS_write_hash(hash, "foo", 1);
955  TEST_EXPECT_EQUAL(GBS_read_hash(hash, "foo"), 1);
956 
957  GBS_write_hash(hash, "foo", 2);
959  TEST_EXPECT_EQUAL(GBS_read_hash(hash, "foo"), 2);
960 
961  GBS_write_hash(hash, "foo", 0);
963  TEST_EXPECT_ZERO(GBS_read_hash(hash, "foo"));
964 
965  GBS_write_hash(hash, "foo", 1);
966  GBS_write_hash(hash, "FOO", 2);
967  GBS_write_hash(hash, "BAR", 1);
968  GBS_write_hash(hash, "bar", 2);
969 
970  if (case_sens) {
972 
973  TEST_EXPECT_EQUAL(GBS_read_hash(hash, "foo"), 1);
974  TEST_EXPECT_EQUAL(GBS_read_hash(hash, "FOO"), 2);
975  TEST_EXPECT_ZERO(GBS_read_hash(hash, "Foo"));
976 
977  TEST_EXPECT_EQUAL(test_hash_count_value(hash, 1), 2);
978  TEST_EXPECT_EQUAL(test_hash_count_value(hash, 2), 2);
979  }
980  else {
982 
983  TEST_EXPECT_EQUAL(GBS_read_hash(hash, "foo"), 2);
984  TEST_EXPECT_EQUAL(GBS_read_hash(hash, "FOO"), 2);
985  TEST_EXPECT_EQUAL(GBS_read_hash(hash, "Foo"), 2);
986 
987  TEST_EXPECT_ZERO(test_hash_count_value(hash, 1));
988  TEST_EXPECT_EQUAL(test_hash_count_value(hash, 2), 2);
989  }
990 
991  if (case_sens) {
992  TEST_EXPECT_ZERO(GBS_read_hash(hash, "foobar"));
993  GBS_write_hash_no_strdup(hash, ARB_strdup("foobar"), 0);
994  TEST_EXPECT_ZERO(GBS_read_hash(hash, "foobar"));
995  GBS_write_hash_no_strdup(hash, ARB_strdup("foobar"), 3);
996  TEST_EXPECT_EQUAL(GBS_read_hash(hash, "foobar"), 3);
997  GBS_write_hash_no_strdup(hash, ARB_strdup("foobar"), 0);
998  TEST_EXPECT_ZERO(GBS_read_hash(hash, "foobar"));
999  }
1000  }
1001 }
1002 
1003 void TEST_GBS_incr_hash() {
1004  TEST.reset();
1005 
1006  for (int case_sens = 0; case_sens <= 1; ++case_sens) {
1007  GB_HASH *hash = TEST.get_hash(case_sens);
1008 
1009  GBS_incr_hash(hash, "foo");
1010  TEST_EXPECT_EQUAL(GBS_read_hash(hash, "foo"), 1);
1011 
1012  GBS_incr_hash(hash, "foo");
1013  TEST_EXPECT_EQUAL(GBS_read_hash(hash, "foo"), 2);
1014 
1015  GBS_incr_hash(hash, "FOO");
1016  TEST_EXPECT_EQUAL(GBS_read_hash(hash, "foo"), case_sens ? 2 : 3);
1017  TEST_EXPECT_EQUAL(GBS_read_hash(hash, "FOO"), case_sens ? 1 : 3);
1018  }
1019 }
1020 
1021 static void test_string_2_hashtab(GB_HASH *hash, char *data) {
1022  // modifies data
1023  char *p, *d, *dp;
1024  int c;
1025  char *nextp;
1026  char *str;
1027  int strlen;
1028  long val;
1029 
1030  for (p = data; p; p = nextp) {
1031  strlen = 0;
1032  for (dp = p; (c = *dp); dp++) {
1033  if (c==':') {
1034  if (dp[1] == ':') dp++;
1035  else break;
1036  }
1037  strlen++;
1038  }
1039  if (*dp) {
1040  nextp = strchr(dp, ' ');
1041  if (nextp) nextp++;
1042  }
1043  else break;
1044 
1045  str = ARB_calloc<char>(strlen+1);
1046  for (dp = p, d = str; (c = *dp); dp++) {
1047  if (c==':') {
1048  if (dp[1] == ':') {
1049  *(d++) = c;
1050  dp++;
1051  }
1052  else break;
1053  }
1054  else {
1055  *(d++) = c;
1056  }
1057  }
1058  val = atoi(dp+1);
1059  GBS_write_hash_no_strdup(hash, str, val);
1060  }
1061 }
1062 
1063 void TEST_GBS_hashtab_2_string() {
1064  TEST.reset();
1065 
1066  for (int case_sens = 0; case_sens <= 1; ++case_sens) {
1067  GB_HASH *hash = TEST.get_hash(case_sens);
1068 
1069  GBS_write_hash(hash, "foo", 1);
1070  GBS_write_hash(hash, "bar", 2);
1071  GBS_write_hash(hash, "FOO", 3);
1072  GBS_write_hash(hash, "BAR", 4);
1073  GBS_write_hash(hash, "foo:bar", 3);
1074  GBS_write_hash(hash, "FOO:bar", 4);
1075  }
1076  for (int case_sens = 0; case_sens <= 1; ++case_sens) {
1077  GB_HASH *hash = TEST.get_hash(case_sens);
1078 
1079  char *as_string = GBS_hashtab_2_string(hash);
1080  TEST_REJECT_NULL(as_string);
1081 
1082  GB_HASH *hash2 = GBS_create_hash(1000, case_sens ? GB_MIND_CASE : GB_IGNORE_CASE);
1083  test_string_2_hashtab(hash2, as_string);
1084  TEST_EXPECT(hashes_are_equal(hash, hash2));
1085  TEST_EXPECT(hashes_are_equal(hash, hash2));
1086 
1087  free(as_string);
1088  GBS_free_hash(hash2);
1089  }
1090 
1091  {
1092  GB_HASH *hash = TEST.get_hash(true);
1093  char *as_string = GBS_hashtab_2_string(hash);
1094 
1095  GB_HASH *hash2 = GBS_create_hash(21, GB_MIND_CASE);
1096  GBS_hash_do_const_sorted_loop(hash, insert_into_hash, GBS_HCF_sortedByKey, hash2);
1097 
1098  GB_HASH *hash3 = GBS_create_hash(100, GB_MIND_CASE);
1099  GBS_hash_do_const_sorted_loop(hash, insert_into_hash, GBS_HCF_sortedByKey, hash3);
1100 
1101  char *as_string2 = GBS_hashtab_2_string(hash2);
1102  char *as_string3 = GBS_hashtab_2_string(hash3);
1103 
1104  TEST_EXPECT_EQUAL__BROKEN(as_string, as_string2, "FOO::bar:4 BAR:4 bar:2 foo:1 FOO:3 foo::bar:3 ");
1105  TEST_EXPECT_EQUAL (as_string, as_string3);
1106 
1107  GBS_free_hash(hash3);
1108  GBS_free_hash(hash2);
1109 
1110  free(as_string3);
1111  free(as_string2);
1112  free(as_string);
1113  }
1114 }
1115 
1116 inline long key2val(long key, int pass) {
1117  long val;
1118  switch (pass) {
1119  case 1:
1120  val = key/3;
1121  break;
1122  case 2:
1123  val = key*17461;
1124  break;
1125  default :
1126  val = LONG_MIN;
1127  TEST_EXPECT(0); // NEED_NO_COV
1128  break;
1129  }
1130  return val;
1131 }
1132 
1133 void TEST_numhash() {
1134  GB_NUMHASH *numhash = GBS_create_numhash(10);
1135  GB_NUMHASH *numhash2 = GBS_create_numhash(10);
1136 
1137  const long LOW = -200;
1138  const long HIGH = 200;
1139  const long STEP = 17;
1140 
1141  long added = 0;
1142  for (int pass = 1; pass <= 2; ++pass) {
1143  added = 0;
1144  for (long key = LOW; key <= HIGH; key += STEP) {
1145  long val = key2val(key, pass);
1146  GBS_write_numhash(numhash, key, val);
1147  added++;
1148  }
1149 
1150  TEST_EXPECT_EQUAL(test_numhash_count_elems(numhash), added);
1151 
1152  for (long key = LOW; key <= HIGH; key += STEP) {
1153  TEST_EXPECT_EQUAL(key2val(key, pass), GBS_read_numhash(numhash, key));
1154  }
1155  }
1156 
1157  TEST_EXPECT_ZERO(GBS_read_numhash(numhash, -4711)); // not-existing entry
1158 
1159  // erase by overwrite:
1160  for (long key = LOW; key <= HIGH; key += STEP) {
1161  GBS_write_numhash(numhash2, key, GBS_read_numhash(numhash, key)); // copy numhash->numhash2
1162  GBS_write_numhash(numhash, key, (long)NULp);
1163  }
1164  TEST_EXPECT_EQUAL(test_numhash_count_elems(numhash2), added);
1165  TEST_EXPECT_ZERO(test_numhash_count_elems(numhash));
1166 
1167  GBS_free_numhash(numhash2); // free filled hash
1168  GBS_free_numhash(numhash); // free empty hash
1169 }
1170 
1171 
1172 static int freeCounter;
1173 static void freeDynamicHashElem(long cl_ptr) {
1174  GBS_dynaval_free(cl_ptr);
1175  freeCounter++;
1176 }
1177 
1178 void TEST_GBS_dynaval_hash() {
1179  const int SIZE = 10;
1180  const int ELEMS = 30;
1181 
1182  GB_HASH *dynahash = GBS_create_dynaval_hash(SIZE, GB_MIND_CASE, freeDynamicHashElem);
1183 
1184  for (int pass = 1; pass <= 2; ++pass) {
1185  freeCounter = 0;
1186 
1187  for (int i = 0; i<ELEMS; ++i) {
1188  char *val = GBS_global_string_copy("value %i", i);
1189  char *oldval = (char*)GBS_write_hash(dynahash, GBS_global_string("key %i", i), (long)val);
1190  free(oldval);
1191  }
1192 
1193  TEST_EXPECT_ZERO(freeCounter); // overwriting values shall not automatically free them
1194  }
1195 
1196  freeCounter = 0;
1197  GBS_free_hash(dynahash);
1198  TEST_EXPECT_EQUAL(freeCounter, ELEMS);
1199 }
1200 
1201 void TEST_GBS_optimize_hash_and_stats() {
1202  const int SIZE = 10;
1203  const int FILL = 70;
1204 
1205  test_clear_hash_statistic_summary("test");
1206  for (int pass = 1; pass <= 3; ++pass) {
1207  GB_HASH *hash = GBS_create_hash(SIZE, GB_MIND_CASE);
1208 
1209  for (int i = 1; i <= FILL; ++i) {
1210  const char *key = GBS_global_string("%i", i);
1211  GBS_write_hash(hash, key, i);
1212  }
1213  TEST_EXPECT(hash->nelem > hash->size); // ensure hash is overfilled!
1214 
1215  switch (pass) {
1216  case 1: // nothing, only free overfilled hash below
1217  break;
1218  case 2: // test overwrite overfilled hash
1219  for (int i = 1; i <= FILL; ++i) {
1220  const char *key = GBS_global_string("%i", i);
1221 
1222  TEST_EXPECT_EQUAL(GBS_read_hash(hash, key), i);
1223  GBS_write_hash(hash, key, 0);
1224  TEST_EXPECT_ZERO(GBS_read_hash(hash, key));
1225  }
1226  break;
1227  case 3: // test optimize
1228  GBS_optimize_hash(hash);
1229  TEST_EXPECT_LESS_EQUAL(hash->nelem, hash->size);
1230  break;
1231  default :
1232  TEST_EXPECT(0); // NEED_NO_COV
1233  break;
1234  }
1235 
1236  test_calc_hash_statistic(hash, "test", 1);
1237  GBS_free_hash(hash);
1238  }
1239 
1240  test_print_hash_statistic_summary("test");
1241 }
1242 
1243 static bool has_value(const char *, long val, void *cd) { return val == (long)cd; }
1244 static bool has_value_greater(const char *, long val, void *cd) { return val > (long)cd; }
1245 
1246 void TEST_GBS_hash_next_element_that() {
1247  TEST.reset();
1248 
1249  for (int case_sens = 0; case_sens <= 1; ++case_sens) {
1250  GB_HASH *hash = TEST.get_hash(case_sens);
1251 
1252  GBS_write_hash(hash, "foo", 0);
1253  GBS_write_hash(hash, "bar", 1);
1254  GBS_write_hash(hash, "foobar", 2);
1255  GBS_write_hash(hash, "barfoo", 3);
1256 
1257 #define READ_REVERSE(value) GBS_hash_next_element_that(hash, NULp, has_value, (void*)value)
1258 #define ASSERT_READ_REVERSE_RETURNS(value, expected) TEST_EXPECT_EQUAL((const char *)expected, READ_REVERSE(value));
1259 
1260  ASSERT_READ_REVERSE_RETURNS(/*0*/ NULp, NULp); // test search for element '0' (cast to 'void*' leads to warning)
1261  ASSERT_READ_REVERSE_RETURNS(1, "bar");
1262  ASSERT_READ_REVERSE_RETURNS(2, "foobar");
1263  ASSERT_READ_REVERSE_RETURNS(3, "barfoo");
1264  ASSERT_READ_REVERSE_RETURNS(4, NULp);
1265 
1266  const char *key = NULp;
1267  long sum = 0;
1268 
1269  for (int iter = 1; iter <= 3; ++iter) {
1270  key = GBS_hash_next_element_that(hash, key, has_value_greater, (void*)1);
1271  if (iter == 3) TEST_REJECT(key);
1272  else {
1273  TEST_REJECT_NULL(key);
1274  sum += GBS_read_hash(hash, key);
1275  }
1276  }
1277  TEST_EXPECT_EQUAL(sum, 5); // sum of all values > 1
1278  }
1279 }
1280 
1281 const size_t MAX_PRIME = sorted_primes[KNOWN_PRIMES-1];
1282 
1283 #if !defined(ASSERTION_USED) || defined(ENABLE_CRASH_TESTS)
1284 static size_t get_overflown_prime() { return gbs_get_a_prime(MAX_PRIME+1); }
1285 #endif
1286 #if defined(ASSERTION_USED) && defined(ENABLE_CRASH_TESTS)
1287 static void detect_prime_overflow() { get_overflown_prime(); }
1288 #endif // ASSERTION_USED
1289 
1290 void TEST_hash_specials__crashtest() {
1291  const size_t SOME_PRIME = 434201;
1292  TEST_EXPECT_EQUAL(gbs_get_a_prime(SOME_PRIME), SOME_PRIME);
1293  TEST_EXPECT_EQUAL(gbs_get_a_prime(MAX_PRIME), MAX_PRIME);
1294 
1295 #if defined(ASSERTION_USED)
1296  TEST_EXPECT_CODE_ASSERTION_FAILS(detect_prime_overflow);
1297 #else
1298  TEST_EXPECT_EQUAL(get_overflown_prime(), MAX_PRIME+1);
1299 #endif // ASSERTION_USED
1300 }
1301 
1302 #endif // UNIT_TESTS
void GBS_dynaval_free(long val)
Definition: adhash.cxx:278
static long write_hash(GB_HASH *hs, char *key, bool copyKey, long val)
Definition: adhash.cxx:420
string result
void GBS_hash_do_const_loop(const GB_HASH *hs, gb_hash_const_loop_type func, void *client_data)
Definition: adhash.cxx:559
long val
Definition: adhash.cxx:25
long gbs_numhash_index(long key, long size)
Definition: adhash.cxx:660
GB_CASE case_sens
Definition: adhash.cxx:31
void GBS_free_hash(GB_HASH *hs)
Definition: adhash.cxx:538
size_t hash_size(size_t estimated_elements)
Definition: adhash.cxx:245
long val
Definition: adhash.cxx:40
void GB_sort(void **array, size_t first, size_t behind_last, gb_compare_function compare, void *client_data)
Definition: arb_sort.cxx:27
static size_t sorted_primes[KNOWN_PRIMES]
Definition: adhash.cxx:53
long
Definition: AW_awar.cxx:152
int(* gbs_hash_compare_function)(const char *key0, long val0, const char *key1, long val1)
Definition: arbdb.h:132
#define KNOWN_PRIMES
Definition: adhash.cxx:52
static void gbs_hash_to_strstruct(const char *key, long val, void *cd_out)
Definition: adhash.cxx:357
long GBS_read_numhash(GB_NUMHASH *hs, long key)
Definition: adhash.cxx:679
char * ARB_strdup(const char *str)
Definition: arb_string.h:27
GB_NUMHASH * GBS_create_numhash(size_t estimated_elements)
Definition: adhash.cxx:668
const char * GBS_global_string(const char *templat,...)
Definition: arb_msg.cxx:203
const char * title
Definition: readseq.c:22
void GBS_hash_do_const_sorted_loop(const GB_HASH *hs, gb_hash_const_loop_type func, gbs_hash_compare_function sorter, void *client_data)
Definition: adhash.cxx:641
#define TEST_EXPECT_LESS_EQUAL(val, ref)
Definition: test_unit.h:1308
char * release()
Definition: arb_strbuf.h:129
void nput(char c, size_t count)
Definition: arb_strbuf.h:164
long(* gb_hash_loop_type)(const char *key, long val, void *client_data)
Definition: arbdb.h:130
long GBS_write_numhash(GB_NUMHASH *hs, long key, long val)
Definition: adhash.cxx:687
static void delete_from_list(GB_HASH *hs, size_t i, gbs_hash_entry *e)
Definition: adhash.cxx:399
static void GBS_erase_numhash(GB_NUMHASH *hs)
Definition: adhash.cxx:727
numhash_entry * next
Definition: adhash.cxx:41
void putlong(long l)
Definition: arb_strbuf.h:224
static int diff(int v1, int v2, int v3, int v4, int st, int en)
Definition: ClustalV.cxx:534
#define TEST_EXPECT(cond)
Definition: test_unit.h:1328
fflush(stdout)
void GB_warningf(const char *templat,...)
Definition: arb_msg.cxx:536
Definition: adhash.cxx:38
Definition: adhash.cxx:23
long GBS_write_hash(GB_HASH *hs, const char *key, long val)
Definition: adhash.cxx:454
static int wrap_hashCompare4gb_sort(const void *v0, const void *v1, void *sorter)
Definition: adhash.cxx:605
#define TEST_EXPECT_EQUAL__BROKEN(expr, want, got)
Definition: test_unit.h:1295
void GBS_optimize_hash(const GB_HASH *hs)
Definition: adhash.cxx:316
#define TEST_REJECT(cond)
Definition: test_unit.h:1330
#define TEST_REJECT_NULL(n)
Definition: test_unit.h:1325
GB_HASH * GBS_create_dynaval_hash(long estimated_elements, GB_CASE case_sens, void(*freefun)(long))
Definition: adhash.cxx:271
size_t nelem
Definition: adhash.cxx:46
char * key
Definition: adhash.cxx:24
#define SIZE
Definition: date.cxx:7
static gbs_hash_entry * find_hash_entry(const GB_HASH *hs, const char *key, size_t *index)
Definition: adhash.cxx:375
char * str
Definition: defines.h:20
void(* freefun)(long val)
Definition: adhash.cxx:34
#define GB_CALC_HASH_INDEX_CASE_IGNORED(string, index, size)
Definition: gb_hashindex.h:36
GB_write_int const char GB_write_autoconv_string WRITE_SKELETON(write_pointer, GBDATA *,"%p", GB_write_pointer) char *AW_awa if)(!gb_var) return strdup("")
Definition: AW_awar.cxx:163
void * gbm_get_mem(size_t size, long index)
Definition: gb_memory.h:130
gbs_hash_entry ** entries
Definition: adhash.cxx:32
const char * GBS_hash_next_element_that(const GB_HASH *hs, const char *last_key, bool(*condition)(const char *key, long val, void *cd), void *cd)
Definition: adhash.cxx:574
long key
Definition: adhash.cxx:39
numhash_entry ** entries
Definition: adhash.cxx:47
GB_CASE
Definition: arb_core.h:30
void(* gb_hash_const_loop_type)(const char *key, long val, void *client_data)
Definition: arbdb.h:131
#define TEST_EXPECT_ZERO(cond)
Definition: test_unit.h:1085
gbs_hash_entry * next
Definition: adhash.cxx:26
while(1)
static void copy(double **i, double **j)
Definition: trnsprob.cxx:32
void GB_internal_error(const char *message)
Definition: arb_msg.cxx:481
TYPE * ARB_calloc(size_t nelem)
Definition: arb_mem.h:81
void GBS_hash_do_sorted_loop(GB_HASH *hs, gb_hash_loop_type func, gbs_hash_compare_function sorter, void *client_data)
Definition: adhash.cxx:629
#define gb_assert(cond)
Definition: arbdbt.h:11
GB_HASH * GBS_create_hash(long estimated_elements, GB_CASE case_sens)
Definition: adhash.cxx:253
#define TEST_EXPECT_CODE_ASSERTION_FAILS(cb)
Definition: test_unit.h:1252
static size_t get_sorted_hash_values(const GB_HASH *hs, gbs_hash_compare_function sorter, gbs_hash_entry **&mtab)
Definition: adhash.cxx:612
void GBK_dump_backtrace(FILE *out, const char *message)
Definition: arb_msg.cxx:416
size_t nelem
Definition: adhash.cxx:30
size_t GBS_hash_elements(const GB_HASH *hs)
Definition: adhash.cxx:570
char * GBS_hashtab_2_string(const GB_HASH *hash)
Definition: adhash.cxx:368
long GBS_incr_hash(GB_HASH *hs, const char *key)
Definition: adhash.cxx:467
long GBS_write_hash_no_strdup(GB_HASH *hs, char *key, long val)
Definition: adhash.cxx:459
static ARB_init_perl_interface init
Definition: ARB_ext.c:101
#define NULp
Definition: cxxforward.h:114
#define GB_CALC_HASH_INDEX(string, index, size, caseSens)
Definition: gb_hashindex.h:70
#define GB_CALC_HASH_INDEX_CASE_SENSITIVE(string, index, size)
Definition: gb_hashindex.h:26
long GBS_read_hash(const GB_HASH *hs, const char *key)
Definition: adhash.cxx:392
static void GBS_erase_hash(GB_HASH *hs)
Definition: adhash.cxx:493
void GBS_free_numhash(GB_NUMHASH *hs)
Definition: adhash.cxx:742
#define TEST()
Definition: admalloc.cxx:295
void gbm_free_mem(void *block, size_t size, long index)
Definition: gb_memory.h:131
long size
Definition: adhash.cxx:45
size_t size
Definition: adhash.cxx:29
size_t gbs_get_a_prime(size_t above_or_equal_this)
Definition: adhash.cxx:193
#define TEST_EXPECT_EQUAL(expr, want)
Definition: test_unit.h:1294
int GBS_HCF_sortedByKey(const char *k0, long, const char *k1, long)
Definition: adhash.cxx:653
char * GBS_global_string_copy(const char *templat,...)
Definition: arb_msg.cxx:194
void put(char c)
Definition: arb_strbuf.h:158
void print(const T &t)
Definition: test_unit.h:359
void GBS_hash_do_loop(GB_HASH *hs, gb_hash_loop_type func, void *client_data)
Definition: adhash.cxx:545