Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #402780 > unrolled thread

AVL tree insertion - programming exercise

Back to article view | Back to comp.lang.c

Contents

  AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 23:08 -0700
    Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 15:25 +0200
      Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-07 12:13 -0700
        Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 21:28 +0200
          Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:31 -0700
            Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
              Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
        Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-07 20:10 -0500
          Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:56 -0700
            Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 15:09 -0500
              Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-08 22:56 +0200
                Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 17:29 -0500
                  Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 09:56 +0200
              Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 01:39 +0200
                Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-09 00:03 -0700
              Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 23:53 -0700
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 10:34 +0200
                  Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 12:27 +0200
                    Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 12:59 +0200
                  Re: AVL tree insertion - programming exercise bart <bc@freeuk.com> - 2026-10-09 11:43 +0100
                    Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 13:20 +0200
                      Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 12:38 +0000
                        Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 16:05 +0200
                          Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 17:54 +0200
                            Re: AVL tree insertion - programming exercise Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-10-10 10:38 +0800
                              Re: AVL tree insertion - programming exercise ram@zedat.fu-berlin.de (Stefan Ram) - 2026-10-10 03:12 +0000
                                Re: AVL tree insertion - programming exercise Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-10-10 04:44 +0000
                                  Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-10 14:12 -0700
                          Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 19:48 +0000
                            Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-09 23:18 +0000
                            Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 15:27 +0200
                              Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-12 18:26 +0000
                                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-12 21:17 +0200
                        Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-09 17:47 +0300
                          Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 16:48 +0000
                            Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 19:08 +0300
                              Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 18:29 +0200
                                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:44 +0000
                                  Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 23:22 +0200
                              Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:43 +0000
                              Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 20:35 +0200
                                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 19:36 +0000
                                  Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:08 +0200
                                  Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:21 +0300
                                    Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 20:55 +0000
                              Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-10 20:22 +0000
                                Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:32 +0300
                                  Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-11 15:24 +0000
    Re: AVL tree insertion - programming exercise Bonita Montero <Bonita.Montero@gmail.com> - 2026-10-10 19:40 +0200
    Re: AVL tree insertion - programming exercise Andrey Tarasevich <noone@noone.net> - 2026-10-10 12:39 -0700
      Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:00 +0300
      Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:28 +0200
      Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-10 19:02 -0700
    Re: AVL tree insertion - programming exercise "chine.bleu" <chine.bleu@yahoo.com> - 2026-10-13 01:38 -0700
      Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-13 11:42 +0200
        Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 10:55 +0000
        Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 04:29 -0700
          Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-13 14:01 +0200
            Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 05:09 -0700
            Re: AVL tree insertion - programming exercise antispam@fricas.org (Waldek Hebisch) - 2026-10-13 19:01 +0000
          Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 15:17 +0000
            Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-13 17:39 +0200
            Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-13 09:01 -0700
              Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 21:17 +0000
                Re: AVL tree insertion - programming exercise "chine.bleu" <chine.bleu@yahoo.com> - 2026-10-13 18:01 -0700
                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 21:13 -0700
                  Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-14 09:43 +0200
                    Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 20:11 +0000
                    Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-14 15:25 -0700
                      Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-15 09:28 +0200
                  Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 14:13 +0000
                    Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-14 18:03 +0200
                      Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 18:21 +0000
                    Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-14 15:42 -0700
                      Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-15 14:25 +0000
                        Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-15 15:54 -0700
                          Re: AVL tree insertion - programming exercise Kaz Kylheku <046-301-5902@kylheku.com> - 2026-10-15 23:51 +0000
                            Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-15 18:14 -0700
                          Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-16 03:09 +0000
                            Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-15 21:34 -0700
                  Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-14 10:39 -0700
            Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-13 17:15 +0000
              Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 21:30 +0000
        Re: AVL tree insertion - programming exercise "chine.bleu" <chine.bleu@yahoo.com> - 2026-10-13 08:19 -0700
        Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-13 13:16 -0700
          Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-13 23:28 +0300
      Re: AVL tree insertion - programming exercise James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-10-13 06:20 -0400
        Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 14:34 +0000
          Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 20:45 -0700
            Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 14:25 +0000
            Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-14 20:54 -0700
              Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-14 22:47 -0700
                Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-15 04:42 -0700
                Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-15 14:07 -0700
      Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-13 03:52 -0700

Page 5 of 5 — ← Prev page 1 2 3 4 [5]

#403158

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>
>> In article <86v775h9o2.fsf@linuxsc.com>,
>> Tim Rentsch  <tr.17687@z991.linuxsc.com> wrote:
>>
>>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>
> [...]
>
>>>> I don't think this is true anymore, as of C23.  Here's the
>>>> relevant text from n3220, sec 7.24.3, describing the return
>>>> value from `malloc` et al:
>>>>
>>>> |The pointer returned if the allocation succeeds is suitably
>>>> |aligned so that it may be assigned to a pointer to any type of
>>>> |object with a fundamental alignment requirement and size less
>>>> |than or equal to the size requested.
>>>>
>>>> This sentence is somewhat ambiguous because it's unclear whether
>>>> the "less than or equal to the size requested" criteria applies
>>>> to both the pointer type's size _and_ fundamental alignment
>>>> requirement, or _just_ the size, [...]
>>>
>>> It's poorly constructed but in English it has only one
>>> grammatical parse.
>>
>> Nope.  Not even close.
>
> I think Tim is right about there being only one grammatical parse.
> [...]

Thanks Keith!  I owe you one. :)

[toc] | [prev] | [next] | [standalone]

#403114

cross@spitfire.i.gajendra.net (Dan Cross) writes:
>In article <11al4mu$fqtl$1@kst.eternal-september.org>,
>Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:

>
>I argue that examining the text from C17 and how it has changed
>further supports this interpretation.  From C17, sec 7.22.3:
>
>|The pointer returned if the allocation succeeds is suitably
>|aligned so that it may be assigned to a pointer to any type of
>|object with a fundamental alignment requirement and then used
>|to access such an object or an array of such objects in the
>|space allocated (until the space is explicitly deallocated).
>
>Here, no mention of the requested size is made at all, and this
>clearly requires the return value from a successful allocation
>by `malloc(1)` to be aligned so that one could assign it to a
>pointer referring to any object of any type with a "fundamental
>alignment requirement."

Note that the processor ABI documents for x86_64 and
arm64 also require the return value always be aligned
congruent to zero module 16.

[toc] | [prev] | [next] | [standalone]

#403127

In article <fHtzS.249963$iAH2.193623@fx14.iad>,
Scott Lurndal <slp53@pacbell.net> wrote:
>cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>In article <11al4mu$fqtl$1@kst.eternal-september.org>,
>>Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>>I argue that examining the text from C17 and how it has changed
>>further supports this interpretation.  From C17, sec 7.22.3:
>>
>>|The pointer returned if the allocation succeeds is suitably
>>|aligned so that it may be assigned to a pointer to any type of
>>|object with a fundamental alignment requirement and then used
>>|to access such an object or an array of such objects in the
>>|space allocated (until the space is explicitly deallocated).
>>
>>Here, no mention of the requested size is made at all, and this
>>clearly requires the return value from a successful allocation
>>by `malloc(1)` to be aligned so that one could assign it to a
>>pointer referring to any object of any type with a "fundamental
>>alignment requirement."
>
>Note that the processor ABI documents for x86_64 and
>arm64 also require the return value always be aligned
>congruent to zero module 16.

Is that true?  Looking at the psABI for x86_64, I don't see that
mentioned anywhere; it does say that `_Alignof(max_align_t)` is
16, but it doesn't mention `malloc` at all.  POSIX is closer,
and uses language close to that in C17.  Arm64 refers to the
AAPCS64, which doesn't go into the return type of `malloc`,
either.

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#403107

David Brown wrote:
> On 13/10/2026 10:38, chine.bleu wrote:
>> Tim Rentsch wrote:
>>> sons[2] array.  These links are basically pointers, but held
>>> as uintptr_t so they can take one of the bits to mean "tall",
>>> which means taller than the other subtree of the node.  The
>>> tree structure should maintain an invariant that at most one
>>
>> Memory is cheap.
>
> Not any more!

I started on 65K.
>
>> Do not encode tags into low bits of an address unless you really know
>> what your doing.
>
> Agreed, as a principle.
>
>> As a precaution check the return address of malloc
>>
>>      p = malloc(m);
>>      if ((uintptr_t)p)&1!=0) abort();
>>
>
> malloc always returns an address with suitable alignment for any
> fundamental alignment on the target.  Typically that means at least
> 64-bit alignment (and thus the three LSB's are always zero), but it is
> implementation dependent.
>


-- 
Siri Seal of Disavowal #777-000. Disavowed. Denied.  @
NO KINGS    For I desire mercy not sacrifice.       /|\
The Church of the Holey Apple .signature 5.5        / \
of Discordian Mysteries. This post insults Islam. Mohamed

[toc] | [prev] | [next] | [standalone]

#403121

On 10/13/2026 2:42 AM, David Brown wrote:
> On 13/10/2026 10:38, chine.bleu wrote:
>> Tim Rentsch wrote:
>>> sons[2] array.  These links are basically pointers, but held
>>> as uintptr_t so they can take one of the bits to mean "tall",
>>> which means taller than the other subtree of the node.  The
>>> tree structure should maintain an invariant that at most one
>>
>> Memory is cheap. 
> 
> Not any more!
> 
>> Do not encode tags into low bits of an address unless you really know 
>> what your doing.
> 
> Agreed, as a principle.
> 
>> As a precaution check the return address of malloc
>>
>>      p = malloc(m);
>>      if ((uintptr_t)p)&1!=0) abort();
>>
> 
> malloc always returns an address with suitable alignment for any 
> fundamental alignment on the target.  Typically that means at least 64- 
> bit alignment (and thus the three LSB's are always zero), but it is 
> implementation dependent.
> 

Right, and sometimes that can be wasteful on certain memory constrained 
environments. Fwiw, I wrote a region allocator a while back that tends 
to pack thing on their alignment, but never needs a max a alignment for 
all.

Oh shit! I cannot get into google groups, I get a god damn: 429 Too Many 
Requests

Well, here is a mutated version of it that uses C++. I had the C only 
version in some of my saved google groups links. Sigh. Anyway:


My code:
____________________________________________



#if ! defined (RALLOC_H)
#  define RALLOC_H
#  if defined (__cplusplus)
extern "C" {
#  endif
     /**************************************************************/




#include <cstddef>
#include <cassert>




#if defined (_MSC_VER)
/* warning C4116: unnamed type definition in parentheses */
#  pragma warning (disable : 4116)
#endif




#if ! defined (NDEBUG)
#  include <cstdio>
#  define RALLOC_DBG_PRINTF(mp_exp) std::printf mp_exp
#else
#  define RALLOC_DBG_PRINTF(mp_exp) ((void)0)
#endif




#if ! defined (RALLOC_UINTPTR_TYPE)
#  define RALLOC_UINTPTR_TYPE size_t
#endif




     typedef RALLOC_UINTPTR_TYPE ralloc_uintptr_type;


     typedef char ralloc_static_assert[
         sizeof(ralloc_uintptr_type) == sizeof(void*) ? 1 : -1
     ];


#define RALLOC_ALIGN_OF(mp_type) alignof(mp_type)
#define RALLOC_ALIGN_MAX alignof(std::max_align_t)


#define RALLOC_ALIGN_UP(mp_ptr, mp_align) \
   ((void*)( \
     (((ralloc_uintptr_type)(mp_ptr)) + ((mp_align) - 1)) \
     & ~(((mp_align) - 1)) \
   ))


#define RALLOC_ALIGN_ASSERT(mp_ptr, mp_align) \
   (((void*)(mp_ptr)) == RALLOC_ALIGN_UP(mp_ptr, mp_align))




     struct region {
         unsigned char* buffer;
         size_t size;
         size_t offset;
     };


     static void
     rinit(
         struct region* const self,
         void* buffer,
         size_t size
     ) {
         self->buffer = (unsigned char*)buffer;
         self->size = size;
         self->offset = 0;

         RALLOC_DBG_PRINTF((
             "rinit(%p) {\n"
             "  buffer          = %p\n"
             "  size            = %lu\n"
             "}\n\n\n",
             (void*)self,
             buffer,
             (unsigned long int)size
             ));
     }


     static void*
     rallocex(
         struct region* const self,
         size_t size,
         size_t align
     ) {
         unsigned char* align_buffer;
         size_t offset = self->offset;
         unsigned char* raw_buffer = self->buffer + offset;

         if (! size) {
             size = 1;
         }

         if (! align) {
             align = RALLOC_ALIGN_MAX;
         }

         assert(align == 1 || RALLOC_ALIGN_ASSERT(align, 2));

         align_buffer = (unsigned char*)RALLOC_ALIGN_UP(raw_buffer, align);

         assert(RALLOC_ALIGN_ASSERT(align_buffer, align));

         size += align_buffer - raw_buffer;

         if (offset + size > self->size) {
             return NULL;
         }

         self->offset = offset + size;

         RALLOC_DBG_PRINTF((
             "rallocex(%p) {\n"
             "  size            = %llu\n"
             "  alignment       = %llu\n"
             "  origin offset   = %llu\n"
             "  final offset    = %llu\n"
             "  raw_buffer      = %p\n"
             "  align_buffer    = %p\n"
             "  size adjustment = %llu\n"
             "  final size      = %llu\n"
             "}\n\n\n",
             (void*)self,
             (unsigned long long int)size - (align_buffer - raw_buffer),
             (unsigned long long int)align,
             (unsigned long long int)offset,
             (unsigned long long int)self->offset,
             (void*)raw_buffer,
             (void*)align_buffer,
             (unsigned long long int)(align_buffer - raw_buffer),
             (unsigned long long int)size
             ));

         return align_buffer;
     }


#define ralloc(mp_self, mp_size) \
   rallocex((mp_self), (mp_size), RALLOC_ALIGN_MAX)

#define ralloct(mp_self, mp_count, mp_type) \
   rallocex( \
     (mp_self), \
     sizeof(mp_type) * (mp_count),\
     RALLOC_ALIGN_OF(mp_type) \
   )


     static void
     rflush(
         struct region* const self
     ) {
         self->offset = 0;

         RALLOC_DBG_PRINTF((
             "rflush(%p) {}\n\n\n",
             (void*)self
             ));
     }




#undef RALLOC_DBG_PRINTF
#undef RALLOC_UINTPTR_TYPE




     /**************************************************************/
#  if defined (__cplusplus)
}
#  endif
#endif

[toc] | [prev] | [next] | [standalone]

#403122

On Tue, 13 Oct 2026 13:16:44 -0700
"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wrote:
> 
> Oh shit! I cannot get into google groups, I get a god damn: 429 Too
> Many Requests

You can get into google groups but you would have to do it manually,
step by step starting from top
https://groups.google.com

Shortcuts, even the simplest ones like
https://groups.google.com/g/comp.lang.c 
nowadays work very rarely.

So it goes.

[toc] | [prev] | [next] | [standalone]

#403089

On 13/10/2026 10:38, chine.bleu wrote:
...> As a precaution check the return
> address of malloc
> 
>      p = malloc(m);
>      if ((uintptr_t)p)&1!=0) abort();
Just to be pedantic, the standard doesn't guarantee that the expression
you use will test what you want to test. Since there is a guarantee that
malloc() returns a universally aligned memory, I think it's actually
more likely that the test will fail than that malloc() will fail, though
both probabilities are quite negligible, so it's hard to be sure.

[toc] | [prev] | [next] | [standalone]

#403103

In article <11al0l0$eefv$1@dont-email.me>,
James Kuyper  <jameskuyper@alumni.caltech.edu> wrote:
>On 13/10/2026 10:38, chine.bleu wrote:
>...> As a precaution check the return
>> address of malloc
>> 
>>      p = malloc(m);
>>      if ((uintptr_t)p)&1!=0) abort();
>
>Just to be pedantic, the standard doesn't guarantee that the expression
>you use will test what you want to test. Since there is a guarantee that
>malloc() returns a universally aligned memory, I think it's actually
>more likely that the test will fail than that malloc() will fail, though
>both probabilities are quite negligible, so it's hard to be sure.

The syntax and precedence errors aside, the test is clearly
meant to ensure that the low bit in the return from `malloc` is
clear, so that it can be repurposed for other things.  It should
likely be:

	p = malloc(m);
	if (p == NULL || ((uintptr_t)p & 1) != 0) abort();

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#403140

cross@spitfire.i.gajendra.net (Dan Cross) writes:
> In article <11al0l0$eefv$1@dont-email.me>,
> James Kuyper  <jameskuyper@alumni.caltech.edu> wrote:
>>On 13/10/2026 10:38, chine.bleu wrote:
>>...> As a precaution check the return
>>> address of malloc
>>> 
>>>  p = malloc(m);
>>>  if ((uintptr_t)p)&1!=0) abort();
>>
>>Just to be pedantic, the standard doesn't guarantee that the expression
>>you use will test what you want to test. Since there is a guarantee that
>>malloc() returns a universally aligned memory, I think it's actually
>>more likely that the test will fail than that malloc() will fail, though
>>both probabilities are quite negligible, so it's hard to be sure.
>
> The syntax and precedence errors aside, the test is clearly
> meant to ensure that the low bit in the return from `malloc` is
> clear, so that it can be repurposed for other things.  It should
> likely be:
>
> 	p = malloc(m);
> 	if (p == NULL || ((uintptr_t)p & 1) != 0) abort();

I'm not sure the NULL test adds anything useful.  The low-order bits of
a null pointer are very likely to be 0 on any real-world system.

Also, the test only looks at the low-order bits of the result of
the current malloc() call.  If you have an exotic system where
an aligned pointer can have a low-order bit set to 1, it might
*sometimes* be set to 0.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#403153

In article <11amttk$14pou$2@kst.eternal-september.org>,
Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>cross@spitfire.i.gajendra.net (Dan Cross) writes:
>> In article <11al0l0$eefv$1@dont-email.me>,
>> James Kuyper  <jameskuyper@alumni.caltech.edu> wrote:
>>>On 13/10/2026 10:38, chine.bleu wrote:
>>>...> As a precaution check the return
>>>> address of malloc
>>>> 
>>>>  p = malloc(m);
>>>>  if ((uintptr_t)p)&1!=0) abort();
>>>
>>>Just to be pedantic, the standard doesn't guarantee that the expression
>>>you use will test what you want to test. Since there is a guarantee that
>>>malloc() returns a universally aligned memory, I think it's actually
>>>more likely that the test will fail than that malloc() will fail, though
>>>both probabilities are quite negligible, so it's hard to be sure.
>>
>> The syntax and precedence errors aside, the test is clearly
>> meant to ensure that the low bit in the return from `malloc` is
>> clear, so that it can be repurposed for other things.  It should
>> likely be:
>>
>> 	p = malloc(m);
>> 	if (p == NULL || ((uintptr_t)p & 1) != 0) abort();
>
>I'm not sure the NULL test adds anything useful.  The low-order bits of
>a null pointer are very likely to be 0 on any real-world system.

It was just meant to `abort` if `malloc` could not allocate for
whatever reason, and was unrelated to this business of stealing
low bits to cache other data.  The assertion is that, if the
program survives these tests, then `p` is suitable for use.

Sorry, I should have been clear about that.

>Also, the test only looks at the low-order bits of the result of
>the current malloc() call.  If you have an exotic system where
>an aligned pointer can have a low-order bit set to 1, it might
>*sometimes* be set to 0.

I think the point is that if one wants to repurpose the low bits
of the integer representation of `p` for some purpose, then one
ought to verify the base assumption that those bits are
available.  One need not do that on every malloc call, however.

In the face of weird implementations and esoteric hardware, I
don't know that one can have a more general test suitable for
e.g. a `static_assert()`.

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#403174

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>
>> In article <11al0l0$eefv$1@dont-email.me>,
>> James Kuyper  <jameskuyper@alumni.caltech.edu> wrote:
>>
>>> On 13/10/2026 10:38, chine.bleu wrote:
>>> ...> As a precaution check the return
>>>
>>>> address of malloc
>>>>
>>>>  p = malloc(m);
>>>>  if ((uintptr_t)p)&1!=0) abort();
>>>
>>> Just to be pedantic, the standard doesn't guarantee that the
>>> expression you use will test what you want to test.  Since there
>>> is a guarantee that malloc() returns a universally aligned memory,
>>> I think it's actually more likely that the test will fail than
>>> that malloc() will fail, though both probabilities are quite
>>> negligible, so it's hard to be sure.
>>
>> The syntax and precedence errors aside, the test is clearly
>> meant to ensure that the low bit in the return from `malloc` is
>> clear, so that it can be repurposed for other things.  It should
>> likely be:
>>
>> 	p = malloc(m);
>> 	if (p == NULL || ((uintptr_t)p & 1) != 0) abort();
>
> I'm not sure the NULL test adds anything useful.  The low-order bits
> of a null pointer are very likely to be 0 on any real-world system.

Surely we would like to protect against a null pointer being used
to access a non-existent object.

> Also, the test only looks at the low-order bits of the result of
> the current malloc() call.  If you have an exotic system where
> an aligned pointer can have a low-order bit set to 1, it might
> *sometimes* be set to 0.

As long as the bit in question /is/ zero it doesn't matter if it
might have been one.  The bit will always be cleared before using
the pointer as a pointer, so the pointer value in use will match
the pointer value originally returned.

Thus we might write a safe allocation function as follows:

   void *
   safe_new( size_t n ){
      void *p = 0;

      while(  !p || (uintptr_t)p %2 != 0  )  free( p ),  p = malloc( n++ );

      return  p;
   }

Of course it might not succeed in some cases, but it will be
quite obvious if it doesn't.  :)

[toc] | [prev] | [next] | [standalone]

#403176

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>> In article <11al0l0$eefv$1@dont-email.me>,
>>> James Kuyper  <jameskuyper@alumni.caltech.edu> wrote:
>>>> On 13/10/2026 10:38, chine.bleu wrote:
>>>> ...> As a precaution check the return
>>>>
>>>>> address of malloc
>>>>>
>>>>>  p = malloc(m);
>>>>>  if ((uintptr_t)p)&1!=0) abort();
>>>>
>>>> Just to be pedantic, the standard doesn't guarantee that the
>>>> expression you use will test what you want to test.  Since there
>>>> is a guarantee that malloc() returns a universally aligned memory,
>>>> I think it's actually more likely that the test will fail than
>>>> that malloc() will fail, though both probabilities are quite
>>>> negligible, so it's hard to be sure.
>>>
>>> The syntax and precedence errors aside, the test is clearly
>>> meant to ensure that the low bit in the return from `malloc` is
>>> clear, so that it can be repurposed for other things.  It should
>>> likely be:
>>>
>>> 	p = malloc(m);
>>> 	if (p == NULL || ((uintptr_t)p & 1) != 0) abort();
>>
>> I'm not sure the NULL test adds anything useful.  The low-order bits
>> of a null pointer are very likely to be 0 on any real-world system.
>
> Surely we would like to protect against a null pointer being used
> to access a non-existent object.
>
>> Also, the test only looks at the low-order bits of the result of
>> the current malloc() call.  If you have an exotic system where
>> an aligned pointer can have a low-order bit set to 1, it might
>> *sometimes* be set to 0.
>
> As long as the bit in question /is/ zero it doesn't matter if it
> might have been one.  The bit will always be cleared before using
> the pointer as a pointer, so the pointer value in use will match
> the pointer value originally returned.
>
> Thus we might write a safe allocation function as follows:
>
>    void *
>    safe_new( size_t n ){
>       void *p = 0;
>
>       while(  !p || (uintptr_t)p %2 != 0  )  free( p ),  p = malloc( n++ );
>
>       return  p;
>    }
>
> Of course it might not succeed in some cases, but it will be
> quite obvious if it doesn't.  :)

I might be missing the point of "chine.bleu"'s suggestion.  I was
assuming that the point was to check whether it's possible *in
general* to play with the low-order bits of malloc'ed pointers.

On most systems, you can probably make that assumption based on
what you know about the system's memory model.  But it can't be
checked reliably at run time.

If I wanted my program to play with low-order bits of pointers, and
refuse to run if the system doesn't support that, I might write a
program that does a *lot* of malloc() calls and invoke it during
configuration, refusing to proceed with the build if it reports that
malloc() can return an "odd" pointer.  Aborting during execution
feels sloppy.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#403185

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>>
>>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>>
>>>> In article <11al0l0$eefv$1@dont-email.me>,
>>>> James Kuyper  <jameskuyper@alumni.caltech.edu> wrote:
>>>>
>>>>> On 13/10/2026 10:38, chine.bleu wrote:
>>>>> ...> As a precaution check the return
>>>>>
>>>>>> address of malloc
>>>>>>
>>>>>>  p = malloc(m);
>>>>>>  if ((uintptr_t)p)&1!=0) abort();
>>>>>
>>>>> Just to be pedantic, the standard doesn't guarantee that the
>>>>> expression you use will test what you want to test.  Since there
>>>>> is a guarantee that malloc() returns a universally aligned memory,
>>>>> I think it's actually more likely that the test will fail than
>>>>> that malloc() will fail, though both probabilities are quite
>>>>> negligible, so it's hard to be sure.
>>>>
>>>> The syntax and precedence errors aside, the test is clearly
>>>> meant to ensure that the low bit in the return from `malloc` is
>>>> clear, so that it can be repurposed for other things.  It should
>>>> likely be:
>>>>
>>>> 	p = malloc(m);
>>>> 	if (p == NULL || ((uintptr_t)p & 1) != 0) abort();
>>>
>>> I'm not sure the NULL test adds anything useful.  The low-order bits
>>> of a null pointer are very likely to be 0 on any real-world system.
>>
>> Surely we would like to protect against a null pointer being used
>> to access a non-existent object.
>>
>>> Also, the test only looks at the low-order bits of the result of
>>> the current malloc() call.  If you have an exotic system where
>>> an aligned pointer can have a low-order bit set to 1, it might
>>> *sometimes* be set to 0.
>>
>> As long as the bit in question /is/ zero it doesn't matter if it
>> might have been one.  The bit will always be cleared before using
>> the pointer as a pointer, so the pointer value in use will match
>> the pointer value originally returned.
>>
>> Thus we might write a safe allocation function as follows:
>>
>>    void *
>>    safe_new( size_t n ){
>>       void *p = 0;
>>
>>       while(  !p || (uintptr_t)p %2 != 0  ){
>>          free( p ),  p = malloc( n++ );
>>       }
>>
>>       return  p;
>>    }
>>
>> Of course it might not succeed in some cases, but it will be
>> quite obvious if it doesn't.  :)
>
> I might be missing the point of "chine.bleu"'s suggestion.  I was
> assuming that the point was to check whether it's possible *in
> general* to play with the low-order bits of malloc'ed pointers.

I took the tests with the abort() calls to be simply protection
against an unsuitable pointer being returned.  Nothing more
complicated than that.

The point I was making is different.  It doesn't matter if the
bit in question is always zero as long as it is zero a fair
amount of the time.  Also it doesn't have to be a low order bit,
or any pre-chosen bit, as long as some particular bit is zero
often enough.  We can imagine doing a lot of malloc() calls at
program startup and tallying how often a zero appears at each bit
position, and using one of the bit positions with a high count.
Simply do enough malloc() calls until the value returned has a
zero bit at the selected bit position.  The code above looks at a
fixed low order bit, but it could just as well look at a bit
whose position was chosen at run time during program startup.

> On most systems, you can probably make that assumption based on
> what you know about the system's memory model.  But it can't be
> checked reliably at run time.
>
> If I wanted my program to play with low-order bits of pointers, and
> refuse to run if the system doesn't support that, I might write a
> program that does a *lot* of malloc() calls and invoke it during
> configuration, refusing to proceed with the build if it reports that
> malloc() can return an "odd" pointer.  Aborting during execution
> feels sloppy.

I understand what you're saying.  It's mostly orthogonal to what
I was saying.

[toc] | [prev] | [next] | [standalone]

#403198

On 10/14/2026 10:47 PM, Keith Thompson wrote:
> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>>> In article <11al0l0$eefv$1@dont-email.me>,
>>>> James Kuyper  <jameskuyper@alumni.caltech.edu> wrote:
>>>>> On 13/10/2026 10:38, chine.bleu wrote:
>>>>> ...> As a precaution check the return
>>>>>
>>>>>> address of malloc
>>>>>>
>>>>>>   p = malloc(m);
>>>>>>   if ((uintptr_t)p)&1!=0) abort();
>>>>>
>>>>> Just to be pedantic, the standard doesn't guarantee that the
>>>>> expression you use will test what you want to test.  Since there
>>>>> is a guarantee that malloc() returns a universally aligned memory,
>>>>> I think it's actually more likely that the test will fail than
>>>>> that malloc() will fail, though both probabilities are quite
>>>>> negligible, so it's hard to be sure.
>>>>
>>>> The syntax and precedence errors aside, the test is clearly
>>>> meant to ensure that the low bit in the return from `malloc` is
>>>> clear, so that it can be repurposed for other things.  It should
>>>> likely be:
>>>>
>>>> 	p = malloc(m);
>>>> 	if (p == NULL || ((uintptr_t)p & 1) != 0) abort();
>>>
>>> I'm not sure the NULL test adds anything useful.  The low-order bits
>>> of a null pointer are very likely to be 0 on any real-world system.
>>
>> Surely we would like to protect against a null pointer being used
>> to access a non-existent object.
>>
>>> Also, the test only looks at the low-order bits of the result of
>>> the current malloc() call.  If you have an exotic system where
>>> an aligned pointer can have a low-order bit set to 1, it might
>>> *sometimes* be set to 0.
>>
>> As long as the bit in question /is/ zero it doesn't matter if it
>> might have been one.  The bit will always be cleared before using
>> the pointer as a pointer, so the pointer value in use will match
>> the pointer value originally returned.
>>
>> Thus we might write a safe allocation function as follows:
>>
>>     void *
>>     safe_new( size_t n ){
>>        void *p = 0;
>>
>>        while(  !p || (uintptr_t)p %2 != 0  )  free( p ),  p = malloc( n++ );
>>
>>        return  p;
>>     }
>>
>> Of course it might not succeed in some cases, but it will be
>> quite obvious if it doesn't.  :)
> 
> I might be missing the point of "chine.bleu"'s suggestion.  I was
> assuming that the point was to check whether it's possible *in
> general* to play with the low-order bits of malloc'ed pointers.
> 
> On most systems, you can probably make that assumption based on
> what you know about the system's memory model.  But it can't be
> checked reliably at run time.
> 
> If I wanted my program to play with low-order bits of pointers, and
> refuse to run if the system doesn't support that, I might write a
> program that does a *lot* of malloc() calls and invoke it during
> configuration, refusing to proceed with the build if it reports that
> malloc() can return an "odd" pointer.  Aborting during execution
> feels sloppy.
> 

Playing the the low order bits is common in some exotic lock-free 
algorihtms. BUT, its much better to over allocate using say malloc, then 
manually align the pointer it returns. Then we can say that pointer is 
aligned on say a 8192 boundary. We know it size if 8192. But we had to 
ask malloc for more memory to make sure we can align and have the right 
size data block. THEN! We can play with the aligned address and store 
whatever data we want. Just make sure to strip it out before we use the 
aligned and packed pointer.

[toc] | [prev] | [next] | [standalone]

#403092

"chine.bleu" <chine.bleu@yahoo.com> writes:

> Tim Rentsch wrote:
>
>> sons[2] array.  These links are basically pointers, but held
>> as uintptr_t so they can take one of the bits to mean "tall",
>> which means taller than the other subtree of the node.  The
>> tree structure should maintain an invariant that at most one
>
> Memory is cheap.  Do not encode tags into low bits of an address unless
> you really know what your doing.  As a precaution check the return
> address of malloc
>
>     p = malloc(m);
>     if ((uintptr_t)p)&1!=0) abort();

Yes, in general the interface described will fall down on some
systems.  But it's just an exercise.  Feel free to use code along
the lines of the following (disclaimer: not tested) to confirm
the suitability of the pointer values being used:

    Node *
    new_node( int key ){
        Node *r = malloc( sizeof *r );
        assert(  (uintptr_t)r %2 ==0  );
        *r = (Node){ .key = key };
        return  r;
    }

[toc] | [prev] | [standalone]

Page 5 of 5 — ← Prev page 1 2 3 4 [5]

Back to top | Article view | comp.lang.c

csiph-web