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
24 struct treeentry {
25 SPLAY_ENTRY(treeentry) entry;
26 uint64_t id;
27 void *data;
28 };
29
30 static int treeentry_cmp(struct treeentry *, struct treeentry *);
31
32 SPLAY_PROTOTYPE(tree, treeentry, entry, treeentry_cmp);
33
34 int
tree_check(struct tree * t,uint64_t id)35 tree_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
43 void *
tree_set(struct tree * t,uint64_t id,void * data)44 tree_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
62 void *
tree_get(struct tree * t,uint64_t id)63 tree_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
76 void *
tree_pop(struct tree * t,uint64_t id)77 tree_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
93 static int
treeentry_cmp(struct treeentry * a,struct treeentry * b)94 treeentry_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
103 SPLAY_GENERATE(tree, treeentry, entry, treeentry_cmp);
104