1 /* ----------------------------------------------------------------------- * 2 * 3 * Copyright 1996-2009 The NASM Authors - All Rights Reserved 4 * See the file AUTHORS included with the NASM distribution for 5 * the specific copyright holders. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following 9 * conditions are met: 10 * 11 * * Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * * Redistributions in binary form must reproduce the above 14 * copyright notice, this list of conditions and the following 15 * disclaimer in the documentation and/or other materials provided 16 * with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 19 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, 20 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 21 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 22 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 25 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 26 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 28 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 29 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 30 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 * 32 * ----------------------------------------------------------------------- */ 33 34 #ifndef NASM_RBTREE_H 35 #define NASM_RBTREE_H 36 37 #include <inttypes.h> 38 #include <stdbool.h> 39 40 /* This structure should be embedded in a larger data structure; 41 the final output from rb_search() can then be converted back 42 to the larger data structure via container_of(). */ 43 struct rbtree { 44 uint64_t key; 45 struct rbtree *left, *right; 46 bool red; 47 }; 48 49 struct rbtree *rb_insert(struct rbtree *, struct rbtree *); 50 struct rbtree *rb_search(struct rbtree *, uint64_t); 51 void rb_destroy(struct rbtree *); 52 53 #endif /* NASM_RBTREE_H */ 54
