From 756749b2d337334b23deffcfe75b4f731f8f78d1 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 5 Dec 2011 09:20:34 +1030 Subject: [PATCH] objset: new module. --- ccan/objset/LICENSE | 1 + ccan/objset/_info | 61 +++++++++++++++ ccan/objset/objset.h | 173 +++++++++++++++++++++++++++++++++++++++++ ccan/objset/test/run.c | 97 +++++++++++++++++++++++ 4 files changed, 332 insertions(+) create mode 120000 ccan/objset/LICENSE create mode 100644 ccan/objset/_info create mode 100644 ccan/objset/objset.h create mode 100644 ccan/objset/test/run.c diff --git a/ccan/objset/LICENSE b/ccan/objset/LICENSE new file mode 120000 index 00000000..dc314eca --- /dev/null +++ b/ccan/objset/LICENSE @@ -0,0 +1 @@ +../../licenses/LGPL-2.1 \ No newline at end of file diff --git a/ccan/objset/_info b/ccan/objset/_info new file mode 100644 index 00000000..cf290289 --- /dev/null +++ b/ccan/objset/_info @@ -0,0 +1,61 @@ +#include +#include "config.h" + +/** + * objset - unordered set of pointers. + * + * This code implements a very simple unordered set of pointers. It's very + * fast to add and check if something is in the set; it's implemented by + * a hash table. + * + * License: LGPL (v2.1 or any later version) + * + * Example: + * // Silly example to determine if an arg starts with a - + * #include + * #include + * + * struct objset_arg { + * OBJSET_MEMBERS(const char *); + * }; + * + * int main(int argc, char *argv[]) + * { + * struct objset_arg args; + * unsigned int i; + * + * objset_init(&args); + * // Put all args starting with - in the set. + * for (i = 1; i < argc; i++) + * if (argv[i][0] == '-') + * objset_add(&args, argv[i]); + * + * if (objset_empty(&args)) + * printf("No arguments start with -.\n"); + * else { + * for (i = 1; i < argc; i++) + * if (objset_get(&args, argv[i])) + * printf("%i,", i); + * printf("\n"); + * } + * return 0; + * } + * // Given 'a b c' outputs No arguments start with -. + * // Given 'a -b c' outputs 2, + * // Given 'a -b -c d' outputs 2,3, + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/hash\n"); + printf("ccan/htable\n"); + printf("ccan/tcon\n"); + return 0; + } + + return 1; +} diff --git a/ccan/objset/objset.h b/ccan/objset/objset.h new file mode 100644 index 00000000..2492a520 --- /dev/null +++ b/ccan/objset/objset.h @@ -0,0 +1,173 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#ifndef CCAN_OBJSET_H +#define CCAN_OBJSET_H +#include "config.h" +#include +#include +#include +#include +#include + +static inline const void *objset_key_(const void *elem) +{ + return elem; +} +static inline size_t objset_hashfn_(const void *elem) +{ + return hash_pointer(elem, 0); +} +static inline bool objset_eqfn_(const void *e1, const void *e2) +{ + return e1 == e2; +} +HTABLE_DEFINE_TYPE(void, objset_key_, objset_hashfn_, objset_eqfn_, objset_h); + +/** + * OBJSET_MEMBERS - declare members for a type-specific unordered objset. + * @type: type for this set's values, or void * for any pointer. + * + * You use this to create your own typed objset for a particular type. + * You can use an integer type, *but* remember you can't use "0" as a + * value! + * + * Example: + * struct objset_int { + * OBJSET_MEMBERS(int *); + * }; + */ +#define OBJSET_MEMBERS(type) \ + struct objset_h raw; \ + TCON(type canary) + +/** + * objset_init - initialize an empty objset + * @set: the typed objset to initialize. + * + * Example: + * struct objset_int set; + * + * objset_init(&set); + */ +#define objset_init(set) objset_h_init(&(set)->raw) + +/** + * objset_empty - is this set empty? + * @set: the typed objset to check. + * + * Example: + * if (!objset_empty(&set)) + * abort(); + */ +#define objset_empty(set) objset_empty_(&(set)->raw) + +static inline bool objset_empty_(const struct objset_h *set) +{ + struct objset_h_iter i; + return objset_h_first(set, &i) == NULL; +} + +/** + * objset_add - place a member into the set. + * @set: the typed objset to add to. + * @value: the (non-NULL) object to place in the set. + * + * This returns false if we run out of memory (errno = ENOMEM), or + * (more normally) if that pointer already appears in the set (EEXIST). + * + * Example: + * int *val; + * + * val = malloc(sizeof *val); + * *val = 17; + * if (!objset_add(&set, val)) + * printf("Impossible: value was already in the set?\n"); + */ +#define objset_add(set, value) \ + objset_h_add(&tcon_check((set), canary, (value))->raw, (void *)(value)) + +/** + * objset_get - get a value from a set + * @set: the typed objset to search. + * @value: the value to search for. + * + * Returns the value, or NULL if it isn't in the set (and sets errno = ENOENT). + * + * Example: + * if (objset_get(&set, val)); + * printf("hello => %i\n", *val); + */ +#define objset_get(set, member) \ + tcon_cast((set), canary, objset_h_get(&(set)->raw, (member))) + +/** + * objset_del - remove a member from the set. + * @set: the typed objset to delete from. + * @value: the value (non-NULL) to remove from the set + * + * This returns false NULL if @value was not in the set (and sets + * errno = ENOENT). + * + * Example: + * if (!objset_del(&set, val)) + * printf("val was not in the set?\n"); + */ +#define objset_del(set, value) \ + objset_h_del(&tcon_check((set), canary, value)->raw, \ + (const void *)value) + +/** + * objset_clear - remove every member from the set. + * @set: the typed objset to clear. + * + * The set will be empty after this. + * + * Example: + * objset_clear(&set); + */ +#define objset_clear(set) objset_h_clear(&(set)->raw) + +/** + * objset_iter - iterator reference. + * + * This is valid for a particular set as long as the contents remain unchaged, + * otherwise the effect is undefined. + */ +struct objset_iter { + struct objset_h_iter iter; +}; + +/** + * objset_first - get an element in the set + * @set: the typed objset to iterate through. + * @i: a struct objset_iter to use as an iterator. + * + * Example: + * struct objset_iter i; + * int *v; + * + * v = objset_first(&set, &i); + * if (v) + * printf("One value is %i\n", *v); + */ +#define objset_first(set, i) \ + tcon_cast((set), canary, objset_h_first(&(set)->raw, &(i)->iter)) + +/** + * objset_next - get the another element in the set + * @set: the typed objset to iterate through. + * @i: a struct objset_iter to use as an iterator. + * + * @i must have been set by a successful objset_first() or + * objset_next() call. + * + * Example: + * while (v) { + * v = objset_next(&set, &i); + * if (v) + * printf("Another value is %i\n", *v); + * } + */ +#define objset_next(set, i) \ + tcon_cast((set), canary, objset_h_next(&(set)->raw, &(i)->iter)) + +#endif /* CCAN_OBJSET_H */ diff --git a/ccan/objset/test/run.c b/ccan/objset/test/run.c new file mode 100644 index 00000000..c4737da7 --- /dev/null +++ b/ccan/objset/test/run.c @@ -0,0 +1,97 @@ +#include +#include + +struct objset_charp { + OBJSET_MEMBERS(char *); +}; + +struct objset_int { + OBJSET_MEMBERS(int *); +}; + +int main(void) +{ + struct objset_charp osetc; + struct objset_int oseti; + struct objset_iter i; + int i1 = 1, i2 = 2; + char c1 = 1, c2 = 2; + + /* This is how many tests you plan to run */ + plan_tests(46); + + objset_init(&osetc); + objset_init(&oseti); + ok1(objset_empty(&osetc)); + ok1(objset_empty(&oseti)); + ok1(objset_get(&oseti, &i1) == NULL); + ok1(objset_get(&oseti, &i2) == NULL); + ok1(objset_get(&osetc, &c1) == NULL); + ok1(objset_get(&osetc, &c2) == NULL); + + ok1(!objset_del(&oseti, &i1)); + ok1(!objset_del(&oseti, &i2)); + ok1(!objset_del(&osetc, &c1)); + ok1(!objset_del(&osetc, &c2)); + + objset_add(&oseti, &i1); + ok1(!objset_empty(&oseti)); + ok1(objset_get(&oseti, &i1) == &i1); + ok1(objset_get(&oseti, &i2) == NULL); + + objset_add(&osetc, &c1); + ok1(!objset_empty(&osetc)); + ok1(objset_get(&osetc, &c1) == &c1); + ok1(objset_get(&osetc, &c2) == NULL); + + objset_add(&oseti, &i2); + ok1(!objset_empty(&oseti)); + ok1(objset_get(&oseti, &i1) == &i1); + ok1(objset_get(&oseti, &i2) == &i2); + + objset_add(&osetc, &c2); + ok1(!objset_empty(&osetc)); + ok1(objset_get(&osetc, &c1) == &c1); + ok1(objset_get(&osetc, &c2) == &c2); + + ok1((objset_first(&oseti, &i) == &i1 + && objset_next(&oseti, &i) == &i2) + || (objset_first(&oseti, &i) == &i2 + && objset_next(&oseti, &i) == &i1)); + ok1(objset_next(&oseti, &i) == NULL); + + ok1((objset_first(&osetc, &i) == &c1 + && objset_next(&osetc, &i) == &c2) + || (objset_first(&osetc, &i) == &c2 + && objset_next(&osetc, &i) == &c1)); + ok1(objset_next(&osetc, &i) == NULL); + + ok1(objset_del(&oseti, &i1)); + ok1(!objset_del(&oseti, &i1)); + ok1(objset_del(&osetc, &c1)); + ok1(!objset_del(&osetc, &c1)); + + ok1(objset_first(&oseti, &i) == &i2); + ok1(objset_next(&oseti, &i) == NULL); + ok1(objset_first(&osetc, &i) == &c2); + ok1(objset_next(&osetc, &i) == NULL); + + objset_clear(&oseti); + ok1(objset_first(&oseti, &i) == NULL); + ok1(objset_empty(&oseti)); + ok1(objset_get(&oseti, &i1) == NULL); + ok1(objset_get(&oseti, &i2) == NULL); + ok1(!objset_del(&oseti, &i1)); + ok1(!objset_del(&oseti, &i2)); + + objset_clear(&osetc); + ok1(objset_first(&osetc, &i) == NULL); + ok1(objset_empty(&osetc)); + ok1(objset_get(&osetc, &c1) == NULL); + ok1(objset_get(&osetc, &c2) == NULL); + ok1(!objset_del(&osetc, &c1)); + ok1(!objset_del(&osetc, &c2)); + + /* This exits depending on whether all tests passed */ + return exit_status(); +} -- 2.39.2