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