Gitweb:     
http://git.kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=96d7fa421e6424ad9ef6d1d039375dc2edb63fe8
Commit:     96d7fa421e6424ad9ef6d1d039375dc2edb63fe8
Parent:     de7d4f0e1172a72277d660fa0be59654ea02bed0
Author:     Kristian Hoegsberg <[EMAIL PROTECTED]>
AuthorDate: Sun Jul 15 23:37:24 2007 -0700
Committer:  Linus Torvalds <[EMAIL PROTECTED]>
CommitDate: Mon Jul 16 09:05:34 2007 -0700

    lib: add idr_for_each()
    
    This patch adds an iterator function for the idr data structure.  Compared
    to just iterating through the idr with an integer and idr_find, this
    iterator is (almost, but not quite) linear in the number of elements, as
    opposed to the number of integers in the range covered by the idr.  This
    makes a difference for sparse idrs, but more importantly, it's a nicer way
    to iterate through the elements.
    
    The drm subsystem is moving to idr for tracking contexts and drawables, and
    with this change, we can use the idr exclusively for tracking these
    resources.
    
    [EMAIL PROTECTED]: fix comment]
    Signed-off-by: Kristian Hoegsberg <[EMAIL PROTECTED]>
    Cc: Tejun Heo <[EMAIL PROTECTED]>
    Cc: Dave Airlie <[EMAIL PROTECTED]>
    Signed-off-by: Andrew Morton <[EMAIL PROTECTED]>
    Signed-off-by: Linus Torvalds <[EMAIL PROTECTED]>
---
 include/linux/idr.h |    2 +
 lib/idr.c           |   55 +++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 57 insertions(+), 0 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index 915572f..8442c0b 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -78,6 +78,8 @@ void *idr_find(struct idr *idp, int id);
 int idr_pre_get(struct idr *idp, gfp_t gfp_mask);
 int idr_get_new(struct idr *idp, void *ptr, int *id);
 int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);
+int idr_for_each(struct idr *idp,
+                int (*fn)(int id, void *p, void *data), void *data);
 void *idr_replace(struct idr *idp, void *ptr, int id);
 void idr_remove(struct idr *idp, int id);
 void idr_destroy(struct idr *idp);
diff --git a/lib/idr.c b/lib/idr.c
index b98f01a..d29da61 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -437,6 +437,61 @@ void *idr_find(struct idr *idp, int id)
 EXPORT_SYMBOL(idr_find);
 
 /**
+ * idr_for_each - iterate through all stored pointers
+ * @idp: idr handle
+ * @fn: function to be called for each pointer
+ * @data: data passed back to callback function
+ *
+ * Iterate over the pointers registered with the given idr.  The
+ * callback function will be called for each pointer currently
+ * registered, passing the id, the pointer and the data pointer passed
+ * to this function.  It is not safe to modify the idr tree while in
+ * the callback, so functions such as idr_get_new and idr_remove are
+ * not allowed.
+ *
+ * We check the return of @fn each time. If it returns anything other
+ * than 0, we break out and return that value.
+ *
+ * The caller must serialize idr_for_each() vs idr_get_new() and idr_remove().
+ */
+int idr_for_each(struct idr *idp,
+                int (*fn)(int id, void *p, void *data), void *data)
+{
+       int n, id, max, error = 0;
+       struct idr_layer *p;
+       struct idr_layer *pa[MAX_LEVEL];
+       struct idr_layer **paa = &pa[0];
+
+       n = idp->layers * IDR_BITS;
+       p = idp->top;
+       max = 1 << n;
+
+       id = 0;
+       while (id < max) {
+               while (n > 0 && p) {
+                       n -= IDR_BITS;
+                       *paa++ = p;
+                       p = p->ary[(id >> n) & IDR_MASK];
+               }
+
+               if (p) {
+                       error = fn(id, (void *)p, data);
+                       if (error)
+                               break;
+               }
+
+               id += 1 << n;
+               while (n < fls(id)) {
+                       n += IDR_BITS;
+                       p = *--paa;
+               }
+       }
+
+       return error;
+}
+EXPORT_SYMBOL(idr_for_each);
+
+/**
  * idr_replace - replace pointer for given id
  * @idp: idr handle
  * @ptr: pointer you want associated with the id
-
To unsubscribe from this list: send the line "unsubscribe git-commits-head" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to