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
  32 #ifndef ARCHIVE_RB_H_INCLUDED
  33 #define ARCHIVE_RB_H_INCLUDED
  34
  35 struct archive_rb_node {
  36         struct archive_rb_node *rb_nodes[2];
  37         /*
  38          * rb_info contains the two flags and the parent back pointer.
  39          * We put the two flags in the low two bits since we know that
  40          * rb_node will have an alignment of 4 or 8 bytes.
  41          */
  42         uintptr_t rb_info;
  43 };
  44
  45 #define ARCHIVE_RB_DIR_LEFT             0
  46 #define ARCHIVE_RB_DIR_RIGHT            1
  47
  48 #define ARCHIVE_RB_TREE_MIN(T) \
  49     __archive_rb_tree_iterate((T), NULL, ARCHIVE_RB_DIR_LEFT)
  50 #define ARCHIVE_RB_TREE_MAX(T) \
  51     __archive_rb_tree_iterate((T), NULL, ARCHIVE_RB_DIR_RIGHT)
  52 #define ARCHIVE_RB_TREE_NEXT(T, N) \
  53     __archive_rb_tree_iterate((T), (N), ARCHIVE_RB_DIR_RIGHT)
  54 #define ARCHIVE_RB_TREE_PREV(T, N) \
  55     __archive_rb_tree_iterate((T), (N), ARCHIVE_RB_DIR_LEFT)
  56 #define ARCHIVE_RB_TREE_FOREACH(N, T) \
  57     for ((N) = ARCHIVE_RB_TREE_MIN(T); (N); \
  58         (N) = ARCHIVE_RB_TREE_NEXT((T), (N)))
  59 #define ARCHIVE_RB_TREE_FOREACH_REVERSE(N, T) \
  60     for ((N) = ARCHIVE_RB_TREE_MAX(T); (N); \
  61         (N) = ARCHIVE_RB_TREE_PREV((T), (N)))
  62 #define ARCHIVE_RB_TREE_FOREACH_SAFE(N, T, S) \
  63     for ((N) = ARCHIVE_RB_TREE_MIN(T); \
  64         (N) && ((S) = ARCHIVE_RB_TREE_NEXT((T), (N)), 1); \
  65         (N) = (S))
  66 #define ARCHIVE_RB_TREE_FOREACH_REVERSE_SAFE(N, T, S) \
  67     for ((N) = ARCHIVE_RB_TREE_MAX(T); \
  68         (N) && ((S) = ARCHIVE_RB_TREE_PREV((T), (N)), 1); \
  69         (N) = (S))
  70
  71 /*
  72  * archive_rbto_compare_nodes_fn:
  73  *      return a positive value if the first node < the second node.
  74  *      return a negative value if the first node > the second node.
  75  *      return 0 if they are considered same.
  76  *
  77  * archive_rbto_compare_key_fn:
  78  *      return a positive value if the node < the key.
  79  *      return a negative value if the node > the key.
  80  *      return 0 if they are considered same.
  81  */
  82
  83 typedef signed int (*const archive_rbto_compare_nodes_fn)(const struct archive_rb_node *,
  84     const struct archive_rb_node *);
  85 typedef signed int (*const archive_rbto_compare_key_fn)(const struct archive_rb_node *,
  86     const void *);
  87
  88 struct archive_rb_tree_ops {
  89         archive_rbto_compare_nodes_fn rbto_compare_nodes;
  90         archive_rbto_compare_key_fn rbto_compare_key;
  91 };
  92
  93 struct archive_rb_tree {
  94         struct archive_rb_node *rbt_root;
  95         const struct archive_rb_tree_ops *rbt_ops;
  96 };
  97
  98 void    __archive_rb_tree_init(struct archive_rb_tree *,
  99     const struct archive_rb_tree_ops *);
 100 int     __archive_rb_tree_insert_node(struct archive_rb_tree *,
 101     struct archive_rb_node *);
 102 struct archive_rb_node  *
 103         __archive_rb_tree_find_node(struct archive_rb_tree *, const void *);
 104 struct archive_rb_node  *
 105         __archive_rb_tree_find_node_geq(struct archive_rb_tree *, const void *);
 106 struct archive_rb_node  *
 107         __archive_rb_tree_find_node_leq(struct archive_rb_tree *, const void *);
 108 void    __archive_rb_tree_remove_node(struct archive_rb_tree *, struct archive_rb_node *);
 109 struct archive_rb_node *
 110         __archive_rb_tree_iterate(struct archive_rb_tree *,
 111         struct archive_rb_node *, const unsigned int);
 112
 113 #endif  /* ARCHIVE_RB_H_*/