Mercurial > hg > octave-nkf > gnulib-hg

annotate lib/gl_anyavltree_list1.h @ 17249:e542fd46ad6f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
maint: update all copyright year number ranges Run "make update-copyright". Compare to commit 1602f0a from last year. Signed-off-by: Eric Blake <eblake@redhat.com>
author Eric Blake <eblake@redhat.com>
date Tue, 01 Jan 2013 00:50:58 +0000
parents 8250f2777afc
children 344018b6e5d7
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
1 /* Sequential list data type implemented by a binary tree.
17249
e542fd46ad6f maint: update all copyright year number ranges
Eric Blake <eblake@redhat.com>
parents: 16201
diff changeset
2 Copyright (C) 2006, 2009-2013 Free Software Foundation, Inc.
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
4
9309
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
5 This program is free software: you can redistribute it and/or modify
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
6 it under the terms of the GNU General Public License as published by
9309
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
7 the Free Software Foundation; either version 3 of the License, or
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
8 (at your option) any later version.
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
9
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
10 This program is distributed in the hope that it will be useful,
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
13 GNU General Public License for more details.
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
14
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
15 You should have received a copy of the GNU General Public License
9309
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
17
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
18 /* Common code of gl_avltree_list.c and gl_avltreehash_list.c. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
19
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
20 /* An AVL tree is a binary tree where
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
21 1. The height of each node is calculated as
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
22 heightof(node) = 1 + max (heightof(node.left), heightof(node.right)).
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
23 2. The heights of the subtrees of each node differ by at most 1:
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
24 | heightof(right) - heightof(left) | <= 1.
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
25 3. The index of the elements in the node.left subtree are smaller than
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
26 the index of node.
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
27 The index of the elements in the node.right subtree are larger than
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
28 the index of node.
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
29 */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
30
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
31 /* -------------------------- gl_list_t Data Type -------------------------- */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
32
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
33 /* Concrete list node implementation, valid for this file only. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
34 struct gl_list_node_impl
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
35 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
36 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
37 struct gl_hash_entry h; /* hash table entry fields; must be first */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
38 #endif
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
39 struct gl_list_node_impl *left; /* left branch, or NULL */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
40 struct gl_list_node_impl *right; /* right branch, or NULL */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
41 /* Parent pointer, or NULL. The parent pointer is not needed for most
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
42 operations. It is needed so that a gl_list_node_t can be returned
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
43 without memory allocation, on which the functions gl_list_remove_node,
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
44 gl_list_add_before, gl_list_add_after can be implemented. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
45 struct gl_list_node_impl *parent;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
46 int balance; /* heightof(right) - heightof(left),
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
47 always = -1 or 0 or 1 */
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
48 size_t branch_size; /* number of nodes in this branch,
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
49 = branchsize(left)+branchsize(right)+1 */
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
50 const void *value;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
51 };
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
52
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
53 /* Concrete gl_list_impl type, valid for this file only. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
54 struct gl_list_impl
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
55 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
56 struct gl_list_impl_base base;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
57 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
58 /* A hash table: managed as an array of collision lists. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
59 struct gl_hash_entry **table;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
60 size_t table_size;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
61 #endif
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
62 struct gl_list_node_impl *root; /* root node or NULL */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
63 };
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
64
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
65 /* An AVL tree of height h has at least F_(h+2) [Fibonacci number] and at most
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
66 2^h - 1 elements. So, h <= 84 (because a tree of height h >= 85 would have
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
67 at least F_87 elements, and because even on 64-bit machines,
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
68 sizeof (gl_list_node_impl) * F_87 > 2^64
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
69 this would exceed the address space of the machine. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
70 #define MAXHEIGHT 83