Radix change to return the slot address
authorBarret Rhoden <brho@cs.berkeley.edu>
Tue, 4 Feb 2014 22:19:16 +0000 (14:19 -0800)
committerBarret Rhoden <brho@cs.berkeley.edu>
Sun, 9 Feb 2014 07:22:59 +0000 (23:22 -0800)
Needed for the upcoming page cache changes.

kern/include/radix.h
kern/src/pagemap.c
kern/src/radix.c
kern/src/testing.c

index 1fd3bea..9629742 100644 (file)
@@ -45,7 +45,8 @@ void radix_tree_init(struct radix_tree *tree);        /* inits one tree */
 void radix_tree_destroy(struct radix_tree *tree);
 
 /* Item management */
-int radix_insert(struct radix_tree *tree, unsigned long key, void *item);
+int radix_insert(struct radix_tree *tree, unsigned long key, void *item,
+                 void ***slot_p);
 void *radix_delete(struct radix_tree *tree, unsigned long key);
 void *radix_lookup(struct radix_tree *tree, unsigned long key);
 void **radix_lookup_slot(struct radix_tree *tree, unsigned long key);
index 62e43bf..524bb29 100644 (file)
@@ -64,7 +64,7 @@ static int pm_insert_page(struct page_map *pm, unsigned long index,
 {
        int error = 0;
        spin_lock(&pm->pm_tree_lock);
-       error = radix_insert(&pm->pm_tree, index, page);
+       error = radix_insert(&pm->pm_tree, index, page, 0);
        if (!error) {
                page_incref(page);
                /* setting PG_BUF since we know it'll be used for IO later... */
index 7543943..9434dc3 100644 (file)
@@ -43,8 +43,10 @@ void radix_tree_destroy(struct radix_tree *tree)
 }
 
 /* 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;
@@ -82,6 +84,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;
 }
 
index 44d9f69..cd2a869 100644 (file)
@@ -1197,15 +1197,15 @@ void test_radix_tree(void)
        struct radix_tree *tree = &real_tree;
        void *retval;
 
-       if (radix_insert(tree, 0, (void*)0xdeadbeef))
+       if (radix_insert(tree, 0, (void*)0xdeadbeef, 0))
                printk("Failed to insert at 0!\n");
        radix_delete(tree, 0);
-       if (radix_insert(tree, 0, (void*)0xdeadbeef))
+       if (radix_insert(tree, 0, (void*)0xdeadbeef, 0))
                printk("Failed to re-insert at 0!\n");
 
-       if (radix_insert(tree, 3, (void*)0xdeadbeef))
+       if (radix_insert(tree, 3, (void*)0xdeadbeef, 0))
                printk("Failed to insert first!\n");
-       radix_insert(tree, 4, (void*)0x04040404);
+       radix_insert(tree, 4, (void*)0x04040404, 0);
        assert((void*)0xdeadbeef == radix_lookup(tree, 3));
        for (int i = 5; i < 100; i++)
                if ((retval = radix_lookup(tree, i))) {
@@ -1214,13 +1214,13 @@ void test_radix_tree(void)
                        print_radix_tree(tree);
                        monitor(0);
                }
-       if (radix_insert(tree, 65, (void*)0xcafebabe))
+       if (radix_insert(tree, 65, (void*)0xcafebabe, 0))
                printk("Failed to insert a two-tier!\n");
-       if (!radix_insert(tree, 4, (void*)0x03030303))
+       if (!radix_insert(tree, 4, (void*)0x03030303, 0))
                printk("Should not let us reinsert\n");
-       if (radix_insert(tree, 4095, (void*)0x4095))
+       if (radix_insert(tree, 4095, (void*)0x4095, 0))
                printk("Failed to insert a two-tier boundary!\n");
-       if (radix_insert(tree, 4096, (void*)0x4096))
+       if (radix_insert(tree, 4096, (void*)0x4096, 0))
                printk("Failed to insert a three-tier!\n");
        //print_radix_tree(tree);
        radix_delete(tree, 65);