Re: AVL tree insertion - programming exercise

From	cross@spitfire.i.gajendra.net (Dan Cross)
Newsgroups	comp.lang.c
Subject	Re: AVL tree insertion - programming exercise
Date	2026-10-16 03:09 +0000
Organization	PANIX Public Access Internet and UNIX, NYC
Message-ID	<11as4h9$7ht$1@reader2.panix.com> (permalink)
References	<86ece2kppv.fsf@linuxsc.com> <11ap0fo$1t8gq$2@kst.eternal-september.org> <11aqnp0$sb$1@reader2.panix.com> <11arlj9$2q39c$1@kst.eternal-september.org>

Show all headers | View raw

In article <11arlj9$2q39c$1@kst.eternal-september.org>,
Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>cross@spitfire.i.gajendra.net (Dan Cross) writes:
>> In article <11ap0fo$1t8gq$2@kst.eternal-september.org>,
>> Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>> >[snip]
>> Somewhat informally, the C17 wording could be read as requiring
>> that the pointer returned from `malloc` must be suitable for
>> assignment to any pointer to a type with `alignof(max_align_t)`
>> regardless of the requested size, which might be smaller.  N2293
>> calls this the, '"strong-alignment" reading.'
>
>The C17 wording is:
>
>    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).
>
>I don't see any other way to interpret that.

Nor do I, but N2293 says that some implementers did.  Here's how
David Goldblatt explains it:

|The current wording
|
|C17, 7.22.3 states: "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".
|
|The two clauses of interest here are "it may be assigned to a
|pointer to any type of object with a fundamental alignment
|requirement" and "and then used to access such an object or an
|array of such objects in the space allocated". Strong-alignment
|readers tend to see both clauses as independent, whereas
|weak-alignment readers tend to see the second as an adverbial
|clause modifying the first.  Neither reading is completely
|satisfactory.  The strong-alignment view implies an independent
|clause with a tense mismatch or a missing verb; the
|weak-alignment view uses "and then" when "then" would suffice,
|which could imply a sequencing at odds with the interpretation.

I don't see it, myself, and I'm a "strong-alignment reader", but
he goes on:

|In the author's view, attempting to declare one of these two
|parsings correct is a waste of time.  Many different
|implementers, fluent in English and acting in good faith, have
|parsed the sentence both ways.  The question is how to
|reconcile the divergence.

Indeed.

>It requires that
>a pointer returned by a successful malloc() must *always* be
>suitably aligned.  A pointer returned by malloc(1) must be aligned
>so that it can point to a long long, for example.
>
>It overlooks the fact that it can't point to a long long, because
>there isn't room for it.  And there's no portable way to tell if an
>implementation violates this requirement.  If an implementation's
>malloc(1) returns an "odd" pointer, it violates the standard's
>requirement, but that violation likely has no real effect.

Agreed.

>For C23, it was recognized that requiring strict alignment for
>tiny allocations is neither useful nor necessarily meaningful.
>malloc(1) might as well be allowed to return an "odd" pointer.

Yes.

>>>[snip]
>>>If you allow an object type to have an alignment greater than its
>>>size, then the ambiguity can result in an actual difference in the
>>>requirements.  But then arrays don't work.
>>
>> That's ok; this is only about the properties vis alignment of
>> the pointer returned from malloc.  Consider x86_64 with the
>> System V ABI again or ARM64 with the AAPCS; suppose that
>> `char *p = malloc(char[3]);` assigns a non-NULL ponter to `p`.
>
>Alas, that's a syntax error.  The argument to malloc is an expression,
>not a type.  (I'm certain you knew that.)

Indeed; I meant to write, `malloc(sizeof(char[3]))` but as you
correctly surmised, I mistyped.

>You can write
>`malloc(sizeof (char[3])`, but that's just malloc(3); no type
>information is passed.
>
>And the alignment of char[3] is 1.  An array of two char[3] objects has
>a size of 6; there are no alignment gaps between the elements.

Right.  The only reason I wanted to write it that way was to
drive that point home; in the "strong-alignment" reading, for
small allocations, the alignment of the address the pointer
returned from `malloc` refers to is totally decoupled from the
requested size: `sizeof(char[3])` is three, which reflects the
fundamental alignment requirement of `char[3]` being 1; because
`malloc` doesn't know whether the resulting allocation will be
used to store something with a fundamental alignment criteria of
two or not (assuming such a type exists in the implementation),
it must return a pointer to an address that is at least aligned
to an even boundary.  In any event, whether `malloc` must return
something with stronger alignment, or merely can at its own
convenience, is the interesting high order bit here.

But, you know, I can't type so flubbed the example. :-D

>> The question is only whether or not the address `p` refers to is
>> required to be aligned on a 16-byte boundary; under the
>> '"strong-alignment" reading' in N2293, it is, even though the
>> allocated size is only 3.  Under the '"weak-alignment" reading',
>> the return address can aligned on an even boundary, and C23
>> codified the weak-alignment reading.  Note that neither reading
>> says anything  about the size of elements or their alignment in
>> an allocation that is treated like an array; it only affects
>> the alignment of the starting address.
>
>Under C17, the result of malloc(3) must be strongly aligned (8
>bytes, for example).  Under C23, it has to be at least 2 if there
>are any types with 2-byte alignment.

Yes, that's my interpretation.

>> N2293 mentions this, but it probably bears repeating here: the
>> utility of forcing `malloc` to align small allocations to e.g.,
>> `alignof(max_align_t)` seems mostly restricted to having some
>> hope of overloading the low bits of the returned address for
>> some program-specific purpose, which is how this came up in the
>> first place in this thread.
>
>It hadn't occurred to me that that might be the reason.  I assumed
>it was just because strong alignment for small allocations is not
>useful and should not be required.  Allocating single bytes for
>malloc(1) calls could have real advantages for some programs, and
>the standard shouldn't prohibit that.

N2293 says that existing implementations differed; Goldblatt
gives a fairly concise list of major implementations and which
does what.

David Goldblatt is one of the maintainers of `jemalloc`, and
probably cares about the space efficiency of small allocations;
I suspect that motivated researching the differing
interpretations and became the real motivation.

It came up in this thread specifically because of discussions
around stealing the low bits from the integer representation of
a pointer.

>As I recall, there was a discussion about reusing low-order bits of
>pointers, and the fact that malloc(1) no longer has to be strongly
>aligned became relevant to that.  It doesn't imply that that was
>the reason.

See above.  I suspect Goldblatt wanted to reconcile the
different interpretations so that the `jemalloc` behavior could
be considering conformant with the standard.

>There might be an ambiguity in the English grammar of the C23
>statement about the alignment of malloc()ed pointers, but I don't
>*think* we've seen a case where the two (or more?) different
>interpretations actually lead to different semantics.

I suppose it depends on which semantics you mean.  There are
definitely implementations that the "weak-alignment" reading
and others that take the "strong-alignment" reading.  **On those
latter implementations**, assuming `malloc` of some small size
is successful, you can almost certainly cast the resulting
pointer to `uintptr_t` and use the low bits of the result for
stuff, whereas on the former implementations, you can't, unless
you know that the fundamental alignment requirement for the
size you request is sufficiently large so that the low bits will
be clear; for `malloc(1)` it basically won't be.

>>                              As has already been mentioned, the
>> standard makes no guarnatee about the integer representation of
>> addresses, so this is already somewhat fraught, but on many
>> platforms we may assume that as a practical matter, for a
>> pointer to a suitably aligned address, those bits will be clear
>> as a practical matter; I suppose if one wants that for a small
>> allocation, use `aligned_alloc`.  Caveat emptor.
>
>Yes, if you need aligned pointers, aligned_alloc() is the way to
>get them.  aligned_alloc(8, 1) gives you an 8-byte aligned pointer
>to a 1-byte object; if that's useful, it's because you're doing
>something weird.  And if you need to fiddle with the low-order
>bits of aligned pointers, you could run into the problems we've
>already discussed.

Yup.  Agreed on all counts.  There _are_ some valid uses for
stealing low bits, but they're pretty esoteric; for instance,
this: https://dl.acm.org/doi/10.1145/3731569.3764807

But if someone is dabbling in those dark magicks, they'd better
know just exactly what they're doing.

	- Dan C.

Thread

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 Kaz Kylheku <046-301-5902@kylheku.com> - 2026-10-16 20:26 +0000
                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-16 15:27 -0700
                Re: AVL tree insertion - programming exercise antispam@fricas.org (Waldek Hebisch) - 2026-10-18 08:42 +0000
                Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-18 13:11 +0200
                Re: AVL tree insertion - programming exercise antispam@fricas.org (Waldek Hebisch) - 2026-10-18 15:12 +0000
                Re: AVL tree insertion - programming exercise Kaz Kylheku <046-301-5902@kylheku.com> - 2026-10-18 19:54 +0000
                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 cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-16 11:27 +0000
                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-16 11:27 -0700
                Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-17 08:21 -0700
                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-17 10:48 -0700
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-17 18:10 +0000
                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 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-17 20:28 -0700
    Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-13 03:52 -0700

csiph-web