net: Allow connectionless convs to auto bind

[akaros.git] / kern / src / radix.c

diff --git a/kern/src/radix.c b/kern/src/radix.c
index 3324c30..e109cfa 100644 (file)
--- a/kern/src/radix.c
+++ b/kern/src/radix.c
@@ -19,8 +19,10 @@ static void __radix_remove_slot(struct radix_node *r_node, struct radix_node **s
 /* Initializes the radix tree system, mostly just builds the kcache */
 void radix_init(void)
 {
-       radix_kcache = kmem_cache_create("radix_nodes", sizeof(struct radix_node),
-                                        __alignof__(struct radix_node), 0, 0, 0);
+       radix_kcache = kmem_cache_create("radix_nodes",
+                                        sizeof(struct radix_node),
+                                        __alignof__(struct radix_node), 0,
+                                        NULL, 0, 0, NULL);
 }
 
 /* Initializes a tree dynamically */
@@ -37,13 +39,18 @@ void radix_tree_init(struct radix_tree *tree)
  * slot. */
 void radix_tree_destroy(struct radix_tree *tree)
 {
+       /* Currently, we may have a root node, even if all the elements were removed
+        */
        panic("Not implemented");
 }
 
 /* Attempts to insert an item in the tree at the given key.  ENOMEM if we ran
- * out of memory, EEXIST if an item is already in the tree. */
-int radix_insert(struct radix_tree *tree, unsigned long key, void *item)
+ * out of memory, EEXIST if an item is already in the tree.  On success, will
+ * also return the slot pointer, if requested. */
+int radix_insert(struct radix_tree *tree, unsigned long key, void *item,
+                 void ***slot_p)
 {
+       printd("RADIX: insert %p at %d\n", item, key);
        struct radix_node *r_node;
        void **slot;
        /* Is the tree tall enough?  if not, it needs to grow a level.  This will
@@ -62,12 +69,14 @@ int radix_insert(struct radix_tree *tree, unsigned long key, void *item)
                } else {
                        /* if there was no root before, we're both the root and a leaf */
                        r_node->leaf = TRUE;
+                       r_node->parent = 0;
                }
                tree->root = r_node;
                r_node->my_slot = &tree->root;
                tree->depth++;
-               tree->upper_bound = 1 << (LOG_RNODE_SLOTS * tree->depth);
+               tree->upper_bound = 1ULL << (LOG_RNODE_SLOTS * tree->depth);
        }
+       assert(tree->root);
        /* the tree now thinks it is tall enough, so find the last node, insert in
         * it, etc */
        r_node = __radix_lookup_node(tree, key, TRUE);
@@ -77,6 +86,8 @@ int radix_insert(struct radix_tree *tree, unsigned long key, void *item)
                return -EEXIST;
        *slot = item;
        r_node->num_items++;
+       if (slot_p)
+               *slot_p = slot;
        return 0;
 }
 
@@ -87,7 +98,10 @@ static void __radix_remove_slot(struct radix_node *r_node, struct radix_node **s
        assert(*slot);          /* make sure there is something there */
        *slot = 0;
        r_node->num_items--;
-       if (!r_node->num_items) {
+       /* this check excludes the root, but the if else handles it.  For now, once
+        * we have a root, we'll always keep it (will need some changing in
+        * radix_insert() */
+       if (!r_node->num_items && r_node->parent) {
                if (r_node->parent)
                        __radix_remove_slot(r_node->parent, r_node->my_slot);
                else                    /* we're the last node, attached to the actual tree */
@@ -102,6 +116,7 @@ static void __radix_remove_slot(struct radix_node *r_node, struct radix_node **s
  * won't "shrink". */
 void *radix_delete(struct radix_tree *tree, unsigned long key)
 {
+       printd("RADIX: delete %d\n", key);
        void **slot;
        void *retval;
        struct radix_node *r_node = __radix_lookup_node(tree, key, 0);
@@ -110,7 +125,7 @@ void *radix_delete(struct radix_tree *tree, unsigned long key)
        slot = &r_node->items[key & (NR_RNODE_SLOTS - 1)];
        retval = *slot;
        if (retval) {
-               __radix_remove_slot(r_node, (struct radix_node**)slot); 
+               __radix_remove_slot(r_node, (struct radix_node**)slot);
        } else {
                /* it's okay to delete an empty, but i want to know about it for now */
                warn("Tried to remove a non-existant item from a radix tree!");
@@ -121,6 +136,7 @@ void *radix_delete(struct radix_tree *tree, unsigned long key)
 /* Returns the item for a given key.  0 means no item, etc. */
 void *radix_lookup(struct radix_tree *tree, unsigned long key)
 {
+       printd("RADIX: lookup %d\n", key);
        void **slot = radix_lookup_slot(tree, key);
        if (!slot)
                return 0;
@@ -139,6 +155,7 @@ void *radix_lookup(struct radix_tree *tree, unsigned long key)
 static struct radix_node *__radix_lookup_node(struct radix_tree *tree,
                                               unsigned long key, bool extend)
 {
+       printd("RADIX: lookup_node %d, %d\n", key, extend);
        unsigned long idx;
        struct radix_node *child_node, *r_node = tree->root;
        if (key >= tree->upper_bound) {
@@ -178,6 +195,7 @@ static struct radix_node *__radix_lookup_node(struct radix_tree *tree,
  * etc */
 void **radix_lookup_slot(struct radix_tree *tree, unsigned long key)
 {
+       printd("RADIX: lookup slot %d\n", key);
        struct radix_node *r_node = __radix_lookup_node(tree, key, FALSE);
        if (!r_node)
                return 0;
@@ -239,7 +257,7 @@ int radix_tag_gang_lookup(struct radix_tree *tree, void **results,
 
 void print_radix_tree(struct radix_tree *tree)
 {
-       printk("Tree %08p, Depth: %d, Bound: %d\n", tree, tree->depth,
+       printk("Tree %p, Depth: %d, Bound: %d\n", tree, tree->depth,
               tree->upper_bound);
 
        void print_rnode(struct radix_node *r_node, int depth)
@@ -249,14 +267,14 @@ void print_radix_tree(struct radix_tree *tree)
                char buf[32] = {0};
                for (int i = 0; i < depth; i++)
                        buf[i] = '\t';
-               printk("%sRnode %08p, parent %08p, myslot %08p, %d items, leaf? %d\n",
+               printk("%sRnode %p, parent %p, myslot %p, %d items, leaf? %d\n",
                       buf, r_node, r_node->parent, r_node->my_slot, r_node->num_items,
                       r_node->leaf);
                for (int i = 0; i < NR_RNODE_SLOTS; i++) {
                        if (!r_node->items[i])
                                continue;
                        if (r_node->leaf)
-                               printk("\t%sRnode Item %d: %08p\n", buf, i, r_node->items[i]);
+                               printk("\t%sRnode Item %d: %p\n", buf, i, r_node->items[i]);
                        else
                                print_rnode(r_node->items[i], depth + 1);
                }