You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
linux/include/linux/rbtree.h
To use rbtrees you'll have to implement your own insert and search cores.
- This will avoid us to use callbacks and to drop drammatically performances.
+ This will avoid us to use callbacks and to drop dramatically performances.
I know it's not the cleaner way, but in C (not in C++) to get
performances and genericity...
#define _LINUX_RBTREE_H
#include <stdlib.h>
+#include <stdint.h>
+#include "compiler.h"
-#undef offsetof
-#ifdef __compiler_offsetof
-#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
-#else
-#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
+#if __GNUC_PREREQ (4, 6)
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-function"
#endif
-#define container_of(ptr, type, member) ({ \
- const typeof( ((type *)0)->member ) *__mptr = (ptr); \
- (type *)( (char *)__mptr - offsetof(type,member) );})
-
struct rb_node
{
- unsigned long rb_parent_color;
+ uintptr_t rb_parent_color;
#define RB_RED 0
#define RB_BLACK 1
struct rb_node *rb_right;
static inline void ext2fs_rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
- rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
+ rb->rb_parent_color = (rb->rb_parent_color & 3) | (uintptr_t)p;
}
static inline void ext2fs_rb_set_color(struct rb_node *rb, int color)
{
#define RB_ROOT (struct rb_root) { NULL, }
#define ext2fs_rb_entry(ptr, type, member) container_of(ptr, type, member)
-#define EXT2FS_RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
-#define EXT2FS_RB_EMPTY_NODE(node) (ext2fs_rb_parent(node) == node)
-#define EXT2FS_RB_CLEAR_NODE(node) (ext2fs_rb_set_parent(node, node))
+static inline int ext2fs_rb_empty_root(struct rb_root *root)
+{
+ return root->rb_node == NULL;
+}
-extern void ext2fs_rb_insert_color(struct rb_node *, struct rb_root *);
-extern void ext2fs_rb_erase(struct rb_node *, struct rb_root *);
+static inline int ext2fs_rb_empty_node(struct rb_node *node)
+{
+ return ext2fs_rb_parent(node) == node;
+}
-typedef void (*rb_augment_f)(struct rb_node *node, void *data);
+static inline void ext2fs_rb_clear_node(struct rb_node *node)
+{
+ ext2fs_rb_set_parent(node, node);
+}
-extern void ext2fs_rb_augment_insert(struct rb_node *node,
- rb_augment_f func, void *data);
-extern struct rb_node *ext2fs_rb_augment_erase_begin(struct rb_node *node);
-extern void ext2fs_rb_augment_erase_end(struct rb_node *node,
- rb_augment_f func, void *data);
+extern void ext2fs_rb_insert_color(struct rb_node *, struct rb_root *);
+extern void ext2fs_rb_erase(struct rb_node *, struct rb_root *);
/* Find logical next and previous nodes in a tree */
-extern struct rb_node *ext2fs_rb_next(const struct rb_node *);
-extern struct rb_node *ext2fs_rb_prev(const struct rb_node *);
+extern struct rb_node *ext2fs_rb_next(struct rb_node *);
+extern struct rb_node *ext2fs_rb_prev(struct rb_node *);
extern struct rb_node *ext2fs_rb_first(const struct rb_root *);
extern struct rb_node *ext2fs_rb_last(const struct rb_root *);
struct rb_node * parent,
struct rb_node ** rb_link)
{
- node->rb_parent_color = (unsigned long )parent;
+ node->rb_parent_color = (uintptr_t)parent;
node->rb_left = node->rb_right = NULL;
*rb_link = node;
}
+#if __GNUC_PREREQ (4, 6)
+#pragma GCC diagnostic pop
+#endif
+
#endif /* _LINUX_RBTREE_H */