Head

GCC Code Coverage Report

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


/*	$OpenBSD: tree.c,v 1.5 2015/01/20 17:37:54 deraadt Exp $	*/

/*
 * Copyright (c) 2012 Eric Faurot <eric@openbsd.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <sys/types.h>
#include <sys/tree.h>

#include <sys/socket.h>	/* for smtpd.h */
#include <sys/queue.h>	/* for smtpd.h */
#include <stdio.h>	/* for smtpd.h */
#include <imsg.h>	/* for smtpd.h */

#include <err.h>
#include <inttypes.h>
#include <stdlib.h>
#include <limits.h>

#include "smtpd.h"

struct treeentry {
	SPLAY_ENTRY(treeentry)	 entry;
	uint64_t		 id;
	void			*data;
};

static int treeentry_cmp(struct treeentry *, struct treeentry *);

SPLAY_PROTOTYPE(_tree, treeentry, entry, treeentry_cmp);

int
tree_check(struct tree *t, uint64_t id)
{
	struct treeentry	key;

	key.id = id;
	return (SPLAY_FIND(_tree, &t->tree, &key) != NULL);
}

void *
tree_set(struct tree *t, uint64_t id, void *data)
{
	struct treeentry	*entry, key;
	char			*old;

	key.id = id;
	if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL) {
		if ((entry = malloc(sizeof *entry)) == NULL)
			err(1, "tree_set: malloc");
		entry->id = id;
		SPLAY_INSERT(_tree, &t->tree, entry);
		old = NULL;
		t->count += 1;
	} else
		old = entry->data;

	entry->data = data;

	return (old);
}

void
tree_xset(struct tree *t, uint64_t id, void *data)
{
	struct treeentry	*entry;

	if ((entry = malloc(sizeof *entry)) == NULL)
		err(1, "tree_xset: malloc");
	entry->id = id;
	entry->data = data;
	if (SPLAY_INSERT(_tree, &t->tree, entry))
		errx(1, "tree_xset(%p, 0x%016"PRIx64 ")", t, id);
	t->count += 1;
}

void *
tree_get(struct tree *t, uint64_t id)
{
	struct treeentry	key, *entry;

	key.id = id;
	if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL)
		return (NULL);

	return (entry->data);
}

void *
tree_xget(struct tree *t, uint64_t id)
{
	struct treeentry	key, *entry;

	key.id = id;
	if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL)
		errx(1, "tree_get(%p, 0x%016"PRIx64 ")", t, id);

	return (entry->data);
}

void *
tree_pop(struct tree *t, uint64_t id)
{
	struct treeentry	key, *entry;
	void			*data;

	key.id = id;
	if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL)
		return (NULL);

	data = entry->data;
	SPLAY_REMOVE(_tree, &t->tree, entry);
	free(entry);
	t->count -= 1;

	return (data);
}

void *
tree_xpop(struct tree *t, uint64_t id)
{
	struct treeentry	key, *entry;
	void			*data;

	key.id = id;
	if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL)
		errx(1, "tree_xpop(%p, 0x%016" PRIx64 ")", t, id);

	data = entry->data;
	SPLAY_REMOVE(_tree, &t->tree, entry);
	free(entry);
	t->count -= 1;

	return (data);
}

int
tree_poproot(struct tree *t, uint64_t *id, void **data)
{
	struct treeentry	*entry;

	entry = SPLAY_ROOT(&t->tree);
	if (entry == NULL)
		return (0);
	if (id)
		*id = entry->id;
	if (data)
		*data = entry->data;
	SPLAY_REMOVE(_tree, &t->tree, entry);
	free(entry);
	t->count -= 1;

	return (1);
}

int
tree_root(struct tree *t, uint64_t *id, void **data)
{
	struct treeentry	*entry;

	entry = SPLAY_ROOT(&t->tree);
	if (entry == NULL)
		return (0);
	if (id)
		*id = entry->id;
	if (data)
		*data = entry->data;
	return (1);
}

int
tree_iter(struct tree *t, void **hdl, uint64_t *id, void **data)
{
	struct treeentry *curr = *hdl;

	if (curr == NULL)
		curr = SPLAY_MIN(_tree, &t->tree);
	else
		curr = SPLAY_NEXT(_tree, &t->tree, curr);

	if (curr) {
		*hdl = curr;
		if (id)
			*id = curr->id;
		if (data)
			*data = curr->data;
		return (1);
	}

	return (0);
}

int
tree_iterfrom(struct tree *t, void **hdl, uint64_t k, uint64_t *id, void **data)
{
	struct treeentry *curr = *hdl, key;

	if (curr == NULL) {
		if (k == 0)
			curr = SPLAY_MIN(_tree, &t->tree);
		else {
			key.id = k;
			curr = SPLAY_FIND(_tree, &t->tree, &key);
			if (curr == NULL) {
				SPLAY_INSERT(_tree, &t->tree, &key);
				curr = SPLAY_NEXT(_tree, &t->tree, &key);
				SPLAY_REMOVE(_tree, &t->tree, &key);
			}
		}
	} else
		curr = SPLAY_NEXT(_tree, &t->tree, curr);

	if (curr) {
		*hdl = curr;
		if (id)
			*id = curr->id;
		if (data)
			*data = curr->data;
		return (1);
	}

	return (0);
}

void
tree_merge(struct tree *dst, struct tree *src)
{
	struct treeentry	*entry;

	while (!SPLAY_EMPTY(&src->tree)) {
		entry = SPLAY_ROOT(&src->tree);
		SPLAY_REMOVE(_tree, &src->tree, entry);
		if (SPLAY_INSERT(_tree, &dst->tree, entry))
			errx(1, "tree_merge: duplicate");
	}
	dst->count += src->count;
	src->count = 0;
}

static int
treeentry_cmp(struct treeentry *a, struct treeentry *b)
{
	if (a->id < b->id)
		return (-1);
	if (a->id > b->id)
		return (1);
	return (0);
}

SPLAY_GENERATE(_tree, treeentry, entry, treeentry_cmp);


Generated by: GCOVR (Version 3.3)

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);