projects
/
gnulib.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
fsusage: port to MacOS X 10.7 with 4 TiB file systems
[gnulib.git]
/
lib
/
gl_anyavltree_list1.h
diff --git
a/lib/gl_anyavltree_list1.h
b/lib/gl_anyavltree_list1.h
index
8bf2604
..
c0f1679
100644
(file)
--- a/
lib/gl_anyavltree_list1.h
+++ b/
lib/gl_anyavltree_list1.h
@@
-1,11
+1,11
@@
/* Sequential list data type implemented by a binary tree.
/* Sequential list data type implemented by a binary tree.
- Copyright (C) 2006 Free Software Foundation, Inc.
+ Copyright (C) 2006
, 2009-2011
Free Software Foundation, Inc.
Written by Bruno Haible <bruno@clisp.org>, 2006.
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
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
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
@@
-13,16
+13,15
@@
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
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
/* 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:
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
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
@@
-45,9
+44,9
@@
struct gl_list_node_impl
gl_list_add_before, gl_list_add_after can be implemented. */
struct gl_list_node_impl *parent;
int balance; /* heightof(right) - heightof(left),
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,
size_t branch_size; /* number of nodes in this branch,
- = branchsize(left)+branchsize(right)+1 */
+
= branchsize(left)+branchsize(right)+1 */
const void *value;
};
const void *value;
};