contrib/libarchive/libarchive/archive_rb.h

   1 /*-
   2  * Copyright (c) 2001 The NetBSD Foundation, Inc.
   3  * All rights reserved.
   4  *
   5  * This code is derived from software contributed to The NetBSD Foundation
   6  * by Matt Thomas <matt@3am-software.com>.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  18  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  19  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  20  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  21  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  22  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  23  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  25  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  27  * POSSIBILITY OF SUCH DAMAGE.
  28  *
  29  * Based on NetBSD: rb.h,v 1.13 2009/08/16 10:57:01 yamt Exp
  30  */
  31 #ifndef ARCHIVE_RB_H_
  32 #define ARCHIVE_RB_H_
  33
  34 struct archive_rb_node {
  35         struct archive_rb_node *rb_nodes[2];
  36         /*
  37          * rb_info contains the two flags and the parent back pointer.
  38          * We put the two flags in the low two bits since we know that
  39          * rb_node will have an alignment of 4 or 8 bytes.
  40          */
  41         uintptr_t rb_info;
  42 };
  43
  44 #define ARCHIVE_RB_DIR_LEFT             0
  45 #define ARCHIVE_RB_DIR_RIGHT            1
  46
  47 #define ARCHIVE_RB_TREE_MIN(T) \
  48     __archive_rb_tree_iterate((T), NULL, ARCHIVE_RB_DIR_LEFT)
  49 #define ARCHIVE_RB_TREE_MAX(T) \
  50     __archive_rb_tree_iterate((T), NULL, ARCHIVE_RB_DIR_RIGHT)
  51 #define ARCHIVE_RB_TREE_FOREACH(N, T) \
  52     for ((N) = ARCHIVE_RB_TREE_MIN(T); (N); \
  53         (N) = __archive_rb_tree_iterate((T), (N), ARCHIVE_RB_DIR_RIGHT))
  54 #define ARCHIVE_RB_TREE_FOREACH_REVERSE(N, T) \
  55     for ((N) = ARCHIVE_RB_TREE_MAX(T); (N); \
  56         (N) = __archive_rb_tree_iterate((T), (N), ARCHIVE_RB_DIR_LEFT))
  57
  58 /*
  59  * archive_rbto_compare_nodes_fn:
  60  *      return a positive value if the first node < the second node.
  61  *      return a negative value if the first node > the second node.
  62  *      return 0 if they are considered same.
  63  *
  64  * archive_rbto_compare_key_fn:
  65  *      return a positive value if the node < the key.
  66  *      return a negative value if the node > the key.
  67  *      return 0 if they are considered same.
  68  */
  69
  70 typedef signed int (*const archive_rbto_compare_nodes_fn)(const struct archive_rb_node *,
  71     const struct archive_rb_node *);
  72 typedef signed int (*const archive_rbto_compare_key_fn)(const struct archive_rb_node *,
  73     const void *);
  74
  75 struct archive_rb_tree_ops {
  76         archive_rbto_compare_nodes_fn rbto_compare_nodes;
  77         archive_rbto_compare_key_fn rbto_compare_key;
  78 };
  79
  80 struct archive_rb_tree {
  81         struct archive_rb_node *rbt_root;
  82         const struct archive_rb_tree_ops *rbt_ops;
  83 };
  84
  85 void    __archive_rb_tree_init(struct archive_rb_tree *,
  86     const struct archive_rb_tree_ops *);
  87 int     __archive_rb_tree_insert_node(struct archive_rb_tree *,
  88     struct archive_rb_node *);
  89 struct archive_rb_node  *
  90         __archive_rb_tree_find_node(struct archive_rb_tree *, const void *);
  91 struct archive_rb_node  *
  92         __archive_rb_tree_find_node_geq(struct archive_rb_tree *, const void *);
  93 struct archive_rb_node  *
  94         __archive_rb_tree_find_node_leq(struct archive_rb_tree *, const void *);
  95 void    __archive_rb_tree_remove_node(struct archive_rb_tree *, struct archive_rb_node *);
  96 struct archive_rb_node *
  97         __archive_rb_tree_iterate(struct archive_rb_tree *,
  98         struct archive_rb_node *, const unsigned int);
  99
 100 #endif  /* ARCHIVE_RB_H_*/