176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ----------------------------------------------------------------------- * 276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Copyright 1996-2009 The NASM Authors - All Rights Reserved 476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * See the file AUTHORS included with the NASM distribution for 576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * the specific copyright holders. 676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Redistribution and use in source and binary forms, with or without 876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * modification, are permitted provided that the following 976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * conditions are met: 1076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 1176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * * Redistributions of source code must retain the above copyright 1276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * notice, this list of conditions and the following disclaimer. 1376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * * Redistributions in binary form must reproduce the above 1476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * copyright notice, this list of conditions and the following 1576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * disclaimer in the documentation and/or other materials provided 1676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * with the distribution. 1776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 1876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 1976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, 2076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 2176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 2276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 2376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 2676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 2876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 2976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 3076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 3276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * ----------------------------------------------------------------------- */ 3376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifndef NASM_RBTREE_H 3576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define NASM_RBTREE_H 3676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <inttypes.h> 3876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stdbool.h> 3976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 4076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* This structure should be embedded in a larger data structure; 4176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman the final output from rb_search() can then be converted back 4276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman to the larger data structure via container_of(). */ 4376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstruct rbtree { 4476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman uint64_t key; 4576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct rbtree *left, *right; 4676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman bool red; 4776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}; 4876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 4976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstruct rbtree *rb_insert(struct rbtree *, struct rbtree *); 5076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstruct rbtree *rb_search(struct rbtree *, uint64_t); 5176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanvoid rb_destroy(struct rbtree *); 5276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 5376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* NASM_RBTREE_H */ 54