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
|
#include "hash_map.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define INITIAL_SIZE (16)
#define LOAD_FACTOR_THRESHOLD (0.75)
typedef struct Pair {
char *key;
int value;
struct Pair *next;
} Pair;
typedef struct HashMap {
Pair **table;
size_t size;
size_t count;
} HashMap;
static unsigned int hash(const char *key, size_t size) {
unsigned int hash_value = 0;
while (*key) hash_value = (hash_value * 31) + *key++;
return hash_value % size;
}
static void resize(HashMap *map) {
size_t new_size = map->size * 2;
Pair **new_table = (Pair**)calloc(new_size, sizeof(Pair*));
assert(new_table);
for (size_t i = 0; i < map->size; ++i) {
Pair *pair = map->table[i];
while (pair) {
unsigned int index = hash(pair->key, new_size);
Pair *next = pair->next;
pair->next = new_table[index];
new_table[index] = pair;
pair = next;
}
}
free(map->table);
map->table = new_table;
map->size = new_size;
}
HashMap *hashmap_create(void) {
HashMap *map = (HashMap*)malloc(sizeof(HashMap));
assert(map);
map->size = INITIAL_SIZE;
map->count = 0;
map->table = (Pair**)calloc(map->size, sizeof(Pair*));
assert(map->table);
return map;
}
void hashmap_insert(HashMap *map, const char *key, int value) {
int *old_value = hashmap_get(map, key);
if (old_value) {
*old_value = value;
return;
}
if ((float)map->count / map->size > LOAD_FACTOR_THRESHOLD) resize(map);
unsigned int index = hash(key, map->size);
Pair *new_pair = (Pair*)malloc(sizeof(Pair));
assert(new_pair);
new_pair->key = strdup(key);
assert(new_pair->key);
new_pair->value = value;
new_pair->next = map->table[index];
map->table[index] = new_pair;
map->count++;
}
int *hashmap_get(HashMap *map, const char *key) {
unsigned int index = hash(key, map->size);
Pair *pair = map->table[index];
while (pair) {
if (strcmp(pair->key, key) == 0) return &pair->value;
pair = pair->next;
}
return NULL;
}
void hashmap_delete(HashMap *map, const char *key) {
unsigned int index = hash(key, map->size);
Pair *pair = map->table[index];
Pair *prev = NULL;
while (pair) {
if (strcmp(pair->key, key) == 0) {
if (prev) prev->next = pair->next;
else map->table[index] = pair->next;
free(pair->key);
free(pair);
map->count--;
return;
}
prev = pair;
pair = pair->next;
}
}
void hashmap_free(HashMap *map) {
for (size_t i = 0; i < map->size; ++i) {
Pair *pair = map->table[i];
while (pair) {
Pair *temp = pair;
pair = pair->next;
free(temp->key);
free(temp);
}
}
free(map->table);
free(map);
}
void hashmap_iterate(HashMap *map, void (*callback)(const char *key, int value)) {
for (size_t i = 0; i < map->size; ++i) {
Pair *pair = map->table[i];
while (pair) {
callback(pair->key, pair->value);
pair = pair->next;
}
}
}
|
