88 lines
1.8 KiB
C
88 lines
1.8 KiB
C
#include "lib.h"
|
|
#include "nbt.h"
|
|
#include "map.h"
|
|
|
|
#include <stdint.h>
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
void map_init(map_t *map) {
|
|
map->len = 0;
|
|
map->capacity = 0;
|
|
map->entries = NULL;
|
|
}
|
|
|
|
void map_free(map_t *map) {
|
|
if (map->entries == NULL)
|
|
return;
|
|
for (uint32_t i = 0; i < map->capacity; i++) {
|
|
if (map->entries[i].name != NULL)
|
|
tag_free(&map->entries[i]);
|
|
}
|
|
free(map->entries);
|
|
}
|
|
|
|
static uint32_t hash(const char *name, uint16_t len) {
|
|
uint32_t hash = 2166136261u;
|
|
while(len > 0) {
|
|
hash ^= (uint8_t)(*name);
|
|
hash *= 16777619;
|
|
name++;
|
|
len--;
|
|
}
|
|
return hash;
|
|
}
|
|
|
|
static tag_t *map_find(tag_t *entries, uint32_t capacity, tag_t *tag) {
|
|
uint32_t index = hash(tag->name, tag->name_len) % capacity;
|
|
while(true) {
|
|
tag_t *entry = &entries[index];
|
|
if (entry->name == NULL) {
|
|
return entry;
|
|
} else if (
|
|
entry->name_len == tag->name_len &&
|
|
memcmp(entry->name, tag->name, tag->name_len) == 0
|
|
) {
|
|
return entry;
|
|
}
|
|
index += 1;
|
|
index %= capacity;
|
|
}
|
|
}
|
|
|
|
static void map_grow(map_t *map, uint32_t capacity) {
|
|
tag_t *entries = xzalloc(capacity * sizeof(tag_t));
|
|
for (uint32_t i = 0; i < capacity; i++) {
|
|
entries[i].name = NULL;
|
|
entries[i].name_len = 0;
|
|
}
|
|
map->len = 0;
|
|
for (uint32_t i = 0; i < map->capacity; i++) {
|
|
tag_t *tag = &map->entries[i];
|
|
if (tag->name == NULL) continue;
|
|
|
|
tag_t *dest = map_find(entries, capacity, tag);
|
|
*dest = *tag;
|
|
map->len++;
|
|
}
|
|
free(map->entries);
|
|
|
|
map->entries = entries;
|
|
map->capacity = capacity;
|
|
}
|
|
|
|
void map_put(map_t *map, tag_t *tag) {
|
|
if (map->len + 1 > map->capacity * 0.75) {
|
|
int capacity = (map->capacity == 0 ? 8 : (2 * map->capacity));
|
|
map_grow(map, capacity);
|
|
}
|
|
tag_t *dest = map_find(map->entries, map->capacity, tag);
|
|
if (dest->name == NULL) {
|
|
map->len++;
|
|
} else {
|
|
tag_free(dest);
|
|
}
|
|
*dest = *tag;
|
|
}
|