From cb2a50691fb0cddb64e1b5a9ed242a6a0b42d503 Mon Sep 17 00:00:00 2001 From: Hristo Venev Date: Mon, 22 Jun 2020 12:32:11 +0300 Subject: Initial commit. --- include/hkvs.h | 318 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 318 insertions(+) create mode 100644 include/hkvs.h (limited to 'include') diff --git a/include/hkvs.h b/include/hkvs.h new file mode 100644 index 0000000..7ab706a --- /dev/null +++ b/include/hkvs.h @@ -0,0 +1,318 @@ +// SPDX-License-Identifier: LGPL-3.0-or-later + +#pragma once +#include +#include +#include +#include + +#ifndef HKVS_API +#define HKVS_API extern __attribute__((__nothrow__)) +#endif + +#ifndef HKVS_INLINE +#define HKVS_INLINE inline static __attribute__((__always_inline__, __unused__, __nothrow__)) +#endif + +#define HKVS_MUSTCHECK __attribute__((__warn_unused_result__)) + +#define HKVS_MAGIC ((uint64_t)0xfffec19153564b48ULL) + +/* Error codes: + * - `-ENOMEM`: Memory allocation failed. + * - `-EFBIG`: An implementation limit on the database size has been reached. + * Note that this may happen to writes that don't change the number of + * records. + * - `-EBADMSG`: Database corruption has been detected. + */ + +/* ================================================================ */ + + +/* + * ---------------------- Core Database API ----------------------- + * + * The database contains a set of tables with 32-bit integer identifiers. Each + * table contains records with fixed-size keys and variable-sized values. + * + * The database storage is provided by an implementation of `hkvs_io`. The core + * of the database does not provide transaction support. That has to be + * implemented at the I/O layer. + */ + +/* `hkvs*` is the database handle type. */ +typedef struct hkvs hkvs; + +/* `hkvs_table*` represents a database table. */ +typedef struct hkvs_table hkvs_table; + +/* `hkvs_io` is an interface for the I/O methods used by the database. */ +typedef struct hkvs_io hkvs_io; + +/* Open a new database. The database pointer is stored in `*pc`. + * + * On failure, a negative error code is returned and `*pc` is left unchanged. + * The `hkvs_io` is destroyed. + */ +HKVS_API HKVS_MUSTCHECK int hkvs_new(hkvs **pc, hkvs_io *io); + +/* Close the database and destroy its `hkvs_io`. + * + * This method does not fail. */ +HKVS_API void hkvs_free(hkvs *c); + +/* Find a table by index. If fewer tables exist, NULL is returned. + * + * This method does not fail. */ +HKVS_API hkvs_table *hkvs_table_at(hkvs *c, size_t i); + +/* Find a table by ID. If no table with the given ID exists or its key size does + * not match, NULL is returned. + * + * This method does not fail. */ +HKVS_API hkvs_table *hkvs_table_open(hkvs *c, uint32_t id, size_t key_size); + +/* Create a table and store its pointer in `*ptable`. + * + * Record values with size <= `val_size_hint` may be stored together with the + * key. + * + * A positive return value indicates that a table was created, and 0 means that + * the table already exists. + * + * On failure, a negative error code is returned and the database is left + * unchanged. If a table with the given ID exists but has a different key size, + * `-EEXIST` is returned. */ +HKVS_API int hkvs_table_create(hkvs *c, hkvs_table **ptable, uint32_t id, size_t key_size, size_t val_size_hint); + +/* Delete the table with the given ID. A positive return value indicates that a + * table was found and deleted, and 0 means that no table with the given ID + * exists. + * + * On failure, a negative error code is returned and the database is left + * unchanged. */ +HKVS_API int hkvs_table_delete(hkvs *c, uint32_t id); + +/* Get the ID of the given table. + * + * This method does not fail. */ +HKVS_API uint32_t hkvs_table_id(hkvs *c, hkvs_table *t); + +/* Get the key size of the given table. + * + * This method does not fail. */ +HKVS_API size_t hkvs_table_key_size(hkvs *c, hkvs_table *t); + +/* Invalidate all record key and value pointers. This may release some + * resources. + * + * This method does not fail. */ +HKVS_API void hkvs_put_records(hkvs *c); + +/* ================================================================ */ + + +/* + * -------------------------- Record API -------------------------- + * + * The record API provides access to the contents of tables. + * + * Record IDs are 64-bit integers. New record IDs are assigned either + * sequentially or by reusing IDs of deleted records. + * + * Record IDs are persistent, meaning that a record will keep its ID until + * deleted. + */ + +/* `hkvs_rid` is a wrapper for a record ID. */ +typedef struct hkvs_rid hkvs_rid; +struct hkvs_rid { + uint64_t id; +}; + +#define HKVS_INVALID_RID ((struct hkvs_rid){(size_t)-1}) + +/* Check if a record ID is valid. */ +HKVS_INLINE bool hkvs_rid_ok(hkvs_rid rid) { + return rid.id <= UINT64_MAX / 2; +} + +/* Return a pointer to the key of the given record, or NULL if no record with + * that ID exists. The pointer is invalidated by methods that add, remove, or + * resize records of any table. + * + * This method does not fail. */ +HKVS_API HKVS_MUSTCHECK const char *hkvs_record_key(hkvs *c, hkvs_table *t, hkvs_rid rid); + +/* Get the data pointer and value of the given record. If the record exists, + * a positive value is returned. If not, 0 is returned. + * + * The pointer is invalidated by methods that add, remove, or resize records + * of any table. Do not forget to call `hkvs_put_records` when done with the + * value. + * + * On failure, a negative error code is returned. */ +HKVS_API HKVS_MUSTCHECK int hkvs_record_value(hkvs *c, hkvs_table *t, hkvs_rid rid, char **pvalue, size_t *psize); + +/* Resize a given record. Only the first `min(keep_size, new_size, old_size)` + * bytes of the value are retained, the rest of the value is uninitialized. + * + * If `pvalue` is provided, a pointer to the record value is stored there. Do + * not forget to call `hkvs_put_records` when done with the value. + * + * It is a programmer error to call this method with an ID that does not + * correspond to an existing record. + * + * On failure, a negative error code is returned and the database is left + * unchanged. */ +HKVS_API HKVS_MUSTCHECK int hkvs_record_resize(hkvs *c, hkvs_table *t, hkvs_rid rid, char **pvalue, size_t new_size, size_t keep_size); + +/* Find the record with the given key. If no record was found, + * `HKVS_INVALID_RID` is returned. + * + * This method does not fail. */ +HKVS_API HKVS_MUSTCHECK hkvs_rid hkvs_record_find(hkvs *c, hkvs_table *t, const char *key); + +/* Delete the given record. + * + * It is a programmer error to call this method with an ID that does not + * correspond to an existing record. + * + * This method does not fail. */ +HKVS_API void hkvs_record_delete(hkvs *c, hkvs_table *t, hkvs_rid rid); + +/* Append a new record to the table. The ID of the new record is stored in + * `*prid`. + * + * It is a programmer error to call this method with a key that is already in + * the table. + * + * On failure, a negative error code is returned and the database is left + * unchanged. */ +HKVS_API HKVS_MUSTCHECK int hkvs_record_append(hkvs *c, hkvs_table *t, hkvs_rid *prid, const char *key, char **pvalue, size_t size); + +/* ================================================================ */ + + +/* + * ---------------------- Utility Functions ----------------------- + * + * These are some utility functions that can be correctly implemented using + * the rest of the public API. However, the implementations provided here may be + * slightly more efficient. + */ + +/* Set the value of a record. + * + * It is a programmer error to call this method with a record ID that does not + * correspond to an existing record. + * + * On failure, a negative error code is returned and the database is left + * unchanged. */ +HKVS_API HKVS_MUSTCHECK int hkvs_record_set(hkvs *c, hkvs_table *t, hkvs_rid rid, const char *value, size_t size); + +/* Append or set the record with the given key. + * + * The ID of the record is stored in `*prid`. If a new record was created, 1 + * is returned. If an existing record was changed, 0 is returned. + * + * On failure, a negative error code is returned and the database is left + * unchanged. */ +HKVS_API HKVS_MUSTCHECK int hkvs_record_update(hkvs *c, hkvs_table *t, hkvs_rid *prid, const char *key, const char *value, size_t size); + +/* ================================================================ */ + + +/* + * ------------------------- Iterator API ------------------------- + * + * An iterator provides a way to enumerate all records in a table. Iterators + * themselves do not consume any resources. + * + * The fields of `hkvs_iter` are an implementation detail. + */ +typedef struct hkvs_iter hkvs_iter; +struct hkvs_iter { + size_t priv1, priv2; +}; + +/* Initialize an iterator. The first call to `hkvs_iter_next` on the iterator + * will return the first record. Any change of the database invalidates the + * iterator, and it must be reinitialized. + * + * This method does not fail. + */ +HKVS_API void hkvs_iter_open(hkvs *c, hkvs_table *t, hkvs_iter *it); + +/* Initialize an iterator positioned at a given record. The next call to + * `hkvs_iter_next()` will return the first record with an ID greater than + * or equal to the one given here. + * + * This method does not fail. */ +HKVS_API void hkvs_iter_seek(hkvs *c, hkvs_table *t, hkvs_iter *it, hkvs_rid rid); + +/* Retrieve the ID of the next record. If `pkey` is provided, a pointer to the + * record's key is stored there. + * + * If the end of the database has been reached, `HKVS_INVALID_RID` is returned. + * + * This method does not fail. */ +HKVS_API HKVS_MUSTCHECK hkvs_rid hkvs_iter_next(hkvs *c, hkvs_table *t, hkvs_iter *it, const char **pkey); + +/* Delete the record last returned by `hkvs_iter_next()` without invalidating + * the iterator. Key and value pointers are still invalidated. + * + * It is a programmer error to call this method without a preceding call to + * `hkvs_iter_next()`. + * + * This method does not fail. */ +HKVS_API void hkvs_iter_delete(hkvs *c, hkvs_table *t, hkvs_iter *it); + +/* ================================================================ */ + + +/* + * ------------------------- hkvs_io API -------------------------- + * + * The I/O interface consists of several methods for operating on memory-mapped + * files. + * + * In order to initialize the database, an empty file 0 must be created. It will + * never be deleted. + */ + +struct hkvs_io { + /* Destroy the IO interface. */ + void (*destroy)(hkvs_io *io); + + /* Write random bytes to the given buffer. */ + int (*random)(hkvs_io *io, char *buf, size_t size); + + /* Open the file and memory-map it. The size is stored in `*psz` and the + * address is stored in `*pmem`. The file is not open when this method is + * called. */ + int (*open)(hkvs_io *io, uint64_t fi, char **pmem, size_t *psz); + + /* Create a zero-filled file with the given size and open it. */ + int (*create)(hkvs_io *io, uint64_t *pfi, char **pmem, size_t sz); + + /* Resize the file and update its memory-mapped address. The file is open + * and mapped at `*pmem` with size `old_sz` when this method is called. */ + int (*resize)(hkvs_io *io, uint64_t fi, char **pmem, size_t old_sz, size_t new_sz); + + /* Release the file's memory mapping and close it. The file is open and + * mapped at `mem` with size `sz` when this method is called. */ + void (*close)(hkvs_io *io, uint64_t fi, char *mem, size_t sz); + + /* Delete the file. The file is not open when this method is called. */ + void (*unlink)(hkvs_io *io, uint64_t fi); +}; + +/* Create a new `hkvs_io` that entirely works in memory. */ +HKVS_API hkvs_io *hkvs_io_new_mem(uint64_t random_seed); + +/* Create a new `hkvs_io` given a directory file descriptor. This implementation + * is simple but it does no locking and is not crash-safe. */ +HKVS_API hkvs_io *hkvs_io_new_unsafe_dirfd(int fd); + +/* ================================================================ */ -- cgit