LINUX IDR/IDA算法分析
1 介绍
IDR/IDA用做唯一ID的分配管理。内部使用Bit实现，在内存占用和性能之间有比较好的平衡。IDR/IDA内部使用RADIX实现。
idr.h: Small id to pointer translation service avoiding fixed sized tables.
A common problem to solve is allocating identifiers (IDs); generally small numbers which identify a thing. Examples include file descriptors, process IDs, packet identifiers in networking protocols, SCSI tags and device instance numbers. The IDR and the IDA provide a reasonable solution to the problem to avoid everybody inventing their own. The IDR provides the ability to map an ID to a pointer, while the IDA provides only ID allocation, and as a result is much more memory-efficient.
2 使用示例
2.1 loop
loop是最简单的使用。以loop.c使用为例阐述：
2.1.1 静态初始化
/*- idr.h -*/ /* Set the IDR flag and the IDR_FREE tag */ #define IDR_RT_MARKER (ROOT_IS_IDR | (__force gfp_t) \ (1 << (ROOT_TAG_SHIFT + IDR_FREE))) #define IDR_INIT_BASE(name, base) { \ .idr_rt = RADIX_TREE_INIT(name, IDR_RT_MARKER), \ .idr_base = (base), \ .idr_next = 0, \ } /** * IDR_INIT() - Initialise an IDR. * @name: Name of IDR. * * A freshly-initialised IDR contains no IDs. */ #define IDR_INIT(name) IDR_INIT_BASE(name, 0) /** * DEFINE_IDR() - Define a statically-allocated IDR. * @name: Name of IDR. * * An IDR defined using this macro is ready for use with no additional * initialisation required. It contains no IDs. */ #define DEFINE_IDR(name) struct idr name = IDR_INIT(name) /*- loop.c -*/ static DEFINE_IDR(loop_index_idr);
2.2 loop示例
3 References
- LWN A simplified IDR API
- https://lwn.net/Articles/536293/