include/sys/rbtree.h

   1 /*      $NetBSD: rbtree.h,v 1.2 2012/02/17 08:20:55 yamt Exp $  */
   2
   3 /*-
   4  * Copyright (c) 2001 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * Portions Copyright (c) 2012 Apple Inc. All rights reserved.
   8  *
   9  * This code is derived from software contributed to The NetBSD Foundation
  10  * by Matt Thomas <matt@3am-software.com>.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimer.
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  23  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  24  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  25  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  26  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  27  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  28  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  29  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  30  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31  * POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 #ifndef _SYS_RBTREE_H_
  35 #define _SYS_RBTREE_H_
  36
  37 #include <Availability.h>
  38
  39 #include <sys/types.h>
  40 #include <stdbool.h>
  41 #include <inttypes.h>
  42 #include <sys/queue.h>
  43
  44 __BEGIN_DECLS
  45
  46
  47 #define RB_DIR_LEFT             0
  48 #define RB_DIR_RIGHT            1
  49
  50 #define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT)
  51 #define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT)
  52 #define RB_TREE_FOREACH(N, T) \
  53     for ((N) = RB_TREE_MIN(T); (N); \
  54         (N) = rb_tree_iterate((T), (N), RB_DIR_RIGHT))
  55 #define RB_TREE_FOREACH_SAFE(N, T, TVAR) \
  56     for ((N) = RB_TREE_MIN(T); (N) && ((TVAR) = rb_tree_iterate((T), (N), RB_DIR_RIGHT), 1); \
  57         (N) = (TVAR))
  58 #define RB_TREE_FOREACH_REVERSE(N, T) \
  59     for ((N) = RB_TREE_MAX(T); (N); \
  60         (N) = rb_tree_iterate((T), (N), RB_DIR_LEFT))
  61 #define RB_TREE_FOREACH_REVERSE_SAFE(N, T, TVAR) \
  62     for ((N) = RB_TREE_MAX(T); (N) && ((TVAR) = rb_tree_iterate((T), (N), RB_DIR_LEFT), 1); \
  63         (N) = (TVAR))
  64
  65
  66 /*
  67  * rbto_compare_nodes_fn:
  68  *      return a positive value if the first node > the second node.
  69  *      return a negative value if the first node < the second node.
  70  *      return 0 if they are considered same.
  71  *
  72  * rbto_compare_key_fn:
  73  *      return a positive value if the node > the key.
  74  *      return a negative value if the node < the key.
  75  *      return 0 if they are considered same.
  76  */
  77
  78 typedef signed int (*rbto_compare_nodes_fn)(void *, const void *, const void *);
  79 typedef signed int (*rbto_compare_key_fn)(void *, const void *, const void *);
  80
  81 typedef struct {
  82         rbto_compare_nodes_fn rbto_compare_nodes;
  83         rbto_compare_key_fn rbto_compare_key;
  84         size_t rbto_node_offset;
  85         void *rbto_context;
  86 } rb_tree_ops_t;
  87
  88 //Begin-Libc
  89 #ifdef _RBTREE_NO_OPAQUE_STRUCTS_
  90 typedef struct rb_node rb_node_t;
  91 typedef struct rb_tree rb_tree_t;
  92 #else
  93 //End-Libc
  94 typedef struct rb_node { void * opaque[3]; } rb_node_t;
  95 typedef struct rb_tree { void *opaque[8]; } rb_tree_t;
  96 //Begin-Libc
  97 #endif
  98 //End-Libc
  99
 100 #define _rb_availability __OSX_AVAILABLE_STARTING(__MAC_10_9,__IPHONE_7_0);
 101 void    rb_tree_init(rb_tree_t *, const rb_tree_ops_t *) _rb_availability;
 102 void *  rb_tree_insert_node(rb_tree_t *, void *) _rb_availability;
 103 void *  rb_tree_find_node(rb_tree_t *, const void *) _rb_availability;
 104 void *  rb_tree_find_node_geq(rb_tree_t *, const void *) _rb_availability;
 105 void *  rb_tree_find_node_leq(rb_tree_t *, const void *) _rb_availability;
 106 void    rb_tree_remove_node(rb_tree_t *, void *) _rb_availability;
 107 void *  rb_tree_iterate(rb_tree_t *, void *, const unsigned int) _rb_availability;
 108 size_t  rb_tree_count(rb_tree_t *) _rb_availability;
 109 #undef _rb_availability
 110
 111 __END_DECLS
 112
 113 #endif  /* _SYS_RBTREE_H_*/