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
|
// Copyright (C) 2023 Dzshy <dzshy@outlook.com>. All Rights Reserved.
// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0.
#include "htable.h"
#include <stdlib.h>
#include <string.h>
#define HTFL_NUL 0
#define HTFL_VAL 1
#define HTFL_DEL 2
static void *htable_end(HTable *ht)
{
return ht->buf + ht->cap * (ht->elemsz + 1);
}
static void rebuild(HTable *ht)
{
HTable newht;
htable_init(&newht, ht->elemsz, ht->size * 8, ht->hash, ht->eq);
void *iter = htable_begin(ht);
while (iter != NULL) {
htable_insert(&newht, iter);
iter = htable_next(ht, iter);
}
free(ht->buf);
*ht = newht;
}
static uint8_t getflag(void *iter) { return *(uint8_t *)(iter - 1); }
static void setflag(void *iter, uint8_t flag) { *(uint8_t *)(iter - 1) = flag; }
void htable_init(HTable *ht, int elemsz, int cap, uint32_t (*hash)(void *),
bool (*eq)(void *, void *))
{
if (cap < 16)
cap = 16;
ht->buf = malloc(cap * (elemsz + 1));
memset(ht->buf, 0, cap * (elemsz + 1));
ht->size = 0;
ht->cap = cap;
ht->taken = 0;
ht->begin = NULL;
ht->elemsz = elemsz;
ht->hash = hash;
ht->eq = eq;
}
bool htable_insert(HTable *ht, void *elem)
{
if (ht->taken + 1 > ht->cap / 4) {
rebuild(ht);
}
ht->taken++;
ht->size++;
int hashcode = ht->hash(elem) % ht->cap;
void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1;
while (getflag(pos) != HTFL_NUL) {
if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem))
return false;
pos += ht->elemsz + 1;
if (pos >= htable_end(ht)) { // arrived end, restart from beginning
pos = ht->buf + 1;
}
}
memcpy(pos, elem, ht->elemsz);
setflag(pos, HTFL_VAL);
if (pos < ht->begin || ht->begin == NULL) {
ht->begin = pos;
}
}
void htable_del(HTable *ht, void *iter)
{
ht->size--;
setflag(iter, HTFL_DEL);
if (iter == ht->begin) {
ht->begin = htable_next(ht, iter);
}
}
void *htable_find(HTable *ht, void *elem)
{
int hashcode = ht->hash(elem) % ht->cap;
void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1;
while (getflag(pos) != HTFL_NUL) {
if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem))
return pos;
pos += ht->elemsz + 1;
if (pos >= htable_end(ht)) { // arrived end, restart from beginning
pos = ht->buf + 1;
}
}
return NULL;
}
void *htable_begin(HTable *ht) { return ht->begin; }
void *htable_next(HTable *ht, void *iter)
{
void *pos = iter;
pos += ht->elemsz + 1;
while (getflag(pos) != HTFL_VAL) {
pos += ht->elemsz + 1;
if (pos >= htable_end(ht)) { // arrived end, restart from beginning
return NULL;
}
}
return pos;
}
|
