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_REVERSE(N, T) \
  56     for ((N) = RB_TREE_MAX(T); (N); \
  57         (N) = rb_tree_iterate((T), (N), RB_DIR_LEFT))
  58
  59 /*
  60  * rbto_compare_nodes_fn:
  61  *      return a positive value if the first node > the second node.
  62  *      return a negative value if the first node < the second node.
  63  *      return 0 if they are considered same.
  64  *
  65  * rbto_compare_key_fn:
  66  *      return a positive value if the node > the key.
  67  *      return a negative value if the node < the key.
  68  *      return 0 if they are considered same.
  69  */
  70
  71 typedef signed int (*rbto_compare_nodes_fn)(void *, const void *, const void *);
  72 typedef signed int (*rbto_compare_key_fn)(void *, const void *, const void *);
  73
  74 typedef struct {
  75         rbto_compare_nodes_fn rbto_compare_nodes;
  76         rbto_compare_key_fn rbto_compare_key;
  77         size_t rbto_node_offset;
  78         void *rbto_context;
  79 } rb_tree_ops_t;
  80
  81 //Begin-Libc
  82 #ifdef _RBTREE_NO_OPAQUE_STRUCTS_
  83 typedef struct rb_node rb_node_t;
  84 typedef struct rb_tree rb_tree_t;
  85 #else
  86 //End-Libc
  87 typedef struct rb_node { void * opaque[3]; } rb_node_t;
  88 typedef struct rb_tree { void *opaque[8]; } rb_tree_t;
  89 //Begin-Libc
  90 #endif
  91 //End-Libc
  92
  93 #define _rb_availability __OSX_AVAILABLE_STARTING(__MAC_10_9,__IPHONE_7_0);
  94 void    rb_tree_init(rb_tree_t *, const rb_tree_ops_t *) _rb_availability;
  95 void *  rb_tree_insert_node(rb_tree_t *, void *) _rb_availability;
  96 void *  rb_tree_find_node(rb_tree_t *, const void *) _rb_availability;
  97 void *  rb_tree_find_node_geq(rb_tree_t *, const void *) _rb_availability;
  98 void *  rb_tree_find_node_leq(rb_tree_t *, const void *) _rb_availability;
  99 void    rb_tree_remove_node(rb_tree_t *, void *) _rb_availability;
 100 void *  rb_tree_iterate(rb_tree_t *, void *, const unsigned int) _rb_availability;
 101 size_t  rb_tree_count(rb_tree_t *) _rb_availability;
 102 #undef _rb_availability
 103
 104 __END_DECLS
 105
 106 #endif  /* _SYS_RBTREE_H_*/