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

Rev	Author	Line No.	Line
1408	serge	1	/*
		2	* include/linux/idr.h
		3	*
		4	* 2002-10-18 written by Jim Houston jim.houston@ccur.com
		5	* Copyright (C) 2002 by Concurrent Computer Corporation
		6	* Distributed under the GNU GPL license version 2.
		7	*
		8	* Small id to pointer translation service avoiding fixed sized
		9	* tables.
		10	*/
		11
		12	#ifndef __IDR_H__
		13	#define __IDR_H__
		14
		15	#include
		16	#include
		17
		18	//#include
		19	//#include
		20	//#include
		21
		22	struct rcu_head {
		23	struct rcu_head *next;
		24	void (func)(struct rcu_head head);
		25	};
		26
		27
		28	# define IDR_BITS 5
		29	# define IDR_FULL 0xfffffffful
		30	/* We can only use two of the bits in the top level because there is
		31	only one possible bit in the top level (5 bits * 7 levels = 35
		32	bits, but you only use 31 bits in the id). */
		33	# define TOP_LEVEL_FULL (IDR_FULL >> 30)
		34
		35	#define IDR_SIZE (1 << IDR_BITS)
		36	#define IDR_MASK ((1 << IDR_BITS)-1)
		37
		38	#define MAX_ID_SHIFT (sizeof(int)*8 - 1)
		39	#define MAX_ID_BIT (1U << MAX_ID_SHIFT)
		40	#define MAX_ID_MASK (MAX_ID_BIT - 1)
		41
		42	/* Leave the possibility of an incomplete final layer */
		43	#define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS
		44
		45	/* Number of id_layer structs to leave in free list */
		46	#define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL
		47
		48	struct idr_layer {
		49	unsigned long bitmap; /* A zero bit means "space here" */
		50	struct idr_layer *ary[1<
		51	int count; /* When zero, we can release it */
		52	int layer; /* distance from leaf */
		53	struct rcu_head rcu_head;
		54	};
		55
		56	struct idr {
		57	struct idr_layer *top;
		58	struct idr_layer *id_free;
		59	int layers; /* only valid without concurrent changes */
		60	int id_free_cnt;
		61	// spinlock_t lock;
		62	};
		63
		64	#define IDR_INIT(name) \
		65	{ \
		66	.top = NULL, \
		67	.id_free = NULL, \
		68	.layers = 0, \
		69	.id_free_cnt = 0, \
		70	// .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
		71	}
		72	#define DEFINE_IDR(name) struct idr name = IDR_INIT(name)
		73
		74	/* Actions to be taken after a call to _idr_sub_alloc */
		75	#define IDR_NEED_TO_GROW -2
		76	#define IDR_NOMORE_SPACE -3
		77
		78	#define _idr_rc_to_errno(rc) ((rc) == -1 ? -EAGAIN : -ENOSPC)
		79
		80	/**
		81	* idr synchronization (stolen from radix-tree.h)
		82	*
		83	* idr_find() is able to be called locklessly, using RCU. The caller must
		84	* ensure calls to this function are made within rcu_read_lock() regions.
		85	* Other readers (lock-free or otherwise) and modifications may be running
		86	* concurrently.
		87	*
		88	* It is still required that the caller manage the synchronization and
		89	* lifetimes of the items. So if RCU lock-free lookups are used, typically
		90	* this would mean that the items have their own locks, or are amenable to
		91	* lock-free access; and that the items are freed by RCU (or only freed after
		92	* having been deleted from the idr tree and a synchronize_rcu() grace
		93	* period).
		94	*/
		95
		96	/*
		97	* This is what we export.
		98	*/
		99
		100	void idr_find(struct idr idp, int id);
		101	int idr_pre_get(struct idr *idp, u32_t gfp_mask);
		102	int idr_get_new(struct idr idp, void ptr, int *id);
		103	int idr_get_new_above(struct idr idp, void ptr, int starting_id, int *id);
		104	int idr_for_each(struct idr *idp,
		105	int (fn)(int id, void p, void data), void data);
		106	void idr_get_next(struct idr idp, int *nextid);
		107	void idr_replace(struct idr idp, void *ptr, int id);
		108	void idr_remove(struct idr *idp, int id);
		109	void idr_remove_all(struct idr *idp);
		110	void idr_destroy(struct idr *idp);
		111	void idr_init(struct idr *idp);
		112
		113
		114	/*
		115	* IDA - IDR based id allocator, use when translation from id to
		116	* pointer isn't necessary.
		117	*/
		118	#define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */
		119	#define IDA_BITMAP_LONGS (128 / sizeof(long) - 1)
		120	#define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8)
		121
		122	struct ida_bitmap {
		123	long nr_busy;
		124	unsigned long bitmap[IDA_BITMAP_LONGS];
		125	};
		126
		127	struct ida {
		128	struct idr idr;
		129	struct ida_bitmap *free_bitmap;
		130	};
		131
		132	#define IDA_INIT(name) { .idr = IDR_INIT(name), .free_bitmap = NULL, }
		133	#define DEFINE_IDA(name) struct ida name = IDA_INIT(name)
		134
		135	int ida_pre_get(struct ida *ida, u32_t gfp_mask);
		136	int ida_get_new_above(struct ida ida, int starting_id, int p_id);
		137	int ida_get_new(struct ida ida, int p_id);
		138	void ida_remove(struct ida *ida, int id);
		139	void ida_destroy(struct ida *ida);
		140	void ida_init(struct ida *ida);
		141
		142	void idr_init_cache(void);
		143
		144	#endif /* __IDR_H__ */

Subversion Repositories Kolibri OS

(root)/drivers/include/linux/idr.h @ 1967 – Rev 1408