i2c-eg20t: use i2c_add_numbered_adapter to get a fixed bus number
[linux-2.6.git] / lib / radix-tree.c
index 348eaef..dc63d08 100644 (file)
 struct radix_tree_node {
        unsigned int    height;         /* Height from the bottom */
        unsigned int    count;
-       struct rcu_head rcu_head;
+       union {
+               struct radix_tree_node *parent; /* Used when ascending tree */
+               struct rcu_head rcu_head;       /* Used when freeing node */
+       };
        void __rcu      *slots[RADIX_TREE_MAP_SIZE];
        unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
 };
 
-struct radix_tree_path {
-       struct radix_tree_node *node;
-       int offset;
-};
-
 #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
 #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
                                          RADIX_TREE_MAP_SHIFT))
@@ -256,6 +254,7 @@ static inline unsigned long radix_tree_maxindex(unsigned int height)
 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
 {
        struct radix_tree_node *node;
+       struct radix_tree_node *slot;
        unsigned int height;
        int tag;
 
@@ -274,18 +273,23 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
                if (!(node = radix_tree_node_alloc(root)))
                        return -ENOMEM;
 
-               /* Increase the height.  */
-               node->slots[0] = indirect_to_ptr(root->rnode);
-
                /* Propagate the aggregated tag info into the new root */
                for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
                        if (root_tag_get(root, tag))
                                tag_set(node, tag, 0);
                }
 
+               /* Increase the height.  */
                newheight = root->height+1;
                node->height = newheight;
                node->count = 1;
+               node->parent = NULL;
+               slot = root->rnode;
+               if (newheight > 1) {
+                       slot = indirect_to_ptr(slot);
+                       slot->parent = node;
+               }
+               node->slots[0] = slot;
                node = ptr_to_indirect(node);
                rcu_assign_pointer(root->rnode, node);
                root->height = newheight;
@@ -331,6 +335,7 @@ int radix_tree_insert(struct radix_tree_root *root,
                        if (!(slot = radix_tree_node_alloc(root)))
                                return -ENOMEM;
                        slot->height = height;
+                       slot->parent = node;
                        if (node) {
                                rcu_assign_pointer(node->slots[offset], slot);
                                node->count++;
@@ -504,47 +509,41 @@ EXPORT_SYMBOL(radix_tree_tag_set);
 void *radix_tree_tag_clear(struct radix_tree_root *root,
                        unsigned long index, unsigned int tag)
 {
-       /*
-        * The radix tree path needs to be one longer than the maximum path
-        * since the "list" is null terminated.
-        */
-       struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
+       struct radix_tree_node *node = NULL;
        struct radix_tree_node *slot = NULL;
        unsigned int height, shift;
+       int uninitialized_var(offset);
 
        height = root->height;
        if (index > radix_tree_maxindex(height))
                goto out;
 
-       shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
-       pathp->node = NULL;
+       shift = height * RADIX_TREE_MAP_SHIFT;
        slot = indirect_to_ptr(root->rnode);
 
-       while (height > 0) {
-               int offset;
-
+       while (shift) {
                if (slot == NULL)
                        goto out;
 
+               shift -= RADIX_TREE_MAP_SHIFT;
                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
-               pathp[1].offset = offset;
-               pathp[1].node = slot;
+               node = slot;
                slot = slot->slots[offset];
-               pathp++;
-               shift -= RADIX_TREE_MAP_SHIFT;
-               height--;
        }
 
        if (slot == NULL)
                goto out;
 
-       while (pathp->node) {
-               if (!tag_get(pathp->node, tag, pathp->offset))
+       while (node) {
+               if (!tag_get(node, tag, offset))
                        goto out;
-               tag_clear(pathp->node, tag, pathp->offset);
-               if (any_tag_set(pathp->node, tag))
+               tag_clear(node, tag, offset);
+               if (any_tag_set(node, tag))
                        goto out;
-               pathp--;
+
+               index >>= RADIX_TREE_MAP_SHIFT;
+               offset = index & RADIX_TREE_MAP_MASK;
+               node = node->parent;
        }
 
        /* clear the root's tag bit */
@@ -576,7 +575,6 @@ int radix_tree_tag_get(struct radix_tree_root *root,
 {
        unsigned int height, shift;
        struct radix_tree_node *node;
-       int saw_unset_tag = 0;
 
        /* check the root's tag bit */
        if (!root_tag_get(root, tag))
@@ -603,15 +601,10 @@ int radix_tree_tag_get(struct radix_tree_root *root,
                        return 0;
 
                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
-
-               /*
-                * This is just a debug check.  Later, we can bale as soon as
-                * we see an unset tag.
-                */
                if (!tag_get(node, tag, offset))
-                       saw_unset_tag = 1;
+                       return 0;
                if (height == 1)
-                       return !!tag_get(node, tag, offset);
+                       return 1;
                node = rcu_dereference_raw(node->slots[offset]);
                shift -= RADIX_TREE_MAP_SHIFT;
                height--;
@@ -652,8 +645,7 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
                unsigned int iftag, unsigned int settag)
 {
        unsigned int height = root->height;
-       struct radix_tree_path path[height];
-       struct radix_tree_path *pathp = path;
+       struct radix_tree_node *node = NULL;
        struct radix_tree_node *slot;
        unsigned int shift;
        unsigned long tagged = 0;
@@ -677,14 +669,8 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
        shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
        slot = indirect_to_ptr(root->rnode);
 
-       /*
-        * we fill the path from (root->height - 2) to 0, leaving the index at
-        * (root->height - 1) as a terminator. Zero the node in the terminator
-        * so that we can use this to end walk loops back up the path.
-        */
-       path[height - 1].node = NULL;
-
        for (;;) {
+               unsigned long upindex;
                int offset;
 
                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
@@ -692,12 +678,10 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
                        goto next;
                if (!tag_get(slot, iftag, offset))
                        goto next;
-               if (height > 1) {
+               if (shift) {
                        /* Go down one level */
-                       height--;
                        shift -= RADIX_TREE_MAP_SHIFT;
-                       path[height - 1].node = slot;
-                       path[height - 1].offset = offset;
+                       node = slot;
                        slot = slot->slots[offset];
                        continue;
                }
@@ -707,15 +691,27 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
                tag_set(slot, settag, offset);
 
                /* walk back up the path tagging interior nodes */
-               pathp = &path[0];
-               while (pathp->node) {
+               upindex = index;
+               while (node) {
+                       upindex >>= RADIX_TREE_MAP_SHIFT;
+                       offset = upindex & RADIX_TREE_MAP_MASK;
+
                        /* stop if we find a node with the tag already set */
-                       if (tag_get(pathp->node, settag, pathp->offset))
+                       if (tag_get(node, settag, offset))
                                break;
-                       tag_set(pathp->node, settag, pathp->offset);
-                       pathp++;
+                       tag_set(node, settag, offset);
+                       node = node->parent;
                }
 
+               /*
+                * Small optimization: now clear that node pointer.
+                * Since all of this slot's ancestors now have the tag set
+                * from setting it above, we have no further need to walk
+                * back up the tree setting tags, until we update slot to
+                * point to another radix_tree_node.
+                */
+               node = NULL;
+
 next:
                /* Go to next item at level determined by 'shift' */
                index = ((index >> shift) + 1) << shift;
@@ -730,8 +726,7 @@ next:
                         * last_index is guaranteed to be in the tree, what
                         * we do below cannot wander astray.
                         */
-                       slot = path[height - 1].node;
-                       height++;
+                       slot = slot->parent;
                        shift += RADIX_TREE_MAP_SHIFT;
                }
        }
@@ -1203,6 +1198,98 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
 }
 EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
 
+#if defined(CONFIG_SHMEM) && defined(CONFIG_SWAP)
+#include <linux/sched.h> /* for cond_resched() */
+
+/*
+ * This linear search is at present only useful to shmem_unuse_inode().
+ */
+static unsigned long __locate(struct radix_tree_node *slot, void *item,
+                             unsigned long index, unsigned long *found_index)
+{
+       unsigned int shift, height;
+       unsigned long i;
+
+       height = slot->height;
+       shift = (height-1) * RADIX_TREE_MAP_SHIFT;
+
+       for ( ; height > 1; height--) {
+               i = (index >> shift) & RADIX_TREE_MAP_MASK;
+               for (;;) {
+                       if (slot->slots[i] != NULL)
+                               break;
+                       index &= ~((1UL << shift) - 1);
+                       index += 1UL << shift;
+                       if (index == 0)
+                               goto out;       /* 32-bit wraparound */
+                       i++;
+                       if (i == RADIX_TREE_MAP_SIZE)
+                               goto out;
+               }
+
+               shift -= RADIX_TREE_MAP_SHIFT;
+               slot = rcu_dereference_raw(slot->slots[i]);
+               if (slot == NULL)
+                       goto out;
+       }
+
+       /* Bottom level: check items */
+       for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
+               if (slot->slots[i] == item) {
+                       *found_index = index + i;
+                       index = 0;
+                       goto out;
+               }
+       }
+       index += RADIX_TREE_MAP_SIZE;
+out:
+       return index;
+}
+
+/**
+ *     radix_tree_locate_item - search through radix tree for item
+ *     @root:          radix tree root
+ *     @item:          item to be found
+ *
+ *     Returns index where item was found, or -1 if not found.
+ *     Caller must hold no lock (since this time-consuming function needs
+ *     to be preemptible), and must check afterwards if item is still there.
+ */
+unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
+{
+       struct radix_tree_node *node;
+       unsigned long max_index;
+       unsigned long cur_index = 0;
+       unsigned long found_index = -1;
+
+       do {
+               rcu_read_lock();
+               node = rcu_dereference_raw(root->rnode);
+               if (!radix_tree_is_indirect_ptr(node)) {
+                       rcu_read_unlock();
+                       if (node == item)
+                               found_index = 0;
+                       break;
+               }
+
+               node = indirect_to_ptr(node);
+               max_index = radix_tree_maxindex(node->height);
+               if (cur_index > max_index)
+                       break;
+
+               cur_index = __locate(node, item, cur_index, &found_index);
+               rcu_read_unlock();
+               cond_resched();
+       } while (cur_index != 0 && cur_index <= max_index);
+
+       return found_index;
+}
+#else
+unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
+{
+       return -1;
+}
+#endif /* CONFIG_SHMEM && CONFIG_SWAP */
 
 /**
  *     radix_tree_shrink    -    shrink height of a radix tree to minimal
@@ -1213,7 +1300,7 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
        /* try to shrink tree height */
        while (root->height > 0) {
                struct radix_tree_node *to_free = root->rnode;
-               void *newptr;
+               struct radix_tree_node *slot;
 
                BUG_ON(!radix_tree_is_indirect_ptr(to_free));
                to_free = indirect_to_ptr(to_free);
@@ -1234,10 +1321,12 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
                 * (to_free->slots[0]), it will be safe to dereference the new
                 * one (root->rnode) as far as dependent read barriers go.
                 */
-               newptr = to_free->slots[0];
-               if (root->height > 1)
-                       newptr = ptr_to_indirect(newptr);
-               root->rnode = newptr;
+               slot = to_free->slots[0];
+               if (root->height > 1) {
+                       slot->parent = NULL;
+                       slot = ptr_to_indirect(slot);
+               }
+               root->rnode = slot;
                root->height--;
 
                /*
@@ -1277,16 +1366,12 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
  */
 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
 {
-       /*
-        * The radix tree path needs to be one longer than the maximum path
-        * since the "list" is null terminated.
-        */
-       struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
+       struct radix_tree_node *node = NULL;
        struct radix_tree_node *slot = NULL;
        struct radix_tree_node *to_free;
        unsigned int height, shift;
        int tag;
-       int offset;
+       int uninitialized_var(offset);
 
        height = root->height;
        if (index > radix_tree_maxindex(height))
@@ -1299,39 +1384,35 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
                goto out;
        }
        slot = indirect_to_ptr(slot);
-
-       shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
-       pathp->node = NULL;
+       shift = height * RADIX_TREE_MAP_SHIFT;
 
        do {
                if (slot == NULL)
                        goto out;
 
-               pathp++;
+               shift -= RADIX_TREE_MAP_SHIFT;
                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
-               pathp->offset = offset;
-               pathp->node = slot;
+               node = slot;
                slot = slot->slots[offset];
-               shift -= RADIX_TREE_MAP_SHIFT;
-               height--;
-       } while (height > 0);
+       } while (shift);
 
        if (slot == NULL)
                goto out;
 
        /*
-        * Clear all tags associated with the just-deleted item
+        * Clear all tags associated with the item to be deleted.
+        * This way of doing it would be inefficient, but seldom is any set.
         */
        for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
-               if (tag_get(pathp->node, tag, pathp->offset))
+               if (tag_get(node, tag, offset))
                        radix_tree_tag_clear(root, index, tag);
        }
 
        to_free = NULL;
        /* Now free the nodes we do not need anymore */
-       while (pathp->node) {
-               pathp->node->slots[pathp->offset] = NULL;
-               pathp->node->count--;
+       while (node) {
+               node->slots[offset] = NULL;
+               node->count--;
                /*
                 * Queue the node for deferred freeing after the
                 * last reference to it disappears (set NULL, above).
@@ -1339,17 +1420,20 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
                if (to_free)
                        radix_tree_node_free(to_free);
 
-               if (pathp->node->count) {
-                       if (pathp->node == indirect_to_ptr(root->rnode))
+               if (node->count) {
+                       if (node == indirect_to_ptr(root->rnode))
                                radix_tree_shrink(root);
                        goto out;
                }
 
                /* Node with zero slots in use so free it */
-               to_free = pathp->node;
-               pathp--;
+               to_free = node;
 
+               index >>= RADIX_TREE_MAP_SHIFT;
+               offset = index & RADIX_TREE_MAP_MASK;
+               node = node->parent;
        }
+
        root_tag_clear_all(root);
        root->height = 0;
        root->rnode = NULL;