X-Git-Url: https://jfr.im/git/irc/rqf/shadowircd.git/blobdiff_plain/c98390004f4f14cd8215302d77313f81e2546e22..99c780941a2cb1ed5f8238093c26b5352a150020:/src/irc_dictionary.c

diff --git a/src/irc_dictionary.c b/src/irc_dictionary.c
index b393e54..89a0a7b 100644
--- a/src/irc_dictionary.c
+++ b/src/irc_dictionary.c
@@ -23,16 +23,12 @@
  */
 
 #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"
 
-static BlockHeap *elem_heap = NULL;
+static rb_bh *elem_heap = NULL;
 
 struct Dictionary
 {
@@ -60,12 +56,12 @@ 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;
 }
@@ -90,13 +86,13 @@ struct Dictionary *irc_dictionary_create(DCF compare_cb)
 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;
 }
@@ -198,40 +194,6 @@ irc_dictionary_get_linear_index(struct Dictionary *dict, const char *key)
  *
  * 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
  *
@@ -241,7 +203,7 @@ irc_dictionary_get_linear_index(struct Dictionary *dict, const char *key)
  * 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;
@@ -340,7 +302,7 @@ irc_dictionary_retune(struct Dictionary *dict, const char *key)
  * Side Effects:
  *     - a node is linked to the dictionary tree
  */
-void
+static void
 irc_dictionary_link(struct Dictionary *dict,
 	struct DictionaryElement *delem)
 {
@@ -401,7 +363,7 @@ irc_dictionary_link(struct Dictionary *dict,
 			dict->root->data = delem->data;
 			dict->count--;
 
-			BlockHeapFree(elem_heap, delem);
+			rb_bh_free(elem_heap, delem);
 		}
 	}
 }
@@ -420,7 +382,7 @@ irc_dictionary_link(struct Dictionary *dict,
  * 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;
@@ -505,15 +467,15 @@ void irc_dictionary_destroy(struct Dictionary *dtree,
 
 	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);
 }
 
 /*
@@ -542,7 +504,7 @@ void irc_dictionary_foreach(struct Dictionary *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;
@@ -580,7 +542,7 @@ void *irc_dictionary_search(struct Dictionary *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;
@@ -682,7 +644,7 @@ void irc_dictionary_foreach_next(struct Dictionary *dtree,
 
 	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;
 	}
 
@@ -741,7 +703,7 @@ struct DictionaryElement *irc_dictionary_find(struct Dictionary *dict, const cha
  * 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;
 
@@ -750,14 +712,14 @@ struct DictionaryElement *irc_dictionary_add(struct Dictionary *dict, char *key,
 	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;
 	}
 
@@ -796,7 +758,7 @@ void *irc_dictionary_delete(struct Dictionary *dtree, const char *key)
 	data = delem->data;
 
 	irc_dictionary_unlink_root(dtree);
-	BlockHeapFree(elem_heap, delem);	
+	rb_bh_free(elem_heap, delem);	
 
 	return data;
 }
@@ -888,15 +850,15 @@ void irc_dictionary_stats(struct Dictionary *dict, void (*cb)(const char *line,
 	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;
 }