Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / filter / tree.c @ 6b3f1a54

History | View | Annotate | Download (3.51 KB)

1
/*
2
 *        Filters: utility functions
3
 *
4
 *        Copyright 1998 Pavel Machek <pavel@ucw.cz>
5
 *
6
 *        Can be freely distributed and used under the terms of the GNU GPL.
7
 */
8

    
9
#include "lib/alloca.h"
10
#include "nest/bird.h"
11
#include "conf/conf.h"
12
#include "filter/filter.h"
13

    
14
/**
15
 * find_tree
16
 * @t: tree to search in
17
 * @val: value to find
18
 *
19
 * Search for given value in the tree. I relies on fact that sorted tree is populated
20
 * by &f_val structures (that can be compared by val_compare()). In each node of tree, 
21
 * either single value (then t->from==t->to) or range is present.
22
 *
23
 * Both set matching and |switch() { }| construction is implemented using this function,
24
 * thus both are as fast as they can be.
25
 */
26
struct f_tree *
27
find_tree(struct f_tree *t, struct f_val val)
28
{
29
  if (!t)
30
    return NULL;
31
  if ((val_compare(t->from, val) != 1) &&
32
      (val_compare(t->to, val) != -1))
33
    return t;
34
  if (val_compare(t->from, val) == -1)
35
    return find_tree(t->right, val);
36
  else
37
    return find_tree(t->left, val);
38
}
39

    
40
static struct f_tree *
41
build_tree_rec(struct f_tree **buf, int l, int h)
42
{
43
  struct f_tree *n;
44
  int pos;
45

    
46
  if (l >= h)
47
    return NULL;
48

    
49
  pos = (l+h)/2;
50
  n = buf[pos];
51
  n->left = build_tree_rec(buf, l, pos);
52
  n->right = build_tree_rec(buf, pos+1, h);
53
  return n;
54
}
55

    
56
static int 
57
tree_compare(const void *p1, const void *p2)
58
{
59
  return val_compare((* (struct f_tree **) p1)->from, (* (struct f_tree **) p2)->from);
60
}
61

    
62
/**
63
 * build_tree
64
 * @from: degenerated tree (linked by @tree->left) to be transformed into form suitable for find_tree()
65
 *
66
 * Transforms degenerated tree into balanced tree.
67
 */
68
struct f_tree *
69
build_tree(struct f_tree *from)
70
{
71
  struct f_tree *tmp, *root;
72
  struct f_tree **buf;
73
  int len, i;
74

    
75
  if (from == NULL)
76
    return NULL;
77

    
78
  len = 0;
79
  for (tmp = from; tmp != NULL; tmp = tmp->left)
80
    len++;
81

    
82
  if (len <= 1024)
83
    buf = alloca(len * sizeof(struct f_tree *));
84
  else
85
    buf = xmalloc(len * sizeof(struct f_tree *));
86

    
87
  /* Convert a degenerated tree into an sorted array */
88
  i = 0;
89
  for (tmp = from; tmp != NULL; tmp = tmp->left)
90
    buf[i++] = tmp;
91

    
92
  qsort(buf, len, sizeof(struct f_tree *), tree_compare);
93

    
94
  root = build_tree_rec(buf, 0, len);
95

    
96
  if (len > 1024)
97
    xfree(buf);
98

    
99
  return root;
100
}
101

    
102
struct f_tree *
103
f_new_tree(void)
104
{
105
  struct f_tree * ret;
106
  ret = cfg_alloc(sizeof(struct f_tree));
107
  ret->left = ret->right = NULL;
108
  ret->from.type = ret->to.type = T_VOID;
109
  ret->from.val.i = ret->to.val.i = 0;
110
  ret->data = NULL;
111
  return ret;
112
}
113

    
114
/**
115
 * same_tree
116
 * @t1: first tree to be compared
117
 * @t2: second one
118
 *
119
 * Compares two trees and returns 1 if they are same
120
 */
121
int
122
same_tree(struct f_tree *t1, struct f_tree *t2)
123
{
124
  if ((!!t1) != (!!t2))
125
    return 0;
126
  if (!t1)
127
    return 1;
128
  if (val_compare(t1->from, t2->from))
129
    return 0;
130
  if (val_compare(t1->to, t2->to))
131
    return 0;
132
  if (!same_tree(t1->left, t2->left))
133
    return 0;
134
  if (!same_tree(t1->right, t2->right))
135
    return 0;
136
  if (!i_same(t1->data, t2->data))
137
    return 0;
138
  return 1;
139
}
140

    
141

    
142
static void
143
tree_node_format(struct f_tree *t, buffer *buf)
144
{
145
  if (t == NULL)
146
    return;
147

    
148
  tree_node_format(t->left, buf);
149

    
150
  val_format(t->from, buf);
151
  if (val_compare(t->from, t->to) != 0)
152
  {
153
    buffer_puts(buf, "..");
154
    val_format(t->to, buf);
155
  }
156
  buffer_puts(buf, ", ");
157

    
158
  tree_node_format(t->right, buf);
159
}
160

    
161
void
162
tree_format(struct f_tree *t, buffer *buf)
163
{
164
  buffer_puts(buf, "[");
165

    
166
  tree_node_format(t, buf);
167

    
168
  if (buf->pos == buf->end)
169
    return;
170

    
171
  /* Undo last separator */
172
  if (buf->pos[-1] != '[')
173
    buf->pos -= 2;
174

    
175
  buffer_puts(buf, "]");
176
}