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 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 Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-13 03:52 -0700

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

#403106

In article <11al4mu$fqtl$1@kst.eternal-september.org>,
Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>David Brown <david.brown@hesbynett.no> writes:
>> 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.

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, but I believe that it is the
former (that is, the "and" applies the size requirement to both
alignment and returned size).  Thus, a conforming implementation
of `malloc(1)` could return a pointer that is `alignof(char)`,
but not `alignof(int)`.

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."

>> Typically that means at least
>> 64-bit alignment (and thus the three LSB's are always zero), but it is
>> implementation dependent.
>
>Typically yes, but the standard says nearly nothing about how
>pointers are represented.  If your assume a 64-bit aligned pointer
>has zeros in the 3 LSBs, it's at least potentionally non-portable.
>(The systems I've used that broke that assumption are most likely
>no longer in use.)

This.  It's unlikely that any real world system will do anything
differently these 

>Another possible issue appear if you're using garbage collection.
>If you alter the low bits of a pointer, you might clobber the only
>live reference to the object it points to, and the garbage collector
>might deallocate it behind your back.
>
>Perhaps more realistically, by *not* playing games with pointer
>representations, you'll have one less thing to worry about when 
>tracking down why your code is mysteriously misbehaving.

Playing games with pointer values can be useful for implementing
things like, e.g, Harris's lock-free linked list.

	- Dan C.

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

#403108

On 13/10/2026 17:17, Dan Cross wrote:
> In article <11al4mu$fqtl$1@kst.eternal-september.org>,
> Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>> 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.
> 
> 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, but I believe that it is the
> former (that is, the "and" applies the size requirement to both
> alignment and returned size).  Thus, a conforming implementation
> of `malloc(1)` could return a pointer that is `alignof(char)`,
> but not `alignof(int)`.
> 

Your interpretation seems sound to me.  (I looked at the C11 standards 
when I made my earlier post - it had not occurred to me that C23 might 
have changed the wording here.  The change is not mentioned in the 
change history, as far as I can see.)

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

#403110

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:
>
>> David Brown <david.brown@hesbynett.no> writes:
>>
>>> 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.
>
> 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.

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

#403124

In article <86v775h9o2.fsf@linuxsc.com>,
Tim Rentsch  <tr.17687@z991.linuxsc.com> 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:
>>
>>> David Brown <david.brown@hesbynett.no> writes:
>>>
>>>> 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.
>>
>> 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.

	- Dan C.

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

#403134

cross@spitfire.i.gajendra.net (Dan Cross) wrote:
>>> 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.

Suitable alignment does not guarantee anything about how bits are used 
in the integer representation. That leads to machine dependent 
assumptions. Assumptions are deadly if not documented. Testing 
assumptions is better,

-- 
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]

#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]

#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 4 of 4 — ← Prev page 1 2 3 [4]

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

csiph-web