diff options
Diffstat (limited to 'examples/redis-unstable/src/rax.h')
| -rw-r--r-- | examples/redis-unstable/src/rax.h | 204 |
1 files changed, 0 insertions, 204 deletions
diff --git a/examples/redis-unstable/src/rax.h b/examples/redis-unstable/src/rax.h deleted file mode 100644 index db8c463..0000000 --- a/examples/redis-unstable/src/rax.h +++ /dev/null @@ -1,204 +0,0 @@ -/* Rax -- A radix tree implementation. - * - * Copyright (c) 2017-Present, Redis Ltd. - * All rights reserved. - * - * Licensed under your choice of (a) the Redis Source Available License 2.0 - * (RSALv2); or (b) the Server Side Public License v1 (SSPLv1); or (c) the - * GNU Affero General Public License v3 (AGPLv3). - */ - -#ifndef RAX_H -#define RAX_H - -#include <stdint.h> - -/* Representation of a radix tree as implemented in this file, that contains - * the strings "foo", "foobar" and "footer" after the insertion of each - * word. When the node represents a key inside the radix tree, we write it - * between [], otherwise it is written between (). - * - * This is the vanilla representation: - * - * (f) "" - * \ - * (o) "f" - * \ - * (o) "fo" - * \ - * [t b] "foo" - * / \ - * "foot" (e) (a) "foob" - * / \ - * "foote" (r) (r) "fooba" - * / \ - * "footer" [] [] "foobar" - * - * However, this implementation implements a very common optimization where - * successive nodes having a single child are "compressed" into the node - * itself as a string of characters, each representing a next-level child, - * and only the link to the node representing the last character node is - * provided inside the representation. So the above representation is turned - * into: - * - * ["foo"] "" - * | - * [t b] "foo" - * / \ - * "foot" ("er") ("ar") "foob" - * / \ - * "footer" [] [] "foobar" - * - * However this optimization makes the implementation a bit more complex. - * For instance if a key "first" is added in the above radix tree, a - * "node splitting" operation is needed, since the "foo" prefix is no longer - * composed of nodes having a single child one after the other. This is the - * above tree and the resulting node splitting after this event happens: - * - * - * (f) "" - * / - * (i o) "f" - * / \ - * "firs" ("rst") (o) "fo" - * / \ - * "first" [] [t b] "foo" - * / \ - * "foot" ("er") ("ar") "foob" - * / \ - * "footer" [] [] "foobar" - * - * Similarly after deletion, if a new chain of nodes having a single child - * is created (the chain must also not include nodes that represent keys), - * it must be compressed back into a single node. - * - */ - -#define RAX_NODE_MAX_SIZE ((1<<29)-1) -typedef struct raxNode { - uint32_t iskey:1; /* Does this node contain a key? */ - uint32_t isnull:1; /* Associated value is NULL (don't store it). */ - uint32_t iscompr:1; /* Node is compressed. */ - uint32_t size:29; /* Number of children, or compressed string len. */ - /* Data layout is as follows: - * - * If node is not compressed we have 'size' bytes, one for each children - * character, and 'size' raxNode pointers, point to each child node. - * Note how the character is not stored in the children but in the - * edge of the parents: - * - * [header iscompr=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?) - * - * if node is compressed (iscompr bit is 1) the node has 1 child. - * In that case the 'size' bytes of the string stored immediately at - * the start of the data section, represent a sequence of successive - * nodes linked one after the other, for which only the last one in - * the sequence is actually represented as a node, and pointed to by - * the current compressed node. - * - * [header iscompr=1][xyz][z-ptr](value-ptr?) - * - * Both compressed and not compressed nodes can represent a key - * with associated data in the radix tree at any level (not just terminal - * nodes). - * - * If the node has an associated key (iskey=1) and is not NULL - * (isnull=0), then after the raxNode pointers pointing to the - * children, an additional value pointer is present (as you can see - * in the representation above as "value-ptr" field). - */ - unsigned char data[]; -} raxNode; - -typedef struct rax { - raxNode *head; - uint64_t numele; - uint64_t numnodes; - size_t *alloc_size; - void *metadata[]; -} rax; - -/* Stack data structure used by raxLowWalk() in order to, optionally, return - * a list of parent nodes to the caller. The nodes do not have a "parent" - * field for space concerns, so we use the auxiliary stack when needed. */ -#define RAX_STACK_STATIC_ITEMS 32 -typedef struct raxStack { - void **stack; /* Points to static_items or an heap allocated array. */ - size_t items, maxitems; /* Number of items contained and total space. */ - /* Up to RAXSTACK_STACK_ITEMS items we avoid to allocate on the heap - * and use this static array of pointers instead. */ - void *static_items[RAX_STACK_STATIC_ITEMS]; - int oom; /* True if pushing into this stack failed for OOM at some point. */ -} raxStack; - -/* Optional callback used for iterators and be notified on each rax node, - * including nodes not representing keys. If the callback returns true - * the callback changed the node pointer in the iterator structure, and the - * iterator implementation will have to replace the pointer in the radix tree - * internals. This allows the callback to reallocate the node to perform - * very special operations, normally not needed by normal applications. - * - * This callback is used to perform very low level analysis of the radix tree - * structure, scanning each possible node (but the root node), or in order to - * reallocate the nodes to reduce the allocation fragmentation (this is the - * Redis application for this callback). - * - * This is currently only supported in forward iterations (raxNext) */ -typedef int (*raxNodeCallback)(raxNode **noderef, void *privdata); - -/* Radix tree iterator state is encapsulated into this data structure. */ -#define RAX_ITER_STATIC_LEN 128 -#define RAX_ITER_JUST_SEEKED (1<<0) /* Iterator was just seeked. Return current - element for the first iteration and - clear the flag. */ -#define RAX_ITER_EOF (1<<1) /* End of iteration reached. */ -#define RAX_ITER_SAFE (1<<2) /* Safe iterator, allows operations while - iterating. But it is slower. */ -typedef struct raxIterator { - int flags; - rax *rt; /* Radix tree we are iterating. */ - unsigned char *key; /* The current string. */ - void *data; /* Data associated to this key. */ - size_t key_len; /* Current key length. */ - size_t key_max; /* Max key len the current key buffer can hold. */ - unsigned char key_static_string[RAX_ITER_STATIC_LEN]; - raxNode *node; /* Current node. Only for unsafe iteration. */ - raxStack stack; /* Stack used for unsafe iteration. */ - raxNodeCallback node_cb; /* Optional node callback. Normally set to NULL. */ - void *privdata; /* Optional private data for node callback. */ -} raxIterator; - -/* Exported API. */ -rax *raxNew(void); -rax *raxNewWithMetadata(int metaSize, size_t *alloc_size); -int raxInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old); -int raxTryInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old); -int raxRemove(rax *rax, unsigned char *s, size_t len, void **old); -int raxFind(rax *rax, unsigned char *s, size_t len, void **value); -void raxFree(rax *rax); -void raxFreeWithCallback(rax *rax, void (*free_callback)(void*)); -void raxFreeWithCbAndContext(rax *rax, - void (*free_callback)(void *item, void *ctx), - void *ctx); -void raxStart(raxIterator *it, rax *rt); -int raxSeek(raxIterator *it, const char *op, unsigned char *ele, size_t len); -int raxNext(raxIterator *it); -int raxPrev(raxIterator *it); -int raxRandomWalk(raxIterator *it, size_t steps); -int raxCompare(raxIterator *iter, const char *op, unsigned char *key, size_t key_len); -void raxStop(raxIterator *it); -int raxEOF(raxIterator *it); -void raxShow(rax *rax); -uint64_t raxSize(rax *rax); -unsigned long raxTouch(raxNode *n); -void raxSetDebugMsg(int onoff); - -/* Internal API. May be used by the node callback in order to access rax nodes - * in a low level way, so this function is exported as well. */ -void raxSetData(raxNode *n, void *data); - -#ifdef REDIS_TEST -int raxTest(int argc, char *argv[], int flags); -#endif - -#endif |