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 / prio_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  2006-08-11  |  3.2 KB  |  121 lines
  1. #ifndef _LINUX_PRIO_TREE_H
  2. #define _LINUX_PRIO_TREE_H
  3.  
  4. /*
  5.  * K&R 2nd ed. A8.3 somewhat obliquely hints that initial sequences of struct
  6.  * fields with identical types should end up at the same location. We'll use
  7.  * this until we can scrap struct raw_prio_tree_node.
  8.  *
  9.  * Note: all this could be done more elegantly by using unnamed union/struct
  10.  * fields. However, gcc 2.95.3 and apparently also gcc 3.0.4 don't support this
  11.  * language extension.
  12.  */
  13.  
  14. struct raw_prio_tree_node {
  15.     struct prio_tree_node    *left;
  16.     struct prio_tree_node    *right;
  17.     struct prio_tree_node    *parent;
  18. };
  19.  
  20. struct prio_tree_node {
  21.     struct prio_tree_node    *left;
  22.     struct prio_tree_node    *right;
  23.     struct prio_tree_node    *parent;
  24.     unsigned long        start;
  25.     unsigned long        last;    /* last location _in_ interval */
  26. };
  27.  
  28. struct prio_tree_root {
  29.     struct prio_tree_node    *prio_tree_node;
  30.     unsigned short         index_bits;
  31.     unsigned short        raw;
  32.         /*
  33.          * 0: nodes are of type struct prio_tree_node
  34.          * 1: nodes are of type raw_prio_tree_node
  35.          */
  36. };
  37.  
  38. struct prio_tree_iter {
  39.     struct prio_tree_node    *cur;
  40.     unsigned long        mask;
  41.     unsigned long        value;
  42.     int            size_level;
  43.  
  44.     struct prio_tree_root    *root;
  45.     pgoff_t            r_index;
  46.     pgoff_t            h_index;
  47. };
  48.  
  49. static inline void prio_tree_iter_init(struct prio_tree_iter *iter,
  50.         struct prio_tree_root *root, pgoff_t r_index, pgoff_t h_index)
  51. {
  52.     iter->root = root;
  53.     iter->r_index = r_index;
  54.     iter->h_index = h_index;
  55.     iter->cur = NULL;
  56. }
  57.  
  58. #define __INIT_PRIO_TREE_ROOT(ptr, _raw)    \
  59. do {                    \
  60.     (ptr)->prio_tree_node = NULL;    \
  61.     (ptr)->index_bits = 1;        \
  62.     (ptr)->raw = (_raw);        \
  63. } while (0)
  64.  
  65. #define INIT_PRIO_TREE_ROOT(ptr)    __INIT_PRIO_TREE_ROOT(ptr, 0)
  66. #define INIT_RAW_PRIO_TREE_ROOT(ptr)    __INIT_PRIO_TREE_ROOT(ptr, 1)
  67.  
  68. #define INIT_PRIO_TREE_NODE(ptr)                \
  69. do {                                \
  70.     (ptr)->left = (ptr)->right = (ptr)->parent = (ptr);    \
  71. } while (0)
  72.  
  73. #define INIT_PRIO_TREE_ITER(ptr)    \
  74. do {                    \
  75.     (ptr)->cur = NULL;        \
  76.     (ptr)->mask = 0UL;        \
  77.     (ptr)->value = 0UL;        \
  78.     (ptr)->size_level = 0;        \
  79. } while (0)
  80.  
  81. #define prio_tree_entry(ptr, type, member) \
  82.        ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
  83.  
  84. static inline int prio_tree_empty(const struct prio_tree_root *root)
  85. {
  86.     return root->prio_tree_node == NULL;
  87. }
  88.  
  89. static inline int prio_tree_root(const struct prio_tree_node *node)
  90. {
  91.     return node->parent == node;
  92. }
  93.  
  94. static inline int prio_tree_left_empty(const struct prio_tree_node *node)
  95. {
  96.     return node->left == node;
  97. }
  98.  
  99. static inline int prio_tree_right_empty(const struct prio_tree_node *node)
  100. {
  101.     return node->right == node;
  102. }
  103.  
  104.  
  105. struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root,
  106.                 struct prio_tree_node *old, struct prio_tree_node *node);
  107. struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,
  108.                 struct prio_tree_node *node);
  109. void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node);
  110. struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter);
  111.  
  112. #define raw_prio_tree_replace(root, old, node) \
  113.     prio_tree_replace(root, (struct prio_tree_node *) (old), \
  114.         (struct prio_tree_node *) (node))
  115. #define raw_prio_tree_insert(root, node) \
  116.     prio_tree_insert(root, (struct prio_tree_node *) (node))
  117. #define raw_prio_tree_remove(root, node) \
  118.     prio_tree_remove(root, (struct prio_tree_node *) (node))
  119.  
  120. #endif /* _LINUX_PRIO_TREE_H */
  121.