diff options
| -rw-r--r-- | server/util/btreemap.c | 175 | ||||
| -rw-r--r-- | server/util/btreemap.h | 32 |
2 files changed, 207 insertions, 0 deletions
diff --git a/server/util/btreemap.c b/server/util/btreemap.c new file mode 100644 index 00000000..7c20086b --- /dev/null +++ b/server/util/btreemap.c @@ -0,0 +1,175 @@ +/* + SSSD + + Service monitor + + Copyright (C) Stephen Gallagher 2008 + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include "talloc.h" +#include "util/btreemap.h" +#include "util/util.h" + +struct btreemap +{ + /* NULL keys are not allowed */ + void *key; + + /* NULL values are permitted */ + void *value; + + struct btreemap *left; + struct btreemap *right; + + /* comparator must return -1, 0 or 1 + * and should only be set for the root node + * other nodes will be ignored. + */ + btreemap_comparison_fn comparator; +}; + +/* btreemap_search_key + * Searches a btreemap for an entry with a specific key + * If found, it will return 0 and node will be set to the + * appropriate node. + * If not found, it will set the following: + * -2: The map was empty, create a new map when adding keys + * -1: A new node created should use node->left + * 1: A new node created should use node->right + */ +int btreemap_search_key(struct btreemap *map, void *key, struct btreemap **node) +{ + struct btreemap *tempnode; + int result; + int found = -2; + + if (!map) + { + *node = NULL; + return -2; + } + + tempnode = map; + while (found == -2) { + result = tempnode->comparator(tempnode->key, key); + if (result > 0) + { + if (tempnode->right) + tempnode=tempnode->right; + else + { + found = 1; + } + } else if (result < 0) + { + if (tempnode->left) + tempnode=tempnode->left; + else + { + found = -1; + } + } else + { + /* This entry matched */ + found = 0; + } + } + + *node = tempnode; + return found; +} + +void *btreemap_get_value(struct btreemap *map, void *key) +{ + struct btreemap *node; + int found; + + if (!map || !key) + { + return NULL; + } + + /* Search for the key */ + found = btreemap_search_key(map, key, &node); + if (found == 0) + { + return node->value; + } + + /* If the key was not found, return NULL */ + return NULL; +} + +int btreemap_set_value(struct btreemap **map, void *key, void *value, + btreemap_comparison_fn comparator) +{ + struct btreemap *node; + struct btreemap *new_node; + int found; + + if (!key) + { + return EINVAL; + } + + /* Search for the key */ + found = btreemap_search_key(*map, key, &node); + if (found == 0) + { + /* Update existing value */ + node->value = value; + return EOK; + } + + /* Need to add a value to the tree */ + new_node = talloc_zero(node, struct btreemap); + if (!new_node) + { + return ENOMEM; + } + new_node->key = talloc_steal(*map, key); + new_node->value = talloc_steal(*map, value); + new_node->comparator = comparator; + + if (found == -2) + { + *map = new_node; + } + if (found == -1) + { + node->left = new_node; + } else if (found == 1) + { + node->right = new_node; + } + return EOK; +} + +struct btreemap *btreemap_new(void *key, void *value, + btreemap_comparison_fn comparator) +{ + struct btreemap *map; + int result; + + map = NULL; + result = btreemap_set_value(&map, key, value, comparator); + if (result != EOK) + { + return NULL; + } + + return map; +} diff --git a/server/util/btreemap.h b/server/util/btreemap.h new file mode 100644 index 00000000..8452732f --- /dev/null +++ b/server/util/btreemap.h @@ -0,0 +1,32 @@ +/* + SSSD + + Service monitor + + Copyright (C) Stephen Gallagher 2008 + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ +#ifndef BTREEMAP_H_ +#define BTREEMAP_H_ + +typedef int (*btreemap_comparison_fn)(void *first, void *second); +struct btreemap; +int btreemap_search_key(struct btreemap *map, void *key, struct btreemap **node); +void *btreemap_get_value(struct btreemap *map, void *key); +int btreemap_set_value(struct btreemap **map, void *key, void *value, + btreemap_comparison_fn comparator); + + +#endif /*BTREEMAP_H_*/ |