idr: Integer ID management library
authorVishesh Yadav <vishesh3y@gmail.com>
Thu, 23 Aug 2012 19:28:27 +0000 (00:58 +0530)
committerFran├žois Tigeot <ftigeot@wolfpond.org>
Tue, 23 Oct 2012 12:56:02 +0000 (14:56 +0200)
Derived from fd code. Almost compatible with Linux. Differences
mentioned in man page.

share/man/man9/Makefile
share/man/man9/idr.9 [new file with mode: 0644]
sys/conf/files
sys/libkern/idr.c [new file with mode: 0644]
sys/sys/idr.h [new file with mode: 0644]

index e0251e8..91f57fc 100644 (file)
@@ -86,6 +86,7 @@ MAN=  accept_filter.9 \
        hash.9 \
        hashinit.9 \
        hexdump.9 \
+       idr.9 \
        ieee80211.9 \
        ieee80211_beacon.9 \
        ieee80211_bmiss.9 \
@@ -469,6 +470,17 @@ MLINKS+=hashinit.9 hashdestroy.9 \
        hashinit.9 hashinit_ext.9 \
        hashinit.9 phashinit.9 \
        hashinit.9 phashinit_ext.9
+MLINKS+=idr.9 idr_destroy.9 \
+       idr.9 idr_find.9 \
+       idr.9 idr_for_each.9 \
+       idr.9 idr_get_new.9 \
+       idr.9 idr_get_new_above.9 \
+       idr.9 idr_init.9 \
+       idr.9 idr_init1.9 \
+       idr.9 idr_pre_get.9 \
+       idr.9 idr_remove.9 \
+       idr.9 idr_remove_all.9 \
+       idr.9 idr_replace.9
 MLINKS+=ioctl.9 _IOR.9 \
        ioctl.9 _IOW.9 \
        ioctl.9 _IOWR.9 \
diff --git a/share/man/man9/idr.9 b/share/man/man9/idr.9
new file mode 100644 (file)
index 0000000..01dc979
--- /dev/null
@@ -0,0 +1,138 @@
+.\" Copyright (c) 2012 Vishesh Yadav
+.\" All rights reserved.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\"    notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\"    notice, this list of conditions and the following disclaimer in the
+.\"    documentation and/or other materials provided with the distribution.
+.\" 3. The name of the author may not be used to endorse or promote products
+.\"    derived from this software without specific prior written permission.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+.\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+.\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+.\"
+.\"
+.Dd August 15, 2012
+.Dt IDR 9
+.Os
+.Sh NAME
+.Nm idr ,
+.Nm idr_destroy ,
+.Nm idr_find ,
+.Nm idr_for_each ,
+.Nm idr_get_new ,
+.Nm idr_get_new_above ,
+.Nm idr_init ,
+.Nm idr_init1 ,
+.Nm idr_pre_get ,
+.Nm idr_remove ,
+.Nm idr_remove_all ,
+.Nm idr_replace
+.Nd Integer ID management library
+.Sh SYNOPSIS
+.In sys/idr.h
+.Ft void
+.Fn idr_destroy "struct idr *idp"
+.Ft void *
+.Fn idr_find "struct idr *idp" "int id"
+.Ft int
+.Fn idr_for_each "struct idr *idp" "int (*fn)(int id, void *p, void *data)" "void *data"
+.Ft int
+.Fn idr_get_new "struct idr *idp" "void *ptr" "int *id"
+.Ft int
+.Fn idr_get_new_above "struct idr *idp" "void *ptr" "int sid" "int *id"
+.Ft void
+.Fn idr_init "struct idr *idp"
+.Ft void
+.Fn idr_init1 "struct idr *idp" "int size"
+.Ft int
+.Fn idr_pre_get "struct idr *idp"
+.Ft void
+.Fn idr_remove "struct idr *idp" "int id"
+.Ft void
+.Fn idr_remove_all "struct idr *idp"
+.Ft void *
+.Fn idr_replace "struct idr *idp" "void *ptr" "int id"
+.
+.Sh DESCRIPTION
+.Pp
+.Fn idr_destroy "struct idr *idp"
+.Pp
+Free all resources taken by given idr handle.
+.
+.Pp
+.Fn idr_find "struct idr *idp" "int id"
+.Pp
+Return data pointer mapped with given id.
+.
+.Pp
+.Fn idr_for_each "struct idr *idp" "int (*fn)(int id, void *p, void *data)" "void *data"
+.Pp
+Iterate through all pointers registered with given idr handle and call the
+callback function 'fn' for each pointer. It is not safe to modify the idr tree
+through the callback function.
+.Pp
+If the callback function returns a non-zero integer, we stop and return the
+value.
+.
+.Pp
+.Fn idr_get_new "struct idr *idp" "void *ptr" "int *id",
+.Fn idr_get_new_above "struct idr *idp" "void *ptr" "int sid" "int *id"
+.Pp
+Allocates a new integer mapped with pointer 'ptr'. The new id will be stored
+in 'id'. If the tree get full, function will return EAGAIN.
+.Fn idr_pre_get
+should be called to grow the tree.
+.
+.Pp
+.Fn idr_init "struct idr *idp",
+.Fn idr_init1 "struct idr *idp" "int size"
+.Pp
+Initialize idr handle that will be used by other functions of the API.
+.Fn idr_init
+initializes tree with hard coded default initial capacity (32).
+.Fn idr_init1
+takes additional parameter 'size' to set the initial capacity manually.
+.
+.Pp
+.Fn idr_pre_get "struct idr *idp"
+.Pp
+This function should be called prior to calling the idr_get_new* functions. It
+preallocates enough memory for subsequent calls to idr_get_new* functions. This 
+function should be called without any locks held.
+.Pp
+This function returns 0 if enough memory couldn't be allocated, otherwise 1.
+.Pp
+This function lacks 'gfp_t gfp_mask' parameter that is found in Linux version of
+this API.
+.
+.Pp
+.Fn idr_remove "struct idr *idp" "int id",
+.Pp
+Remove the given id from tree.
+.
+.Pp
+.Fn idr_remove_all "struct idr *idp"
+.Pp
+Remove all entries in the idr tree.
+.
+.Pp
+.Fn idr_replace "struct idr *idp" "void *ptr" "int id"
+.Pp
+Replace pointer for given id with new pointer.
+.Pp
+NULL is returned if pointer is not found. This behavior is different from the
+Linux API.
+.
index 776f534..d7b25ac 100644 (file)
@@ -1826,6 +1826,7 @@ libkern/bsearch.c                 standard
 libkern/crc32.c                                standard
 libkern/cmpdi2.c                       standard
 libkern/ucmpdi2.c                      standard
+libkern/idr.c                          standard
 libkern/index.c                                standard
 libkern/inet_ntoa.c                    standard
 libkern/mcount.c                       optional        profiling-routine
diff --git a/sys/libkern/idr.c b/sys/libkern/idr.c
new file mode 100644 (file)
index 0000000..485a083
--- /dev/null
@@ -0,0 +1,422 @@
+/*
+ * Copyright (c) 2005-2012 The DragonFly Project.  All rights reserved.
+ *
+ * This code is derived from software contributed to The DragonFly Project
+ * by Jeffrey Hsu.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name of The DragonFly Project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific, prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ */
+
+#include <sys/idr.h>
+#include <sys/kernel.h>
+#include <sys/libkern.h>
+#include <sys/malloc.h>
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/spinlock2.h>
+#include <sys/limits.h>
+
+#define IDR_DEFAULT_SIZE    32
+
+MALLOC_DEFINE(M_IDR, "idr", "Integer ID management");
+
+static void    idr_grow(struct idr *idp, int want);
+static void    idr_reserve(struct idr *idp, int id, int incr);
+int            idr_alloc(struct idr *idp, int want, int lim, int *result);
+void           idr_set(struct idr *idp, int id, void *ptr);
+int            idr_find_free(struct idr *idp, int want, int lim);
+int            idr_pre_get1(struct idr *idp, int want, int lim);
+
+/*
+ * Number of nodes in right subtree, including the root.
+ */
+static __inline int
+right_subtree_size(int n)
+{
+       return (n ^ (n | (n + 1)));
+}
+
+/*
+ * Bigger ancestor.
+ */
+static __inline int
+right_ancestor(int n)
+{
+       return (n | (n + 1));
+}
+
+/*
+ * Smaller ancestor.
+ */
+static __inline int
+left_ancestor(int n)
+{
+       return ((n & (n + 1)) - 1);
+}
+
+static __inline
+void
+idrfixup(struct idr *idp, int id)
+{
+       if (id < idp->idr_freeindex) {
+               idp->idr_freeindex = id;
+       }
+       while (idp->idr_lastindex >= 0 &&
+               idp->idr_nodes[idp->idr_lastindex].data == NULL &&
+               idp->idr_nodes[idp->idr_lastindex].reserved == 0
+       ) {
+               --idp->idr_lastindex;
+       }
+}
+
+static __inline
+struct idr_node *
+idr_get_node(struct idr *idp, int id)
+{
+       struct idr_node *idrnp;
+       if (id >= idp->idr_count)
+               return (NULL);
+       idrnp = &idp->idr_nodes[id];
+       if (idrnp->allocated == 0)
+               return (NULL);
+       return (idrnp);
+}
+
+static void
+idr_reserve(struct idr *idp, int id, int incr)
+{
+       while (id >= 0) {
+               idp->idr_nodes[id].allocated += incr;
+               KKASSERT(idp->idr_nodes[id].allocated >= 0);
+               id = left_ancestor(id);
+       }
+}
+
+int
+idr_find_free(struct idr *idp, int want, int lim)
+{
+       int id, rsum, rsize, node;
+       /*
+        * Search for a free descriptor starting at the higher
+        * of want or fd_freefile.  If that fails, consider
+        * expanding the ofile array.
+        *
+        * NOTE! the 'allocated' field is a cumulative recursive allocation
+        * count.  If we happen to see a value of 0 then we can shortcut
+        * our search.  Otherwise we run through through the tree going
+        * down branches we know have free descriptor(s) until we hit a
+        * leaf node.  The leaf node will be free but will not necessarily
+        * have an allocated field of 0.
+        */
+
+       /* move up the tree looking for a subtree with a free node */
+       for (id = max(want, idp->idr_freeindex); id < min(idp->idr_count, lim);
+                       id = right_ancestor(id)) {
+               if (idp->idr_nodes[id].allocated == 0)
+                       return (id);
+
+               rsize = right_subtree_size(id);
+               if (idp->idr_nodes[id].allocated == rsize)
+                       continue;       /* right subtree full */
+
+               /*
+                * Free fd is in the right subtree of the tree rooted at fd.
+                * Call that subtree R.  Look for the smallest (leftmost)
+                * subtree of R with an unallocated fd: continue moving
+                * down the left branch until encountering a full left
+                * subtree, then move to the right.
+                */
+               for (rsum = 0, rsize /= 2; rsize > 0; rsize /= 2) {
+                       node = id + rsize;
+                       rsum += idp->idr_nodes[node].allocated;
+                       if (idp->idr_nodes[id].allocated == rsum + rsize) {
+                               id = node;      /* move to the right */
+                               if (idp->idr_nodes[node].allocated == 0)
+                                       return (id);
+                               rsum = 0;
+                       }
+               }
+               return (id);
+       }
+       return (-1);
+}
+
+int
+idr_pre_get1(struct idr *idp, int want, int lim)
+{
+       int id;
+
+       spin_lock(&idp->idr_spin);
+       if (want >= idp->idr_count)
+               idr_grow(idp, want);
+
+retry:
+       id = idr_find_free(idp, want, lim);
+       if (id > -1)
+               goto found;
+
+       /*
+        * No space in current array.  Expand?
+        */
+       if (idp->idr_count >= lim) {
+               spin_unlock(&idp->idr_spin);
+               return (ENOSPC);
+       }
+       idr_grow(idp, want);
+       goto retry;
+
+found:
+       spin_unlock(&idp->idr_spin);
+       return (0);
+}
+
+int
+idr_pre_get(struct idr *idp)
+{
+       int error = idr_pre_get1(idp, idp->idr_maxwant, INT_MAX);
+       return (error == 0);
+}
+
+int
+idr_get_new(struct idr *idp, void *ptr, int *id)
+{
+       int resid;
+
+       if (ptr == NULL)
+               return (EINVAL);
+
+       resid = idr_find_free(idp, 0, INT_MAX);
+       if (resid == -1)
+               return (EAGAIN);
+
+       if (resid > idp->idr_lastindex)
+               idp->idr_lastindex = resid;
+       idp->idr_freeindex = resid;
+       *id = resid;
+       KKASSERT(idp->idr_nodes[resid].reserved == 0);
+       idp->idr_nodes[resid].reserved = 1;
+       idr_reserve(idp, resid, 1);
+       idr_set(idp, resid, ptr);
+       return (0);
+}
+
+int
+idr_get_new_above(struct idr *idp, void *ptr, int sid, int *id)
+{
+       int resid;
+       if (sid >= idp->idr_count) {
+               idp->idr_maxwant = max(idp->idr_maxwant, sid);
+               return (EAGAIN);
+       }
+
+       if (ptr == NULL)
+               return (EINVAL);
+
+       resid = idr_find_free(idp, sid, INT_MAX);
+       if (resid == -1)
+               return (EAGAIN);
+
+       if (resid > idp->idr_lastindex)
+               idp->idr_lastindex = resid;
+       if (sid <= idp->idr_freeindex)
+               idp->idr_freeindex = resid;
+       *id = resid;
+       KKASSERT(idp->idr_nodes[resid].reserved == 0);
+       idp->idr_nodes[resid].reserved = 1;
+       idr_reserve(idp, resid, 1);
+       idr_set(idp, resid, ptr);
+       return (0);
+}
+
+/*
+ * Grow the file table so it can hold through descriptor (want).
+ *
+ * The fdp's spinlock must be held exclusively on entry and may be held
+ * exclusively on return.  The spinlock may be cycled by the routine.
+ *
+ * MPSAFE
+ */
+static void
+idr_grow(struct idr *idp, int want)
+{
+       struct idr_node *newnodes;
+       struct idr_node *oldnodes;
+       int nf, extra;
+
+       nf = idp->idr_count;
+       do {
+               /* nf has to be of the form 2^n - 1 */
+               nf = 2 * nf + 1;
+       } while (nf <= want);
+
+       spin_unlock(&idp->idr_spin);
+       newnodes = kmalloc(nf * sizeof(struct idr_node), M_IDR, M_WAITOK);
+       spin_lock(&idp->idr_spin);
+
+       /*
+        * We could have raced another extend while we were not holding
+        * the spinlock.
+        */
+       if (idp->idr_count >= nf) {
+               spin_unlock(&idp->idr_spin);
+               kfree(newnodes, M_IDR);
+               spin_lock(&idp->idr_spin);
+               return;
+       }
+       /*
+        * Copy the existing ofile and ofileflags arrays
+        * and zero the new portion of each array.
+        */
+       extra = nf - idp->idr_count;
+       if (idp->idr_nodes != NULL)
+               bcopy(idp->idr_nodes, newnodes, idp->idr_count * sizeof(struct idr_node));
+       bzero(&newnodes[idp->idr_count], extra * sizeof(struct idr_node));
+
+       oldnodes = idp->idr_nodes;
+       idp->idr_nodes = newnodes;
+       idp->idr_count = nf;
+
+       if (oldnodes != NULL) {
+               spin_unlock(&idp->idr_spin);
+               kfree(oldnodes, M_IDR);
+               spin_lock(&idp->idr_spin);
+       }
+
+       idp->idr_nexpands++;
+}
+
+void
+idr_remove(struct idr *idp, int id)
+{
+       void *ptr;
+
+       if (id >= idp->idr_count)
+               return;
+       if ((ptr = idp->idr_nodes[id].data) == NULL)
+               return;
+       idp->idr_nodes[id].data = NULL;
+
+       idr_reserve(idp, id, -1);
+       idrfixup(idp, id);
+}
+
+void
+idr_remove_all(struct idr *idp)
+{
+       kfree(idp->idr_nodes, M_IDR);
+       idp->idr_nodes = kmalloc(idp->idr_count * sizeof *idp, M_IDR, M_WAITOK | M_ZERO);
+       idp->idr_lastindex = -1;
+       idp->idr_freeindex = 0;
+       idp->idr_nexpands = 0;
+       idp->idr_maxwant = 0;
+       spin_init(&idp->idr_spin);
+}
+
+void
+idr_destroy(struct idr *idp)
+{
+       kfree(idp->idr_nodes, M_IDR);
+       memset(idp, 0, sizeof(struct idr));
+}
+
+void *
+idr_find(struct idr *idp, int id)
+{
+       if (id > idp->idr_count) {
+               return (NULL);
+       } else if (idp->idr_nodes[id].allocated == 0) {
+               return (NULL);
+       }
+       KKASSERT(idp->idr_nodes[id].data != NULL);
+       return idp->idr_nodes[id].data;
+}
+
+void
+idr_set(struct idr *idp, int id, void *ptr)
+{
+       KKASSERT(id < idp->idr_count);
+       KKASSERT(idp->idr_nodes[id].reserved != 0);
+       if (ptr) {
+               idp->idr_nodes[id].data = ptr;
+               idp->idr_nodes[id].reserved = 0;
+       } else {
+               idp->idr_nodes[id].reserved = 0;
+               idr_reserve(idp, id, -1);
+               idrfixup(idp, id);
+       }
+}
+
+int
+idr_for_each(struct idr *idp, int (*fn)(int id, void *p, void *data), void *data)
+{
+       int i, error;
+       struct idr_node *nodes = idp->idr_nodes;
+       for (i = 0; i < idp->idr_count; i++) {
+               if (nodes[i].data != NULL && nodes[i].allocated > 0) {
+                       error = fn(i, nodes[i].data, data);
+                       if (error != 0)
+                               return (error);
+               }
+       }
+       return (0);
+}
+
+void *
+idr_replace(struct idr *idp, void *ptr, int id)
+{
+       struct idr_node *idrnp;
+       void *ret;
+
+       idrnp = idr_get_node(idp, id);
+
+       if (idrnp == NULL || ptr == NULL)
+               return (NULL);
+
+       ret = idrnp->data;
+       idrnp->data = ptr;
+
+       return (ret);
+}
+
+void
+idr_init1(struct idr *idp, int size)
+{
+       memset(idp, 0, sizeof(struct idr));
+       idp->idr_nodes = kmalloc(size * sizeof *idp, M_IDR, M_WAITOK | M_ZERO);
+       idp->idr_count = size;
+       idp->idr_lastindex = -1;
+       idp->idr_maxwant = 0;
+       spin_init(&idp->idr_spin);
+}
+
+void
+idr_init(struct idr *idp)
+{
+       idr_init1(idp, IDR_DEFAULT_SIZE);
+}
diff --git a/sys/sys/idr.h b/sys/sys/idr.h
new file mode 100644 (file)
index 0000000..54140bd
--- /dev/null
@@ -0,0 +1,84 @@
+/*
+ * Copyright (c) 2005-2012 The DragonFly Project.  All rights reserved.
+ *
+ * This code is derived from software contributed to The DragonFly Project
+ * by Jeffrey Hsu.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name of The DragonFly Project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific, prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ */
+
+/**
+ * IDR is a small Integer ID management library that provides an interface to
+ * map integers with some pointer that can later be retrieved.
+ *
+ * NOTE: Pointer mapped by integer can't be NULL.
+ *
+ */
+
+
+#ifndef _IDR_H_
+#define _IDR_H_
+
+#ifdef _KERNEL
+
+#include <sys/spinlock.h>
+
+struct idr_node {
+       void    *data;
+       char     reserved;
+       int      allocated;
+};
+
+struct idr {
+       struct      idr_node *idr_nodes;
+       int         idr_count;
+       int         idr_lastindex;
+       int         idr_freeindex;
+       int         idr_nexpands;
+       int         idr_maxwant;
+       struct      spinlock idr_spin;
+};
+
+void   *idr_find(struct idr *idp, int id);
+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);
+int     idr_for_each(struct idr *idp, int (*fn)(int id, void *p, void *data), void *data);
+int     idr_get_new(struct idr *idp, void *ptr, int *id);
+int     idr_get_new_above(struct idr *idp, void *ptr, int sid, int *id);
+int     idr_pre_get(struct idr *idp);
+
+void    idr_init1(struct idr *idp, int size);
+void    idr_init(struct idr *idp);
+
+
+#endif /* _KERNEL */
+
+#endif /* _IDR_H_ */