*/
#include "stdinc.h"
-#include "sprintf_irc.h"
-#include "tools.h"
-#include "irc_string.h"
+#include "match.h"
#include "client.h"
-#include "memory.h"
#include "setup.h"
-#include "balloc.h"
#include "irc_dictionary.h"
+#include "s_assert.h"
+#include "logger.h"
-static BlockHeap *elem_heap = NULL;
+static rb_bh *elem_heap = NULL;
struct Dictionary
{
*/
struct Dictionary *irc_dictionary_create(DCF compare_cb)
{
- struct Dictionary *dtree = (struct Dictionary *) MyMalloc(sizeof(struct Dictionary));
+ struct Dictionary *dtree = (struct Dictionary *) rb_malloc(sizeof(struct Dictionary));
dtree->compare_cb = compare_cb;
if (!elem_heap)
- elem_heap = BlockHeapCreate(sizeof(struct DictionaryElement), 1024);
+ elem_heap = rb_bh_create(sizeof(struct DictionaryElement), 1024, "dictionary_elem_heap");
return dtree;
}
struct Dictionary *irc_dictionary_create_named(const char *name,
DCF compare_cb)
{
- struct Dictionary *dtree = (struct Dictionary *) MyMalloc(sizeof(struct Dictionary));
+ struct Dictionary *dtree = (struct Dictionary *) rb_malloc(sizeof(struct Dictionary));
dtree->compare_cb = compare_cb;
- DupString(dtree->id, name);
+ dtree->id = rb_strdup(name);
if (!elem_heap)
- elem_heap = BlockHeapCreate(sizeof(struct DictionaryElement), 1024);
+ elem_heap = rb_bh_create(sizeof(struct DictionaryElement), 1024, "dictionary_elem_heap");
return dtree;
}
*
* Retunes the tree, self-optimizing for the element which belongs to key.
*
- * Tuning the tree structure is a very complex operation. Unlike
- * 2-3-4 trees and BTree/BTree+ structures, this structure is a
- * constantly evolving algorithm.
- *
- * Instead of maintaining a balanced tree, we constantly adapt the
- * tree by nominating a new root nearby the most recently looked up
- * or added data. We are constantly retuning ourselves instead of
- * doing massive O(n) rebalance operations as seen in BTrees,
- * and the level of data stored in a tree is dynamic, instead of being
- * held to a restricted design like other trees.
- *
- * Moreover, we are different than a radix/patricia tree, because we
- * don't statically allocate positions. Radix trees have the advantage
- * of not requiring tuning or balancing operations while having the
- * disadvantage of requiring a large amount of memory to store
- * large trees. Our efficiency as far as speed goes is not as
- * fast as a radix tree; but is close to it.
- *
- * The retuning algorithm uses the comparison callback that is
- * passed in the initialization of the tree container. If the
- * comparator returns a value which is less than zero, we push the
- * losing node out of the way, causing it to later be reparented
- * with another node. The winning child of this comparison is always
- * the right-most node.
- *
- * Once we have reached the key which has been targeted, or have reached
- * a deadend, we nominate the nearest node as the new root of the tree.
- * If an exact match has been found, the new root becomes the node which
- * represents key.
- *
- * This results in a tree which can self-optimize for both critical
- * conditions: nodes which are distant and similar and trees which
- * have ordered lookups.
- *
* Inputs:
* - node to begin search from
*
* Side Effects:
* - a new root node is nominated.
*/
-void
+static void
irc_dictionary_retune(struct Dictionary *dict, const char *key)
{
struct DictionaryElement n, *tn, *left, *right, *node;
* Side Effects:
* - a node is linked to the dictionary tree
*/
-void
+static void
irc_dictionary_link(struct Dictionary *dict,
struct DictionaryElement *delem)
{
dict->root->data = delem->data;
dict->count--;
- BlockHeapFree(elem_heap, delem);
+ rb_bh_free(elem_heap, delem);
}
}
}
* Side Effects:
* - the root node is unlinked from the dictionary tree
*/
-void
+static void
irc_dictionary_unlink_root(struct Dictionary *dict)
{
struct DictionaryElement *delem, *nextnode, *parentofnext;
s_assert(dtree != NULL);
- DLINK_FOREACH_SAFE(n, tn, dtree->head)
+ RB_DLINK_FOREACH_SAFE(n, tn, dtree->head)
{
if (destroy_cb != NULL)
(*destroy_cb)(n, privdata);
- BlockHeapFree(elem_heap, n);
+ rb_bh_free(elem_heap, n);
}
- MyFree(dtree);
+ rb_free(dtree);
}
/*
s_assert(dtree != NULL);
- DLINK_FOREACH_SAFE(n, tn, dtree->head)
+ RB_DLINK_FOREACH_SAFE(n, tn, dtree->head)
{
/* delem_t is a subclass of node_t. */
struct DictionaryElement *delem = (struct DictionaryElement *) n;
s_assert(dtree != NULL);
- DLINK_FOREACH_SAFE(n, tn, dtree->head)
+ RB_DLINK_FOREACH_SAFE(n, tn, dtree->head)
{
/* delem_t is a subclass of node_t. */
struct DictionaryElement *delem = (struct DictionaryElement *) n;
if (state->cur == NULL)
{
- ilog(L_MAIN, "irc_dictionary_foreach_next(): called again after iteration finished on dtree<%p>", dtree);
+ ilog(L_MAIN, "irc_dictionary_foreach_next(): called again after iteration finished on dtree<%p>", (void *)dtree);
return;
}
* Side Effects:
* - data is inserted into the DTree.
*/
-struct DictionaryElement *irc_dictionary_add(struct Dictionary *dict, char *key, void *data)
+struct DictionaryElement *irc_dictionary_add(struct Dictionary *dict, const char *key, void *data)
{
struct DictionaryElement *delem;
s_assert(data != NULL);
s_assert(irc_dictionary_find(dict, key) == NULL);
- delem = BlockHeapAlloc(elem_heap);
+ delem = rb_bh_alloc(elem_heap);
delem->key = key;
delem->data = data;
/* TBD: is this needed? --nenolod */
if (delem->key == NULL)
{
- BlockHeapFree(elem_heap, delem);
+ rb_bh_free(elem_heap, delem);
return NULL;
}
data = delem->data;
irc_dictionary_unlink_root(dtree);
- BlockHeapFree(elem_heap, delem);
+ rb_bh_free(elem_heap, delem);
return data;
}
s_assert(dict != NULL);
if (dict->id != NULL)
- snprintf(str, sizeof str, "Dictionary stats for %s (%d)",
+ rb_snprintf(str, sizeof str, "Dictionary stats for %s (%d)",
dict->id, dict->count);
else
- snprintf(str, sizeof str, "Dictionary stats for <%p> (%d)",
- dict, dict->count);
+ rb_snprintf(str, sizeof str, "Dictionary stats for <%p> (%d)",
+ (void *)dict, dict->count);
cb(str, privdata);
maxdepth = 0;
sum = stats_recurse(dict->root, 0, &maxdepth);
- snprintf(str, sizeof str, "Depth sum %d Avg depth %d Max depth %d", sum, sum / dict->count, maxdepth);
+ rb_snprintf(str, sizeof str, "Depth sum %d Avg depth %d Max depth %d", sum, sum / dict->count, maxdepth);
cb(str, privdata);
return;
}