diff options
Diffstat (limited to 'mcastseed/lib/gl_anyrbtree_list1.h')
| -rw-r--r-- | mcastseed/lib/gl_anyrbtree_list1.h | 76 |
1 files changed, 0 insertions, 76 deletions
diff --git a/mcastseed/lib/gl_anyrbtree_list1.h b/mcastseed/lib/gl_anyrbtree_list1.h deleted file mode 100644 index 0ae0715..0000000 --- a/mcastseed/lib/gl_anyrbtree_list1.h +++ /dev/null @@ -1,76 +0,0 @@ -/* Sequential list data type implemented by a binary tree. - Copyright (C) 2006, 2009-2016 Free Software Foundation, Inc. - Written by Bruno Haible <bruno@clisp.org>, 2006. - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. */ - -/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */ - -/* A red-black tree is a binary tree where every node is colored black or - red such that - 1. The root is black. - 2. No red node has a red parent. - Or equivalently: No red node has a red child. - 3. All paths from the root down to any NULL endpoint contain the same - number of black nodes. - Let's call this the "black-height" bh of the tree. It follows that every - such path contains exactly bh black and between 0 and bh red nodes. (The - extreme cases are a path containing only black nodes, and a path colored - alternately black-red-black-red-...-black-red.) The height of the tree - therefore is >= bh, <= 2*bh. - */ - -/* -------------------------- gl_list_t Data Type -------------------------- */ - -/* Color of a node. */ -typedef enum color { BLACK, RED } color_t; - -/* Concrete list node implementation, valid for this file only. */ -struct gl_list_node_impl -{ -#if WITH_HASHTABLE - struct gl_hash_entry h; /* hash table entry fields; must be first */ -#endif - struct gl_list_node_impl *left; /* left branch, or NULL */ - struct gl_list_node_impl *right; /* right branch, or NULL */ - /* Parent pointer, or NULL. The parent pointer is not needed for most - operations. It is needed so that a gl_list_node_t can be returned - without memory allocation, on which the functions gl_list_remove_node, - gl_list_add_before, gl_list_add_after can be implemented. */ - struct gl_list_node_impl *parent; - color_t color; /* node's color */ - size_t branch_size; /* number of nodes in this branch, - = branchsize(left)+branchsize(right)+1 */ - const void *value; -}; - -/* Concrete gl_list_impl type, valid for this file only. */ -struct gl_list_impl -{ - struct gl_list_impl_base base; -#if WITH_HASHTABLE - /* A hash table: managed as an array of collision lists. */ - struct gl_hash_entry **table; - size_t table_size; -#endif - struct gl_list_node_impl *root; /* root node or NULL */ -}; - -/* A red-black tree of height h has a black-height bh >= ceil(h/2) and - therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree - of height h >= 117 would have at least 2^59 - 1 elements, and because even - on 64-bit machines, - sizeof (gl_list_node_impl) * (2^59 - 1) > 2^64 - this would exceed the address space of the machine. */ -#define MAXHEIGHT 116 |