home *** CD-ROM | disk | FTP | other *** search
/ PC Welt 2006 November (DVD) / PCWELT_11_2006.ISO / casper / filesystem.squashfs / usr / src / linux-headers-2.6.17-6 / include / linux / idr.h < prev    next >
Encoding:
C/C++ Source or Header  |  2006-08-11  |  2.3 KB  |  86 lines
  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 <linux/types.h>
  16. #include <linux/bitops.h>
  17.  
  18. #if BITS_PER_LONG == 32
  19. # define IDR_BITS 5
  20. # define IDR_FULL 0xfffffffful
  21. /* We can only use two of the bits in the top level because there is
  22.    only one possible bit in the top level (5 bits * 7 levels = 35
  23.    bits, but you only use 31 bits in the id). */
  24. # define TOP_LEVEL_FULL (IDR_FULL >> 30)
  25. #elif BITS_PER_LONG == 64
  26. # define IDR_BITS 6
  27. # define IDR_FULL 0xfffffffffffffffful
  28. /* We can only use two of the bits in the top level because there is
  29.    only one possible bit in the top level (6 bits * 6 levels = 36
  30.    bits, but you only use 31 bits in the id). */
  31. # define TOP_LEVEL_FULL (IDR_FULL >> 62)
  32. #else
  33. # error "BITS_PER_LONG is not 32 or 64"
  34. #endif
  35.  
  36. #define IDR_SIZE (1 << IDR_BITS)
  37. #define IDR_MASK ((1 << IDR_BITS)-1)
  38.  
  39. #define MAX_ID_SHIFT (sizeof(int)*8 - 1)
  40. #define MAX_ID_BIT (1U << MAX_ID_SHIFT)
  41. #define MAX_ID_MASK (MAX_ID_BIT - 1)
  42.  
  43. /* Leave the possibility of an incomplete final layer */
  44. #define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS
  45.  
  46. /* Number of id_layer structs to leave in free list */
  47. #define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL
  48.  
  49. struct idr_layer {
  50.     unsigned long         bitmap; /* A zero bit means "space here" */
  51.     struct idr_layer    *ary[1<<IDR_BITS];
  52.     int             count;     /* When zero, we can release it */
  53. };
  54.  
  55. struct idr {
  56.     struct idr_layer *top;
  57.     struct idr_layer *id_free;
  58.     int          layers;
  59.     int          id_free_cnt;
  60.     spinlock_t      lock;
  61. };
  62.  
  63. #define IDR_INIT(name)                        \
  64. {                                \
  65.     .top        = NULL,                    \
  66.     .id_free    = NULL,                    \
  67.     .layers     = 0,                    \
  68.     .id_free_cnt    = 0,                    \
  69.     .lock        = SPIN_LOCK_UNLOCKED,            \
  70. }
  71. #define DEFINE_IDR(name)    struct idr name = IDR_INIT(name)
  72.  
  73. /*
  74.  * This is what we export.
  75.  */
  76.  
  77. void *idr_find(struct idr *idp, int id);
  78. int idr_pre_get(struct idr *idp, gfp_t gfp_mask);
  79. int idr_get_new(struct idr *idp, void *ptr, int *id);
  80. int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);
  81. void idr_remove(struct idr *idp, int id);
  82. void idr_destroy(struct idr *idp);
  83. void idr_init(struct idr *idp);
  84.  
  85. #endif /* __IDR_H__ */
  86.