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
|
/*
htop
(C) 2004-2006 Hisham H. Muhammad
Released under the GNU GPL, see the COPYING file
in the source distribution for its full text.
*/
#include "Hashtable.h"
#include <stdlib.h>
#include <stdbool.h>
#include "debug.h"
/*{
typedef struct Hashtable_ Hashtable;
typedef void(*Hashtable_PairFunction)(int, void*, void*);
typedef struct HashtableItem {
int key;
void* value;
struct HashtableItem* next;
} HashtableItem;
struct Hashtable_ {
int size;
HashtableItem** buckets;
int items;
bool owner;
};
}*/
HashtableItem* HashtableItem_new(int key, void* value) {
HashtableItem* this;
this = (HashtableItem*) malloc(sizeof(HashtableItem));
this->key = key;
this->value = value;
this->next = NULL;
return this;
}
Hashtable* Hashtable_new(int size, bool owner) {
Hashtable* this;
this = (Hashtable*) malloc(sizeof(Hashtable));
this->size = size;
this->buckets = (HashtableItem**) calloc(sizeof(HashtableItem*), size);
this->owner = owner;
return this;
}
void Hashtable_delete(Hashtable* this) {
for (int i = 0; i < this->size; i++) {
HashtableItem* walk = this->buckets[i];
while (walk != NULL) {
if (this->owner)
free(walk->value);
HashtableItem* savedWalk = walk;
walk = savedWalk->next;
free(savedWalk);
}
}
free(this->buckets);
free(this);
}
inline int Hashtable_size(Hashtable* this) {
return this->items;
}
void Hashtable_put(Hashtable* this, int key, void* value) {
int index = key % this->size;
HashtableItem** bucketPtr = &(this->buckets[index]);
while (true)
if (*bucketPtr == NULL) {
*bucketPtr = HashtableItem_new(key, value);
this->items++;
break;
} else if ((*bucketPtr)->key == key) {
if (this->owner)
free((*bucketPtr)->value);
(*bucketPtr)->value = value;
break;
} else
bucketPtr = &((*bucketPtr)->next);
}
void* Hashtable_remove(Hashtable* this, int key) {
int index = key % this->size;
HashtableItem** bucketPtr = &(this->buckets[index]);
while (true)
if (*bucketPtr == NULL) {
return NULL;
break;
} else if ((*bucketPtr)->key == key) {
void* savedValue = (*bucketPtr)->value;
HashtableItem* savedNext = (*bucketPtr)->next;
free(*bucketPtr);
(*bucketPtr) = savedNext;
this->items--;
if (this->owner) {
free(savedValue);
return NULL;
} else {
return savedValue;
}
} else
bucketPtr = &((*bucketPtr)->next);
}
//#include <stdio.h>
inline void* Hashtable_get(Hashtable* this, int key) {
int index = key % this->size;
HashtableItem* bucketPtr = this->buckets[index];
// fprintf(stderr, "%d -> %d\n", key, index);
while (true) {
if (bucketPtr == NULL) {
return NULL;
} else if (bucketPtr->key == key) {
return bucketPtr->value;
} else
bucketPtr = bucketPtr->next;
// fprintf(stderr, "*\n");
}
}
void Hashtable_foreach(Hashtable* this, Hashtable_PairFunction f, void* userData) {
for (int i = 0; i < this->size; i++) {
HashtableItem* walk = this->buckets[i];
while (walk != NULL) {
f(walk->key, walk->value, userData);
walk = walk->next;
}
}
}
|
