GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/smtpd/smtpctl/../tree.c Lines: 0 113 0.0 %
Date: 2017-11-13 Branches: 0 116 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: tree.c,v 1.5 2015/01/20 17:37:54 deraadt Exp $	*/
2
3
/*
4
 * Copyright (c) 2012 Eric Faurot <eric@openbsd.org>
5
 *
6
 * Permission to use, copy, modify, and distribute this software for any
7
 * purpose with or without fee is hereby granted, provided that the above
8
 * copyright notice and this permission notice appear in all copies.
9
 *
10
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17
 */
18
19
#include <sys/types.h>
20
#include <sys/tree.h>
21
22
#include <sys/socket.h>	/* for smtpd.h */
23
#include <sys/queue.h>	/* for smtpd.h */
24
#include <stdio.h>	/* for smtpd.h */
25
#include <imsg.h>	/* for smtpd.h */
26
27
#include <err.h>
28
#include <inttypes.h>
29
#include <stdlib.h>
30
#include <limits.h>
31
32
#include "smtpd.h"
33
34
struct treeentry {
35
	SPLAY_ENTRY(treeentry)	 entry;
36
	uint64_t		 id;
37
	void			*data;
38
};
39
40
static int treeentry_cmp(struct treeentry *, struct treeentry *);
41
42
SPLAY_PROTOTYPE(_tree, treeentry, entry, treeentry_cmp);
43
44
int
45
tree_check(struct tree *t, uint64_t id)
46
{
47
	struct treeentry	key;
48
49
	key.id = id;
50
	return (SPLAY_FIND(_tree, &t->tree, &key) != NULL);
51
}
52
53
void *
54
tree_set(struct tree *t, uint64_t id, void *data)
55
{
56
	struct treeentry	*entry, key;
57
	char			*old;
58
59
	key.id = id;
60
	if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL) {
61
		if ((entry = malloc(sizeof *entry)) == NULL)
62
			err(1, "tree_set: malloc");
63
		entry->id = id;
64
		SPLAY_INSERT(_tree, &t->tree, entry);
65
		old = NULL;
66
		t->count += 1;
67
	} else
68
		old = entry->data;
69
70
	entry->data = data;
71
72
	return (old);
73
}
74
75
void
76
tree_xset(struct tree *t, uint64_t id, void *data)
77
{
78
	struct treeentry	*entry;
79
80
	if ((entry = malloc(sizeof *entry)) == NULL)
81
		err(1, "tree_xset: malloc");
82
	entry->id = id;
83
	entry->data = data;
84
	if (SPLAY_INSERT(_tree, &t->tree, entry))
85
		errx(1, "tree_xset(%p, 0x%016"PRIx64 ")", t, id);
86
	t->count += 1;
87
}
88
89
void *
90
tree_get(struct tree *t, uint64_t id)
91
{
92
	struct treeentry	key, *entry;
93
94
	key.id = id;
95
	if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL)
96
		return (NULL);
97
98
	return (entry->data);
99
}
100
101
void *
102
tree_xget(struct tree *t, uint64_t id)
103
{
104
	struct treeentry	key, *entry;
105
106
	key.id = id;
107
	if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL)
108
		errx(1, "tree_get(%p, 0x%016"PRIx64 ")", t, id);
109
110
	return (entry->data);
111
}
112
113
void *
114
tree_pop(struct tree *t, uint64_t id)
115
{
116
	struct treeentry	key, *entry;
117
	void			*data;
118
119
	key.id = id;
120
	if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL)
121
		return (NULL);
122
123
	data = entry->data;
124
	SPLAY_REMOVE(_tree, &t->tree, entry);
125
	free(entry);
126
	t->count -= 1;
127
128
	return (data);
129
}
130
131
void *
132
tree_xpop(struct tree *t, uint64_t id)
133
{
134
	struct treeentry	key, *entry;
135
	void			*data;
136
137
	key.id = id;
138
	if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL)
139
		errx(1, "tree_xpop(%p, 0x%016" PRIx64 ")", t, id);
140
141
	data = entry->data;
142
	SPLAY_REMOVE(_tree, &t->tree, entry);
143
	free(entry);
144
	t->count -= 1;
145
146
	return (data);
147
}
148
149
int
150
tree_poproot(struct tree *t, uint64_t *id, void **data)
151
{
152
	struct treeentry	*entry;
153
154
	entry = SPLAY_ROOT(&t->tree);
155
	if (entry == NULL)
156
		return (0);
157
	if (id)
158
		*id = entry->id;
159
	if (data)
160
		*data = entry->data;
161
	SPLAY_REMOVE(_tree, &t->tree, entry);
162
	free(entry);
163
	t->count -= 1;
164
165
	return (1);
166
}
167
168
int
169
tree_root(struct tree *t, uint64_t *id, void **data)
170
{
171
	struct treeentry	*entry;
172
173
	entry = SPLAY_ROOT(&t->tree);
174
	if (entry == NULL)
175
		return (0);
176
	if (id)
177
		*id = entry->id;
178
	if (data)
179
		*data = entry->data;
180
	return (1);
181
}
182
183
int
184
tree_iter(struct tree *t, void **hdl, uint64_t *id, void **data)
185
{
186
	struct treeentry *curr = *hdl;
187
188
	if (curr == NULL)
189
		curr = SPLAY_MIN(_tree, &t->tree);
190
	else
191
		curr = SPLAY_NEXT(_tree, &t->tree, curr);
192
193
	if (curr) {
194
		*hdl = curr;
195
		if (id)
196
			*id = curr->id;
197
		if (data)
198
			*data = curr->data;
199
		return (1);
200
	}
201
202
	return (0);
203
}
204
205
int
206
tree_iterfrom(struct tree *t, void **hdl, uint64_t k, uint64_t *id, void **data)
207
{
208
	struct treeentry *curr = *hdl, key;
209
210
	if (curr == NULL) {
211
		if (k == 0)
212
			curr = SPLAY_MIN(_tree, &t->tree);
213
		else {
214
			key.id = k;
215
			curr = SPLAY_FIND(_tree, &t->tree, &key);
216
			if (curr == NULL) {
217
				SPLAY_INSERT(_tree, &t->tree, &key);
218
				curr = SPLAY_NEXT(_tree, &t->tree, &key);
219
				SPLAY_REMOVE(_tree, &t->tree, &key);
220
			}
221
		}
222
	} else
223
		curr = SPLAY_NEXT(_tree, &t->tree, curr);
224
225
	if (curr) {
226
		*hdl = curr;
227
		if (id)
228
			*id = curr->id;
229
		if (data)
230
			*data = curr->data;
231
		return (1);
232
	}
233
234
	return (0);
235
}
236
237
void
238
tree_merge(struct tree *dst, struct tree *src)
239
{
240
	struct treeentry	*entry;
241
242
	while (!SPLAY_EMPTY(&src->tree)) {
243
		entry = SPLAY_ROOT(&src->tree);
244
		SPLAY_REMOVE(_tree, &src->tree, entry);
245
		if (SPLAY_INSERT(_tree, &dst->tree, entry))
246
			errx(1, "tree_merge: duplicate");
247
	}
248
	dst->count += src->count;
249
	src->count = 0;
250
}
251
252
static int
253
treeentry_cmp(struct treeentry *a, struct treeentry *b)
254
{
255
	if (a->id < b->id)
256
		return (-1);
257
	if (a->id > b->id)
258
		return (1);
259
	return (0);
260
}
261
262
SPLAY_GENERATE(_tree, treeentry, entry, treeentry_cmp);