aboutsummaryrefslogtreecommitdiffstats
path: root/lib/idr.c
diff options
context:
space:
mode:
authorKristian Hoegsberg <krh@redhat.com>2007-07-16 02:37:24 -0400
committerLinus Torvalds <torvalds@woody.linux-foundation.org>2007-07-16 12:05:34 -0400
commit96d7fa421e6424ad9ef6d1d039375dc2edb63fe8 (patch)
treeba8a8200bda4576e1e4dcce2ff27a7a7a94723a2 /lib/idr.c
parentde7d4f0e1172a72277d660fa0be59654ea02bed0 (diff)
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. [akpm@linux-foundation.org: fix comment] Signed-off-by: Kristian Hoegsberg <krh@redhat.com> Cc: Tejun Heo <htejun@gmail.com> Cc: Dave Airlie <airlied@linux.ie> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib/idr.c')
-rw-r--r--lib/idr.c55
1 files changed, 55 insertions, 0 deletions
diff --git a/lib/idr.c b/lib/idr.c
index b98f01a2eb94..d29da6159dae 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -437,6 +437,61 @@ void *idr_find(struct idr *idp, int id)
437EXPORT_SYMBOL(idr_find); 437EXPORT_SYMBOL(idr_find);
438 438
439/** 439/**
440 * idr_for_each - iterate through all stored pointers
441 * @idp: idr handle
442 * @fn: function to be called for each pointer
443 * @data: data passed back to callback function
444 *
445 * Iterate over the pointers registered with the given idr. The
446 * callback function will be called for each pointer currently
447 * registered, passing the id, the pointer and the data pointer passed
448 * to this function. It is not safe to modify the idr tree while in
449 * the callback, so functions such as idr_get_new and idr_remove are
450 * not allowed.
451 *
452 * We check the return of @fn each time. If it returns anything other
453 * than 0, we break out and return that value.
454 *
455 * The caller must serialize idr_for_each() vs idr_get_new() and idr_remove().
456 */
457int idr_for_each(struct idr *idp,
458 int (*fn)(int id, void *p, void *data), void *data)
459{
460 int n, id, max, error = 0;
461 struct idr_layer *p;
462 struct idr_layer *pa[MAX_LEVEL];
463 struct idr_layer **paa = &pa[0];
464
465 n = idp->layers * IDR_BITS;
466 p = idp->top;
467 max = 1 << n;
468
469 id = 0;
470 while (id < max) {
471 while (n > 0 && p) {
472 n -= IDR_BITS;
473 *paa++ = p;
474 p = p->ary[(id >> n) & IDR_MASK];
475 }
476
477 if (p) {
478 error = fn(id, (void *)p, data);
479 if (error)
480 break;
481 }
482
483 id += 1 << n;
484 while (n < fls(id)) {
485 n += IDR_BITS;
486 p = *--paa;
487 }
488 }
489
490 return error;
491}
492EXPORT_SYMBOL(idr_for_each);
493
494/**
440 * idr_replace - replace pointer for given id 495 * idr_replace - replace pointer for given id
441 * @idp: idr handle 496 * @idp: idr handle
442 * @ptr: pointer you want associated with the id 497 * @ptr: pointer you want associated with the id