summaryrefslogtreecommitdiffstats
path: root/filter/tree.c
blob: ea1f18f234a7a3905c87ebae5213871cb03032bd (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/*
 *	Filters: utility functions
 *
 *	Copyright 1998 Pavel Machek <pavel@ucw.cz>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/signal.h>
#include <setjmp.h>

#include "nest/bird.h"
#include "lib/lists.h"
#include "lib/resource.h"
#include "lib/socket.h"
#include "nest/route.h"
#include "nest/protocol.h"
#include "nest/iface.h"
#include "conf/conf.h"
#include "filter/filter.h"

/* Finds n-th item in list linked by right. Trashes pointers in right. */
static struct f_tree *
find_nth(struct f_tree *from, int nth)
{
  struct f_tree *pivot;
  int lcount = 0, rcount = 0;
  struct f_tree *left, *right, *next;

  pivot = from;

  left = right = NULL;
  next = from->right;
  while (from = next) {
    next = from->right;
    if (val_compare(pivot->from, from->from)==1) {
      from->right = left;
      left = from;
      lcount++;
    } else {
      from->right = right;
      right = from;
      rcount++;
    }
  }
  if (lcount == nth) 
    return pivot;
  if (lcount < nth)
    return find_nth(right, nth-lcount-1);
  return find_nth(left, nth);
}

/* Gets list linked by left, finds its median, trashes pointers in right */
static struct f_tree *
find_median(struct f_tree *from)
{
  struct f_tree *t = from;
  int cnt = 0;

  if (!from)
    return NULL;
  do {
    t->right = t->left;
    cnt++;
  } while (t = t->left);
  return find_nth(from, cnt/2);
}

struct f_tree *
find_tree(struct f_tree *t, struct f_val val)
{
  if (!t)
    return 0;
  if ((val_compare(t->from, val) != 1) &&
      (val_compare(t->to, val) != -1))
    return t;
  if (val_compare(t->from, val) == -1)
    return find_tree(t->right, val);
  else
    return find_tree(t->left, val);
}

/* Gets list linked by left */
struct f_tree *
build_tree(struct f_tree *from)
{
  struct f_tree *median, *t = from, *next, *left = NULL, *right = NULL;

  median = find_median(from);
  if (!median)
    return NULL;

  do {
    next = t->left;
    if (t == median)
      continue;

    if (val_compare(median->from, t->from)==1) {
      t->left = left;
      left = t;
    } else {
      t->left = right;
      right = t;
    }
  } while(t = next);

  median->left = build_tree(left);
  median->right = build_tree(right);
  return median;
}

struct f_tree *
f_new_tree(void)
{
  struct f_tree * ret;
  ret = cfg_alloc(sizeof(struct f_tree));
  ret->left = ret->right = NULL;
  ret->from.type = ret->to.type = T_VOID;
  ret->from.val.i = ret->to.val.i = 0;
  ret->data = NULL;
  return ret;
}