WebSVN – Kolibri OS – Diff – /drivers/include/linux/idr.h

  */
 #ifndef __IDR_H__
+#define __IDR_H__
 #define __IDR_H__
 #include
 #include
 #include
 #include
+//#include
+//#include
+#include
-//#include
-//#include
-struct rcu_head {
-    struct rcu_head *next;
-    void (*func)(struct rcu_head *head);
-};
-#if BITS_PER_LONG == 32
-# define IDR_BITS 5
-# define IDR_FULL 0xfffffffful
-/* We can only use two of the bits in the top level because there is
-   only one possible bit in the top level (5 bits * 7 levels = 35
-   bits, but you only use 31 bits in the id). */
-# define TOP_LEVEL_FULL (IDR_FULL >> 30)
-#elif BITS_PER_LONG == 64
-# define IDR_BITS 6
-# define IDR_FULL 0xfffffffffffffffful
-/* We can only use two of the bits in the top level because there is
-   only one possible bit in the top level (6 bits * 6 levels = 36
-   bits, but you only use 31 bits in the id). */
-# define TOP_LEVEL_FULL (IDR_FULL >> 62)
+#include
+#include
+/*
+ * We want shallower trees and thus more bits covered at each layer.  8
+ * bits gives us large enough first layer for most use cases and maximum
-#else
+ * tree depth of 4.  Each idr_layer is slightly larger than 2k on 64bit and
-# error "BITS_PER_LONG is not 32 or 64"
+ * 1k on 32bit.
-#endif
-#define IDR_SIZE (1 << IDR_BITS)
-#define IDR_MASK ((1 << IDR_BITS)-1)
-#define MAX_ID_SHIFT (sizeof(int)*8 - 1)
-#define MAX_ID_BIT (1U << MAX_ID_SHIFT)
-#define MAX_ID_MASK (MAX_ID_BIT - 1)
-/* Leave the possibility of an incomplete final layer */
-#define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS
+ */
+#define IDR_BITS 8
+#define IDR_SIZE (1 << IDR_BITS)
-/* Number of id_layer structs to leave in free list */
+#define IDR_MASK ((1 << IDR_BITS)-1)
 #define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL
 struct idr_layer {
-struct idr_layer {
+	int			prefix;	/* the ID prefix of this idr_layer */
-	unsigned long		 bitmap; /* A zero bit means "space here" */
+	DECLARE_BITMAP(bitmap, IDR_SIZE); /* A zero bit means "space here" */
 	struct idr_layer __rcu	*ary[1<
+	int			 count;	 /* When zero, we can release it */
-	int			 count;	 /* When zero, we can release it */
+	int			 layer;	 /* distance from leaf */
-	int			 layer;	 /* distance from leaf */
+    struct rcu_head      rcu_head;
-    struct rcu_head      rcu_head;
+};
 };
+struct idr {
-struct idr {
+	struct idr_layer __rcu	*hint;	/* the last layer allocated from */
 	struct idr_layer __rcu *top;
 	struct idr_layer *id_free;
-	int		  layers; /* only valid without concurrent changes */
-	int		  id_free_cnt;
-//   spinlock_t    lock;
-};
+	int			layers;	/* only valid w/o concurrent changes */
-#define IDR_INIT(name)						\
+	int		  id_free_cnt;
-{								\
+	spinlock_t		lock;
-	.top		= NULL,					\
-	.id_free	= NULL,					\
-	.layers 	= 0,					\
-	.id_free_cnt	= 0,					\
-//   .lock       = __SPIN_LOCK_UNLOCKED(name.lock),  \
-}
-#define DEFINE_IDR(name)	struct idr name = IDR_INIT(name)
+};
-/* Actions to be taken after a call to _idr_sub_alloc */
+#define IDR_INIT(name)						\
-#define IDR_NEED_TO_GROW -2
+{								\
-#define IDR_NOMORE_SPACE -3
+	.lock			= __SPIN_LOCK_UNLOCKED(name.lock),	\
 /*
  * This is what we export.
  */
-void *idr_find(struct idr *idp, int id);
-int idr_pre_get(struct idr *idp, gfp_t gfp_mask);
+void *idr_find_slowpath(struct idr *idp, int id);
+int idr_pre_get(struct idr *idp, gfp_t gfp_mask);
+int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);
-int idr_get_new(struct idr *idp, void *ptr, int *id);
+void idr_preload(gfp_t gfp_mask);
-int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);
+int idr_alloc(struct idr *idp, void *ptr, int start, int end, gfp_t gfp_mask);
 int idr_for_each(struct idr *idp,
 		 int (*fn)(int id, void *p, void *data), void *data);
 void *idr_get_next(struct idr *idp, int *nextid);
 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_free(struct idr *idp, int id);
+void idr_destroy(struct idr *idp);
+void idr_init(struct idr *idp);
+/**
+ * idr_preload_end - end preload section started with idr_preload()
+ *
+ * Each idr_preload() should be matched with an invocation of this
+ * function.  See idr_preload() for details.
+ */
+static inline void idr_preload_end(void)
+{
+//	preempt_enable();
+}
+/**
+ * idr_find - return pointer for given id
+ * @idp: idr handle
+ * @id: lookup key
+ *
+ * Return the pointer given the id it has been registered with.  A %NULL
+ * return indicates that @id is not valid or you passed %NULL in
+ * idr_get_new().
+ *
+ * This function can be called under rcu_read_lock(), given that the leaf
+ * pointers lifetimes are correctly managed.
+ */
+static inline void *idr_find(struct idr *idr, int id)
+{
+	struct idr_layer *hint = rcu_dereference_raw(idr->hint);
+	if (hint && (id & ~IDR_MASK) == hint->prefix)
+		return rcu_dereference_raw(hint->ary[id & IDR_MASK]);
+	return idr_find_slowpath(idr, id);
+}
+/**
+ * idr_get_new - allocate new idr entry
+ * @idp: idr handle
+ * @ptr: pointer you want associated with the id
+ * @id: pointer to the allocated handle
+ *
+ * Simple wrapper around idr_get_new_above() w/ @starting_id of zero.
+ */
+static inline int idr_get_new(struct idr *idp, void *ptr, int *id)
+{
+	return idr_get_new_above(idp, ptr, 0, id);
+}
+/**
+ * idr_for_each_entry - iterate over an idr's elements of a given type
+ * @idp:     idr handle
+ * @entry:   the type * to use as cursor
+ * @id:      id entry's key
+ */
+#define idr_for_each_entry(idp, entry, id)				\
+	for (id = 0, entry = (typeof(entry))idr_get_next((idp), &(id)); \
+	     entry != NULL;                                             \
+	     ++id, entry = (typeof(entry))idr_get_next((idp), &(id)))
+void __idr_remove_all(struct idr *idp);	/* don't use */
+/**
+ * idr_remove_all - remove all ids from the given idr tree
+ * @idp: idr handle
+ *
+ * If you're trying to destroy @idp, calling idr_destroy() is enough.
+ * This is going away.  Don't use.
+ */
+static inline void __deprecated idr_remove_all(struct idr *idp)
 void idr_destroy(struct idr *idp);
-void idr_init(struct idr *idp);
+	__idr_remove_all(idp);
+}
 struct ida {
 	struct idr		idr;
 	struct ida_bitmap	*free_bitmap;
 };
-#define IDA_INIT(name)		{ .idr = IDR_INIT(name), .free_bitmap = NULL, }
+#define IDA_INIT(name)		{ .idr = IDR_INIT((name).idr), .free_bitmap = NULL, }
 #define DEFINE_IDA(name)	struct ida name = IDA_INIT(name)
-int ida_pre_get(struct ida *ida, gfp_t gfp_mask);
-int ida_get_new_above(struct ida *ida, int starting_id, int *p_id);
+int ida_pre_get(struct ida *ida, gfp_t gfp_mask);
-int ida_get_new(struct ida *ida, int *p_id);
+int ida_get_new_above(struct ida *ida, int starting_id, int *p_id);
 void ida_remove(struct ida *ida, int id);
 void ida_destroy(struct ida *ida);
+void ida_init(struct ida *ida);
-void ida_init(struct ida *ida);
+void __init idr_init_cache(void);

Subversion Repositories Kolibri OS

(root)/drivers/include/linux/idr.h – Rev 1967 → 3391