-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathexp_hash.h
141 lines (108 loc) · 3.09 KB
/
exp_hash.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#ifndef _exp_hash_h
#define _exp_hash_h
/* This was entirely experimental
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <limits.h>
#include <stdarg.h>
#include <assert.h>
#include <string.h>
#include <inttypes.h>
// Colours for error and diagnostic prints
#define RED "\x1B[31m"
#define GREEN "\e[32m"
#define YELLOW "\e[93m"
#define END "\e[0m"
#define POW_SIZE 24
#define COLLISION 1
#define OPEN_ADDR 2
#define INT_KEY_INT_VAL 1
#define INT_KEY_STR_VAL 2
#define STR_KEY_STR_VAL 3
#define STR_KEY_INT_VAL 4
// Pre-defined sizes for optimisations
#define SIZE_int_k_int_v sizeof(struct INT_k_INT_v)
#define SIZE_int_k_str_v sizeof(struct INT_k_STR_v)
#define SIZE_str_k_str_v sizeof(struct STR_k_STR_v)
#define SIZE_str_k_int_v sizeof(struct STR_k_INT_v)
#define SIZE_hash sizeof(struct Hash)
#define SIZE_int_node sizeof(struct int_node)
#define SIZE_int sizeof(int)
#define DEFAULT_LF 0.75
// Collision nodes
typedef struct int_node
{
int k;
int v;
struct int_node *next;
} int_node;
// Open addressing: int key, int val
typedef struct INT_k_INT_v
{
int k;
int v;
unsigned int distance;
} INT_k_INT_v;
// Open addressing: int key, string val
typedef struct INT_k_STR_v
{
int k;
char *v;
int distance;
} INT_k_STR_v;
typedef struct STR_k_STR_v
{
char *k;
char *v;
int distance;
} STR_k_STR_v;
typedef struct STR_k_INT_v
{
char *k;
int v;
int distance;
} STR_k_INT_v;
typedef struct Hash
{
// Open addressing and collision nodes
// INT_k_INT_v ** int_k_int_v; EXPERIMENTAL
int * int_k_int_v;
INT_k_STR_v ** int_k_str_v;
STR_k_STR_v ** str_k_str_v;
STR_k_INT_v ** str_k_int_v;
unsigned int cur_size;
unsigned int num_elem;
unsigned int k_v_type;
// Size until next resize
unsigned int to_resize;
// Max probes until resize
unsigned int probe_limit;
unsigned int type;
double load_factor;
} Hash;
// Function decl
extern INT_k_INT_v * createINT_k_INT_v(int cur_key, int cur_value, int dist);
extern INT_k_STR_v * createINT_k_STR_v(int cur_key, char *cur_value, int dist);
extern Hash * createHash(int elements, ...);
extern void put (Hash * H, int k);
extern void put_INT_k_INT_v (Hash * H, int cur_key);
extern void put_INT_k_STR_v (Hash * H, int cur_key);
extern int get(Hash * H, void * key);
extern int get_INT_k_INT_v(Hash * H, int key);
extern int get_INT_k_STR_v(Hash * H, int key);
extern void del(Hash * H, int key);
extern void resize(Hash * H);
extern void resize_OPEN_INT_k_INT_v(Hash * old_H);
extern void resize_OPEN_INT_k_STR_v(Hash * old_H);
extern unsigned int overwriteKey(Hash * H, int key, int val, int gen_key);
extern void set_lf (Hash * H, double new_load);
extern void insert(Hash * H, int cur_key, int cur_value);
extern void free_hash(Hash * H);
extern void printHash(Hash * H);
extern double load_factor(Hash * H);
extern void swap_INT_k_INT_v(INT_k_INT_v ** tmp1, INT_k_INT_v ** tmp2);
extern void swap_INT_k_STR_v(INT_k_STR_v ** tmp1, INT_k_STR_v ** tmp2);
#endif