/* Sequential list data type implemented by a binary tree.
- Copyright (C) 2006 Free Software Foundation, Inc.
+ Copyright (C) 2006, 2009-2013 Free Software Foundation, Inc.
Written by Bruno Haible <bruno@clisp.org>, 2006.
- This program is free software; you can redistribute it and/or modify
+ 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 2, or (at your option)
- any later version.
+ 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
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, write to the Free Software Foundation,
- Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
/* Common code of gl_avltree_list.c and gl_avltreehash_list.c. */
/* An AVL tree is a binary tree where
1. The height of each node is calculated as
- heightof(node) = 1 + max (heightof(node.left), heightof(node.right)).
+ heightof(node) = 1 + max (heightof(node.left), heightof(node.right)).
2. The heights of the subtrees of each node differ by at most 1:
- | heightof(right) - heightof(left) | <= 1.
+ | heightof(right) - heightof(left) | <= 1.
3. The index of the elements in the node.left subtree are smaller than
the index of node.
The index of the elements in the node.right subtree are larger than
gl_list_add_before, gl_list_add_after can be implemented. */
struct gl_list_node_impl *parent;
int balance; /* heightof(right) - heightof(left),
- always = -1 or 0 or 1 */
+ always = -1 or 0 or 1 */
size_t branch_size; /* number of nodes in this branch,
- = branchsize(left)+branchsize(right)+1 */
+ = branchsize(left)+branchsize(right)+1 */
const void *value;
};