1/*	$OpenBSD: tree.c,v 1.2 2014/02/05 20:13:58 syl 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 <stdlib.h>
20#include <errno.h>
21
22#include "fuse_private.h"
23
24struct treeentry {
25	SPLAY_ENTRY(treeentry)	 entry;
26	uint64_t		 id;
27	void			*data;
28};
29
30static int treeentry_cmp(struct treeentry *, struct treeentry *);
31
32SPLAY_PROTOTYPE(tree, treeentry, entry, treeentry_cmp);
33
34int
35tree_check(struct tree *t, uint64_t id)
36{
37	struct treeentry	key;
38
39	key.id = id;
40	return (SPLAY_FIND(tree, t, &key) != NULL);
41}
42
43void *
44tree_set(struct tree *t, uint64_t id, void *data)
45{
46	struct treeentry	*entry, key;
47
48	key.id = id;
49	if ((entry = SPLAY_FIND(tree, t, &key)) == NULL) {
50		entry = malloc(sizeof *entry);
51		if (entry == NULL)
52			return (NULL);
53		entry->id = id;
54		SPLAY_INSERT(tree, t, entry);
55	}
56
57	entry->data = data;
58
59	return (entry);
60}
61
62void *
63tree_get(struct tree *t, uint64_t id)
64{
65	struct treeentry	key, *entry;
66
67	key.id = id;
68	if ((entry = SPLAY_FIND(tree, t, &key)) == NULL) {
69		errno = ENOENT;
70		return (NULL);
71	}
72
73	return (entry->data);
74}
75
76void *
77tree_pop(struct tree *t, uint64_t id)
78{
79	struct treeentry	key, *entry;
80	void			*data;
81
82	key.id = id;
83	if ((entry = SPLAY_FIND(tree, t, &key)) == NULL)
84		return (NULL);
85
86	data = entry->data;
87	SPLAY_REMOVE(tree, t, entry);
88	free(entry);
89
90	return (data);
91}
92
93static int
94treeentry_cmp(struct treeentry *a, struct treeentry *b)
95{
96	if (a->id < b->id)
97		return (-1);
98	if (a->id > b->id)
99		return (1);
100	return (0);
101}
102
103SPLAY_GENERATE(tree, treeentry, entry, treeentry_cmp);
104