From c9fcd047509a0c5f8f2ca7181147728684f9f2e1 Mon Sep 17 00:00:00 2001 From: Marko Kreen Date: Fri, 20 Jun 2014 00:26:59 +0300 Subject: [PATCH] cbtree: allow long keys --- test/test_cbtree.c | 2 +- usual/cbtree.c | 45 +++++++++++++++++++++++++-------------------- usual/cbtree.h | 6 +++--- usual/mdict.c | 2 +- usual/strpool.c | 4 ++-- usual/strpool.h | 6 +++--- 6 files changed, 35 insertions(+), 30 deletions(-) diff --git a/test/test_cbtree.c b/test/test_cbtree.c index 0af97ed..dd36822 100644 --- a/test/test_cbtree.c +++ b/test/test_cbtree.c @@ -11,7 +11,7 @@ struct MyNode { int len; }; -static unsigned int my_getkey(void *ctx, void *obj, const void **dst_p) +static size_t my_getkey(void *ctx, void *obj, const void **dst_p) { struct MyNode *node = obj; *dst_p = node->str; diff --git a/usual/cbtree.c b/usual/cbtree.c index 39d2321..50c8a66 100644 --- a/usual/cbtree.c +++ b/usual/cbtree.c @@ -39,7 +39,7 @@ struct Node { struct Node *child[2]; - unsigned bitpos; + size_t bitpos; }; struct CBTree { @@ -51,14 +51,16 @@ struct CBTree { CxMem *cx; }; -#define SAME_KEY 0xFFFFFFFF +#define SAME_KEY SIZE_MAX + +#define MAX_KEY (SIZE_MAX / 8) /* * Low-level operations. */ /* does ptr point to user object or slot */ -static inline int is_node(void *ptr) +static inline bool is_node(void *ptr) { return ((uintptr_t)(ptr) & 1) == 0; } @@ -76,34 +78,35 @@ static inline void *get_external(void *extval) } /* get specific bit from string */ -static inline unsigned get_bit(unsigned bitpos, const unsigned char *key, unsigned klen) +static inline unsigned int get_bit(size_t bitpos, const unsigned char *key, size_t klen) { - unsigned pos = bitpos / 8; - unsigned bit = 7 - (bitpos % 8); + size_t pos = bitpos / 8; + unsigned int bit = 7 - (bitpos % 8); return (pos < klen) && (key[pos] & (1 << bit)); } /* use callback to get key for a stored object */ -static inline unsigned get_key(struct CBTree *tree, void *obj, const void **key_p) +static inline size_t get_key(struct CBTree *tree, void *obj, const void **key_p) { return tree->obj_key_cb(tree->cb_ctx, obj, key_p); } /* check if object key matches argument */ -static inline bool key_matches(struct CBTree *tree, void *obj, const void *key, unsigned klen) +static inline bool key_matches(struct CBTree *tree, void *obj, const void *key, size_t klen) { const void *o_key; - unsigned o_klen; + size_t o_klen; o_klen = get_key(tree, obj, &o_key); return (o_klen == klen) && (memcmp(key, o_key, klen) == 0); } /* Find first differing bit on 2 strings. */ -static unsigned find_crit_bit(const unsigned char *a, unsigned alen, const unsigned char *b, unsigned blen) +static size_t find_crit_bit(const unsigned char *a, size_t alen, const unsigned char *b, size_t blen) { - unsigned i, c, pos, av, bv; - unsigned minlen = (alen > blen) ? blen : alen; - unsigned maxlen = (alen > blen) ? alen : blen; + unsigned char av, bv, c, pos; + size_t i; + size_t minlen = (alen > blen) ? blen : alen; + size_t maxlen = (alen > blen) ? alen : blen; /* find differing byte in common data */ for (i = 0; i < minlen; i++) { @@ -138,10 +141,10 @@ found: */ /* walk nodes until external pointer is found */ -static void *raw_lookup(struct CBTree *tree, const void *key, unsigned klen) +static void *raw_lookup(struct CBTree *tree, const void *key, size_t klen) { struct Node *node = tree->root; - unsigned bit; + unsigned int bit; while (is_node(node)) { bit = get_bit(node->bitpos, key, klen); node = node->child[bit]; @@ -150,7 +153,7 @@ static void *raw_lookup(struct CBTree *tree, const void *key, unsigned klen) } /* actual lookup. returns obj ptr or NULL of not found */ -void *cbtree_lookup(struct CBTree *tree, const void *key, unsigned klen) +void *cbtree_lookup(struct CBTree *tree, const void *key, size_t klen) { void *obj; @@ -188,12 +191,12 @@ static bool insert_first(struct CBTree *tree, void *obj) } /* insert into specific bit-position */ -static bool insert_at(struct CBTree *tree, unsigned newbit, const void *key, unsigned klen, void *obj) +static bool insert_at(struct CBTree *tree, size_t newbit, const void *key, size_t klen, void *obj) { /* location of current node/obj pointer under examination */ struct Node **pos = &tree->root; struct Node *node; - unsigned bit; + unsigned int bit; while (is_node(*pos) && ((*pos)->bitpos < newbit)) { bit = get_bit((*pos)->bitpos, key, klen); @@ -215,7 +218,7 @@ static bool insert_at(struct CBTree *tree, unsigned newbit, const void *key, uns bool cbtree_insert(struct CBTree *tree, void *obj) { const void *key, *old_key; - unsigned newbit, klen, old_klen; + size_t newbit, klen, old_klen; void *old_obj; if (!tree->root) @@ -223,6 +226,8 @@ bool cbtree_insert(struct CBTree *tree, void *obj) /* current key */ klen = get_key(tree, obj, &key); + if (klen > MAX_KEY) + return false; /* nearest key in tree */ old_obj = raw_lookup(tree, key, klen); @@ -241,7 +246,7 @@ bool cbtree_insert(struct CBTree *tree, void *obj) */ /* true -> object was found and removed, false -> not found */ -bool cbtree_delete(struct CBTree *tree, const void *key, unsigned klen) +bool cbtree_delete(struct CBTree *tree, const void *key, size_t klen) { void *obj, *tmp; unsigned bit = 0; diff --git a/usual/cbtree.h b/usual/cbtree.h index 358983c..5eafe42 100644 --- a/usual/cbtree.h +++ b/usual/cbtree.h @@ -24,7 +24,7 @@ #include /** returns length of the key */ -typedef unsigned int (*cbtree_getkey_func)(void *ctx, void *obj, const void **dst_p); +typedef size_t (*cbtree_getkey_func)(void *ctx, void *obj, const void **dst_p); /** walk over tree */ typedef bool (*cbtree_walker_func)(void *ctx, void *obj); @@ -57,14 +57,14 @@ bool cbtree_insert(struct CBTree *tree, void *obj) _MUSTCHECK; * * @returns true if key was found, false otherwise. */ -bool cbtree_delete(struct CBTree *tree, const void *key, unsigned klen); +bool cbtree_delete(struct CBTree *tree, const void *key, size_t klen); /** * Lookup a key. * * @returns object pointer if found, NULL ohterwise */ -void *cbtree_lookup(struct CBTree *tree, const void *key, unsigned klen); +void *cbtree_lookup(struct CBTree *tree, const void *key, size_t klen); /** Walk over tree */ bool cbtree_walk(struct CBTree *tree, cbtree_walker_func cb_func, void *cb_arg); diff --git a/usual/mdict.c b/usual/mdict.c index 6f6857d..a9ce36a 100644 --- a/usual/mdict.c +++ b/usual/mdict.c @@ -20,7 +20,7 @@ struct MDictElem { }; /* hook for CBTree */ -static unsigned int mdict_getkey(void *ctx, void *obj, const void **dst_p) +static size_t mdict_getkey(void *ctx, void *obj, const void **dst_p) { struct MDictElem *el = obj; *dst_p = mbuf_data(&el->key); diff --git a/usual/strpool.c b/usual/strpool.c index 9388ecb..8282cdc 100644 --- a/usual/strpool.c +++ b/usual/strpool.c @@ -31,7 +31,7 @@ struct StrPool { }; /* pass key info to cbtree */ -static unsigned get_key(void *ctx, void *obj, const void **dst_p) +static size_t get_key(void *ctx, void *obj, const void **dst_p) { struct PStr *s = obj; *dst_p = s->str; @@ -84,7 +84,7 @@ int strpool_total(struct StrPool *sp) } /* get new reference to str */ -struct PStr *strpool_get(struct StrPool *sp, const char *str, int len) +struct PStr *strpool_get(struct StrPool *sp, const char *str, ssize_t len) { struct PStr *cstr; bool ok; diff --git a/usual/strpool.h b/usual/strpool.h index b1a8e6f..e308cc9 100644 --- a/usual/strpool.h +++ b/usual/strpool.h @@ -37,10 +37,10 @@ struct StrPool; struct PStr { /** Parent pool */ struct StrPool *pool; + /** String length */ + size_t len; /** Reference count */ int refcnt; - /** String length */ - int len; /** Zero-terminated value */ char str[FLEX_ARRAY]; }; @@ -52,7 +52,7 @@ struct StrPool *strpool_create(CxMem *ca); void strpool_free(struct StrPool *sp); /** Return either existing or new PStr for given value */ -struct PStr *strpool_get(struct StrPool *sp, const char *str, int len); +struct PStr *strpool_get(struct StrPool *sp, const char *str, ssize_t len); /** Increase reference count for existing PStr */ void strpool_incref(struct PStr *str); -- 2.39.5