From 72ce81407f677cf279eb46b1c90c34316067b674 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 3 Dec 2012 22:06:38 +1030 Subject: [PATCH] tal/link: new module for reference-count style coding for tal. Tests and example copied from talloc_link, which I also wrote. Signed-off-by: Rusty Russell --- Makefile-ccan | 1 + ccan/tal/link/LICENSE | 1 + ccan/tal/link/_info | 139 +++++++++++++++++++++++++++++++++++++++ ccan/tal/link/link.c | 105 +++++++++++++++++++++++++++++ ccan/tal/link/link.h | 69 +++++++++++++++++++ ccan/tal/link/test/run.c | 73 ++++++++++++++++++++ 6 files changed, 388 insertions(+) create mode 120000 ccan/tal/link/LICENSE create mode 100644 ccan/tal/link/_info create mode 100644 ccan/tal/link/link.c create mode 100644 ccan/tal/link/link.h create mode 100644 ccan/tal/link/test/run.c diff --git a/Makefile-ccan b/Makefile-ccan index 39467383..ef5f8289 100644 --- a/Makefile-ccan +++ b/Makefile-ccan @@ -72,6 +72,7 @@ MODS_NORMAL_WITH_SRC := antithread \ str_talloc \ take \ tal \ + tal/link \ tal/path \ tal/str \ talloc \ diff --git a/ccan/tal/link/LICENSE b/ccan/tal/link/LICENSE new file mode 120000 index 00000000..2b1feca5 --- /dev/null +++ b/ccan/tal/link/LICENSE @@ -0,0 +1 @@ +../../../licenses/BSD-MIT \ No newline at end of file diff --git a/ccan/tal/link/_info b/ccan/tal/link/_info new file mode 100644 index 00000000..d128e010 --- /dev/null +++ b/ccan/tal/link/_info @@ -0,0 +1,139 @@ +#include +#include +#include "config.h" + +/** + * tal/link - link helper for tal + * + * Tal does not support talloc-style references. In the cases where + * an object needs multiple parents, all parents need to be aware of + * the situation; thus tal/link is a helper where all "parents" + * tal_link an object they agree to share ownership of. + * + * Example: + * // Silly program which keeps a cache of uppercased strings. + * // The cache wants to keep strings around even after they may have + * // been "freed" by the caller. + * // Given 'hello' outputs '1 cache hits HELLO ' + * // Given 'hello hello there' outputs '4 cache hits HELLO HELLO THERE ' + * #include + * #include + * #include + * #include + * #include + * #include + * + * struct upcache { + * const char *str; + * const char *upstr; + * }; + * + * static struct upcache *cache; + * static unsigned int cache_hits = 0; + * #define CACHE_SIZE 4 + * static void init_upcase(void) + * { + * cache = tal_arrz(NULL, struct upcache, CACHE_SIZE); + * } + * + * static struct upcache *lookup_upcase(const char *str) + * { + * unsigned int i; + * for (i = 0; i < CACHE_SIZE; i++) + * if (cache[i].str && !strcmp(cache[i].str, str)) { + * cache_hits++; + * return &cache[i]; + * } + * return NULL; + * } + * + * static struct upcache *new_upcase(const char *str) + * { + * unsigned int i; + * char *upstr; + * + * upstr = tal_linkable(tal_strdup(NULL, str)); + * i = random() % CACHE_SIZE; + * + * // Throw out old: works fine if cache[i].upstr is NULL. + * tal_delink(cache, cache[i].upstr); + * + * // Replace with new. + * cache[i].str = str; + * cache[i].upstr = tal_link(cache, upstr); + * while (*upstr) { + * *upstr = toupper(*upstr); + * upstr++; + * } + * return &cache[i]; + * } + * + * // If you want to keep the result, tal_link it. + * static const char *get_upcase(const char *str) + * { + * struct upcache *uc = lookup_upcase(str); + * if (!uc) + * uc = new_upcase(str); + * if (!uc) + * return NULL; + * return uc->upstr; + * } + * + * static void exit_upcase(void) + * { + * tal_free(cache); + * printf("%u cache hits ", cache_hits); + * } + * + * int main(int argc, char *argv[]) + * { + * unsigned int i; + * const char **values; + * + * // Initialize cache. + * init_upcase(); + * + * // Throw values in. + * values = tal_arr(NULL, const char *, argc); + * for (i = 1; i < argc; i++) + * values[i-1] = tal_link(values, get_upcase(argv[i])); + * + * // This will free all the values, but cache will still work. + * tal_free(values); + * + * // Repeat! + * values = tal_arr(NULL, const char *, argc); + * for (i = 1; i < argc; i++) + * values[i-1] = tal_link(values, get_upcase(argv[i])); + * + * // This will remove cache links, but we still have a link. + * exit_upcase(); + * + * // Show values, so we output something. + * for (i = 0; i < argc - 1; i++) + * printf("%s ", values[i]); + * printf("\n"); + * + * // This will finally free the upcase strings (last link). + * tal_free(values); + * + * return 0; + * } + * + * License: BSD-MIT + * Author: Rusty Russell + */ +int main(int argc, char *argv[]) +{ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/container_of\n"); + printf("ccan/list\n"); + printf("ccan/tal\n"); + return 0; + } + + return 1; +} diff --git a/ccan/tal/link/link.c b/ccan/tal/link/link.c new file mode 100644 index 00000000..c25d97e5 --- /dev/null +++ b/ccan/tal/link/link.c @@ -0,0 +1,105 @@ +/* Licensed under BSD-MIT - see LICENSE file for details */ +#include +#include +#include +#include + +/* Our linkable parent. */ +struct linkable { + struct list_head links; +}; + +struct link { + struct list_node list; +}; + +static void linkable_notifier(tal_t *linkable, + enum tal_notify_type type, + void *info) +{ + struct linkable *l = tal_parent(linkable); + assert(type == TAL_NOTIFY_STEAL || type == TAL_NOTIFY_FREE); + + /* We let you free it if you haven't linked it yet. */ + if (type == TAL_NOTIFY_FREE && list_empty(&l->links)) { + tal_free(l); + return; + } + + /* Don't try to steal or free this: it has multiple links! */ + abort(); +} + +void *tal_linkable_(tal_t *newobj) +{ + struct linkable *l; + + /* Must be a fresh object. */ + assert(!tal_parent(newobj)); + + l = tal(NULL, struct linkable); + if (!l) + goto fail; + list_head_init(&l->links); + + if (!tal_steal(l, newobj)) + goto fail; + + if (!tal_add_notifier(newobj, TAL_NOTIFY_STEAL|TAL_NOTIFY_FREE, + linkable_notifier)) { + tal_steal(NULL, newobj); + goto fail; + } + + return (void *)newobj; + +fail: + tal_free(l); + return NULL; +} + +static void destroy_link(struct link *lnk) +{ + struct linkable *l; + + /* Only true if we're first in list! */ + l = container_of(lnk->list.prev, struct linkable, links.n); + + list_del(&lnk->list); + + if (list_empty(&l->links)) + tal_free(l); +} + +void *tal_link_(const tal_t *ctx, const tal_t *link) +{ + struct linkable *l = tal_parent(link); + struct link *lnk = tal(ctx, struct link); + + if (!lnk) + return NULL; + if (!tal_add_destructor(lnk, destroy_link)) { + tal_free(lnk); + return NULL; + } + list_add(&l->links, &lnk->list); + return (void *)link; +} + +void tal_delink_(const tal_t *ctx, const tal_t *link) +{ + struct linkable *l = tal_parent(link); + struct link *i; + + if (!link) + return; + + /* FIXME: slow, but hopefully unusual. */ + list_for_each(&l->links, i, list) { + if (tal_parent(i) == ctx) { + tal_free(i); + return; + } + } + abort(); +} diff --git a/ccan/tal/link/link.h b/ccan/tal/link/link.h new file mode 100644 index 00000000..18d598b8 --- /dev/null +++ b/ccan/tal/link/link.h @@ -0,0 +1,69 @@ +/* Licensed under BSD-MIT - see LICENSE file for details */ +#ifndef TAL_LINK_H +#define TAL_LINK_H +#include "config.h" +#include + +/** + * tal_linkable - set up a tal object to be linkable. + * @newobj - the newly allocated object (with a NULL parent) + * + * The object will be freed when @newobj is freed or the last talloc_link() + * is talloc_delink'ed. + * + * Returns @newobj or NULL (if an allocation fails). + * + * Example: + * int *shared_count; + * + * shared_count = tal_linkable(talz(NULL, int)); + * assert(shared_count); + */ +#define tal_linkable(newobj) \ + (tal_typeof(newobj) tal_linkable_((newobj))) + +/** + * tal_link - add a(nother) link to a linkable object. + * @ctx - the context to link to (parent of the resulting link) + * @obj - the object previously made linkable with talloc_linked(). + * + * If @ctx is non-NULL, the link will be a child of @ctx, and this freed + * when @ctx is. + * + * Returns NULL on failure (out of memory). + * + * Example: + * void *my_ctx = NULL; + * + * tal_link(my_ctx, shared_count); + */ +#if HAVE_STATEMENT_EXPR +/* Weird macro avoids gcc's 'warning: value computed is not used'. */ +#define tal_link(ctx, obj) \ + ({ tal_typeof(obj) tal_link_((ctx), (obj)); }) +#else +#define tal_link(ctx, obj) \ + (tal_typeof(obj) tal_link_((ctx), (obj))) +#endif + +/** + * tal_delink - explicitly remove a link from a linkable object. + * @ctx - the context to link to (parent of the resulting link) + * @obj - the object previously made linkable with talloc_linked(). + * + * Explicitly remove a link: normally it is implied by freeing @ctx. + * Removing the last link frees the object. If @obj is NULL, nothing + * is done. + * + * Example: + * tal_delink(my_ctx, shared_count); + */ +#define tal_delink(ctx, obj) \ + tal_delink_((ctx), (obj)) + +/* Internal helpers. */ +void *tal_linkable_(tal_t *newobj); +void *tal_link_(const tal_t *ctx, const tal_t *dest); +void tal_delink_(const tal_t *ctx, const tal_t *dest); + +#endif /* TAL_LINK_H */ diff --git a/ccan/tal/link/test/run.c b/ccan/tal/link/test/run.c new file mode 100644 index 00000000..fdbb4f02 --- /dev/null +++ b/ccan/tal/link/test/run.c @@ -0,0 +1,73 @@ +#include +#include +#include +#include + +static unsigned int destroy_count = 0; +static void destroy_obj(void *obj) +{ + destroy_count++; +} + +int main(int argc, char *argv[]) +{ + char *linkable, *p1, *p2, *p3; + void **voidpp; + + plan_tests(23); + + linkable = tal(NULL, char); + ok1(tal_linkable(linkable) == linkable); + ok1(tal_add_destructor(linkable, destroy_obj)); + /* First, free it immediately. */ + tal_free(linkable); + ok1(destroy_count == 1); + + /* Now create and remove a single link. */ + linkable = tal_linkable(tal(NULL, char)); + ok1(tal_add_destructor(linkable, destroy_obj)); + ok1(p1 = tal_link(NULL, linkable)); + ok1(p1 == linkable); + tal_delink(NULL, linkable); + ok1(destroy_count == 2); + + /* Two links.*/ + linkable = tal_linkable(tal(NULL, char)); + ok1(tal_add_destructor(linkable, destroy_obj)); + ok1(p1 = tal_link(NULL, linkable)); + ok1(p1 == linkable); + ok1(p2 = tal_link(NULL, linkable)); + ok1(p2 == linkable); + tal_delink(NULL, linkable); + tal_delink(NULL, linkable); + ok1(destroy_count == 3); + + /* Three links.*/ + linkable = tal_linkable(tal(NULL, char)); + ok1(tal_add_destructor(linkable, destroy_obj)); + ok1(p1 = tal_link(NULL, linkable)); + ok1(p1 == linkable); + ok1(p2 = tal_link(NULL, linkable)); + ok1(p2 == linkable); + ok1(p3 = tal_link(NULL, linkable)); + ok1(p3 == linkable); + tal_delink(NULL, linkable); + tal_delink(NULL, linkable); + tal_delink(NULL, linkable); + ok1(destroy_count == 4); + + /* Now, indirectly. */ + voidpp = tal(NULL, void *); + linkable = tal_linkable(tal(NULL, char)); + ok1(tal_add_destructor(linkable, destroy_obj)); +/* Suppress gratuitous warning with tests_compile_without_features */ +#if HAVE_STATEMENT_EXPR + tal_link(voidpp, linkable); +#else + (void)tal_link(voidpp, linkable); +#endif + tal_free(voidpp); + ok1(destroy_count == 5); + + return exit_status(); +} -- 2.39.2