octave-nkf/gnulib-hg: lib/gl_anytree

annotate lib/gl_anytree_oset.h @ 17605:23cb5b2fd95b

relocatable-perl: like relocatable-script, but for Perl scripts * build-aux/relocatable.pl.in: Add. * doc/relocatable-maint.texi: Add documentation. * modules/relocatable-perl: Add.

author	Reuben Thomas <rrt@sc3d.org>
date	Thu, 09 Jan 2014 22:31:42 +0000
parents	344018b6e5d7
children	ab58d4870664

rev	line source
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1 /* Ordered set data type implemented by a binary tree.
17587 344018b6e5d7 maint: update copyright Eric Blake <eblake@redhat.com> parents: 17249 diff changeset	2 Copyright (C) 2006-2007, 2009-2014 Free Software Foundation, Inc.
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	3 Written by Bruno Haible <bruno@clisp.org>, 2006.
c7d0a3879b08 Common code of several ordered 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: 8436 diff changeset	5 This program is free software: you can redistribute it and/or modify
6974 c7d0a3879b08 Common code of several ordered 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: 8436 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: 8436 diff changeset	8 (at your option) any later version.
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	9
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	10 This program is distributed in the hope that it will be useful,
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	11 but WITHOUT ANY WARRANTY; without even the implied warranty of
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	13 GNU General Public License for more details.
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	14
c7d0a3879b08 Common code of several ordered 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: 8436 diff changeset	16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	17
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	18 /* Common code of gl_avltree_oset.c and gl_rbtree_oset.c. */
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	19
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	20 /* An item on the stack used for iterating across the elements. */
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	21 typedef struct
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	22 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	23 gl_oset_node_t node;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	24 bool rightp;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	25 } iterstack_item_t;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	26
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	27 /* A stack used for iterating across the elements. */
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	28 typedef iterstack_item_t iterstack_t[MAXHEIGHT];
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	29
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	30 static gl_oset_t
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	31 gl_tree_nx_create_empty (gl_oset_implementation_t implementation,
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	32 gl_setelement_compar_fn compar_fn,
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	33 gl_setelement_dispose_fn dispose_fn)
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	34 {
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	35 struct gl_oset_impl *set =
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	36 (struct gl_oset_impl *) malloc (sizeof (struct gl_oset_impl));
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	37
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	38 if (set == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	39 return NULL;
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	40
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	41 set->base.vtable = implementation;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	42 set->base.compar_fn = compar_fn;
8436 36bbb949160c Add an element disposal function. Bruno Haible <bruno@clisp.org> parents: 7645 diff changeset	43 set->base.dispose_fn = dispose_fn;
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	44 set->root = NULL;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	45 set->count = 0;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	46
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	47 return set;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	48 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	49
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	50 static size_t
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	51 gl_tree_size (gl_oset_t set)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	52 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	53 return set->count;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	54 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	55
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	56 static bool
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	57 gl_tree_search (gl_oset_t set, const void *elt)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	58 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	59 gl_setelement_compar_fn compar = set->base.compar_fn;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	60 gl_oset_node_t node;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	61
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	62 for (node = set->root; node != NULL; )
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	63 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	64 int cmp = (compar != NULL
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	65 ? compar (node->value, elt)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	66 : (node->value > elt ? 1 :
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	67 node->value < elt ? -1 : 0));
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	68
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	69 if (cmp < 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	70 node = node->right;
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	71 else if (cmp > 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	72 node = node->left;
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	73 else /* cmp == 0 */
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	74 /* We have an element equal to ELT. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	75 return true;
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	76 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	77 return false;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	78 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	79
7403 2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	80 static bool
2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	81 gl_tree_search_atleast (gl_oset_t set,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	82 gl_setelement_threshold_fn threshold_fn,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	83 const void *threshold,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	84 const void **eltp)
7403 2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	85 {
2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	86 gl_oset_node_t node;
2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	87
2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	88 for (node = set->root; node != NULL; )
2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	89 {
2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	90 if (! threshold_fn (node->value, threshold))
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	91 node = node->right;
7403 2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	92 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	93 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	94 /* We have an element >= VALUE. But we need the leftmost such
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	95 element. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	96 gl_oset_node_t found = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	97 node = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	98 for (; node != NULL; )
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	99 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	100 if (! threshold_fn (node->value, threshold))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	101 node = node->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	102 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	103 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	104 found = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	105 node = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	106 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	107 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	108 *eltp = found->value;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	109 return true;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	110 }
7403 2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	111 }
2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	112 return false;
2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	113 }
2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	114
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	115 static gl_oset_node_t
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	116 gl_tree_search_node (gl_oset_t set, const void *elt)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	117 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	118 gl_setelement_compar_fn compar = set->base.compar_fn;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	119 gl_oset_node_t node;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	120
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	121 for (node = set->root; node != NULL; )
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	122 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	123 int cmp = (compar != NULL
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	124 ? compar (node->value, elt)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	125 : (node->value > elt ? 1 :
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	126 node->value < elt ? -1 : 0));
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	127
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	128 if (cmp < 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	129 node = node->right;
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	130 else if (cmp > 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	131 node = node->left;
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	132 else /* cmp == 0 */
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	133 /* We have an element equal to ELT. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	134 return node;
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	135 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	136 return NULL;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	137 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	138
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	139 static int
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	140 gl_tree_nx_add (gl_oset_t set, const void *elt)
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	141 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	142 gl_setelement_compar_fn compar;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	143 gl_oset_node_t node = set->root;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	144
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	145 if (node == NULL)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	146 {
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	147 if (gl_tree_nx_add_first (set, elt) == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	148 return -1;
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	149 return true;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	150 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	151
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	152 compar = set->base.compar_fn;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	153
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	154 for (;;)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	155 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	156 int cmp = (compar != NULL
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	157 ? compar (node->value, elt)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	158 : (node->value > elt ? 1 :
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	159 node->value < elt ? -1 : 0));
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	160
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	161 if (cmp < 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	162 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	163 if (node->right == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	164 {
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	165 if (gl_tree_nx_add_after (set, node, elt) == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	166 return -1;
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	167 return true;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	168 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	169 node = node->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	170 }
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	171 else if (cmp > 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	172 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	173 if (node->left == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	174 {
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	175 if (gl_tree_nx_add_before (set, node, elt) == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	176 return -1;
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	177 return true;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	178 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	179 node = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	180 }
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	181 else /* cmp == 0 */
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	182 return false;
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	183 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	184 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	185
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	186 static bool
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	187 gl_tree_remove (gl_oset_t set, const void *elt)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	188 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	189 gl_oset_node_t node = gl_tree_search_node (set, elt);
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	190
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	191 if (node != NULL)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	192 return gl_tree_remove_node (set, node);
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	193 else
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	194 return false;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	195 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	196
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	197 static void
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	198 gl_tree_oset_free (gl_oset_t set)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	199 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	200 /* Iterate across all elements in post-order. */
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	201 gl_oset_node_t node = set->root;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	202 iterstack_t stack;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	203 iterstack_item_t *stack_ptr = &stack[0];
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	204
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	205 for (;;)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	206 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	207 /* Descend on left branch. */
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	208 for (;;)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	209 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	210 if (node == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	211 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	212 stack_ptr->node = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	213 stack_ptr->rightp = false;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	214 node = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	215 stack_ptr++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	216 }
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	217 /* Climb up again. */
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	218 for (;;)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	219 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	220 if (stack_ptr == &stack[0])
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	221 goto done_iterate;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	222 stack_ptr--;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	223 node = stack_ptr->node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	224 if (!stack_ptr->rightp)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	225 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	226 /* Free the current node. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	227 if (set->base.dispose_fn != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	228 set->base.dispose_fn (node->value);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	229 free (node);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	230 }
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	231 /* Descend on right branch. */
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	232 stack_ptr->rightp = true;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	233 node = node->right;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	234 stack_ptr++;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	235 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	236 done_iterate:
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	237 free (set);
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	238 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	239
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	240 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	241
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	242 static gl_oset_iterator_t
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	243 gl_tree_iterator (gl_oset_t set)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	244 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	245 gl_oset_iterator_t result;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	246 gl_oset_node_t node;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	247
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	248 result.vtable = set->base.vtable;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	249 result.set = set;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	250 /* Start node is the leftmost node. */
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	251 node = set->root;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	252 if (node != NULL)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	253 while (node->left != NULL)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	254 node = node->left;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	255 result.p = node;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	256 /* End point is past the rightmost node. */
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	257 result.q = NULL;
7352 3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 6974 diff changeset	258 #ifdef lint
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 6974 diff changeset	259 result.i = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 6974 diff changeset	260 result.j = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 6974 diff changeset	261 result.count = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 6974 diff changeset	262 #endif
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	263
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	264 return result;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	265 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	266
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	267 static bool
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	268 gl_tree_iterator_next (gl_oset_iterator_t iterator, const void *eltp)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	269 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	270 if (iterator->p != iterator->q)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	271 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	272 gl_oset_node_t node = (gl_oset_node_t) iterator->p;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	273 *eltp = node->value;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	274 /* Advance to the next node. */
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	275 if (node->right != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	276 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	277 node = node->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	278 while (node->left != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	279 node = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	280 }
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	281 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	282 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	283 while (node->parent != NULL && node->parent->right == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	284 node = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	285 node = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	286 }
6974 c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	287 iterator->p = node;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	288 return true;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	289 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	290 else
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	291 return false;
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	292 }
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	293
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	294 static void
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	295 gl_tree_iterator_free (gl_oset_iterator_t *iterator)
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	296 {
c7d0a3879b08 Common code of several ordered list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	297 }

Mercurial > hg > octave-nkf > gnulib-hg

annotate lib/gl_anytree_oset.h @ 17605:23cb5b2fd95b