-
Notifications
You must be signed in to change notification settings - Fork 0
/
ts_hashtable.cpp
70 lines (63 loc) · 1.71 KB
/
ts_hashtable.cpp
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ts_hashtable.h"
ts_hashtable * new_hashtable(int capacity) {
ts_hashtable * table = (ts_hashtable *)malloc(sizeof(ts_hashtable));
table -> capacity = capacity;
table -> nodes = (ts_hashnode_t*)malloc(sizeof(ts_hashnode_t) * capacity);
memset(table -> nodes, 0, sizeof(ts_hashnode_t) * capacity);
return table;
}
// return hastable_has
bool hashtable_set(ts_hashtable * table, hash_data_t data) {
int index = data % table -> capacity;
ts_hashnode_t* hash_table = table -> nodes;
if(!hash_table[index].valid &&
__sync_bool_compare_and_swap(&hash_table[index].valid, false, true)) {
hash_table[index].data = data;
hash_table[index].next = NULL;
return false;
}
else {
ts_hashnode_t* node = hash_table + index;
ts_hashnode_t* new_node = (ts_hashnode_t*)malloc(sizeof(ts_hashnode_t));
new_node -> next = NULL;
new_node -> data = data;
while(true) {
if(node -> data == data) {
free(new_node);
return true;
}
if(node -> next == NULL &&
__sync_bool_compare_and_swap(&node -> next, NULL, new_node)) {
return false;
}
node = node -> next;
}
}
}
bool hashtable_has(ts_hashtable * table, hash_data_t data) {
int index = data % table -> capacity;
ts_hashnode_t* hash_table = table -> nodes;
if(!hash_table[index].valid) {
return false;
}
else {
ts_hashnode_t* node = hash_table + index;
while(node != NULL) {
if(node -> data == data) {
return true;
}
node = node -> next;
}
return false;
}
}
void hashtable_free(ts_hashtable * table) {
free(table -> nodes);
free(table);
}
void hashtable_reset(ts_hashtable * table) {
memset(table -> nodes, 0, sizeof(ts_hashnode_t) * table -> capacity);
}