objset: new module.
authorRusty Russell <rusty@rustcorp.com.au>
Sun, 4 Dec 2011 22:50:34 +0000 (09:20 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Sun, 4 Dec 2011 22:50:34 +0000 (09:20 +1030)
ccan/objset/LICENSE [new symlink]
ccan/objset/_info [new file with mode: 0644]
ccan/objset/objset.h [new file with mode: 0644]
ccan/objset/test/run.c [new file with mode: 0644]

diff --git a/ccan/objset/LICENSE b/ccan/objset/LICENSE
new file mode 120000 (symlink)
index 0000000..dc314ec
--- /dev/null
@@ -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 (file)
index 0000000..cf29028
--- /dev/null
@@ -0,0 +1,61 @@
+#include <string.h>
+#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 <ccan/objset/objset.h>
+ *     #include <stdio.h>
+ *
+ *     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 (file)
index 0000000..2492a52
--- /dev/null
@@ -0,0 +1,173 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#ifndef CCAN_OBJSET_H
+#define CCAN_OBJSET_H
+#include "config.h"
+#include <ccan/htable/htable_type.h>
+#include <ccan/hash/hash.h>
+#include <ccan/tcon/tcon.h>
+#include <stdlib.h>
+#include <stdbool.h>
+
+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 (file)
index 0000000..c4737da
--- /dev/null
@@ -0,0 +1,97 @@
+#include <ccan/objset/objset.h>
+#include <ccan/tap/tap.h>
+
+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();
+}