This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] Reduce memory size of tsearch red-black tree.
- From: Adhemerval Zanella <adhemerval dot zanella at linaro dot org>
- To: libc-alpha at sourceware dot org
- Date: Mon, 15 Aug 2016 14:40:38 -0300
- Subject: Re: [PATCH] Reduce memory size of tsearch red-black tree.
- Authentication-results: sourceware.org; auth=none
- References: <1471209342-7462-1-git-send-email-mark@klomp.org>
> diff --git a/misc/tsearch.c b/misc/tsearch.c
> index ffb89ec..708239f 100644
> --- a/misc/tsearch.c
> +++ b/misc/tsearch.c
> @@ -83,19 +83,70 @@
> In this case, A has been rotated left. This preserves the ordering of the
> binary tree. */
>
> +#include <assert.h>
> +#include <stdalign.h>
> +#include <stddef.h>
> #include <stdlib.h>
> #include <string.h>
> #include <search.h>
>
> +/* Assume malloc returns naturally aligned (alignof (max_align_t))
> + pointers so we can use the low bits to store some extra info. This
> + works for the left/right node pointers since they are not user
> + visible and always allocated by malloc. The user provides the key
> + pointer and so that can point anywhere and doesn't have to be
> + aligned. */
> +#define CAN_USE_MALLOC_LOW_BIT 1
> +
> +#ifndef CAN_USE_MALLOC_LOW_BIT
Why not enforce alignment with memalign/posix_memalign/aligned_alloc and
drop CAN_USE_MALLOC_LOW_BIT?