jcs.org
jcs's openbsd hax
openbsd
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);