biomcmc-lib  0.1
low level library for phylogenetic analysis
hashtable.h
Go to the documentation of this file.
1 /*
2  * This file is part of biomcmc-lib, a low-level library for phylogenomic analysis.
3  * Copyright (C) 2019-today Leonardo de Oliveira Martins [ leomrtns at gmail.com; http://www.leomartins.org ]
4  *
5  * biomcmc is free software; you can redistribute it and/or modify it under the terms of the GNU General Public
6  * License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later
7  * version.
8  *
9  * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied
10  * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
11  * details (file "COPYING" or http://www.gnu.org/copyleft/gpl.html).
12  */
13 
23 #ifndef _biomcmc_hashtable_h_
24 #define _biomcmc_hashtable_h_
25 
26 #include "hashfunctions.h"
27 
28 typedef struct hashtable_struct* hashtable;
29 typedef struct hashtable_item_struct* hashtable_item;
30 typedef struct bip_hashtable_struct* bip_hashtable;
31 typedef struct bip_hashitem_struct* bip_hashitem;
32 
34 struct hashtable_item_struct {
36  char* key;
38  int value;
39 };
40 
42 struct hashtable_struct
43 {
45  int size;
47  int probelength;
49  uint32_t h;
50  uint32_t a1,
51  a2,
52  b1,
53  b2,
54  P;
56  hashtable_item* table;
58  int ref_counter;
59 };
60 
62 struct bip_hashtable_struct
63 {
64  int size;
65  int probelength;
66  int maxfreq;
67  uint32_t h;
68  uint32_t a1, a2, b1, b2, P;
69  bip_hashitem* table;
70  int ref_counter;
71 };
72 
74 struct bip_hashitem_struct {
75  bipartition key;
76  int count;
77 };
78 
80 void insert_hashtable (hashtable ht, char* key, int value);
82 int lookup_hashtable (hashtable ht, char* key);
84 hashtable new_hashtable (int size);
86 void del_hashtable (hashtable ht);
87 
89 bip_hashtable new_bip_hashtable (int size);
91 void del_bip_hashtable (bip_hashtable ht);
93 void bip_hashtable_insert (bip_hashtable ht, bipartition key);
95 double bip_hashtable_get_frequency (bip_hashtable ht, bipartition key);
96 
97 #endif
bip_hashitem_struct::count
int count
pointer to bipartition (must update ref_counter)
Definition: hashtable.h:76
new_bip_hashtable
bip_hashtable new_bip_hashtable(int size)
Create new hashtable of size bipartitions.
Definition: hashtable.c:155
hashtable_struct
Hash table (vector indexed by strings).
Definition: hashtable.h:42
hashtable_struct::table
hashtable_item * table
Vector with key/value pairs.
Definition: hashtable.h:56
del_hashtable
void del_hashtable(hashtable ht)
Free hashtable space.
Definition: hashtable.c:63
hashtable_struct::probelength
int probelength
Number of collisions before empty slot is found.
Definition: hashtable.h:47
hashfunctions.h
Collections of hash functions for 32 and 64 bits, including one-liners, murmurhash, and xxhash.
hashtable_struct::h
uint32_t h
Value set by hash(). Used in hash1() and hash2() to avoid calling hash() again.
Definition: hashtable.h:49
bip_hashtable_struct::maxfreq
int maxfreq
Number of collisions before empty slot is found.
Definition: hashtable.h:66
bip_hashtable_insert
void bip_hashtable_insert(bip_hashtable ht, bipartition key)
Insert key (bipartition) into bipartition hashtable, adding one to its count (freq).
Definition: hashtable.c:209
bip_hashtable_struct::P
uint32_t P
Random values used in hash functions.
Definition: hashtable.h:68
hashtable_item_struct::value
int value
Integer (position in vector where hashtable_item_struct::key can be found)
Definition: hashtable.h:38
hashtable_struct::size
int size
Table size.
Definition: hashtable.h:45
hashtable_item_struct::key
char * key
String (vector of char).
Definition: hashtable.h:36
bip_hashtable_get_frequency
double bip_hashtable_get_frequency(bip_hashtable ht, bipartition key)
Return frequency of bipartition (count/maxfreq) or zero if not found.
Definition: hashtable.c:235
hashtable_item_struct
key/value pair for hash table
Definition: hashtable.h:34
bip_hashtable_struct
Hash table of bipartitions (see hashtable.h for original version, with string keys and integer values...
Definition: hashtable.h:62
hashtable_struct::ref_counter
int ref_counter
Counter of how many external references (structures sharing this hashtable) to avoid deletion...
Definition: hashtable.h:58
hashtable_struct::P
uint32_t P
Random values used in hash functions.
Definition: hashtable.h:50
insert_hashtable
void insert_hashtable(hashtable ht, char *key, int value)
Insert key/value pair into hashtable.
Definition: hashtable.c:107
bip_hashtable_struct::h
uint32_t h
frequency (integer) of most frequent bipartition
Definition: hashtable.h:67
bip_hashtable_struct::ref_counter
int ref_counter
Vector with key/value pairs.
Definition: hashtable.h:70
bip_hashtable_struct::probelength
int probelength
Table size.
Definition: hashtable.h:65
bip_hashitem_struct
key (bipartition) and value (frequency) pair for hash table of bipartitions
Definition: hashtable.h:74
lookup_hashtable
int lookup_hashtable(hashtable ht, char *key)
Return location (value) of corresponding key (string) or negative value if not found.
Definition: hashtable.c:132
bipartition_struct
Bit-string representation of splits.
Definition: bipartition.h:30
del_bip_hashtable
void del_bip_hashtable(bip_hashtable ht)
Free bipartition hashtable space.
Definition: hashtable.c:190
new_hashtable
hashtable new_hashtable(int size)
Create new hashtable of size elements.
Definition: hashtable.c:26
Generated by   doxygen 1.8.13