aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/hash_table.c91
-rw-r--r--src/hash_table.h3
-rw-r--r--src/priority_queue.h2
-rw-r--r--src/str.c7
4 files changed, 60 insertions, 43 deletions
diff --git a/src/hash_table.c b/src/hash_table.c
index 3b635f4..e738a9b 100644
--- a/src/hash_table.c
+++ b/src/hash_table.c
@@ -7,9 +7,6 @@
#define HTFL_VAL 1
#define HTFL_DEL 2
-static void *hash_table_end(hash_table_t *ht) {
- return ht->buf + ht->cap * (ht->elemsz + 1);
-}
static void rebuild(hash_table_t *ht) {
hash_table_t newht;
@@ -20,22 +17,20 @@ static void rebuild(hash_table_t *ht) {
iter = hash_table_next(ht, iter);
}
free(ht->buf);
+ free(ht->flagbuf);
*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 init_hash_table(hash_table_t *ht, int64_t elemsz, int64_t cap,
uint64_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->buf = malloc(cap * elemsz);
+ ht->flagbuf = malloc(cap);
+ memset(ht->buf, 0, cap * elemsz);
+ memset(ht->flagbuf, 0, cap);
ht->size = 0;
ht->cap = cap;
ht->taken = 0;
- ht->begin = NULL;
ht->elemsz = elemsz;
ht->hash = hash;
ht->eq = eq;
@@ -47,53 +42,69 @@ bool hash_table_insert(hash_table_t *ht, void *elem) {
}
ht->taken++;
ht->size++;
- int64_t 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 >= hash_table_end(ht)) { // arrived end, restart from beginning
- pos = ht->buf + 1;
+ int64_t pos = ht->hash(elem) % ht->cap;
+ while (ht->flagbuf[pos] != HTFL_NUL) {
+ if (ht->flagbuf[pos] == HTFL_VAL
+ && ht->eq(ht->buf + pos * ht->elemsz, elem)) {
+ return false;
+ }
+ pos++;
+ if (pos >= ht->cap) { // arrived end, restart from beginning
+ pos = 0;
}
}
- memcpy(pos, elem, ht->elemsz);
- setflag(pos, HTFL_VAL);
- if (pos < ht->begin || ht->begin == NULL) {
- ht->begin = pos;
- }
+ memcpy(ht->buf + pos * ht->elemsz, elem, ht->elemsz);
+ ht->flagbuf[pos] = HTFL_VAL;
return true;
}
-void hash_table_remove(hash_table_t *ht, void *iter) {
+void hash_table_remove(hash_table_t *ht, void * ptr) {
ht->size--;
- setflag(iter, HTFL_DEL);
- if (iter == ht->begin) {
- ht->begin = hash_table_next(ht, iter);
- }
+ int64_t pos = (ptr - ht->buf) / ht->elemsz;
+ ht->flagbuf[pos] = HTFL_DEL;
+}
+
+void *hash_table_ref(hash_table_t *ht, int64_t pos) {
+ return ht->buf + pos * ht->elemsz;
}
void *hash_table_find(hash_table_t *ht, void *elem) {
- int64_t 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 >= hash_table_end(ht)) { // arrived end, restart from beginning
- pos = ht->buf + 1;
+ int64_t pos = ht->hash(elem) % ht->cap;
+ while (ht->flagbuf[pos] != HTFL_NUL) {
+ if (ht->flagbuf[pos] == HTFL_VAL
+ && ht->eq(hash_table_ref(ht, pos), elem)) {
+ return hash_table_ref(ht, pos);
+ }
+ pos++;
+ if (pos >= ht->cap) { // arrived end, restart from beginning
+ pos = 0;
}
}
return NULL;
}
-void *hash_table_begin(hash_table_t *ht) { return ht->begin; }
+void* hash_table_begin(hash_table_t *ht) {
+ if (ht->size <= 0) return NULL;
+ for (int64_t i = 0; i < ht->cap; i++) {
+ if (ht->flagbuf[i] == HTFL_VAL) {
+ return hash_table_ref(ht, i);
+ }
+ }
+ return NULL;
+}
void *hash_table_next(hash_table_t *ht, void *iter) {
- void *pos = iter;
+ int64_t pos = (iter - ht->buf) / ht->elemsz;
do {
- pos += ht->elemsz + 1;
- if (pos >= hash_table_end(ht)) {
+ pos++;
+ if (pos >= ht->cap) {
return NULL;
}
- } while (getflag(pos) != HTFL_VAL);
- return pos;
+ } while (ht->flagbuf[pos] != HTFL_VAL);
+ return hash_table_ref(ht, pos);
+}
+
+void destroy_hash_table(hash_table_t *ht) {
+ free(ht->buf);
+ free(ht->flagbuf);
}
diff --git a/src/hash_table.h b/src/hash_table.h
index 1bf6cfe..3e18be6 100644
--- a/src/hash_table.h
+++ b/src/hash_table.h
@@ -6,10 +6,10 @@
struct hash_table {
void *buf;
+ char *flagbuf;
int64_t size;
int64_t cap;
int64_t taken;
- void *begin;
int64_t elemsz;
uint64_t (*hash)(void *);
bool (*eq)(void *, void *);
@@ -25,5 +25,6 @@ void hash_table_remove(hash_table_t *ht, void *iter);
void *hash_table_find(hash_table_t *ht, void *elem);
void *hash_table_begin(hash_table_t *ht);
void *hash_table_next(hash_table_t *ht, void *iter);
+void destroy_hash_table(hash_table_t *ht);
#endif
diff --git a/src/priority_queue.h b/src/priority_queue.h
index 895bb42..98250c9 100644
--- a/src/priority_queue.h
+++ b/src/priority_queue.h
@@ -14,6 +14,6 @@ void init_priority_queue(priority_queue_t *pq, int cap, int elemsz,
int (*cmp)(void *, void *));
void priority_queue_push(priority_queue_t *pq, void *elem);
void priority_queue_pop(priority_queue_t *pq);
-void *priority_queue_top();
+void *priority_queue_top(priority_queue_t *pq);
#endif
diff --git a/src/str.c b/src/str.c
index 22aebac..011da99 100644
--- a/src/str.c
+++ b/src/str.c
@@ -65,12 +65,17 @@ void destroy_str_list(char **list) {
char *str_strip(char *str) {
if (str == NULL) return NULL;
int len = strlen(str);
+ if (len == 0) {
+ char* ret = malloc(1);
+ ret[0] = '\0';
+ return ret;
+ }
char *begin = str;
char *end = str + len - 1;
while (isspace(*begin) && begin < end) {
begin++;
}
- while (isspace(*end) && end >= begin) {
+ while (end >= begin && isspace(*end)) {
end--;
}
len = end - begin + 1;
generated by cgit v1.0 at 2025-12-29 21:29:20 +0000