diff options
Diffstat (limited to 'inc/store.h')
| -rw-r--r-- | inc/store.h | 264 |
1 files changed, 264 insertions, 0 deletions
diff --git a/inc/store.h b/inc/store.h new file mode 100644 index 0000000..a6df112 --- /dev/null +++ b/inc/store.h @@ -0,0 +1,264 @@ +/* + * MIT License + * + * Copyright (c) 2020 Samuel Vogelsanger <vogelsangersamuel@gmail.com> + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ +#ifndef STORE_STORE_H +#define STORE_STORE_H + +#include <stdint.h> +#include <stddef.h> + +#ifndef STORE_VERBOSITY +#define STORE_VERBOSITY 0 +#endif + +#define DEBUG_NOTICE(fmt, ...) \ + do { \ + if (STORE_VERBOSITY >= 5) \ + fprintf(stderr, "DEBUG: store: " fmt, __VA_ARGS__); \ + } while (0) +#define DEBUG_WARN(fmt, ...) \ + do { \ + if (STORE_VERBOSITY >= 4) \ + fprintf(stderr, "DEBUG: store: " fmt, __VA_ARGS__); \ + } while (0) + +#ifndef STORE_KEY_T +#define STORE_KEY_T void * +#endif + +#ifndef STORE_VALUE_T +#define STORE_VALUE_T void * +#endif + +/** + * These are mostly for convenience + */ + +#define STORE_HASHFN_T(name) uint32_t (*name)(const STORE_KEY_T) +#define STORE_EQUALSFN_T(name) \ + int (*name)(const STORE_KEY_T left, const STORE_KEY_T right) +#define STORE_ASSOCFN_T(name) \ + STORE_VALUE_T(*name) \ + (const STORE_KEY_T key, const STORE_VALUE_T old_value, void *user_data) +#define STORE_VALUE_EQUALSFN_T(name) \ + int (*name)(const STORE_VALUE_T left, const STORE_VALUE_T right) + +/** + * These macros help with defining the various callbacks. Use them like so: + * @code{c} + * STORE_MAKE_EQUALSFN(equals_int, left, right) + * { + * return left == right; + * } + * @endcode + */ + +#define STORE_MAKE_HASHFN(name, arg_1) uint32_t name(const STORE_KEY_T arg_1) +#define STORE_MAKE_EQUALSFN(name, arg_l, arg_r) \ + int name(const STORE_KEY_T arg_l, const STORE_KEY_T arg_r) +#define STORE_MAKE_ASSOCFN(name, key_arg, value_arg, user_data_arg) \ + STORE_VALUE_T name(const STORE_KEY_T key_arg, \ + const STORE_VALUE_T value_arg, void *user_data_arg) +#define STORE_MAKE_VALUE_EQUALSFN(name, arg_l, arg_r) \ + int name(const STORE_VALUE_T arg_l, const STORE_VALUE_T arg_r) + +struct store { + volatile uint32_t ref_count; + unsigned length; + struct node *root; + + STORE_HASHFN_T(hash); + STORE_EQUALSFN_T(equals); +}; + +/** + * Creates a new map with the given hash and equals functions. This implementation is based on the assumption that if + * two keys are equal, their hashes must be equal as well. This is commonly known as the Java Hashcode contract. + * + * The reference count of a new map is zero. + * + * @param hash + * @param equals + * @return + */ +struct store *store_new(STORE_HASHFN_T(hash), STORE_EQUALSFN_T(equals)); + +/** + * Destroys a store. Doesn't clean up the stored key-value-pairs. + * + * @param old + */ +void store_destroy(struct store **store); + +/** + * Atomically increases the reference count of a map. + * + * @param store + * @return + */ +struct store *store_acquire(const struct store *store); + +/** + * Atomically decreases the reference count of a map and calls store_destroy if it caused the count to drop to zero. + * + * In either case then sets the reference to NULL. + * + * @param store + */ +void store_release(struct store **store); + +/** + * Returns the number of entries in store. + * + * @param store + * @return the number of entries + */ +unsigned store_length(const struct store *store); + +/** + * Looks up key and sets *value_receiver to the associated value. Doesn't change value_receiver if key is not set. + * + * @param store + * @param key + * @param found is set to 0 if key is not set + * @return + */ +STORE_VALUE_T store_get(const struct store *store, const STORE_KEY_T key, + int *found); + +/** + * Returns a new map derived from store but with key set to value. + * If replaced is not NULL, sets it to indicate if the key is present in store. + * + * Reference count of the new map is zero. + * + * @param store + * @param key + * @param value + * @param replaced + * @return a new store + */ +struct store *store_set(const struct store *store, const STORE_KEY_T key, + const STORE_VALUE_T value, int *replaced); + +/** + * Returns a new map derived from store but without a mapping for key. + * + * Reference count of the new map is zero. + * + * @param store + * @param key + * @param modified + * @return + */ +struct store *store_del(const struct store *store, const STORE_KEY_T key, + int *modified); + +/** + * Creates a new store with the given hash and equals functions, and inserts the given keys and values. + * Only the first 'length' elements from keys and values are inserted. + * + * Reference count of the new map is zero. + * + * @param hash + * @param equals + * @param keys + * @param values + * @param length + * @return + */ +struct store *store_of(STORE_HASHFN_T(hash), STORE_EQUALSFN_T(equals), + STORE_KEY_T *keys, STORE_VALUE_T *values, size_t length); + +/** + * Returns a new map derived from store, but with key set to the return value of fn. + * fn is passed the key, the current value for key, and user_data. + * If key is not present in store, NULL is passed in place of the key and current value. + * + * Reference count of the new map is zero. + * + * @param store + * @param key + * @param fn + * @param user_data + * @return + */ +struct store *store_assoc(const struct store *store, const STORE_KEY_T key, + STORE_ASSOCFN_T(fn), const void *user_data); + +/** + * Compares two maps for equality. A lot of short-circuiting is done on the assumption that unequal hashes + * (for both keys and values) imply inequality. This is commonly known as the Java Hashcode contract: If two values + * are equal, their hashes must be equal as well. + * + * @param left + * @param right + * @return + */ +int store_equals(const struct store *left, const struct store *right, + STORE_VALUE_EQUALSFN_T(value_equals)); + +/** + * An iterator for store. Meant to be put on the stack. + */ +struct store_iter { + int stack_level; + unsigned element_cursor; + unsigned element_arity; + unsigned branch_cursor_stack[8]; + unsigned branch_arity_stack[8]; + const void *node_stack[8]; +}; + +/** + * Initializes an iterator with a store. + * + * Example: + * @code{.c} + * struct store_iter iter; + * STORE_KEY_T key; + * STORE_VAL_T val; + * + * store_iter_init(&iter, store); + * while(store_iter_next(&iter, &key, &val)) { + * // do something with key and value + * } + * @endcode + * + * @param iter + * @param store + */ +void store_iter_init(struct store_iter *iter, const struct store *store); + +/** + * Advances iter and points key_receiver and value_receiver to the next pair. + * + * @param iter + * @param key_receiver + * @param value_receiver + * @return 0 if the end of the store has been reached + */ +int store_iter_next(struct store_iter *iter, STORE_KEY_T *key_receiver, + STORE_VALUE_T *value_receiver); + +#endif |