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.
Signed-off-by: Kristian Hoegsberg <[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 8268034..d71735e 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 305117c..dd43be5 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -404,6 +404,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_find() 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
--
1.5.0.6
Remove all ids from the given idr tree. idr_destroy() only frees up
unused, cached idp_layers, but this function will remove all id mappings
and leave all idp_layers unused.
A typical clean-up sequence for objects stored in an idr tree, will
use idr_for_each() to free all objects, if necessay, then
idr_remove_all() to remove all ids, and idr_destroy() to free
up the cached idr_layers.
Signed-off-by: Kristian Hoegsberg <[email protected]>
---
include/linux/idr.h | 1 +
lib/idr.c | 47 +++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 48 insertions(+), 0 deletions(-)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index d71735e..2d1e105 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -82,6 +82,7 @@ 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_remove_all(struct idr *idp);
void idr_destroy(struct idr *idp);
void idr_init(struct idr *idp);
diff --git a/lib/idr.c b/lib/idr.c
index dd43be5..b4d18d4 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -358,6 +358,53 @@ void idr_remove(struct idr *idp, int id)
EXPORT_SYMBOL(idr_remove);
/**
+ * idr_remove_all - remove all ids from the given idr tree
+ * @idp: idr handle
+ *
+ * idr_destroy() only frees up unused, cached idp_layers, but this
+ * function will remove all id mappings and leave all idp_layers
+ * unused.
+ *
+ * A typical clean-up sequence for objects stored in an idr tree, will
+ * use idr_for_each() to free all objects, if necessay, then
+ * idr_remove_all() to remove all ids, and idr_destroy() to free
+ * up the cached idr_layers.
+ */
+void idr_remove_all(struct idr *idp)
+{
+ 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 && !error) {
+ while (n > IDR_BITS && p) {
+ n -= IDR_BITS;
+ *paa++ = p;
+ p = p->ary[(id >> n) & IDR_MASK];
+ }
+
+ id += 1 << n;
+ while (n < fls(id)) {
+ if (p) {
+ memset(p, 0, sizeof *p);
+ free_layer(idp, p);
+ }
+ n += IDR_BITS;
+ p = *--paa;
+ }
+ }
+ idp->top = NULL;
+ idp->layers = 0;
+}
+EXPORT_SYMBOL(idr_remove_all);
+
+/**
* idr_destroy - release all cached layers within an idr tree
* idp: idr handle
*/
--
1.5.0.6
Kristian H?gsberg wrote:
> /**
> + * idr_for_each - iterate through all stored pointers
...
> + * The caller must serialize idr_find() vs idr_get_new() and idr_remove().
^^^^^^^^
> + */
> +int idr_for_each(struct idr *idp,
> + int (*fn)(int id, void *p, void *data), void *data)
> +{
...must serialize idr_for_each() vs...
--
Stefan Richter
-=====-=-=== -==- ----=
http://arcgraph.de/sr/