Changeset View
Standalone View
swh/perfecthash/hash.c
- This file was added.
#include <assert.h> | |||||||||||||||||||
#include <fcntl.h> | |||||||||||||||||||
#include <memory.h> | |||||||||||||||||||
#include <sys/mman.h> | |||||||||||||||||||
#include <sys/stat.h> | |||||||||||||||||||
#include <sys/types.h> | |||||||||||||||||||
#include <unistd.h> | |||||||||||||||||||
#include "swh/perfecthash/hash.h" | |||||||||||||||||||
#ifdef HASH_DEBUG | |||||||||||||||||||
#define debug(...) printf(__VA_ARGS__) | |||||||||||||||||||
#else | |||||||||||||||||||
#define debug(...) | |||||||||||||||||||
#endif | |||||||||||||||||||
size_t ntohq(size_t v) { return __builtin_bswap64(v); } | |||||||||||||||||||
size_t htonq(size_t v) { return __builtin_bswap64(v); } | |||||||||||||||||||
douardda: why do we need 2 versions of the same function? | |||||||||||||||||||
Done Inline ActionsThis is not strictly necessary indeed but clarifies the intent and helps me with code reading. dachary: This is not strictly necessary indeed but clarifies the intent and helps me with code reading. | |||||||||||||||||||
int shard_size_align(size_t s) { | |||||||||||||||||||
int r = sizeof(size_t); | |||||||||||||||||||
if (s % r) | |||||||||||||||||||
return s + r - (s % r); | |||||||||||||||||||
else | |||||||||||||||||||
return s; | |||||||||||||||||||
} | |||||||||||||||||||
Done Inline Actions
I found this better but that's just an unblocking suggestion. ardumont: I found this better but that's just an unblocking suggestion. | |||||||||||||||||||
int shard_header_load(shard_header_t *header, int fd) { | |||||||||||||||||||
if (lseek(fd, 0, SEEK_SET) < 0) { | |||||||||||||||||||
perror("lseek"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
if (read(fd, (void *)header, sizeof(shard_header_t)) < 0) { | |||||||||||||||||||
perror("read"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_header_reset(shard_header_t *header) { | |||||||||||||||||||
memset((void *)header, '\0', sizeof(shard_header_t)); | |||||||||||||||||||
header->objects_position = SHARD_OFFSET_HEADER; | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_header_save(shard_t *shard) { | |||||||||||||||||||
memcpy((void *)shard->addr, (void *)&(shard->header), | |||||||||||||||||||
sizeof(shard_header_t)); | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_map(shard_t *shard, int flags) { | |||||||||||||||||||
int fd = open(shard->path, flags); | |||||||||||||||||||
if (fd < 0) { | |||||||||||||||||||
perror("open"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
struct stat sb; | |||||||||||||||||||
if (fstat(fd, &sb) == -1) { | |||||||||||||||||||
perror("fstat"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
shard->file_size = sb.st_size; | |||||||||||||||||||
int prot = flags == O_RDONLY ? PROT_READ : PROT_WRITE; | |||||||||||||||||||
shard->addr = mmap(NULL, shard->file_size, prot, MAP_SHARED, fd, 0); | |||||||||||||||||||
if (shard->addr == NULL) { | |||||||||||||||||||
perror("mmap"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
if (shard_header_load(&shard->header, fd) < 0) | |||||||||||||||||||
return -1; | |||||||||||||||||||
if (close(fd) < 0) { | |||||||||||||||||||
perror("close"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_uninit(shard_t *shard) { | |||||||||||||||||||
if (shard->addr) | |||||||||||||||||||
return munmap(shard->addr, shard->file_size); | |||||||||||||||||||
else | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_object_write(shard_t *shard, const char *key, const char *object, | |||||||||||||||||||
size_t object_size) { | |||||||||||||||||||
// save key & index to later build the hash | |||||||||||||||||||
shard_index_t *index = &shard->index[shard->index_offset]; | |||||||||||||||||||
memcpy((void *)index->key, key, SHARD_KEY_LEN); | |||||||||||||||||||
index->object_offset = shard->object_offset; | |||||||||||||||||||
shard->index_offset++; | |||||||||||||||||||
// write the object size and the object itself | |||||||||||||||||||
size_t n_object_size = htonq(object_size); | |||||||||||||||||||
debug("shard_object_write: object_size = %ld n_object_size = %ld\n", | |||||||||||||||||||
object_size, n_object_size); | |||||||||||||||||||
size_t object_offset = | |||||||||||||||||||
shard->header.objects_position + shard->object_offset; | |||||||||||||||||||
debug("shard_object_write: object_offset = %ld\n", object_offset); | |||||||||||||||||||
memcpy((void *)(shard->addr + object_offset), (const void *)&n_object_size, | |||||||||||||||||||
sizeof(size_t)); | |||||||||||||||||||
memcpy((void *)(shard->addr + object_offset + sizeof(size_t)), | |||||||||||||||||||
Done Inline Actionsindentation is off. I think we miss a call to make format, don't we? ardumont: indentation is off.
I think we miss a call to `make format`, don't we? | |||||||||||||||||||
Done Inline ActionsRight :-) dachary: Right :-) | |||||||||||||||||||
(const void *)object, object_size); | |||||||||||||||||||
shard->object_offset += shard_size_align(sizeof(size_t) + object_size); | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
static int io_read(void *data, char **key, cmph_uint32 *keylen) { | |||||||||||||||||||
shard_t *shard = (shard_t *)data; | |||||||||||||||||||
*key = shard->index[shard->index_offset].key; | |||||||||||||||||||
*keylen = SHARD_KEY_LEN; | |||||||||||||||||||
shard->index_offset++; | |||||||||||||||||||
return shard->index_offset >= shard->header.objects_count ? -1 : 0; | |||||||||||||||||||
} | |||||||||||||||||||
static void io_dispose(void *data, char *key, cmph_uint32 keylen) {} | |||||||||||||||||||
Done Inline ActionsAre those error log messages (i see those in all C functions) destined to say as is or Note: I gather those printf instructions with those checks are actually some kind of ardumont: Are those error log messages (i see those in all C functions) destined to say as is or
is there… | |||||||||||||||||||
Done Inline ActionsThe debug messags are for debug, the printf messages are here to stay. They are designed to uniquely identify the location of the error in the source code. When arguments are provided they are also printed: they are all the information that can be provided to the user, instead of just "fail error fail" :-) In the case of this line, arguments are hardcoded and there is no gain in printing them again. Does that make sense. dachary: The **debug** messags are for debug, the **printf** messages are here to stay.
They are… | |||||||||||||||||||
Done Inline Actionsyes, it does, thanks. ardumont: yes, it does, thanks. | |||||||||||||||||||
static void io_rewind(void *data) { | |||||||||||||||||||
shard_t *shard = (shard_t *)data; | |||||||||||||||||||
shard->index_offset = 0; | |||||||||||||||||||
} | |||||||||||||||||||
static cmph_io_adapter_t *io_adapter(shard_t *shard) { | |||||||||||||||||||
cmph_io_adapter_t *key_source = | |||||||||||||||||||
(cmph_io_adapter_t *)malloc(sizeof(cmph_io_adapter_t)); | |||||||||||||||||||
if (key_source == NULL) | |||||||||||||||||||
return NULL; | |||||||||||||||||||
key_source->data = (void *)shard; | |||||||||||||||||||
key_source->nkeys = shard->header.objects_count; | |||||||||||||||||||
key_source->read = io_read; | |||||||||||||||||||
key_source->dispose = io_dispose; | |||||||||||||||||||
key_source->rewind = io_rewind; | |||||||||||||||||||
return key_source; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_lookup(shard_t *shard, const char *key, char **object, | |||||||||||||||||||
size_t *object_size) { | |||||||||||||||||||
cmph_uint32 h = cmph_search(shard->hash, key, SHARD_KEY_LEN); | |||||||||||||||||||
debug("shard_lookup: h = %d\n", h); | |||||||||||||||||||
size_t index_offset = shard->header.index_position + h * sizeof(size_t); | |||||||||||||||||||
debug("shard_lookup: index_offset = %ld\n", index_offset); | |||||||||||||||||||
size_t object_offset = shard->header.objects_position + | |||||||||||||||||||
ntohq(*(size_t *)(shard->addr + index_offset)); | |||||||||||||||||||
debug("shard_lookup: object_offset = %ld\n", object_offset); | |||||||||||||||||||
*object_size = ntohq(*(size_t *)(shard->addr + object_offset)); | |||||||||||||||||||
debug("shard_lookup: object_size = %ld\n", *object_size); | |||||||||||||||||||
*object = shard->addr + object_offset + sizeof(size_t); | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_hash_create(shard_t *shard) { | |||||||||||||||||||
shard->source = io_adapter(shard); | |||||||||||||||||||
shard->config = cmph_config_new(shard->source); | |||||||||||||||||||
cmph_config_set_algo(shard->config, CMPH_CHD_PH); | |||||||||||||||||||
cmph_config_set_keys_per_bin(shard->config, 1); | |||||||||||||||||||
cmph_config_set_b(shard->config, 4); | |||||||||||||||||||
shard->hash = cmph_new(shard->config); | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_index_save(shard_t *shard) { | |||||||||||||||||||
shard->header.index_position = shard_size_align( | |||||||||||||||||||
shard->header.objects_position + shard->header.objects_size); | |||||||||||||||||||
cmph_uint32 count = cmph_size(shard->hash); | |||||||||||||||||||
debug("shard_index_save: count = %d\n", count); | |||||||||||||||||||
shard->header.index_size = count * sizeof(size_t); | |||||||||||||||||||
size_t *index = (size_t *)malloc(shard->header.index_size); | |||||||||||||||||||
for (size_t i = 0; i < shard->index_offset; i++) { | |||||||||||||||||||
cmph_uint32 h = | |||||||||||||||||||
cmph_search(shard->hash, shard->index[i].key, SHARD_KEY_LEN); | |||||||||||||||||||
debug("shard_index_save: i = %ld, h = %d, offset = %ld\n", i, h, | |||||||||||||||||||
shard->index[i].object_offset); | |||||||||||||||||||
index[h] = htonq(shard->index[i].object_offset); | |||||||||||||||||||
} | |||||||||||||||||||
memcpy((void *)(shard->addr + shard->header.index_position), index, | |||||||||||||||||||
shard->header.index_size); | |||||||||||||||||||
free(index); | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_hash_save(shard_t *shard) { | |||||||||||||||||||
shard->header.hash_position = shard_size_align( | |||||||||||||||||||
shard->header.index_position + shard->header.index_size); | |||||||||||||||||||
FILE *fd = fopen(shard->path, "r+"); | |||||||||||||||||||
fseek(fd, shard->header.hash_position, SEEK_SET); | |||||||||||||||||||
cmph_dump(shard->hash, fd); | |||||||||||||||||||
fclose(fd); | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_hash_load(shard_t *shard) { | |||||||||||||||||||
FILE *fd = fopen(shard->path, "r"); | |||||||||||||||||||
fseek(fd, shard->header.hash_position, SEEK_SET); | |||||||||||||||||||
shard->hash = cmph_load(fd); | |||||||||||||||||||
assert(shard->hash != NULL); | |||||||||||||||||||
fclose(fd); | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_save(shard_t *shard) { | |||||||||||||||||||
shard->header.objects_size = shard->object_offset; | |||||||||||||||||||
if (shard_hash_create(shard) < 0) | |||||||||||||||||||
return -1; | |||||||||||||||||||
if (shard_index_save(shard) < 0) | |||||||||||||||||||
return -1; | |||||||||||||||||||
if (shard_hash_save(shard) < 0) | |||||||||||||||||||
return -1; | |||||||||||||||||||
if (shard_header_save(shard) < 0) | |||||||||||||||||||
return -1; | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
Done Inline Actions
? ardumont: ? | |||||||||||||||||||
Done Inline ActionsI used yours 👍 dachary: I used yours 👍 | |||||||||||||||||||
int shard_destroy(shard_t *shard) { | |||||||||||||||||||
if (shard->source) | |||||||||||||||||||
free(shard->source); | |||||||||||||||||||
if (shard->config) | |||||||||||||||||||
cmph_config_destroy(shard->config); | |||||||||||||||||||
if (shard->hash) | |||||||||||||||||||
cmph_destroy(shard->hash); | |||||||||||||||||||
shard_uninit(shard); | |||||||||||||||||||
if (shard->index) | |||||||||||||||||||
free(shard->index); | |||||||||||||||||||
free(shard->path); | |||||||||||||||||||
free(shard); | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
shard_t *shard_init(const char *path) { | |||||||||||||||||||
shard_t *shard = (shard_t *)malloc(sizeof(shard_t)); | |||||||||||||||||||
if (shard == NULL) | |||||||||||||||||||
return NULL; | |||||||||||||||||||
memset((void *)shard, '\0', sizeof(shard_t)); | |||||||||||||||||||
shard->path = strdup(path); | |||||||||||||||||||
return shard; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_reset(shard_t *shard) { return shard_header_reset(&shard->header); } | |||||||||||||||||||
int shard_create(shard_t *shard, size_t objects_count) { | |||||||||||||||||||
if (shard_map(shard, O_RDWR) < 0) | |||||||||||||||||||
return -1; | |||||||||||||||||||
if (shard_reset(shard) < 0) | |||||||||||||||||||
return -1; | |||||||||||||||||||
shard->header.objects_count = objects_count; | |||||||||||||||||||
shard->index = | |||||||||||||||||||
(shard_index_t *)malloc(sizeof(shard_index_t) * objects_count); | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_load(shard_t *shard) { | |||||||||||||||||||
if (shard_map(shard, O_RDONLY) < 0) | |||||||||||||||||||
return -1; | |||||||||||||||||||
return shard_hash_load(shard); | |||||||||||||||||||
} | |||||||||||||||||||
Done Inline ActionsI'm rusty in c. I've only read it superficially for now. I guess that's part of "let's document it" in the earlier comment? ardumont: I'm rusty in c. I've only read it superficially for now.
That source code would definitely be… | |||||||||||||||||||
Done Inline ActionsThat looks like an unreachable statement. ardumont: That looks like an unreachable statement. | |||||||||||||||||||
Done Inline ActionsIt does :-D dachary: It does :-D |
why do we need 2 versions of the same function?