diff options
author | Alasdair Kergon <agk@redhat.com> | 2005-10-16 22:57:20 +0000 |
---|---|---|
committer | Alasdair Kergon <agk@redhat.com> | 2005-10-16 22:57:20 +0000 |
commit | a3f6b2ce798cf738c4e8bf510f86ebd45815842c (patch) | |
tree | e593e7f28c80cc9e3ff6bca1469aeb69bb8be54b /libdm/datastruct | |
parent | 58d83f1a94789718a1588edd350753390cc05cbe (diff) | |
download | lvm2-a3f6b2ce798cf738c4e8bf510f86ebd45815842c.tar.gz |
export bitset, pool, hash, malloc
Diffstat (limited to 'libdm/datastruct')
-rw-r--r-- | libdm/datastruct/bitset.c | 37 | ||||
-rw-r--r-- | libdm/datastruct/hash.c | 91 |
2 files changed, 63 insertions, 65 deletions
diff --git a/libdm/datastruct/bitset.c b/libdm/datastruct/bitset.c index 4962245c8..bb05e5e86 100644 --- a/libdm/datastruct/bitset.c +++ b/libdm/datastruct/bitset.c @@ -14,21 +14,20 @@ */ #include "lib.h" -#include "bitset.h" /* FIXME: calculate this. */ #define INT_SHIFT 5 -bitset_t bitset_create(struct pool *mem, unsigned num_bits) +dm_bitset_t dm_bitset_create(struct dm_pool *mem, unsigned num_bits) { - unsigned n = (num_bits / BITS_PER_INT) + 2; + unsigned n = (num_bits / DM_BITS_PER_INT) + 2; size_t size = sizeof(int) * n; - bitset_t bs; + dm_bitset_t bs; if (mem) - bs = pool_zalloc(mem, size); + bs = dm_pool_zalloc(mem, size); else - bs = dbg_malloc(size); + bs = dm_malloc(size); if (!bs) return NULL; @@ -36,20 +35,20 @@ bitset_t bitset_create(struct pool *mem, unsigned num_bits) *bs = num_bits; if (!mem) - bit_clear_all(bs); + dm_bit_clear_all(bs); return bs; } -void bitset_destroy(bitset_t bs) +void dm_bitset_destroy(dm_bitset_t bs) { - dbg_free(bs); + dm_free(bs); } -void bit_union(bitset_t out, bitset_t in1, bitset_t in2) +void dm_bit_union(dm_bitset_t out, dm_bitset_t in1, dm_bitset_t in2) { int i; - for (i = (in1[0] / BITS_PER_INT) + 1; i; i--) + for (i = (in1[0] / DM_BITS_PER_INT) + 1; i; i--) out[i] = in1[i] | in2[i]; } @@ -58,7 +57,7 @@ void bit_union(bitset_t out, bitset_t in1, bitset_t in2) */ static inline int _test_word(uint32_t test, int bit) { - while (bit < BITS_PER_INT) { + while (bit < DM_BITS_PER_INT) { if (test & (0x1 << bit)) return bit; bit++; @@ -67,7 +66,7 @@ static inline int _test_word(uint32_t test, int bit) return -1; } -int bit_get_next(bitset_t bs, int last_bit) +int dm_bit_get_next(dm_bitset_t bs, int last_bit) { int bit, word; uint32_t test; @@ -77,19 +76,19 @@ int bit_get_next(bitset_t bs, int last_bit) while (last_bit < bs[0]) { word = last_bit >> INT_SHIFT; test = bs[word + 1]; - bit = last_bit & (BITS_PER_INT - 1); + bit = last_bit & (DM_BITS_PER_INT - 1); if ((bit = _test_word(test, bit)) >= 0) - return (word * BITS_PER_INT) + bit; + return (word * DM_BITS_PER_INT) + bit; - last_bit = last_bit - (last_bit & (BITS_PER_INT - 1)) + - BITS_PER_INT; + last_bit = last_bit - (last_bit & (DM_BITS_PER_INT - 1)) + + DM_BITS_PER_INT; } return -1; } -int bit_get_first(bitset_t bs) +int dm_bit_get_first(dm_bitset_t bs) { - return bit_get_next(bs, -1); + return dm_bit_get_next(bs, -1); } diff --git a/libdm/datastruct/hash.c b/libdm/datastruct/hash.c index 6753ca7ab..d5564e0d2 100644 --- a/libdm/datastruct/hash.c +++ b/libdm/datastruct/hash.c @@ -14,19 +14,18 @@ */ #include "lib.h" -#include "hash.h" -struct hash_node { - struct hash_node *next; +struct dm_hash_node { + struct dm_hash_node *next; void *data; int keylen; char key[0]; }; -struct hash_table { +struct dm_hash_table { int num_nodes; int num_slots; - struct hash_node **slots; + struct dm_hash_node **slots; }; /* Permutation of the Integers 0 through 255 */ @@ -57,9 +56,9 @@ static unsigned char _nums[] = { 209 }; -static struct hash_node *_create_node(const char *str, int len) +static struct dm_hash_node *_create_node(const char *str, int len) { - struct hash_node *n = dbg_malloc(sizeof(*n) + len); + struct dm_hash_node *n = dm_malloc(sizeof(*n) + len); if (n) { memcpy(n->key, str, len); @@ -86,11 +85,11 @@ static unsigned _hash(const char *str, uint32_t len) return h; } -struct hash_table *hash_create(unsigned size_hint) +struct dm_hash_table *dm_hash_create(unsigned size_hint) { size_t len; unsigned new_size = 16u; - struct hash_table *hc = dbg_malloc(sizeof(*hc)); + struct dm_hash_table *hc = dm_malloc(sizeof(*hc)); if (!hc) { stack; @@ -105,7 +104,7 @@ struct hash_table *hash_create(unsigned size_hint) hc->num_slots = new_size; len = sizeof(*(hc->slots)) * new_size; - if (!(hc->slots = dbg_malloc(len))) { + if (!(hc->slots = dm_malloc(len))) { stack; goto bad; } @@ -113,35 +112,35 @@ struct hash_table *hash_create(unsigned size_hint) return hc; bad: - dbg_free(hc->slots); - dbg_free(hc); + dm_free(hc->slots); + dm_free(hc); return 0; } -static void _free_nodes(struct hash_table *t) +static void _free_nodes(struct dm_hash_table *t) { - struct hash_node *c, *n; + struct dm_hash_node *c, *n; int i; for (i = 0; i < t->num_slots; i++) for (c = t->slots[i]; c; c = n) { n = c->next; - dbg_free(c); + dm_free(c); } } -void hash_destroy(struct hash_table *t) +void dm_hash_destroy(struct dm_hash_table *t) { _free_nodes(t); - dbg_free(t->slots); - dbg_free(t); + dm_free(t->slots); + dm_free(t); } -static inline struct hash_node **_find(struct hash_table *t, const char *key, +static inline struct dm_hash_node **_find(struct dm_hash_table *t, const char *key, uint32_t len) { unsigned h = _hash(key, len) & (t->num_slots - 1); - struct hash_node **c; + struct dm_hash_node **c; for (c = &t->slots[h]; *c; c = &((*c)->next)) if (!memcmp(key, (*c)->key, len)) @@ -150,22 +149,22 @@ static inline struct hash_node **_find(struct hash_table *t, const char *key, return c; } -void *hash_lookup_binary(struct hash_table *t, const char *key, +void *dm_hash_lookup_binary(struct dm_hash_table *t, const char *key, uint32_t len) { - struct hash_node **c = _find(t, key, len); + struct dm_hash_node **c = _find(t, key, len); return *c ? (*c)->data : 0; } -int hash_insert_binary(struct hash_table *t, const char *key, +int dm_hash_insert_binary(struct dm_hash_table *t, const char *key, uint32_t len, void *data) { - struct hash_node **c = _find(t, key, len); + struct dm_hash_node **c = _find(t, key, len); if (*c) (*c)->data = data; else { - struct hash_node *n = _create_node(key, len); + struct dm_hash_node *n = _create_node(key, len); if (!n) return 0; @@ -179,42 +178,42 @@ int hash_insert_binary(struct hash_table *t, const char *key, return 1; } -void hash_remove_binary(struct hash_table *t, const char *key, +void dm_hash_remove_binary(struct dm_hash_table *t, const char *key, uint32_t len) { - struct hash_node **c = _find(t, key, len); + struct dm_hash_node **c = _find(t, key, len); if (*c) { - struct hash_node *old = *c; + struct dm_hash_node *old = *c; *c = (*c)->next; - dbg_free(old); + dm_free(old); t->num_nodes--; } } -void *hash_lookup(struct hash_table *t, const char *key) +void *dm_hash_lookup(struct dm_hash_table *t, const char *key) { - return hash_lookup_binary(t, key, strlen(key) + 1); + return dm_hash_lookup_binary(t, key, strlen(key) + 1); } -int hash_insert(struct hash_table *t, const char *key, void *data) +int dm_hash_insert(struct dm_hash_table *t, const char *key, void *data) { - return hash_insert_binary(t, key, strlen(key) + 1, data); + return dm_hash_insert_binary(t, key, strlen(key) + 1, data); } -void hash_remove(struct hash_table *t, const char *key) +void dm_hash_remove(struct dm_hash_table *t, const char *key) { - hash_remove_binary(t, key, strlen(key) + 1); + dm_hash_remove_binary(t, key, strlen(key) + 1); } -unsigned hash_get_num_entries(struct hash_table *t) +unsigned dm_hash_get_num_entries(struct dm_hash_table *t) { return t->num_nodes; } -void hash_iter(struct hash_table *t, iterate_fn f) +void dm_hash_iter(struct dm_hash_table *t, dm_hash_iterate_fn f) { - struct hash_node *c; + struct dm_hash_node *c; int i; for (i = 0; i < t->num_slots; i++) @@ -222,26 +221,26 @@ void hash_iter(struct hash_table *t, iterate_fn f) f(c->data); } -void hash_wipe(struct hash_table *t) +void dm_hash_wipe(struct dm_hash_table *t) { _free_nodes(t); - memset(t->slots, 0, sizeof(struct hash_node *) * t->num_slots); + memset(t->slots, 0, sizeof(struct dm_hash_node *) * t->num_slots); t->num_nodes = 0; } -char *hash_get_key(struct hash_table *t, struct hash_node *n) +char *dm_hash_get_key(struct dm_hash_table *t, struct dm_hash_node *n) { return n->key; } -void *hash_get_data(struct hash_table *t, struct hash_node *n) +void *dm_hash_get_data(struct dm_hash_table *t, struct dm_hash_node *n) { return n->data; } -static struct hash_node *_next_slot(struct hash_table *t, unsigned s) +static struct dm_hash_node *_next_slot(struct dm_hash_table *t, unsigned s) { - struct hash_node *c = NULL; + struct dm_hash_node *c = NULL; int i; for (i = s; i < t->num_slots && !c; i++) @@ -250,12 +249,12 @@ static struct hash_node *_next_slot(struct hash_table *t, unsigned s) return c; } -struct hash_node *hash_get_first(struct hash_table *t) +struct dm_hash_node *dm_hash_get_first(struct dm_hash_table *t) { return _next_slot(t, 0); } -struct hash_node *hash_get_next(struct hash_table *t, struct hash_node *n) +struct dm_hash_node *dm_hash_get_next(struct dm_hash_table *t, struct dm_hash_node *n) { unsigned h = _hash(n->key, n->keylen) & (t->num_slots - 1); return n->next ? n->next : _next_slot(t, h + 1); |