From 0363099e539bf48a9a9ba68ce5005f3aaca6f8a1 Mon Sep 17 00:00:00 2001 From: David Herrmann Date: Wed, 2 Apr 2014 16:33:53 +0200 Subject: build: move shl_xy to shl-xy Same move as with the other TSM files. Signed-off-by: David Herrmann --- Makefile.am | 8 +- src/shared/shl-array.h | 192 ++++++++++++++++++++++ src/shared/shl-htable.c | 428 ++++++++++++++++++++++++++++++++++++++++++++++++ src/shared/shl-htable.h | 222 +++++++++++++++++++++++++ src/shared/shl-llog.h | 247 ++++++++++++++++++++++++++++ src/shared/shl_array.h | 192 ---------------------- src/shared/shl_htable.c | 428 ------------------------------------------------ src/shared/shl_htable.h | 222 ------------------------- src/shared/shl_llog.h | 247 ---------------------------- src/tsm/libtsm-int.h | 2 +- src/tsm/tsm-render.c | 2 +- src/tsm/tsm-screen.c | 2 +- src/tsm/tsm-selection.c | 2 +- src/tsm/tsm-unicode.c | 4 +- src/tsm/tsm-vte.c | 2 +- 15 files changed, 1100 insertions(+), 1100 deletions(-) create mode 100644 src/shared/shl-array.h create mode 100644 src/shared/shl-htable.c create mode 100644 src/shared/shl-htable.h create mode 100644 src/shared/shl-llog.h delete mode 100644 src/shared/shl_array.h delete mode 100644 src/shared/shl_htable.c delete mode 100644 src/shared/shl_htable.h delete mode 100644 src/shared/shl_llog.h diff --git a/Makefile.am b/Makefile.am index 66fc904..b9eb4d8 100644 --- a/Makefile.am +++ b/Makefile.am @@ -105,10 +105,10 @@ endif noinst_LTLIBRARIES += libshl.la libshl_la_SOURCES = \ - src/shared/shl_array.h \ - src/shared/shl_htable.h \ - src/shared/shl_htable.c \ - src/shared/shl_llog.h + src/shared/shl-array.h \ + src/shared/shl-htable.h \ + src/shared/shl-htable.c \ + src/shared/shl-llog.h libshl_la_CPPFLAGS = $(AM_CPPFLAGS) libshl_la_LDFLAGS = $(AM_LDFLAGS) libshl_la_LIBADD = $(AM_LIBADD) diff --git a/src/shared/shl-array.h b/src/shared/shl-array.h new file mode 100644 index 0000000..f776807 --- /dev/null +++ b/src/shared/shl-array.h @@ -0,0 +1,192 @@ +/* + * shl - Dynamic Array + * + * Copyright (c) 2011-2013 David Herrmann + * + * 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. + */ + +/* + * A dynamic array implementation + */ + +#ifndef SHL_ARRAY_H +#define SHL_ARRAY_H + +#include +#include +#include + +struct shl_array { + size_t element_size; + size_t length; + size_t size; + void *data; +}; + +#define SHL_ARRAY_AT(_arr, _type, _pos) \ + (&((_type*)shl_array_get_array(_arr))[(_pos)]) + +static inline int shl_array_new(struct shl_array **out, size_t element_size, + size_t initial_size) +{ + struct shl_array *arr; + + if (!out || !element_size) + return -EINVAL; + + if (!initial_size) + initial_size = 4; + + arr = malloc(sizeof(*arr)); + if (!arr) + return -ENOMEM; + memset(arr, 0, sizeof(*arr)); + arr->element_size = element_size; + arr->length = 0; + arr->size = initial_size; + + arr->data = malloc(arr->element_size * arr->size); + if (!arr->data) { + free(arr); + return -ENOMEM; + } + + *out = arr; + return 0; +} + +static inline void shl_array_free(struct shl_array *arr) +{ + if (!arr) + return; + + free(arr->data); + free(arr); +} + +/* Compute next higher power-of-2 of @v. Returns 4 in case v is 0. */ +static inline size_t shl_array_pow2(size_t v) +{ + size_t i; + + if (!v) + return 4; + + --v; + + for (i = 1; i < 8 * sizeof(size_t); i *= 2) + v |= v >> i; + + return ++v; +} + +/* resize to length=size and zero out new array entries */ +static inline int shl_array_zresize(struct shl_array *arr, size_t size) +{ + void *tmp; + size_t newsize; + + if (!arr) + return -EINVAL; + + if (size > arr->size) { + newsize = shl_array_pow2(size); + tmp = realloc(arr->data, arr->element_size * newsize); + if (!tmp) + return -ENOMEM; + + arr->data = tmp; + arr->size = newsize; + + memset(((uint8_t*)arr->data) + arr->element_size * arr->length, + 0, arr->element_size * (size - arr->length)); + } + + arr->length = size; + return 0; +} + +static inline int shl_array_push(struct shl_array *arr, const void *data) +{ + void *tmp; + size_t newsize; + + if (!arr || !data) + return -EINVAL; + + if (arr->length >= arr->size) { + newsize = arr->size * 2; + tmp = realloc(arr->data, arr->element_size * newsize); + if (!tmp) + return -ENOMEM; + + arr->data = tmp; + arr->size = newsize; + } + + memcpy(((uint8_t*)arr->data) + arr->element_size * arr->length, + data, arr->element_size); + ++arr->length; + + return 0; +} + +static inline void shl_array_pop(struct shl_array *arr) +{ + if (!arr || !arr->length) + return; + + --arr->length; +} + +static inline void *shl_array_get_array(struct shl_array *arr) +{ + if (!arr) + return NULL; + + return arr->data; +} + +static inline size_t shl_array_get_length(struct shl_array *arr) +{ + if (!arr) + return 0; + + return arr->length; +} + +static inline size_t shl_array_get_bsize(struct shl_array *arr) +{ + if (!arr) + return 0; + + return arr->length * arr->element_size; +} + +static inline size_t shl_array_get_element_size(struct shl_array *arr) +{ + if (!arr) + return 0; + + return arr->element_size; +} + +#endif /* SHL_ARRAY_H */ diff --git a/src/shared/shl-htable.c b/src/shared/shl-htable.c new file mode 100644 index 0000000..74e3d09 --- /dev/null +++ b/src/shared/shl-htable.c @@ -0,0 +1,428 @@ +/* + * SHL - Dynamic hash-table + * + * Written-by: Rusty Russell + * Adjusted-by: David Herrmann + * Licensed under LGPLv2+ - see LICENSE_htable file for details + */ + +/* + * Please see ccan/htable/_info at: + * https://github.com/rustyrussell/ccan/tree/master/ccan/htable + * for information on the hashtable algorithm. This file copies the code inline + * and is released under the same conditions. + * + * At the end of the file you can find some helpers to use this htable to store + * objects with "unsigned long" or "char*" keys. + */ + +#include +#include +#include +#include +#include +#include +#include +#include "shl-htable.h" + +#define COLD __attribute__((cold)) + +struct htable { + /* KEEP IN SYNC WITH "struct shl_htable_int" */ + size_t (*rehash)(const void *elem, void *priv); + void *priv; + unsigned int bits; + size_t elems, deleted, max, max_with_deleted; + /* These are the bits which are the same in all pointers. */ + uintptr_t common_mask, common_bits; + uintptr_t perfect_bit; + uintptr_t *table; +}; + +#define HTABLE_INITIALIZER(name, rehash, priv) \ + { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit } + +struct htable_iter { + size_t off; +}; + +/* + * INLINE COPY OF ccan/htable.c + */ + +/* We use 0x1 as deleted marker. */ +#define HTABLE_DELETED (0x1) + +/* We clear out the bits which are always the same, and put metadata there. */ +static inline uintptr_t get_extra_ptr_bits(const struct htable *ht, + uintptr_t e) +{ + return e & ht->common_mask; +} + +static inline void *get_raw_ptr(const struct htable *ht, uintptr_t e) +{ + return (void *)((e & ~ht->common_mask) | ht->common_bits); +} + +static inline uintptr_t make_hval(const struct htable *ht, + const void *p, uintptr_t bits) +{ + return ((uintptr_t)p & ~ht->common_mask) | bits; +} + +static inline bool entry_is_valid(uintptr_t e) +{ + return e > HTABLE_DELETED; +} + +static inline uintptr_t get_hash_ptr_bits(const struct htable *ht, + size_t hash) +{ + /* Shuffling the extra bits (as specified in mask) down the + * end is quite expensive. But the lower bits are redundant, so + * we fold the value first. */ + return (hash ^ (hash >> ht->bits)) + & ht->common_mask & ~ht->perfect_bit; +} + +static void htable_init(struct htable *ht, + size_t (*rehash)(const void *elem, void *priv), + void *priv) +{ + struct htable empty = HTABLE_INITIALIZER(empty, NULL, NULL); + *ht = empty; + ht->rehash = rehash; + ht->priv = priv; + ht->table = &ht->perfect_bit; +} + +static void htable_clear(struct htable *ht, + void (*free_cb) (void *entry, void *ctx), + void *ctx) +{ + size_t i; + + if (ht->table != &ht->perfect_bit) { + if (free_cb) { + for (i = 0; i < (size_t)1 << ht->bits; ++i) { + if (entry_is_valid(ht->table[i])) + free_cb(get_raw_ptr(ht, ht->table[i]), + ctx); + } + } + + free((void *)ht->table); + } + + htable_init(ht, ht->rehash, ht->priv); +} + +static void htable_visit(struct htable *ht, + void (*visit_cb) (void *elem, void *ctx), + void *ctx) +{ + size_t i; + + if (visit_cb && ht->table != &ht->perfect_bit) { + for (i = 0; i < (size_t)1 << ht->bits; ++i) { + if (entry_is_valid(ht->table[i])) + visit_cb(get_raw_ptr(ht, ht->table[i]), ctx); + } + } +} + +static size_t hash_bucket(const struct htable *ht, size_t h) +{ + return h & ((1 << ht->bits)-1); +} + +static void *htable_val(const struct htable *ht, + struct htable_iter *i, size_t hash, uintptr_t perfect) +{ + uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect; + + while (ht->table[i->off]) { + if (ht->table[i->off] != HTABLE_DELETED) { + if (get_extra_ptr_bits(ht, ht->table[i->off]) == h2) + return get_raw_ptr(ht, ht->table[i->off]); + } + i->off = (i->off + 1) & ((1 << ht->bits)-1); + h2 &= ~perfect; + } + return NULL; +} + +static void *htable_firstval(const struct htable *ht, + struct htable_iter *i, size_t hash) +{ + i->off = hash_bucket(ht, hash); + return htable_val(ht, i, hash, ht->perfect_bit); +} + +static void *htable_nextval(const struct htable *ht, + struct htable_iter *i, size_t hash) +{ + i->off = (i->off + 1) & ((1 << ht->bits)-1); + return htable_val(ht, i, hash, 0); +} + +/* This does not expand the hash table, that's up to caller. */ +static void ht_add(struct htable *ht, const void *new, size_t h) +{ + size_t i; + uintptr_t perfect = ht->perfect_bit; + + i = hash_bucket(ht, h); + + while (entry_is_valid(ht->table[i])) { + perfect = 0; + i = (i + 1) & ((1 << ht->bits)-1); + } + ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect); +} + +static COLD bool double_table(struct htable *ht) +{ + unsigned int i; + size_t oldnum = (size_t)1 << ht->bits; + uintptr_t *oldtable, e; + + oldtable = ht->table; + ht->table = calloc(1 << (ht->bits+1), sizeof(size_t)); + if (!ht->table) { + ht->table = oldtable; + return false; + } + ht->bits++; + ht->max = ((size_t)3 << ht->bits) / 4; + ht->max_with_deleted = ((size_t)9 << ht->bits) / 10; + + /* If we lost our "perfect bit", get it back now. */ + if (!ht->perfect_bit && ht->common_mask) { + for (i = 0; i < sizeof(ht->common_mask) * CHAR_BIT; i++) { + if (ht->common_mask & ((size_t)1 << i)) { + ht->perfect_bit = (size_t)1 << i; + break; + } + } + } + + if (oldtable != &ht->perfect_bit) { + for (i = 0; i < oldnum; i++) { + if (entry_is_valid(e = oldtable[i])) { + void *p = get_raw_ptr(ht, e); + ht_add(ht, p, ht->rehash(p, ht->priv)); + } + } + free(oldtable); + } + ht->deleted = 0; + return true; +} + +static COLD void rehash_table(struct htable *ht) +{ + size_t start, i; + uintptr_t e; + + /* Beware wrap cases: we need to start from first empty bucket. */ + for (start = 0; ht->table[start]; start++); + + for (i = 0; i < (size_t)1 << ht->bits; i++) { + size_t h = (i + start) & ((1 << ht->bits)-1); + e = ht->table[h]; + if (!e) + continue; + if (e == HTABLE_DELETED) + ht->table[h] = 0; + else if (!(e & ht->perfect_bit)) { + void *p = get_raw_ptr(ht, e); + ht->table[h] = 0; + ht_add(ht, p, ht->rehash(p, ht->priv)); + } + } + ht->deleted = 0; +} + +/* We stole some bits, now we need to put them back... */ +static COLD void update_common(struct htable *ht, const void *p) +{ + unsigned int i; + uintptr_t maskdiff, bitsdiff; + + if (ht->elems == 0) { + /* Always reveal one bit of the pointer in the bucket, + * so it's not zero or HTABLE_DELETED (1), even if + * hash happens to be 0. Assumes (void *)1 is not a + * valid pointer. */ + for (i = sizeof(uintptr_t)*CHAR_BIT - 1; i > 0; i--) { + if ((uintptr_t)p & ((uintptr_t)1 << i)) + break; + } + + ht->common_mask = ~((uintptr_t)1 << i); + ht->common_bits = ((uintptr_t)p & ht->common_mask); + ht->perfect_bit = 1; + return; + } + + /* Find bits which are unequal to old common set. */ + maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask); + + /* These are the bits which go there in existing entries. */ + bitsdiff = ht->common_bits & maskdiff; + + for (i = 0; i < (size_t)1 << ht->bits; i++) { + if (!entry_is_valid(ht->table[i])) + continue; + /* Clear the bits no longer in the mask, set them as + * expected. */ + ht->table[i] &= ~maskdiff; + ht->table[i] |= bitsdiff; + } + + /* Take away those bits from our mask, bits and perfect bit. */ + ht->common_mask &= ~maskdiff; + ht->common_bits &= ~maskdiff; + ht->perfect_bit &= ~maskdiff; +} + +static bool htable_add(struct htable *ht, size_t hash, const void *p) +{ + if (ht->elems+1 > ht->max && !double_table(ht)) + return false; + if (ht->elems+1 + ht->deleted > ht->max_with_deleted) + rehash_table(ht); + assert(p); + if (((uintptr_t)p & ht->common_mask) != ht->common_bits) + update_common(ht, p); + + ht_add(ht, p, hash); + ht->elems++; + return true; +} + +static void htable_delval(struct htable *ht, struct htable_iter *i) +{ + assert(i->off < (size_t)1 << ht->bits); + assert(entry_is_valid(ht->table[i->off])); + + ht->elems--; + ht->table[i->off] = HTABLE_DELETED; + ht->deleted++; +} + +/* + * Wrapper code to make it easier to use this hash-table as map. + */ + +void shl_htable_init(struct shl_htable *htable, + bool (*compare) (const void *a, const void *b), + size_t (*rehash)(const void *elem, void *priv), + void *priv) +{ + struct htable *ht = (void*)&htable->htable; + + htable->compare = compare; + htable_init(ht, rehash, priv); +} + +void shl_htable_clear(struct shl_htable *htable, + void (*free_cb) (void *elem, void *ctx), + void *ctx) +{ + struct htable *ht = (void*)&htable->htable; + + htable_clear(ht, free_cb, ctx); +} + +void shl_htable_visit(struct shl_htable *htable, + void (*visit_cb) (void *elem, void *ctx), + void *ctx) +{ + struct htable *ht = (void*)&htable->htable; + + htable_visit(ht, visit_cb, ctx); +} + +bool shl_htable_lookup(struct shl_htable *htable, const void *obj, size_t hash, + void **out) +{ + struct htable *ht = (void*)&htable->htable; + struct htable_iter i; + void *c; + + for (c = htable_firstval(ht, &i, hash); + c; + c = htable_nextval(ht, &i, hash)) { + if (htable->compare(obj, c)) { + if (out) + *out = c; + return true; + } + } + + return false; +} + +int shl_htable_insert(struct shl_htable *htable, const void *obj, size_t hash) +{ + struct htable *ht = (void*)&htable->htable; + bool b; + + b = htable_add(ht, hash, (void*)obj); + return b ? 0 : -ENOMEM; +} + +bool shl_htable_remove(struct shl_htable *htable, const void *obj, size_t hash, + void **out) +{ + struct htable *ht = (void*)&htable->htable; + struct htable_iter i; + void *c; + + for (c = htable_firstval(ht, &i, hash); + c; + c = htable_nextval(ht, &i, hash)) { + if (htable->compare(obj, c)) { + if (out) + *out = c; + htable_delval(ht, &i); + return true; + } + } + + return false; +} + +/* + * Helpers + */ + +bool shl_htable_compare_ulong(const void *a, const void *b) +{ + return *(const unsigned long*)a == *(const unsigned long*)b; +} + +size_t shl_htable_rehash_ulong(const void *elem, void *priv) +{ + return (size_t)*(const unsigned long*)elem; +} + +bool shl_htable_compare_str(const void *a, const void *b) +{ + return !strcmp(*(char**)a, *(char**)b); +} + +/* DJB's hash function */ +size_t shl_htable_rehash_str(const void *elem, void *priv) +{ + const char *str = *(char**)elem; + size_t hash = 5381; + + for ( ; *str; ++str) + hash = (hash << 5) + hash + (size_t)*str; + + return hash; +} diff --git a/src/shared/shl-htable.h b/src/shared/shl-htable.h new file mode 100644 index 0000000..9591180 --- /dev/null +++ b/src/shared/shl-htable.h @@ -0,0 +1,222 @@ +/* + * SHL - Dynamic hash-table + * + * Copyright (c) 2010-2013 David Herrmann + * Licensed under LGPLv2+ - see LICENSE_htable file for details + */ + +/* + * Dynamic hash-table + * Implementation of a self-resizing hashtable to store arbitrary objects. + * Entries are not allocated by the table itself but are user-allocated. A + * single entry can be stored multiple times in the hashtable. No + * maintenance-members need to be embedded in user-allocated objects. However, + * the key (and optionally the hash) must be stored in the objects. + * + * Uses internally the htable from CCAN. See LICENSE_htable. + */ + +#ifndef SHL_HTABLE_H +#define SHL_HTABLE_H + +#include +#include +#include +#include +#include + +/* miscellaneous */ + +#define shl_htable_offsetof(pointer, type, member) ({ \ + const typeof(((type*)0)->member) *__ptr = (pointer); \ + (type*)(((char*)__ptr) - offsetof(type, member)); \ + }) + +/* htable */ + +struct shl_htable_int { + size_t (*rehash)(const void *elem, void *priv); + void *priv; + unsigned int bits; + size_t elems, deleted, max, max_with_deleted; + /* These are the bits which are the same in all pointers. */ + uintptr_t common_mask, common_bits; + uintptr_t perfect_bit; + uintptr_t *table; +}; + +struct shl_htable { + bool (*compare) (const void *a, const void *b); + struct shl_htable_int htable; +}; + +#define SHL_HTABLE_INIT(_obj, _compare, _rehash, _priv) \ + { \ + .compare = (_compare), \ + .htable = { \ + .rehash = (_rehash), \ + .priv = (_priv), \ + .bits = 0, \ + .elems = 0, \ + .deleted = 0, \ + .max = 0, \ + .max_with_deleted = 0, \ + .common_mask = -1, \ + .common_bits = 0, \ + .perfect_bit = 0, \ + .table = &(_obj).htable.perfect_bit \ + } \ + } + +void shl_htable_init(struct shl_htable *htable, + bool (*compare) (const void *a, const void *b), + size_t (*rehash)(const void *elem, void *priv), + void *priv); +void shl_htable_clear(struct shl_htable *htable, + void (*free_cb) (void *elem, void *ctx), + void *ctx); +void shl_htable_visit(struct shl_htable *htable, + void (*visit_cb) (void *elem, void *ctx), + void *ctx); +bool shl_htable_lookup(struct shl_htable *htable, const void *obj, size_t hash, + void **out); +int shl_htable_insert(struct shl_htable *htable, const void *obj, size_t hash); +bool shl_htable_remove(struct shl_htable *htable, const void *obj, size_t hash, + void **out); + +/* ulong htables */ + +#if SIZE_MAX < ULONG_MAX +# error "'size_t' is smaller than 'unsigned long'" +#endif + +bool shl_htable_compare_ulong(const void *a, const void *b); +size_t shl_htable_rehash_ulong(const void *elem, void *priv); + +#define SHL_HTABLE_INIT_ULONG(_obj) \ + SHL_HTABLE_INIT((_obj), shl_htable_compare_ulong, \ + shl_htable_rehash_ulong, \ + NULL) + +static inline void shl_htable_init_ulong(struct shl_htable *htable) +{ + shl_htable_init(htable, shl_htable_compare_ulong, + shl_htable_rehash_ulong, NULL); +} + +static inline void shl_htable_clear_ulong(struct shl_htable *htable, + void (*cb) (unsigned long *elem, + void *ctx), + void *ctx) +{ + shl_htable_clear(htable, (void (*) (void*, void*))cb, ctx); +} + +static inline void shl_htable_visit_ulong(struct shl_htable *htable, + void (*cb) (unsigned long *elem, + void *ctx), + void *ctx) +{ + shl_htable_visit(htable, (void (*) (void*, void*))cb, ctx); +} + +static inline bool shl_htable_lookup_ulong(struct shl_htable *htable, + unsigned long key, + unsigned long **out) +{ + return shl_htable_lookup(htable, (const void*)&key, (size_t)key, + (void**)out); +} + +static inline int shl_htable_insert_ulong(struct shl_htable *htable, + const unsigned long *key) +{ + return shl_htable_insert(htable, (const void*)key, (size_t)*key); +} + +static inline bool shl_htable_remove_ulong(struct shl_htable *htable, + unsigned long key, + unsigned long **out) +{ + return shl_htable_remove(htable, (const void*)&key, (size_t)key, + (void**)out); +} + +/* string htables */ + +bool shl_htable_compare_str(const void *a, const void *b); +size_t shl_htable_rehash_str(const void *elem, void *priv); + +#define SHL_HTABLE_INIT_STR(_obj) \ + SHL_HTABLE_INIT((_obj), shl_htable_compare_str, \ + shl_htable_rehash_str, \ + NULL) + +static inline void shl_htable_init_str(struct shl_htable *htable) +{ + shl_htable_init(htable, shl_htable_compare_str, + shl_htable_rehash_str, NULL); +} + +static inline void shl_htable_clear_str(struct shl_htable *htable, + void (*cb) (char **elem, + void *ctx), + void *ctx) +{ + shl_htable_clear(htable, (void (*) (void*, void*))cb, ctx); +} + +static inline void shl_htable_visit_str(struct shl_htable *htable, + void (*cb) (char **elem, + void *ctx), + void *ctx) +{ + shl_htable_visit(htable, (void (*) (void*, void*))cb, ctx); +} + +static inline size_t shl_htable_hash_str(struct shl_htable *htable, + const char *str, size_t *hash) +{ + size_t h; + + if (hash && *hash) { + h = *hash; + } else { + h = htable->htable.rehash((const void*)&str, NULL); + if (hash) + *hash = h; + } + + return h; +} + +static inline bool shl_htable_lookup_str(struct shl_htable *htable, + const char *str, size_t *hash, + char ***out) +{ + size_t h; + + h = shl_htable_hash_str(htable, str, hash); + return shl_htable_lookup(htable, (const void*)&str, h, (void**)out); +} + +static inline int shl_htable_insert_str(struct shl_htable *htable, + char **str, size_t *hash) +{ + size_t h; + + h = shl_htable_hash_str(htable, *str, hash); + return shl_htable_insert(htable, (const void*)str, h); +} + +static inline bool shl_htable_remove_str(struct shl_htable *htable, + const char *str, size_t *hash, + char ***out) +{ + size_t h; + + h = shl_htable_hash_str(htable, str, hash); + return shl_htable_remove(htable, (const void*)&str, h, (void **)out); +} + +#endif /* SHL_HTABLE_H */ diff --git a/src/shared/shl-llog.h b/src/shared/shl-llog.h new file mode 100644 index 0000000..1dd4a3c --- /dev/null +++ b/src/shared/shl-llog.h @@ -0,0 +1,247 @@ +/* + * SHL - Library Log/Debug Interface + * + * Copyright (c) 2010-2013 David Herrmann + * Dedicated to the Public Domain + */ + +/* + * Library Log/Debug Interface + * Libraries should always avoid producing side-effects. This includes writing + * log-messages of any kind. However, you often don't want to disable debugging + * entirely, therefore, the core objects often contain a pointer to a function + * which performs logging. If that pointer is NULL (default), logging is + * disabled. + * + * This header should never be installed into the system! This is _no_ public + * header. Instead, copy it into your application if you want and use it there. + * Your public library API should include something like this: + * + * typedef void (*MYPREFIX_log_t) (void *data, + * const char *file, + * int line, + * const char *func, + * const char *subs, + * unsigned int sev, + * const char *format, + * va_list args); + * + * And then the user can supply such a function when creating a new context + * object of your library or simply supply NULL. Internally, you have a field of + * type "MYPREFIX_log_t llog" in your main structure. If you pass this to the + * convenience helpers like llog_dbg(), llog_warn() etc. it will automatically + * use the "llog" field to print the message. If it is NULL, nothing is done. + * + * The arguments of the log-function are defined as: + * data: User-supplied data field that is passed straight through. + * file: Zero terminated string of the file-name where the log-message + * occurred. Can be NULL. + * line: Line number of @file where the message occurred. Set to 0 or smaller + * if not available. + * func: Function name where the log-message occurred. Can be NULL. + * subs: Subsystem where the message occurred (zero terminated). Can be NULL. + * sev: Severity of log-message. An integer between 0 and 7 as defined below. + * These are identical to the linux-kernel severities so there is no need + * to include these in your public API. Every app can define them + * themselves, if they need it. + * format: Format string. Must not be NULL. + * args: Argument array + * + * The user should also be able to optionally provide a data field which is + * always passed unmodified as first parameter to the log-function. This allows + * to add context to the logger. + */ + +#ifndef SHL_LLOG_H +#define SHL_LLOG_H + +#include +#include +#include +#include + +enum llog_severity { + LLOG_FATAL = 0, + LLOG_ALERT = 1, + LLOG_CRITICAL = 2, + LLOG_ERROR = 3, + LLOG_WARNING = 4, + LLOG_NOTICE = 5, + LLOG_INFO = 6, + LLOG_DEBUG = 7, + LLOG_SEV_NUM, +}; + +typedef void (*llog_submit_t) (void *data, + const char *file, + int line, + const char *func, + const char *subs, + unsigned int sev, + const char *format, + va_list args); + +static inline __attribute__((format(printf, 8, 9))) +void llog_format(llog_submit_t llog, + void *data, + const char *file, + int line, + const char *func, + const char *subs, + unsigned int sev, + const char *format, + ...) +{ + int saved_errno = errno; + va_list list; + + if (llog) { + va_start(list, format); + errno = saved_errno; + llog(data, file, line, func, subs, sev, format, list); + va_end(list); + } +} + +#ifndef LLOG_SUBSYSTEM +static const char *LLOG_SUBSYSTEM __attribute__((__unused__)); +#endif + +#define LLOG_DEFAULT __FILE__, __LINE__, __func__, LLOG_SUBSYSTEM + +#define llog_printf(obj, sev, format, ...) \ + llog_format((obj)->llog, \ + (obj)->llog_data, \ + LLOG_DEFAULT, \ + (sev), \ + (format), \ + ##__VA_ARGS__) +#define llog_dprintf(obj, data, sev, format, ...) \ + llog_format((obj), \ + (data), \ + LLOG_DEFAULT, \ + (sev), \ + (format), \ + ##__VA_ARGS__) + +static inline __attribute__((format(printf, 4, 5))) +void llog_dummyf(llog_submit_t llog, void *data, unsigned int sev, + const char *format, ...) +{ +} + +/* + * Helpers + * They pick up all the default values and submit the message to the + * llog-subsystem. The llog_debug() function will discard the message unless + * BUILD_ENABLE_DEBUG is defined. + */ + +#ifdef BUILD_ENABLE_DEBUG + #define llog_ddebug(obj, data, format, ...) \ + llog_dprintf((obj), (data), LLOG_DEBUG, (format), ##__VA_ARGS__) + #define llog_debug(obj, format, ...) \ + llog_ddebug((obj)->llog, (obj)->llog_data, (format), ##__VA_ARGS__) +#else + #define llog_ddebug(obj, data, format, ...) \ + llog_dummyf((obj), (data), LLOG_DEBUG, (format), ##__VA_ARGS__) + #define llog_debug(obj, format, ...) \ + llog_ddebug((obj)->llog, (obj)->llog_data, (format), ##__VA_ARGS__) +#endif + +#define llog_info(obj, format, ...) \ + llog_printf((obj), LLOG_INFO, (format), ##__VA_ARGS__) +#define llog_dinfo(obj, data, format, ...) \ + llog_dprintf((obj), (data), LLOG_INFO, (format), ##__VA_ARGS__) +#define llog_notice(obj, format, ...) \ + llog_printf((obj), LLOG_NOTICE, (format), ##__VA_ARGS__) +#define llog_dnotice(obj, data, format, ...) \ + llog_dprintf((obj), (data), LLOG_NOTICE, (format), ##__VA_ARGS__) +#define llog_warning(obj, format, ...) \ + llog_printf((obj), LLOG_WARNING, (format), ##__VA_ARGS__) +#define llog_dwarning(obj, data, format, ...) \ + llog_dprintf((obj), (data), LLOG_WARNING, (format), ##__VA_ARGS__) +#define llog_error(obj, format, ...) \ + llog_printf((obj), LLOG_ERROR, (format), ##__VA_ARGS__) +#define llog_derror(obj, data, format, ...) \ + llog_dprintf((obj), (data), LLOG_ERROR, (format), ##__VA_ARGS__) +#define llog_critical(obj, format, ...) \ + llog_printf((obj), LLOG_CRITICAL, (format), ##__VA_ARGS__) +#define llog_dcritical(obj, data, format, ...) \ + llog_dprintf((obj), (data), LLOG_CRITICAL, (format), ##__VA_ARGS__) +#define llog_alert(obj, format, ...) \ + llog_printf((obj), LLOG_ALERT, (format), ##__VA_ARGS__) +#define llog_dalert(obj, data, format, ...) \ + llog_dprintf((obj), (data), LLOG_ALERT, (format), ##__VA_ARGS__) +#define llog_fatal(obj, format, ...) \ + llog_printf((obj), LLOG_FATAL, (format), ##__VA_ARGS__) +#define llog_dfatal(obj, data, format, ...) \ + llog_dprintf((obj), (data), LLOG_FATAL, (format), ##__VA_ARGS__) + +/* + * Default log messages + * These macros can be used to produce default log messages. You can use them + * directly in an "return" statement. The "v" variants automatically cast the + * result to void so it can be used in return statements inside of void + * functions. The "d" variants use the logging object directly as the parent + * might not exist, yet. + * + * Most of the messages work only if debugging is enabled. This is, because they + * are used in debug paths and would slow down normal applications. + */ + +#define llog_dEINVAL(obj, data) \ + (llog_derror((obj), (data), "invalid arguments"), -EINVAL) +#define llog_EINVAL(obj) \ + (llog_dEINVAL((obj)->llog, (obj)->llog_data)) +#define llog_vEINVAL(obj) \ + ((void)llog_EINVAL(obj)) +#define llog_vdEINVAL(obj, data) \ + ((void)llog_dEINVAL((obj), (data))) + +#define llog_dEFAULT(obj, data) \ + (llog_derror((obj), (data), "internal operation failed"), -EFAULT) +#define llog_EFAULT(obj) \ + (llog_dEFAULT((obj)->llog, (obj)->llog_data)) +#define llog_vEFAULT(obj) \ + ((void)llog_EFAULT(obj)) +#define llog_vdEFAULT(obj, data) \ + ((void)llog_dEFAULT((obj), (data))) + +#define llog_dENOMEM(obj, data) \ + (llog_derror((obj), (data), "out of memory"), -ENOMEM) +#define llog_ENOMEM(obj) \ + (llog_dENOMEM((obj)->llog, (obj)->llog_data)) +#define llog_vENOMEM(obj) \ + ((void)llog_ENOMEM(obj)) +#define llog_vdENOMEM(obj, data) \ + ((void)llog_dENOMEM((obj), (data))) + +#define llog_dEPIPE(obj, data) \ + (llog_derror((obj), (data), "fd closed unexpectedly"), -EPIPE) +#define llog_EPIPE(obj) \ + (llog_dEPIPE((obj)->llog, (obj)->llog_data)) +#define llog_vEPIPE(obj) \ + ((void)llog_EPIPE(obj)) +#define llog_vdEPIPE(obj, data) \ + ((void)llog_dEPIPE((obj), (data))) + +#define llog_dERRNO(obj, data) \ + (llog_derror((obj), (data), "syscall failed (%d): %m", errno), -errno) +#define llog_ERRNO(obj) \ + (llog_dERRNO((obj)->llog, (obj)->llog_data)) +#define llog_vERRNO(obj) \ + ((void)llog_ERRNO(obj)) +#define llog_vdERRNO(obj, data) \ + ((void)llog_dERRNO((obj), (data))) + +#define llog_dERR(obj, data, _r) \ + (errno = -(_r), llog_derror((obj), (data), "syscall failed (%d): %m", (_r)), (_r)) +#define llog_ERR(obj, _r) \ + (llog_dERR((obj)->llog, (obj)->llog_data, (_r))) +#define llog_vERR(obj, _r) \ + ((void)llog_ERR((obj), (_r))) +#define llog_vdERR(obj, data, _r) \ + ((void)llog_dERR((obj), (data), (_r))) + +#endif /* SHL_LLOG_H */ diff --git a/src/shared/shl_array.h b/src/shared/shl_array.h deleted file mode 100644 index f776807..0000000 --- a/src/shared/shl_array.h +++ /dev/null @@ -1,192 +0,0 @@ -/* - * shl - Dynamic Array - * - * Copyright (c) 2011-2013 David Herrmann - * - * 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. - */ - -/* - * A dynamic array implementation - */ - -#ifndef SHL_ARRAY_H -#define SHL_ARRAY_H - -#include -#include -#include - -struct shl_array { - size_t element_size; - size_t length; - size_t size; - void *data; -}; - -#define SHL_ARRAY_AT(_arr, _type, _pos) \ - (&((_type*)shl_array_get_array(_arr))[(_pos)]) - -static inline int shl_array_new(struct shl_array **out, size_t element_size, - size_t initial_size) -{ - struct shl_array *arr; - - if (!out || !element_size) - return -EINVAL; - - if (!initial_size) - initial_size = 4; - - arr = malloc(sizeof(*arr)); - if (!arr) - return -ENOMEM; - memset(arr, 0, sizeof(*arr)); - arr->element_size = element_size; - arr->length = 0; - arr->size = initial_size; - - arr->data = malloc(arr->element_size * arr->size); - if (!arr->data) { - free(arr); - return -ENOMEM; - } - - *out = arr; - return 0; -} - -static inline void shl_array_free(struct shl_array *arr) -{ - if (!arr) - return; - - free(arr->data); - free(arr); -} - -/* Compute next higher power-of-2 of @v. Returns 4 in case v is 0. */ -static inline size_t shl_array_pow2(size_t v) -{ - size_t i; - - if (!v) - return 4; - - --v; - - for (i = 1; i < 8 * sizeof(size_t); i *= 2) - v |= v >> i; - - return ++v; -} - -/* resize to length=size and zero out new array entries */ -static inline int shl_array_zresize(struct shl_array *arr, size_t size) -{ - void *tmp; - size_t newsize; - - if (!arr) - return -EINVAL; - - if (size > arr->size) { - newsize = shl_array_pow2(size); - tmp = realloc(arr->data, arr->element_size * newsize); - if (!tmp) - return -ENOMEM; - - arr->data = tmp; - arr->size = newsize; - - memset(((uint8_t*)arr->data) + arr->element_size * arr->length, - 0, arr->element_size * (size - arr->length)); - } - - arr->length = size; - return 0; -} - -static inline int shl_array_push(struct shl_array *arr, const void *data) -{ - void *tmp; - size_t newsize; - - if (!arr || !data) - return -EINVAL; - - if (arr->length >= arr->size) { - newsize = arr->size * 2; - tmp = realloc(arr->data, arr->element_size * newsize); - if (!tmp) - return -ENOMEM; - - arr->data = tmp; - arr->size = newsize; - } - - memcpy(((uint8_t*)arr->data) + arr->element_size * arr->length, - data, arr->element_size); - ++arr->length; - - return 0; -} - -static inline void shl_array_pop(struct shl_array *arr) -{ - if (!arr || !arr->length) - return; - - --arr->length; -} - -static inline void *shl_array_get_array(struct shl_array *arr) -{ - if (!arr) - return NULL; - - return arr->data; -} - -static inline size_t shl_array_get_length(struct shl_array *arr) -{ - if (!arr) - return 0; - - return arr->length; -} - -static inline size_t shl_array_get_bsize(struct shl_array *arr) -{ - if (!arr) - return 0; - - return arr->length * arr->element_size; -} - -static inline size_t shl_array_get_element_size(struct shl_array *arr) -{ - if (!arr) - return 0; - - return arr->element_size; -} - -#endif /* SHL_ARRAY_H */ diff --git a/src/shared/shl_htable.c b/src/shared/shl_htable.c deleted file mode 100644 index e79a7c0..0000000 --- a/src/shared/shl_htable.c +++ /dev/null @@ -1,428 +0,0 @@ -/* - * SHL - Dynamic hash-table - * - * Written-by: Rusty Russell - * Adjusted-by: David Herrmann - * Licensed under LGPLv2+ - see LICENSE_htable file for details - */ - -/* - * Please see ccan/htable/_info at: - * https://github.com/rustyrussell/ccan/tree/master/ccan/htable - * for information on the hashtable algorithm. This file copies the code inline - * and is released under the same conditions. - * - * At the end of the file you can find some helpers to use this htable to store - * objects with "unsigned long" or "char*" keys. - */ - -#include -#include -#include -#include -#include -#include -#include -#include "shl_htable.h" - -#define COLD __attribute__((cold)) - -struct htable { - /* KEEP IN SYNC WITH "struct shl_htable_int" */ - size_t (*rehash)(const void *elem, void *priv); - void *priv; - unsigned int bits; - size_t elems, deleted, max, max_with_deleted; - /* These are the bits which are the same in all pointers. */ - uintptr_t common_mask, common_bits; - uintptr_t perfect_bit; - uintptr_t *table; -}; - -#define HTABLE_INITIALIZER(name, rehash, priv) \ - { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit } - -struct htable_iter { - size_t off; -}; - -/* - * INLINE COPY OF ccan/htable.c - */ - -/* We use 0x1 as deleted marker. */ -#define HTABLE_DELETED (0x1) - -/* We clear out the bits which are always the same, and put metadata there. */ -static inline uintptr_t get_extra_ptr_bits(const struct htable *ht, - uintptr_t e) -{ - return e & ht->common_mask; -} - -static inline void *get_raw_ptr(const struct htable *ht, uintptr_t e) -{ - return (void *)((e & ~ht->common_mask) | ht->common_bits); -} - -static inline uintptr_t make_hval(const struct htable *ht, - const void *p, uintptr_t bits) -{ - return ((uintptr_t)p & ~ht->common_mask) | bits; -} - -static inline bool entry_is_valid(uintptr_t e) -{ - return e > HTABLE_DELETED; -} - -static inline uintptr_t get_hash_ptr_bits(const struct htable *ht, - size_t hash) -{ - /* Shuffling the extra bits (as specified in mask) down the - * end is quite expensive. But the lower bits are redundant, so - * we fold the value first. */ - return (hash ^ (hash >> ht->bits)) - & ht->common_mask & ~ht->perfect_bit; -} - -static void htable_init(struct htable *ht, - size_t (*rehash)(const void *elem, void *priv), - void *priv) -{ - struct htable empty = HTABLE_INITIALIZER(empty, NULL, NULL); - *ht = empty; - ht->rehash = rehash; - ht->priv = priv; - ht->table = &ht->perfect_bit; -} - -static void htable_clear(struct htable *ht, - void (*free_cb) (void *entry, void *ctx), - void *ctx) -{ - size_t i; - - if (ht->table != &ht->perfect_bit) { - if (free_cb) { - for (i = 0; i < (size_t)1 << ht->bits; ++i) { - if (entry_is_valid(ht->table[i])) - free_cb(get_raw_ptr(ht, ht->table[i]), - ctx); - } - } - - free((void *)ht->table); - } - - htable_init(ht, ht->rehash, ht->priv); -} - -static void htable_visit(struct htable *ht, - void (*visit_cb) (void *elem, void *ctx), - void *ctx) -{ - size_t i; - - if (visit_cb && ht->table != &ht->perfect_bit) { - for (i = 0; i < (size_t)1 << ht->bits; ++i) { - if (entry_is_valid(ht->table[i])) - visit_cb(get_raw_ptr(ht, ht->table[i]), ctx); - } - } -} - -static size_t hash_bucket(const struct htable *ht, size_t h) -{ - return h & ((1 << ht->bits)-1); -} - -static void *htable_val(const struct htable *ht, - struct htable_iter *i, size_t hash, uintptr_t perfect) -{ - uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect; - - while (ht->table[i->off]) { - if (ht->table[i->off] != HTABLE_DELETED) { - if (get_extra_ptr_bits(ht, ht->table[i->off]) == h2) - return get_raw_ptr(ht, ht->table[i->off]); - } - i->off = (i->off + 1) & ((1 << ht->bits)-1); - h2 &= ~perfect; - } - return NULL; -} - -static void *htable_firstval(const struct htable *ht, - struct htable_iter *i, size_t hash) -{ - i->off = hash_bucket(ht, hash); - return htable_val(ht, i, hash, ht->perfect_bit); -} - -static void *htable_nextval(const struct htable *ht, - struct htable_iter *i, size_t hash) -{ - i->off = (i->off + 1) & ((1 << ht->bits)-1); - return htable_val(ht, i, hash, 0); -} - -/* This does not expand the hash table, that's up to caller. */ -static void ht_add(struct htable *ht, const void *new, size_t h) -{ - size_t i; - uintptr_t perfect = ht->perfect_bit; - - i = hash_bucket(ht, h); - - while (entry_is_valid(ht->table[i])) { - perfect = 0; - i = (i + 1) & ((1 << ht->bits)-1); - } - ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect); -} - -static COLD bool double_table(struct htable *ht) -{ - unsigned int i; - size_t oldnum = (size_t)1 << ht->bits; - uintptr_t *oldtable, e; - - oldtable = ht->table; - ht->table = calloc(1 << (ht->bits+1), sizeof(size_t)); - if (!ht->table) { - ht->table = oldtable; - return false; - } - ht->bits++; - ht->max = ((size_t)3 << ht->bits) / 4; - ht->max_with_deleted = ((size_t)9 << ht->bits) / 10; - - /* If we lost our "perfect bit", get it back now. */ - if (!ht->perfect_bit && ht->common_mask) { - for (i = 0; i < sizeof(ht->common_mask) * CHAR_BIT; i++) { - if (ht->common_mask & ((size_t)1 << i)) { - ht->perfect_bit = (size_t)1 << i; - break; - } - } - } - - if (oldtable != &ht->perfect_bit) { - for (i = 0; i < oldnum; i++) { - if (entry_is_valid(e = oldtable[i])) { - void *p = get_raw_ptr(ht, e); - ht_add(ht, p, ht->rehash(p, ht->priv)); - } - } - free(oldtable); - } - ht->deleted = 0; - return true; -} - -static COLD void rehash_table(struct htable *ht) -{ - size_t start, i; - uintptr_t e; - - /* Beware wrap cases: we need to start from first empty bucket. */ - for (start = 0; ht->table[start]; start++); - - for (i = 0; i < (size_t)1 << ht->bits; i++) { - size_t h = (i + start) & ((1 << ht->bits)-1); - e = ht->table[h]; - if (!e) - continue; - if (e == HTABLE_DELETED) - ht->table[h] = 0; - else if (!(e & ht->perfect_bit)) { - void *p = get_raw_ptr(ht, e); - ht->table[h] = 0; - ht_add(ht, p, ht->rehash(p, ht->priv)); - } - } - ht->deleted = 0; -} - -/* We stole some bits, now we need to put them back... */ -static COLD void update_common(struct htable *ht, const void *p) -{ - unsigned int i; - uintptr_t maskdiff, bitsdiff; - - if (ht->elems == 0) { - /* Always reveal one bit of the pointer in the bucket, - * so it's not zero or HTABLE_DELETED (1), even if - * hash happens to be 0. Assumes (void *)1 is not a - * valid pointer. */ - for (i = sizeof(uintptr_t)*CHAR_BIT - 1; i > 0; i--) { - if ((uintptr_t)p & ((uintptr_t)1 << i)) - break; - } - - ht->common_mask = ~((uintptr_t)1 << i); - ht->common_bits = ((uintptr_t)p & ht->common_mask); - ht->perfect_bit = 1; - return; - } - - /* Find bits which are unequal to old common set. */ - maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask); - - /* These are the bits which go there in existing entries. */ - bitsdiff = ht->common_bits & maskdiff; - - for (i = 0; i < (size_t)1 << ht->bits; i++) { - if (!entry_is_valid(ht->table[i])) - continue; - /* Clear the bits no longer in the mask, set them as - * expected. */ - ht->table[i] &= ~maskdiff; - ht->table[i] |= bitsdiff; - } - - /* Take away those bits from our mask, bits and perfect bit. */ - ht->common_mask &= ~maskdiff; - ht->common_bits &= ~maskdiff; - ht->perfect_bit &= ~maskdiff; -} - -static bool htable_add(struct htable *ht, size_t hash, const void *p) -{ - if (ht->elems+1 > ht->max && !double_table(ht)) - return false; - if (ht->elems+1 + ht->deleted > ht->max_with_deleted) - rehash_table(ht); - assert(p); - if (((uintptr_t)p & ht->common_mask) != ht->common_bits) - update_common(ht, p); - - ht_add(ht, p, hash); - ht->elems++; - return true; -} - -static void htable_delval(struct htable *ht, struct htable_iter *i) -{ - assert(i->off < (size_t)1 << ht->bits); - assert(entry_is_valid(ht->table[i->off])); - - ht->elems--; - ht->table[i->off] = HTABLE_DELETED; - ht->deleted++; -} - -/* - * Wrapper code to make it easier to use this hash-table as map. - */ - -void shl_htable_init(struct shl_htable *htable, - bool (*compare) (const void *a, const void *b), - size_t (*rehash)(const void *elem, void *priv), - void *priv) -{ - struct htable *ht = (void*)&htable->htable; - - htable->compare = compare; - htable_init(ht, rehash, priv); -} - -void shl_htable_clear(struct shl_htable *htable, - void (*free_cb) (void *elem, void *ctx), - void *ctx) -{ - struct htable *ht = (void*)&htable->htable; - - htable_clear(ht, free_cb, ctx); -} - -void shl_htable_visit(struct shl_htable *htable, - void (*visit_cb) (void *elem, void *ctx), - void *ctx) -{ - struct htable *ht = (void*)&htable->htable; - - htable_visit(ht, visit_cb, ctx); -} - -bool shl_htable_lookup(struct shl_htable *htable, const void *obj, size_t hash, - void **out) -{ - struct htable *ht = (void*)&htable->htable; - struct htable_iter i; - void *c; - - for (c = htable_firstval(ht, &i, hash); - c; - c = htable_nextval(ht, &i, hash)) { - if (htable->compare(obj, c)) { - if (out) - *out = c; - return true; - } - } - - return false; -} - -int shl_htable_insert(struct shl_htable *htable, const void *obj, size_t hash) -{ - struct htable *ht = (void*)&htable->htable; - bool b; - - b = htable_add(ht, hash, (void*)obj); - return b ? 0 : -ENOMEM; -} - -bool shl_htable_remove(struct shl_htable *htable, const void *obj, size_t hash, - void **out) -{ - struct htable *ht = (void*)&htable->htable; - struct htable_iter i; - void *c; - - for (c = htable_firstval(ht, &i, hash); - c; - c = htable_nextval(ht, &i, hash)) { - if (htable->compare(obj, c)) { - if (out) - *out = c; - htable_delval(ht, &i); - return true; - } - } - - return false; -} - -/* - * Helpers - */ - -bool shl_htable_compare_ulong(const void *a, const void *b) -{ - return *(const unsigned long*)a == *(const unsigned long*)b; -} - -size_t shl_htable_rehash_ulong(const void *elem, void *priv) -{ - return (size_t)*(const unsigned long*)elem; -} - -bool shl_htable_compare_str(const void *a, const void *b) -{ - return !strcmp(*(char**)a, *(char**)b); -} - -/* DJB's hash function */ -size_t shl_htable_rehash_str(const void *elem, void *priv) -{ - const char *str = *(char**)elem; - size_t hash = 5381; - - for ( ; *str; ++str) - hash = (hash << 5) + hash + (size_t)*str; - - return hash; -} diff --git a/src/shared/shl_htable.h b/src/shared/shl_htable.h deleted file mode 100644 index 9591180..0000000 --- a/src/shared/shl_htable.h +++ /dev/null @@ -1,222 +0,0 @@ -/* - * SHL - Dynamic hash-table - * - * Copyright (c) 2010-2013 David Herrmann - * Licensed under LGPLv2+ - see LICENSE_htable file for details - */ - -/* - * Dynamic hash-table - * Implementation of a self-resizing hashtable to store arbitrary objects. - * Entries are not allocated by the table itself but are user-allocated. A - * single entry can be stored multiple times in the hashtable. No - * maintenance-members need to be embedded in user-allocated objects. However, - * the key (and optionally the hash) must be stored in the objects. - * - * Uses internally the htable from CCAN. See LICENSE_htable. - */ - -#ifndef SHL_HTABLE_H -#define SHL_HTABLE_H - -#include -#include -#include -#include -#include - -/* miscellaneous */ - -#define shl_htable_offsetof(pointer, type, member) ({ \ - const typeof(((type*)0)->member) *__ptr = (pointer); \ - (type*)(((char*)__ptr) - offsetof(type, member)); \ - }) - -/* htable */ - -struct shl_htable_int { - size_t (*rehash)(const void *elem, void *priv); - void *priv; - unsigned int bits; - size_t elems, deleted, max, max_with_deleted; - /* These are the bits which are the same in all pointers. */ - uintptr_t common_mask, common_bits; - uintptr_t perfect_bit; - uintptr_t *table; -}; - -struct shl_htable { - bool (*compare) (const void *a, const void *b); - struct shl_htable_int htable; -}; - -#define SHL_HTABLE_INIT(_obj, _compare, _rehash, _priv) \ - { \ - .compare = (_compare), \ - .htable = { \ - .rehash = (_rehash), \ - .priv = (_priv), \ - .bits = 0, \ - .elems = 0, \ - .deleted = 0, \ - .max = 0, \ - .max_with_deleted = 0, \ - .common_mask = -1, \ - .common_bits = 0, \ - .perfect_bit = 0, \ - .table = &(_obj).htable.perfect_bit \ - } \ - } - -void shl_htable_init(struct shl_htable *htable, - bool (*compare) (const void *a, const void *b), - size_t (*rehash)(const void *elem, void *priv), - void *priv); -void shl_htable_clear(struct shl_htable *htable, - void (*free_cb) (void *elem, void *ctx), - void *ctx); -void shl_htable_visit(struct shl_htable *htable, - void (*visit_cb) (void *elem, void *ctx), - void *ctx); -bool shl_htable_lookup(struct shl_htable *htable, const void *obj, size_t hash, - void **out); -int shl_htable_insert(struct shl_htable *htable, const void *obj, size_t hash); -bool shl_htable_remove(struct shl_htable *htable, const void *obj, size_t hash, - void **out); - -/* ulong htables */ - -#if SIZE_MAX < ULONG_MAX -# error "'size_t' is smaller than 'unsigned long'" -#endif - -bool shl_htable_compare_ulong(const void *a, const void *b); -size_t shl_htable_rehash_ulong(const void *elem, void *priv); - -#define SHL_HTABLE_INIT_ULONG(_obj) \ - SHL_HTABLE_INIT((_obj), shl_htable_compare_ulong, \ - shl_htable_rehash_ulong, \ - NULL) - -static inline void shl_htable_init_ulong(struct shl_htable *htable) -{ - shl_htable_init(htable, shl_htable_compare_ulong, - shl_htable_rehash_ulong, NULL); -} - -static inline void shl_htable_clear_ulong(struct shl_htable *htable, - void (*cb) (unsigned long *elem, - void *ctx), - void *ctx) -{ - shl_htable_clear(htable, (void (*) (void*, void*))cb, ctx); -} - -static inline void shl_htable_visit_ulong(struct shl_htable *htable, - void (*cb) (unsigned long *elem, - void *ctx), - void *ctx) -{ - shl_htable_visit(htable, (void (*) (void*, void*))cb, ctx); -} - -static inline bool shl_htable_lookup_ulong(struct shl_htable *htable, - unsigned long key, - unsigned long **out) -{ - return shl_htable_lookup(htable, (const void*)&key, (size_t)key, - (void**)out); -} - -static inline int shl_htable_insert_ulong(struct shl_htable *htable, - const unsigned long *key) -{ - return shl_htable_insert(htable, (const void*)key, (size_t)*key); -} - -static inline bool shl_htable_remove_ulong(struct shl_htable *htable, - unsigned long key, - unsigned long **out) -{ - return shl_htable_remove(htable, (const void*)&key, (size_t)key, - (void**)out); -} - -/* string htables */ - -bool shl_htable_compare_str(const void *a, const void *b); -size_t shl_htable_rehash_str(const void *elem, void *priv); - -#define SHL_HTABLE_INIT_STR(_obj) \ - SHL_HTABLE_INIT((_obj), shl_htable_compare_str, \ - shl_htable_rehash_str, \ - NULL) - -static inline void shl_htable_init_str(struct shl_htable *htable) -{ - shl_htable_init(htable, shl_htable_compare_str, - shl_htable_rehash_str, NULL); -} - -static inline void shl_htable_clear_str(struct shl_htable *htable, - void (*cb) (char **elem, - void *ctx), - void *ctx) -{ - shl_htable_clear(htable, (void (*) (void*, void*))cb, ctx); -} - -static inline void shl_htable_visit_str(struct shl_htable *htable, - void (*cb) (char **elem, - void *ctx), - void *ctx) -{ - shl_htable_visit(htable, (void (*) (void*, void*))cb, ctx); -} - -static inline size_t shl_htable_hash_str(struct shl_htable *htable, - const char *str, size_t *hash) -{ - size_t h; - - if (hash && *hash) { - h = *hash; - } else { - h = htable->htable.rehash((const void*)&str, NULL); - if (hash) - *hash = h; - } - - return h; -} - -static inline bool shl_htable_lookup_str(struct shl_htable *htable, - const char *str, size_t *hash, - char ***out) -{ - size_t h; - - h = shl_htable_hash_str(htable, str, hash); - return shl_htable_lookup(htable, (const void*)&str, h, (void**)out); -} - -static inline int shl_htable_insert_str(struct shl_htable *htable, - char **str, size_t *hash) -{ - size_t h; - - h = shl_htable_hash_str(htable, *str, hash); - return shl_htable_insert(htable, (const void*)str, h); -} - -static inline bool shl_htable_remove_str(struct shl_htable *htable, - const char *str, size_t *hash, - char ***out) -{ - size_t h; - - h = shl_htable_hash_str(htable, str, hash); - return shl_htable_remove(htable, (const void*)&str, h, (void **)out); -} - -#endif /* SHL_HTABLE_H */ diff --git a/src/shared/shl_llog.h b/src/shared/shl_llog.h deleted file mode 100644 index 1dd4a3c..0000000 --- a/src/shared/shl_llog.h +++ /dev/null @@ -1,247 +0,0 @@ -/* - * SHL - Library Log/Debug Interface - * - * Copyright (c) 2010-2013 David Herrmann - * Dedicated to the Public Domain - */ - -/* - * Library Log/Debug Interface - * Libraries should always avoid producing side-effects. This includes writing - * log-messages of any kind. However, you often don't want to disable debugging - * entirely, therefore, the core objects often contain a pointer to a function - * which performs logging. If that pointer is NULL (default), logging is - * disabled. - * - * This header should never be installed into the system! This is _no_ public - * header. Instead, copy it into your application if you want and use it there. - * Your public library API should include something like this: - * - * typedef void (*MYPREFIX_log_t) (void *data, - * const char *file, - * int line, - * const char *func, - * const char *subs, - * unsigned int sev, - * const char *format, - * va_list args); - * - * And then the user can supply such a function when creating a new context - * object of your library or simply supply NULL. Internally, you have a field of - * type "MYPREFIX_log_t llog" in your main structure. If you pass this to the - * convenience helpers like llog_dbg(), llog_warn() etc. it will automatically - * use the "llog" field to print the message. If it is NULL, nothing is done. - * - * The arguments of the log-function are defined as: - * data: User-supplied data field that is passed straight through. - * file: Zero terminated string of the file-name where the log-message - * occurred. Can be NULL. - * line: Line number of @file where the message occurred. Set to 0 or smaller - * if not available. - * func: Function name where the log-message occurred. Can be NULL. - * subs: Subsystem where the message occurred (zero terminated). Can be NULL. - * sev: Severity of log-message. An integer between 0 and 7 as defined below. - * These are identical to the linux-kernel severities so there is no need - * to include these in your public API. Every app can define them - * themselves, if they need it. - * format: Format string. Must not be NULL. - * args: Argument array - * - * The user should also be able to optionally provide a data field which is - * always passed unmodified as first parameter to the log-function. This allows - * to add context to the logger. - */ - -#ifndef SHL_LLOG_H -#define SHL_LLOG_H - -#include -#include -#include -#include - -enum llog_severity { - LLOG_FATAL = 0, - LLOG_ALERT = 1, - LLOG_CRITICAL = 2, - LLOG_ERROR = 3, - LLOG_WARNING = 4, - LLOG_NOTICE = 5, - LLOG_INFO = 6, - LLOG_DEBUG = 7, - LLOG_SEV_NUM, -}; - -typedef void (*llog_submit_t) (void *data, - const char *file, - int line, - const char *func, - const char *subs, - unsigned int sev, - const char *format, - va_list args); - -static inline __attribute__((format(printf, 8, 9))) -void llog_format(llog_submit_t llog, - void *data, - const char *file, - int line, - const char *func, - const char *subs, - unsigned int sev, - const char *format, - ...) -{ - int saved_errno = errno; - va_list list; - - if (llog) { - va_start(list, format); - errno = saved_errno; - llog(data, file, line, func, subs, sev, format, list); - va_end(list); - } -} - -#ifndef LLOG_SUBSYSTEM -static const char *LLOG_SUBSYSTEM __attribute__((__unused__)); -#endif - -#define LLOG_DEFAULT __FILE__, __LINE__, __func__, LLOG_SUBSYSTEM - -#define llog_printf(obj, sev, format, ...) \ - llog_format((obj)->llog, \ - (obj)->llog_data, \ - LLOG_DEFAULT, \ - (sev), \ - (format), \ - ##__VA_ARGS__) -#define llog_dprintf(obj, data, sev, format, ...) \ - llog_format((obj), \ - (data), \ - LLOG_DEFAULT, \ - (sev), \ - (format), \ - ##__VA_ARGS__) - -static inline __attribute__((format(printf, 4, 5))) -void llog_dummyf(llog_submit_t llog, void *data, unsigned int sev, - const char *format, ...) -{ -} - -/* - * Helpers - * They pick up all the default values and submit the message to the - * llog-subsystem. The llog_debug() function will discard the message unless - * BUILD_ENABLE_DEBUG is defined. - */ - -#ifdef BUILD_ENABLE_DEBUG - #define llog_ddebug(obj, data, format, ...) \ - llog_dprintf((obj), (data), LLOG_DEBUG, (format), ##__VA_ARGS__) - #define llog_debug(obj, format, ...) \ - llog_ddebug((obj)->llog, (obj)->llog_data, (format), ##__VA_ARGS__) -#else - #define llog_ddebug(obj, data, format, ...) \ - llog_dummyf((obj), (data), LLOG_DEBUG, (format), ##__VA_ARGS__) - #define llog_debug(obj, format, ...) \ - llog_ddebug((obj)->llog, (obj)->llog_data, (format), ##__VA_ARGS__) -#endif - -#define llog_info(obj, format, ...) \ - llog_printf((obj), LLOG_INFO, (format), ##__VA_ARGS__) -#define llog_dinfo(obj, data, format, ...) \ - llog_dprintf((obj), (data), LLOG_INFO, (format), ##__VA_ARGS__) -#define llog_notice(obj, format, ...) \ - llog_printf((obj), LLOG_NOTICE, (format), ##__VA_ARGS__) -#define llog_dnotice(obj, data, format, ...) \ - llog_dprintf((obj), (data), LLOG_NOTICE, (format), ##__VA_ARGS__) -#define llog_warning(obj, format, ...) \ - llog_printf((obj), LLOG_WARNING, (format), ##__VA_ARGS__) -#define llog_dwarning(obj, data, format, ...) \ - llog_dprintf((obj), (data), LLOG_WARNING, (format), ##__VA_ARGS__) -#define llog_error(obj, format, ...) \ - llog_printf((obj), LLOG_ERROR, (format), ##__VA_ARGS__) -#define llog_derror(obj, data, format, ...) \ - llog_dprintf((obj), (data), LLOG_ERROR, (format), ##__VA_ARGS__) -#define llog_critical(obj, format, ...) \ - llog_printf((obj), LLOG_CRITICAL, (format), ##__VA_ARGS__) -#define llog_dcritical(obj, data, format, ...) \ - llog_dprintf((obj), (data), LLOG_CRITICAL, (format), ##__VA_ARGS__) -#define llog_alert(obj, format, ...) \ - llog_printf((obj), LLOG_ALERT, (format), ##__VA_ARGS__) -#define llog_dalert(obj, data, format, ...) \ - llog_dprintf((obj), (data), LLOG_ALERT, (format), ##__VA_ARGS__) -#define llog_fatal(obj, format, ...) \ - llog_printf((obj), LLOG_FATAL, (format), ##__VA_ARGS__) -#define llog_dfatal(obj, data, format, ...) \ - llog_dprintf((obj), (data), LLOG_FATAL, (format), ##__VA_ARGS__) - -/* - * Default log messages - * These macros can be used to produce default log messages. You can use them - * directly in an "return" statement. The "v" variants automatically cast the - * result to void so it can be used in return statements inside of void - * functions. The "d" variants use the logging object directly as the parent - * might not exist, yet. - * - * Most of the messages work only if debugging is enabled. This is, because they - * are used in debug paths and would slow down normal applications. - */ - -#define llog_dEINVAL(obj, data) \ - (llog_derror((obj), (data), "invalid arguments"), -EINVAL) -#define llog_EINVAL(obj) \ - (llog_dEINVAL((obj)->llog, (obj)->llog_data)) -#define llog_vEINVAL(obj) \ - ((void)llog_EINVAL(obj)) -#define llog_vdEINVAL(obj, data) \ - ((void)llog_dEINVAL((obj), (data))) - -#define llog_dEFAULT(obj, data) \ - (llog_derror((obj), (data), "internal operation failed"), -EFAULT) -#define llog_EFAULT(obj) \ - (llog_dEFAULT((obj)->llog, (obj)->llog_data)) -#define llog_vEFAULT(obj) \ - ((void)llog_EFAULT(obj)) -#define llog_vdEFAULT(obj, data) \ - ((void)llog_dEFAULT((obj), (data))) - -#define llog_dENOMEM(obj, data) \ - (llog_derror((obj), (data), "out of memory"), -ENOMEM) -#define llog_ENOMEM(obj) \ - (llog_dENOMEM((obj)->llog, (obj)->llog_data)) -#define llog_vENOMEM(obj) \ - ((void)llog_ENOMEM(obj)) -#define llog_vdENOMEM(obj, data) \ - ((void)llog_dENOMEM((obj), (data))) - -#define llog_dEPIPE(obj, data) \ - (llog_derror((obj), (data), "fd closed unexpectedly"), -EPIPE) -#define llog_EPIPE(obj) \ - (llog_dEPIPE((obj)->llog, (obj)->llog_data)) -#define llog_vEPIPE(obj) \ - ((void)llog_EPIPE(obj)) -#define llog_vdEPIPE(obj, data) \ - ((void)llog_dEPIPE((obj), (data))) - -#define llog_dERRNO(obj, data) \ - (llog_derror((obj), (data), "syscall failed (%d): %m", errno), -errno) -#define llog_ERRNO(obj) \ - (llog_dERRNO((obj)->llog, (obj)->llog_data)) -#define llog_vERRNO(obj) \ - ((void)llog_ERRNO(obj)) -#define llog_vdERRNO(obj, data) \ - ((void)llog_dERRNO((obj), (data))) - -#define llog_dERR(obj, data, _r) \ - (errno = -(_r), llog_derror((obj), (data), "syscall failed (%d): %m", (_r)), (_r)) -#define llog_ERR(obj, _r) \ - (llog_dERR((obj)->llog, (obj)->llog_data, (_r))) -#define llog_vERR(obj, _r) \ - ((void)llog_ERR((obj), (_r))) -#define llog_vdERR(obj, data, _r) \ - ((void)llog_dERR((obj), (data), (_r))) - -#endif /* SHL_LLOG_H */ diff --git a/src/tsm/libtsm-int.h b/src/tsm/libtsm-int.h index 9de690e..ff3f3bc 100644 --- a/src/tsm/libtsm-int.h +++ b/src/tsm/libtsm-int.h @@ -30,7 +30,7 @@ #include #include #include "libtsm.h" -#include "shl_llog.h" +#include "shl-llog.h" #define SHL_EXPORT __attribute__((visibility("default"))) diff --git a/src/tsm/tsm-render.c b/src/tsm/tsm-render.c index 7e365f9..cb6c7d7 100644 --- a/src/tsm/tsm-render.c +++ b/src/tsm/tsm-render.c @@ -37,7 +37,7 @@ #include #include "libtsm.h" #include "libtsm-int.h" -#include "shl_llog.h" +#include "shl-llog.h" #define LLOG_SUBSYSTEM "tsm-render" diff --git a/src/tsm/tsm-screen.c b/src/tsm/tsm-screen.c index 4399d3f..5c6161e 100644 --- a/src/tsm/tsm-screen.c +++ b/src/tsm/tsm-screen.c @@ -63,7 +63,7 @@ #include #include "libtsm.h" #include "libtsm-int.h" -#include "shl_llog.h" +#include "shl-llog.h" #define LLOG_SUBSYSTEM "tsm-screen" diff --git a/src/tsm/tsm-selection.c b/src/tsm/tsm-selection.c index 3c852e0..9056abf 100644 --- a/src/tsm/tsm-selection.c +++ b/src/tsm/tsm-selection.c @@ -57,7 +57,7 @@ #include #include "libtsm.h" #include "libtsm-int.h" -#include "shl_llog.h" +#include "shl-llog.h" #define LLOG_SUBSYSTEM "tsm-selection" diff --git a/src/tsm/tsm-unicode.c b/src/tsm/tsm-unicode.c index ad282de..aef95f7 100644 --- a/src/tsm/tsm-unicode.c +++ b/src/tsm/tsm-unicode.c @@ -60,8 +60,8 @@ #include "external/wcwidth.h" #include "libtsm.h" #include "libtsm-int.h" -#include "shl_array.h" -#include "shl_htable.h" +#include "shl-array.h" +#include "shl-htable.h" /* * Unicode Symbol Handling diff --git a/src/tsm/tsm-vte.c b/src/tsm/tsm-vte.c index 3ef3851..ec8a936 100644 --- a/src/tsm/tsm-vte.c +++ b/src/tsm/tsm-vte.c @@ -51,7 +51,7 @@ #include #include "libtsm.h" #include "libtsm-int.h" -#include "shl_llog.h" +#include "shl-llog.h" #ifdef BUILD_HAVE_XKBCOMMON # include -- cgit v1.2.3