← Back to branch summary

~ubuntu-branches/ubuntu/trusty/syslog-ng/trusty-proposed

« back to all changes in this revision

Viewing changes to lib/ivykis/lib/test/avl.c

  • Committer: Package Import Robot
  • Author(s): Laszlo Boszormenyi (GCS), Gergely Nagy
  • Date: 2011-10-11 14:30:48 UTC
  • mfrom: (1.3.7)
  • Revision ID: package-import@ubuntu.com-20111011143048-r1iljux9xbvj3lwh
Tags: 3.3.1.dfsg-1
http://bugs.debian.org/496521
http://bugs.debian.org/616069
http://bugs.debian.org/630172
http://bugs.debian.org/609154
http://bugs.debian.org/608605
http://bugs.debian.org/644458
http://bugs.debian.org/634715
http://bugs.debian.org/589081
* New upstream release with important fixes from upstream git tree with
  non-free manpages removed.
* Drop syslog-ng.conf(5) (closes: #496521).
* syslog-ng(8) is generated, and does not mention -Q anymore
  (closes: #616069).
* Supports CAP_SYSLOG on recent kernels (closes: #630172).
* Does not use g_timeout_add_seconds anymore (closes: #609154).

[ Gergely Nagy <algernon@madhouse-project.org> ]
* Update debian/copyright to DEP-5 format.
* Simplified the logrotate file by merging identical entries.
* Include local configuration files from /etc/syslog-ng/conf.d/ (Closes:
  #609050).
* Update syslog-ng.conf to be fully 3.3 compliant.
* Compress both source and binaries (except the syslog-ng meta
  package) with xz, instead of gzip.
* Use dpkg triggers to restart syslog-ng when appropriate.
* Include DFSG-free manual pages for all binaries.
* Build with Hardening enabled.
* Mention syslog(3) in /etc/default/syslog-ng, instead of
  <linux/kernel.h> (Closes: #608605)
* Support 'status' in the init script.
  Patch from Peter Eisentraut <petere@debian.org> (Closes: #644458)
* Build-Depend on libevtlog-dev (>= 0.2.12-5~) for correct shlibs.
* Use [linux-any] in Build-Depends instead of hardcoded links.
  (Closes: #634715)
* Use $SYSLOGNG_OPTS in the init script when reloading syslog-ng.
  (Closes: #589081)

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/ivykis/lib/test/avl.c
 
1
/*
 
2
 * ivykis, an event handling library
 
3
 * Copyright (C) 2002, 2003 Lennert Buytenhek
 
4
 * Dedicated to Marija Kulikova.
 
5
 *
 
6
 * This program is free software; you can redistribute it and/or modify
 
7
 * it under the terms of the GNU Lesser General Public License version
 
8
 * 2.1 as published by the Free Software Foundation.
 
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 Lesser General Public License version 2.1 for more details.
 
14
 *
 
15
 * You should have received a copy of the GNU Lesser General Public
 
16
 * License version 2.1 along with this program; if not, write to the
 
17
 * Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
 
18
 * Boston, MA 02110-1301, USA.
 
19
 */
 
20
 
 
21
#include <stdio.h>
 
22
#include <stdlib.h>
 
23
#include <iv.h>
 
24
#include <iv_avl.h>
 
25
#include <iv_list.h>
 
26
#include <sys/types.h>
 
27
#include <time.h>
 
28
#include <unistd.h>
 
29
 
 
30
static void
 
31
tree_node_print(int depth, struct iv_avl_node *an,
 
32
                void (*print)(struct iv_avl_node *an))
 
33
{
 
34
        int i;
 
35
 
 
36
        for (i = 0; i < depth; i++)
 
37
                printf("  ");
 
38
        printf("%p (parent=%p): ", an, an->parent);
 
39
        print(an);
 
40
 
 
41
        if (an->left != NULL)
 
42
                tree_node_print(depth + 1, an->left, print);
 
43
        if (an->right != NULL)
 
44
                tree_node_print(depth + 1, an->right, print);
 
45
}
 
46
 
 
47
static void
 
48
tree_print(char *msg, struct iv_avl_tree *this,
 
49
           void (*print)(struct iv_avl_node *an))
 
50
{
 
51
        printf("%s:\n", msg);
 
52
        if (this->root != NULL)
 
53
                tree_node_print(0, this->root, print);
 
54
        printf("\n");
 
55
}
 
56
 
 
57
 
 
58
struct foo {
 
59
        struct iv_avl_node      an;
 
60
        int                     num;
 
61
};
 
62
 
 
63
static void printit(struct iv_avl_node *an)
 
64
{
 
65
        struct foo *f = container_of(an, struct foo, an);
 
66
 
 
67
        printf("%d (height %d)\n", f->num, f->an.height);
 
68
}
 
69
 
 
70
static int
 
71
tree_node_verify(struct iv_avl_tree *this, struct iv_avl_node *an,
 
72
                 struct iv_avl_node *parent,
 
73
                 struct iv_avl_node *min, struct iv_avl_node *max, int *cnt)
 
74
{
 
75
        int hl;
 
76
        int hr;
 
77
        int my;
 
78
 
 
79
        if (an->parent != parent) {
 
80
                printf("parent mismatch: %p, %p versus %p\n",
 
81
                       an, an->parent, parent);
 
82
                abort();
 
83
        }
 
84
 
 
85
        (*cnt)++;
 
86
 
 
87
        if (min != NULL || max != NULL) {
 
88
                int err;
 
89
 
 
90
                err = 0;
 
91
                if (min != NULL && this->compare(min, an) >= 0)
 
92
                        err++;
 
93
                if (max != NULL && this->compare(an, max) >= 0)
 
94
                        err++;
 
95
 
 
96
                if (err)
 
97
                        printf("violated %p < %p < %p\n", min, an, max);
 
98
        }
 
99
 
 
100
        hl = 0;
 
101
        if (an->left != NULL)
 
102
                hl = tree_node_verify(this, an->left, an, min, an, cnt);
 
103
 
 
104
        hr = 0;
 
105
        if (an->right != NULL)
 
106
                hr = tree_node_verify(this, an->right, an, an, max, cnt);
 
107
 
 
108
        if (abs(hl - hr) > 1)
 
109
                printf("balance mismatch!\n");
 
110
 
 
111
        my = 1 + ((hl > hr) ? hl : hr);
 
112
        if (an->height != my) {
 
113
                printf("height mismatch: %d vs %d/%d\n", an->height, hl, hr);
 
114
                abort();
 
115
        }
 
116
 
 
117
        return my;
 
118
}
 
119
 
 
120
static void tree_check(struct iv_avl_tree *this, int expected_count)
 
121
{
 
122
        int count;
 
123
 
 
124
        count = 0;
 
125
        if (this->root != NULL)
 
126
                tree_node_verify(this, this->root, NULL, NULL, NULL, &count);
 
127
 
 
128
        if (expected_count >= 0 && expected_count != count) {
 
129
                printf("count mismatch: %d versus %d\n", count, expected_count);
 
130
                abort();
 
131
        }
 
132
}
 
133
 
 
134
 
 
135
static int docomp(struct iv_avl_node *_a, struct iv_avl_node *_b)
 
136
{
 
137
        struct foo *a = container_of(_a, struct foo, an);
 
138
        struct foo *b = container_of(_b, struct foo, an);
 
139
 
 
140
        if (a->num < b->num)
 
141
                return -1;
 
142
        if (a->num > b->num)
 
143
                return 1;
 
144
        return 0;
 
145
}
 
146
 
 
147
 
 
148
 
 
149
#define NUM     16384
 
150
 
 
151
static struct iv_avl_tree x;
 
152
static struct foo *f[NUM];
 
153
 
 
154
int main()
 
155
{
 
156
        struct iv_avl_node *an;
 
157
        int i;
 
158
 
 
159
        srandom(time(NULL) ^ getpid());
 
160
 
 
161
        INIT_IV_AVL_TREE(&x, docomp);
 
162
 
 
163
        for (i = 0; i < NUM; i++) {
 
164
                int ret;
 
165
 
 
166
                if ((i & 1023) == 0)
 
167
                        printf("inserting #%d\n", i);
 
168
 
 
169
                f[i] = malloc(sizeof(struct foo));
 
170
 
 
171
                do {
 
172
                        f[i]->num = random();
 
173
                        ret = iv_avl_tree_insert(&x, &f[i]->an);
 
174
                } while (ret == -EEXIST);
 
175
 
 
176
                if (ret) {
 
177
                        fprintf(stderr, "error %d\n", ret);
 
178
                        exit(1);
 
179
                }
 
180
 
 
181
                tree_check(&x, i + 1);
 
182
        }
 
183
 
 
184
        tree_check(&x, NUM);
 
185
 
 
186
        iv_avl_tree_for_each (an, &x)
 
187
                printit(an);
 
188
 
 
189
        for (i = 0; i < NUM; i++) {
 
190
                if ((i & 1023) == 0)
 
191
                        printf("deleting #%d\n", i);
 
192
 
 
193
                an = &f[i]->an;
 
194
 
 
195
                iv_avl_tree_delete(&x, an);
 
196
 
 
197
                tree_check(&x, NUM - i - 1);
 
198
        }
 
199
 
 
200
        tree_print("deletions done", &x, printit);
 
201
 
 
202
        return 0;
 
203
}