Home | History | Annotate | Line # | Download | only in libarchive 
      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 (at) 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_INCLUDED */
    114