1 /* Sequential list data type implemented by a binary tree.
2 Copyright (C) 2006 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2, or (at your option)
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
19 /* Common code of gl_avltree_list.c and gl_avltreehash_list.c. */
21 /* An AVL tree is a binary tree where
22 1. The height of each node is calculated as
23 heightof(node) = 1 + max (heightof(node.left), heightof(node.right)).
24 2. The heights of the subtrees of each node differ by at most 1:
25 | heightof(right) - heightof(left) | <= 1.
26 3. The index of the elements in the node.left subtree are smaller than
28 The index of the elements in the node.right subtree are larger than
32 /* -------------------------- gl_list_t Data Type -------------------------- */
34 /* Concrete list node implementation, valid for this file only. */
35 struct gl_list_node_impl
38 struct gl_hash_entry h; /* hash table entry fields; must be first */
40 struct gl_list_node_impl *left; /* left branch, or NULL */
41 struct gl_list_node_impl *right; /* right branch, or NULL */
42 /* Parent pointer, or NULL. The parent pointer is not needed for most
43 operations. It is needed so that a gl_list_node_t can be returned
44 without memory allocation, on which the functions gl_list_remove_node,
45 gl_list_add_before, gl_list_add_after can be implemented. */
46 struct gl_list_node_impl *parent;
47 int balance; /* heightof(right) - heightof(left),
48 always = -1 or 0 or 1 */
49 size_t branch_size; /* number of nodes in this branch,
50 = branchsize(left)+branchsize(right)+1 */
54 /* Concrete gl_list_impl type, valid for this file only. */
57 struct gl_list_impl_base base;
59 /* A hash table: managed as an array of collision lists. */
60 struct gl_hash_entry **table;
63 struct gl_list_node_impl *root; /* root node or NULL */
66 /* An AVL tree of height h has at least F_(h+2) [Fibonacci number] and at most
67 2^h - 1 elements. So, h <= 84 (because a tree of height h >= 85 would have
68 at least F_87 elements, and because even on 64-bit machines,
69 sizeof (gl_list_node_impl) * F_87 > 2^64
70 this would exceed the address space of the machine. */