[ccan] [PATCH] btree: Add custom allocator interface.

[Rusty Russell]

stuartl at longlandclan.id.au writes:
> From: Stuart Longland <me at vk4msl.id.au>
>
> This provides a way for btree to be used with external allocator
> libraries such as the tal or talloc modules.

Sure.  In my libraries I generally use a global allocator override;
it's not thread-safe, but much easier to use in practice.

Since I don't use btree, I'm agnostic about it though!

Minor nits below:

> ---
>  ccan/btree/btree.c | 194 +++++++++++++++++++++++++++++++----------------------
>  ccan/btree/btree.h |  29 +++++---
>  2 files changed, 136 insertions(+), 87 deletions(-)
>
> diff --git a/ccan/btree/btree.c b/ccan/btree/btree.c
> index 636edbc..5bb2435 100644
> --- a/ccan/btree/btree.c
> +++ b/ccan/btree/btree.c
> @@ -29,12 +29,15 @@
>  #define MAX (BTREE_ITEM_MAX)
>  #define MIN (BTREE_ITEM_MAX >> 1)
>  
> -static struct btree_node *node_alloc(int internal);
> +static struct btree_node *node_alloc(const struct btree_allocator* alloc, int internal);
>  static void node_delete(struct btree_node *node, struct btree *btree);
> +static void node_free(struct btree_node *node);
>  
>  static void branch_begin(btree_iterator iter);
>  static void branch_end(btree_iterator iter);
>  static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr);
> +static void* default_malloc(const struct btree_allocator* alloc, size_t size);
> +static void default_free(const struct btree_allocator* alloc, void* ptr);

You don't need to pre-declare these, see below.

>  /*
>   * If iter->node has parent, returns 1 and ascends the iterator such that
> @@ -65,11 +68,19 @@ static int node_walk_forward(const struct btree_node *node,
>  
>  struct btree *btree_new(btree_search_t search)
>  {
> -	struct btree *btree = calloc(1, sizeof(struct btree));
> -	struct btree_node *node = node_alloc(0);
> +	return btree_new_with_alloc(search, &BTREE_DEFAULT_ALLOCATOR);
> +}
> +
> +struct btree *btree_new_with_alloc(btree_search_t search,
> +		const struct btree_allocator *alloc)
> +{
> +	struct btree *btree = (*(alloc->malloc))(alloc, sizeof(struct btree));

You can call a function pointer, so alloc->malloc(alloc, sizeof(struct btree));
should work.  

> +	struct btree_node *node = node_alloc(alloc, 0);
>  		node->parent = NULL;
>  		node->count = 0;
>  		node->depth = 0;
> +	memset(btree, 0, sizeof(struct btree));
> +	btree->alloc = alloc;
>  	btree->root = node;
>  	btree->search = search;
>  	btree->multi = false;
> @@ -79,16 +90,16 @@ struct btree *btree_new(btree_search_t search)
>  void btree_delete(struct btree *btree)
>  {
>  	node_delete(btree->root, btree);
> -	free(btree);
> +	(*(btree->alloc->free))(btree->alloc, btree);
>  }

Ditto.

>  bool btree_insert(struct btree *btree, const void *item)
>  {
>  	btree_iterator iter;
> -	
> +
>  	if (btree_find_last(btree, item, iter) && !btree->multi)
>  		return false;
> -	
> +

Lots of whitespace cleanups.  Not a problem, but prefer a separate patch
for clarity.

> +
> +/* Default allocator implementation */
> +const struct btree_allocator BTREE_DEFAULT_ALLOCATOR = {
> +	.malloc = default_malloc,
> +	.free = default_free,
> +};
> +
> +static void* default_malloc(const struct btree_allocator* alloc, size_t size)
> +{
> +	return malloc(size);
> +}
> +
> +static void default_free(const struct btree_allocator* alloc, void* ptr)
> +{
> +	free(ptr);
> +}

Put default_malloc and default_free above the BTREE_DEFAULT_ALLOCATOR
definition, and you don't need to pre-declare them.

Thanks,
Rusty.