-
Notifications
You must be signed in to change notification settings - Fork 6
Expand file tree
/
Copy pathhashmap.cpp
More file actions
181 lines (164 loc) · 4.24 KB
/
hashmap.cpp
File metadata and controls
181 lines (164 loc) · 4.24 KB
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
// This file is part of SmallBASIC
//
// Support for dictionary/associative array variables
//
// This program is distributed under the terms of the GPL v2.0 or later
// Download the GNU Public License (GPL) from www.gnu.org
//
// Copyright(C) 2007-2016 Chris Warren-Smith.
#include "config.h"
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <ctype.h>
#include <cstdio>
#include "include/var.h"
#include "include/hashmap.h"
#define MAP_SIZE 32
/**
* Our internal tree element node
*/
typedef struct Node {
var_p_t key;
var_p_t value;
struct Node *left, *right;
} Node;
/**
* Returns a new tree node
*/
Node *tree_create_node(var_p_t key) {
Node *node = (Node *)malloc(sizeof(Node));
node->key = key;
node->value = nullptr;
node->left = nullptr;
node->right = nullptr;
return node;
}
int str_compare(const char *s1, int s1n, const char *s2, int s2n) {
int result = 0;
for (int i = 0;; i++) {
if (i == s1n || i == s2n) {
result = s1n < s2n ? -1 : s1n > s2n ? 1 : 0;
break;
}
char c1 = s1[i];
char c2 = s2[i];
if (c1 != c2) {
c1 = tolower(c1);
c2 = tolower(c2);
if (c1 != c2) {
result = c1 < c2 ? -1 : 1;
break;
}
}
}
return result;
}
static inline int tree_compare(const char *key, int length, var_p_t vkey) {
int len1 = length;
if (len1 && key[len1 - 1] == '\0') {
len1--;
}
int len2 = vkey->v.p.length;
if (len2 && vkey->v.p.ptr[len2 - 1] == '\0') {
len2--;
}
return str_compare(key, len1, vkey->v.p.ptr, len2);
}
Node *tree_search(Node **rootp, const char *key, int length) {
while (*rootp != nullptr) {
int r = tree_compare(key, length, (*rootp)->key);
if (r == 0) {
return *rootp;
}
rootp = (r < 0) ? &(*rootp)->left : &(*rootp)->right;
}
Node *result = tree_create_node(nullptr);
*rootp = result;
return result;
}
Node *tree_find(Node **rootp, const char *key, int length) {
while (*rootp != nullptr) {
int r = tree_compare(key, length, (*rootp)->key);
if (r == 0) {
return *rootp;
}
rootp = (r < 0) ? &(*rootp)->left : &(*rootp)->right;
}
return nullptr;
}
int hashmap_get_hash(const char *key, int length) {
int hash = 1, i;
for (i = 0; i < length && key[i] != '\0'; i++) {
hash += tolower(key[i]);
hash <<= 3;
hash ^= (hash >> 3);
}
return hash;
}
static inline Node *hashmap_search(var_p_t map, const char *key, int length) {
int index = hashmap_get_hash(key, length) % map->v.m.size;
Node **table = (Node **)map->v.m.map;
Node *result = table[index];
if (result == nullptr) {
// new entry
result = table[index] = tree_create_node(nullptr);
} else {
int r = tree_compare(key, length, result->key);
if (r < 0) {
result = tree_search(&result->left, key, length);
} else if (r > 0) {
result = tree_search(&result->right, key, length);
}
}
return result;
}
static inline Node *hashmap_find(var_p_t map, const char *key) {
int length = strlen(key);
int index = hashmap_get_hash(key, length) % map->v.m.size;
Node **table = (Node **)map->v.m.map;
Node *result = table[index];
if (result != nullptr) {
int r = tree_compare(key, length, result->key);
if (r < 0 && result->left != nullptr) {
result = tree_find(&result->left, key, length);
} else if (r > 0 && result->right != nullptr) {
result = tree_find(&result->right, key, length);
} else if (r != 0) {
result = nullptr;
}
}
return result;
}
void hashmap_create(var_p_t map, int size) {
map->type = V_MAP;
map->v.m.count = 0;
map->v.m.id = -1;
map->v.m.lib_id = -1;
map->v.m.cls_id = -1;
if (size == 0) {
map->v.m.size = MAP_SIZE;
} else {
map->v.m.size = (size * 100) / 75;
}
map->v.m.map = calloc(map->v.m.size, sizeof(Node *));
}
var_p_t hashmap_putv(var_p_t map, const var_p_t key) {
assert(key->type == V_STR);
Node *node = hashmap_search(map, key->v.p.ptr, key->v.p.length);
assert(node->key == nullptr);
node->key = key;
node->value = v_new();
map->v.m.count++;
return node->value;
}
var_p_t hashmap_get(var_p_t map, const char *key) {
var_p_t result;
Node *node = hashmap_find(map, key);
if (node != nullptr) {
result = node->value;
} else {
result = nullptr;
}
return result;
}