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