← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/m4/gutsy

« back to all changes in this revision

Viewing changes to lib/gl_anytree_oset.h

  • Committer: Bazaar Package Importer
  • Author(s): Santiago Vila
  • Date: 2006-11-29 16:53:44 UTC
  • Revision ID: james.westby@ubuntu.com-20061129165344-0qimyyyhh135a7mf
Tags: 1.4.8-1
New upstream release. Lots of fixes, see the NEWS file for details.

Show diffs side-by-side

added added

removed removed

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