Changeset View
Standalone View
swh/perfecthash/hash.c
- This file was added.
/* | |||||||||||||||||||
* Copyright (C) 2021 The Software Heritage developers | |||||||||||||||||||
* See the AUTHORS file at the top-level directory of this distribution | |||||||||||||||||||
* License: GNU General Public License version 3, or any later version | |||||||||||||||||||
* See top-level LICENSE file for more information | |||||||||||||||||||
*/ | |||||||||||||||||||
#include <assert.h> | |||||||||||||||||||
#include <errno.h> | |||||||||||||||||||
#include <fcntl.h> | |||||||||||||||||||
#include <memory.h> | |||||||||||||||||||
#include <string.h> | |||||||||||||||||||
#include <sys/mman.h> | |||||||||||||||||||
#include <sys/stat.h> | |||||||||||||||||||
#include <sys/types.h> | |||||||||||||||||||
#include <unistd.h> | |||||||||||||||||||
#include "swh/perfecthash/hash.h" | |||||||||||||||||||
#ifdef HASH_DEBUG | |||||||||||||||||||
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. | |||||||||||||||||||
#define debug(...) printf(__VA_ARGS__) | |||||||||||||||||||
#else | |||||||||||||||||||
#define debug(...) | |||||||||||||||||||
#endif | |||||||||||||||||||
size_t ntohq(size_t v) { return __builtin_bswap64(v); } | |||||||||||||||||||
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. | |||||||||||||||||||
size_t htonq(size_t v) { return __builtin_bswap64(v); } | |||||||||||||||||||
/*********************************************************** | |||||||||||||||||||
* wrappers around FILE functions that: | |||||||||||||||||||
* - return -1 on error | |||||||||||||||||||
* - print a meaningful message when an error occurs | |||||||||||||||||||
* | |||||||||||||||||||
*/ | |||||||||||||||||||
int shard_open(shard_t *shard, const char *mode) { | |||||||||||||||||||
shard->f = fopen(shard->path, mode); | |||||||||||||||||||
if (shard->f == NULL) { | |||||||||||||||||||
printf("shard_open: open(%s, %s): %s\n", shard->path, mode, | |||||||||||||||||||
strerror(errno)); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} else | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_close(shard_t *shard) { | |||||||||||||||||||
if (shard->f == NULL) | |||||||||||||||||||
return 0; | |||||||||||||||||||
int r = fclose(shard->f); | |||||||||||||||||||
if (r < 0) | |||||||||||||||||||
printf("shard_close: fclose(%p): %s\n", shard->f, strerror(errno)); | |||||||||||||||||||
return r; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_seek(shard_t *shard, long offset, int whence) { | |||||||||||||||||||
int r = fseek(shard->f, offset, whence); | |||||||||||||||||||
if (r < 0) | |||||||||||||||||||
printf("shard_seek: fseek(%p, %ld, %d): %s\n", shard->f, offset, whence, | |||||||||||||||||||
strerror(errno)); | |||||||||||||||||||
return r; | |||||||||||||||||||
} | |||||||||||||||||||
size_t shard_tell(shard_t *shard) { | |||||||||||||||||||
long r = ftell(shard->f); | |||||||||||||||||||
if (r < 0) | |||||||||||||||||||
printf("shard_tell: ftell(%p): %s\n", shard->f, strerror(errno)); | |||||||||||||||||||
return r; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_read(shard_t *shard, void *ptr, size_t size) { | |||||||||||||||||||
size_t read; | |||||||||||||||||||
if ((read = fread(ptr, 1, size, shard->f)) != size) { | |||||||||||||||||||
printf("shard_read: read %ld instead of %ld\n", read, size); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_read_size_t(shard_t *shard, size_t *ptr) { | |||||||||||||||||||
size_t n_size; | |||||||||||||||||||
if (shard_read(shard, &n_size, sizeof(size_t)) < 0) { | |||||||||||||||||||
printf("shard_read_size_t: shard_read\n"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
*ptr = ntohq(n_size); | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_write(shard_t *shard, const void *ptr, size_t nmemb) { | |||||||||||||||||||
size_t wrote; | |||||||||||||||||||
if ((wrote = fwrite(ptr, 1, nmemb, shard->f)) != nmemb) { | |||||||||||||||||||
printf("shard_write: wrote %ld instead of %ld\n", wrote, nmemb); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
/*********************************************************** | |||||||||||||||||||
* load or save a shard_header_t | |||||||||||||||||||
*/ | |||||||||||||||||||
int shard_header_print(shard_header_t *header) { | |||||||||||||||||||
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 :-) | |||||||||||||||||||
#define PRINT(name) debug("shard_header_print: " #name " %ld\n", header->name) | |||||||||||||||||||
PRINT(objects_count); | |||||||||||||||||||
PRINT(objects_position); | |||||||||||||||||||
PRINT(objects_size); | |||||||||||||||||||
PRINT(index_position); | |||||||||||||||||||
PRINT(index_size); | |||||||||||||||||||
PRINT(hash_position); | |||||||||||||||||||
#undef PRINT | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_header_load(shard_t *shard) { | |||||||||||||||||||
if (shard_seek(shard, 0, SEEK_SET) < 0) { | |||||||||||||||||||
printf("shard_header_load\n"); | |||||||||||||||||||
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. | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
shard_header_t header; | |||||||||||||||||||
if (shard_read(shard, (void *)&header, sizeof(shard_header_t)) < 0) { | |||||||||||||||||||
printf("shard_header_load\n"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
#define LOAD(name) shard->header.name = ntohq(header.name) | |||||||||||||||||||
LOAD(objects_count); | |||||||||||||||||||
LOAD(objects_position); | |||||||||||||||||||
LOAD(objects_size); | |||||||||||||||||||
LOAD(index_position); | |||||||||||||||||||
LOAD(index_size); | |||||||||||||||||||
LOAD(hash_position); | |||||||||||||||||||
#undef LOAD | |||||||||||||||||||
shard_header_print(&shard->header); | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_header_save(shard_t *shard) { | |||||||||||||||||||
if (shard_seek(shard, 0, SEEK_SET) < 0) { | |||||||||||||||||||
printf("shard_header_save\n"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
shard_header_print(&shard->header); | |||||||||||||||||||
shard_header_t header; | |||||||||||||||||||
#define SAVE(name) header.name = htonq(shard->header.name) | |||||||||||||||||||
SAVE(objects_count); | |||||||||||||||||||
SAVE(objects_position); | |||||||||||||||||||
SAVE(objects_size); | |||||||||||||||||||
SAVE(index_position); | |||||||||||||||||||
SAVE(index_size); | |||||||||||||||||||
SAVE(hash_position); | |||||||||||||||||||
#undef SAVE | |||||||||||||||||||
if (shard_write(shard, (void *)&header, sizeof(shard_header_t)) < 0) { | |||||||||||||||||||
printf("shard_header_save\n"); | |||||||||||||||||||
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; | |||||||||||||||||||
} | |||||||||||||||||||
/*********************************************************** | |||||||||||||||||||
* Create the Read Shard | |||||||||||||||||||
*/ | |||||||||||||||||||
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_tell(shard); | |||||||||||||||||||
shard->index_offset++; | |||||||||||||||||||
// write the object size and the object itself | |||||||||||||||||||
size_t n_object_size = htonq(object_size); | |||||||||||||||||||
if (shard_write(shard, (void *)&n_object_size, sizeof(size_t)) < 0) { | |||||||||||||||||||
printf("shard_object_write: object_size\n"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
if (shard_write(shard, (void *)object, object_size) < 0) { | |||||||||||||||||||
printf("shard_object_write: object\n"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
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) {} | |||||||||||||||||||
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; | |||||||||||||||||||
Done Inline Actions
? ardumont: ? | |||||||||||||||||||
Done Inline ActionsI used yours 👍 dachary: I used yours 👍 | |||||||||||||||||||
return key_source; | |||||||||||||||||||
} | |||||||||||||||||||
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->header.objects_position + shard->header.objects_size; | |||||||||||||||||||
debug("shard_index_save: index_position %ld\n", | |||||||||||||||||||
shard->header.index_position); | |||||||||||||||||||
assert(shard->header.index_position == shard_tell(shard)); | |||||||||||||||||||
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 *)calloc(1, 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); | |||||||||||||||||||
assert(h < count); | |||||||||||||||||||
index[h] = htonq(shard->index[i].object_offset); | |||||||||||||||||||
} | |||||||||||||||||||
size_t index_size = shard->header.index_size; | |||||||||||||||||||
if (shard_write(shard, (void *)index, index_size) < 0) { | |||||||||||||||||||
printf("shard_index_save\n"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
free(index); | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_hash_save(shard_t *shard) { | |||||||||||||||||||
shard->header.hash_position = | |||||||||||||||||||
shard->header.index_position + shard->header.index_size; | |||||||||||||||||||
debug("shard_hash_save: hash_position %ld\n", shard->header.hash_position); | |||||||||||||||||||
cmph_dump(shard->hash, shard->f); | |||||||||||||||||||
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… | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_save(shard_t *shard) { | |||||||||||||||||||
shard->header.objects_size = | |||||||||||||||||||
shard_tell(shard) - shard->header.objects_position; | |||||||||||||||||||
return (shard_hash_create(shard) < 0 || shard_index_save(shard) < 0 || | |||||||||||||||||||
shard_hash_save(shard) < 0 || shard_header_save(shard) < 0) | |||||||||||||||||||
? -1 | |||||||||||||||||||
: 0; | |||||||||||||||||||
return 0; | |||||||||||||||||||
ardumontUnsubmitted Done Inline ActionsThat looks like an unreachable statement. ardumont: That looks like an unreachable statement. | |||||||||||||||||||
dacharyAuthorUnsubmitted Done Inline ActionsIt does :-D dachary: It does :-D | |||||||||||||||||||
} | |||||||||||||||||||
int shard_reset(shard_t *shard) { | |||||||||||||||||||
if (shard_header_reset(&shard->header) < 0) | |||||||||||||||||||
return -1; | |||||||||||||||||||
return shard_seek(shard, SHARD_OFFSET_HEADER, SEEK_SET); | |||||||||||||||||||
} | |||||||||||||||||||
int shard_create(shard_t *shard, size_t objects_count) { | |||||||||||||||||||
if (shard_open(shard, "w+") < 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; | |||||||||||||||||||
} | |||||||||||||||||||
/********************************************************** | |||||||||||||||||||
* Lookup objects from a Read Shard | |||||||||||||||||||
*/ | |||||||||||||||||||
int shard_lookup_object_size(shard_t *shard, const char *key, | |||||||||||||||||||
size_t *object_size) { | |||||||||||||||||||
debug("shard_lookup_object_size\n"); | |||||||||||||||||||
cmph_uint32 h = cmph_search(shard->hash, key, SHARD_KEY_LEN); | |||||||||||||||||||
debug("shard_lookup_object_size: h = %d\n", h); | |||||||||||||||||||
size_t index_offset = shard->header.index_position + h * sizeof(size_t); | |||||||||||||||||||
debug("shard_lookup_object_size: index_offset = %ld\n", index_offset); | |||||||||||||||||||
if (shard_seek(shard, index_offset, SEEK_SET) < 0) { | |||||||||||||||||||
printf("shard_lookup_object_size: index_offset\n"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
size_t object_offset; | |||||||||||||||||||
if (shard_read_size_t(shard, &object_offset) < 0) { | |||||||||||||||||||
printf("shard_lookup_object_size: object_offset\n"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
debug("shard_lookup_object_size: object_offset = %ld\n", object_offset); | |||||||||||||||||||
if (shard_seek(shard, object_offset, SEEK_SET) < 0) { | |||||||||||||||||||
printf("shard_lookup_object_size: object_offset\n"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
if (shard_read_size_t(shard, object_size) < 0) { | |||||||||||||||||||
printf("shard_lookup_object_size: object_size\n"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
debug("shard_lookup_object_size: object_size = %ld\n", *object_size); | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_lookup_object(shard_t *shard, char *object, size_t object_size) { | |||||||||||||||||||
if (shard_read(shard, (void *)object, object_size) < 0) { | |||||||||||||||||||
printf("shard_lookup_object: object\n"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_hash_load(shard_t *shard) { | |||||||||||||||||||
if (shard_seek(shard, shard->header.hash_position, SEEK_SET) < 0) { | |||||||||||||||||||
printf("shard_hash_load\n"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
debug("shard_hash_load: hash_position %ld\n", shard->header.hash_position); | |||||||||||||||||||
shard->hash = cmph_load(shard->f); | |||||||||||||||||||
if (shard->hash == NULL) { | |||||||||||||||||||
printf("shard_hash_load: cmph_load\n"); | |||||||||||||||||||
return -1; | |||||||||||||||||||
} | |||||||||||||||||||
return 0; | |||||||||||||||||||
} | |||||||||||||||||||
int shard_load(shard_t *shard) { | |||||||||||||||||||
debug("shard_load\n"); | |||||||||||||||||||
if (shard_open(shard, "r") < 0) | |||||||||||||||||||
return -1; | |||||||||||||||||||
if (shard_header_load(shard) < 0) | |||||||||||||||||||
return -1; | |||||||||||||||||||
return shard_hash_load(shard); | |||||||||||||||||||
} | |||||||||||||||||||
/********************************************************** | |||||||||||||||||||
* Initialize and destroy a Read Shard | |||||||||||||||||||
*/ | |||||||||||||||||||
shard_t *shard_init(const char *path) { | |||||||||||||||||||
debug("shard_init\n"); | |||||||||||||||||||
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_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); | |||||||||||||||||||
if (shard->index) | |||||||||||||||||||
free(shard->index); | |||||||||||||||||||
free(shard->path); | |||||||||||||||||||
int r = shard_close(shard); | |||||||||||||||||||
free(shard); | |||||||||||||||||||
return r; | |||||||||||||||||||
} |
why do we need 2 versions of the same function?