Mercurial > hg > octave-kai > gnulib-hg

annotate lib/gl_anytree_list1.h @ 17476:6057744acd2c default tip master

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
autoupdate
author Karl Berry <karl@freefriends.org>
date Fri, 16 Aug 2013 06:32:22 -0700
parents e542fd46ad6f
children
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: 7405
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: 7405
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: 7405
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: 7405
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, gl_rbtree_list.c,
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
19 gl_avltreehash_list.c, gl_rbtreehash_list.c. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
20
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
21 /* An item on the stack used for iterating across the elements. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
22 typedef struct
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
23 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
24 gl_list_node_t node;
7405
0de49c40e105 Add searching operations, limited to a subsequence of the list.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
25 size_t rightp;
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
26 } iterstack_item_t;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
27
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
28 /* A stack used for iterating across the elements. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
29 typedef iterstack_item_t iterstack_t[MAXHEIGHT];
12445
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
30
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
31 /* Free a non-empty subtree recursively.
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
32 This function is recursive and therefore not very fast. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
33 static void
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
34 free_subtree (gl_list_node_t node)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
35 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
36 if (node->left != NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
37 free_subtree (node->left);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
38 if (node->right != NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
39 free_subtree (node->right);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
40 free (node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
41 }