Re: AVL tree insertion - programming exercise

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups	comp.lang.c
Subject	Re: AVL tree insertion - programming exercise
Date	2026-10-29 13:38 -0700
Organization	A noiseless patient Spider
Message-ID	<861p98medf.fsf@linuxsc.com> (permalink)
References	(5 earlier) <11arlj9$2q39c$1@kst.eternal-september.org> <20261015163445.76@kylheku.com> <11b20os$3qlbh$1@paganini.bofh.team> <11b29gv$3pvda$3@dont-email.me> <11b2njv$3rvef$2@paganini.bofh.team>

Show all headers | View raw

antispam@fricas.org (Waldek Hebisch) writes:

[I am responding to two postings, restoring a sentence that
was removed by an intermediate poster]

> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
>
>> On 2026-10-18 10:42, Waldek Hebisch wrote:
>>
>>>> [...]
>>>
>>> I read the above as:  "can access part of object that fits in
>>> allocated space".  That is important for structs and unions:  you
>>> clearly do not want to allocate memory for biggest union variant.
>>> And I think that allocating memory only for used part of a struct
>>> is pretty common.

I confess to being rather incredulous of these claims.  More
below.

>> Mind to explain that opinion?
>>
>> If I define a (C-)'union' type I definitely want to store anything
>> possible in those unions, changing the value to another type as
>> necessary. - Mind the 'sizeof' of a union is [at least?] the size
>> of its largest component. - If I 'malloc' a union I use that size.
>> In cases where I want to use just one [smaller] component-type of
>> a union I just allocate that specific type not the union-type.
>>
>> But maybe you meant something different?
>
> I meant what I wrote.

I think your alleged facts are wrong.  The vast majority of C
programs, and the vast majority of C programmers, have no
interest in doing either of those things.  If C code needs to use
some part of an allocated struct, a whole struct is allocated.
Evidence for this pattern can be seen in the common idiom for
calling malloc():

   struct foo *pfoo = malloc( sizeof *pfoo );

The case for unions is even weaker.  First it is unusual for a
union to have highly disparate sizes for its members;  a factor
of two or four, maybe, but rarely more than that.  Furthermore if
it were important to access only a subset of the smaller members
then it is simple to create a new union type with only those
members.  At some level it's necessary to do that to know what
size to give to malloc().  (And if it's only one member that is
meant to be accessed, then we expect to follow the above common
idiom for malloc() with a pointer to the member's type.)

Of course it is not impossible that there are C programs that
violate these norms.  But they are at best few and far between,
and anyone who would write such programs runs a greatly increased
risk of undefined behavior.  No sensible developer would do so.

In any case any use of such anti-patterns is so rare that it
wasn't a factor in deciding how malloc() is supposed to work.

> C type system is too weak to give exact
> type for more complicated data structure.  Instead, real program
> give approximate type and depend on holes in type system.

This idea is nonsense.  The C type system is powerful enough to
express any type that C code can deal with.

> So you
> have pointer to union and program is structured so that it only
> accesses valid variant.  Allocating memory for whole using may
> waste a lot of memory and does not buy you any real safety:
> accessing wrong variant is likely to lead to troubles regardless
> of amount of memory that you allocated.  And in case of
> interesting data structures variant does not change after
> creation (allocation).  If you need different variant you simply
> allocate new piece of memory.
>
> BTW:  Pascal 'new' for variant records takes extra argument
> specifying requested variant.  Corresponding pointer has type
> 'pointer to variant record', but legally can only be used with
> the variant specified in call to 'new'.  In C you get equivalent
> effect (with essentially the same conditions) by allocating
> amount of memory needed for specific variant of union, but
> assigning 'malloc' result to pointer to union.

Here we see the key to understanding the earlier comments:  we
have someone who wants to write code in C but who wants to think
in Pascal.  There is no reason to think the C standard means to
support the anti-patterns being advocated.

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 Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-29 13:38 -0700
                Re: AVL tree insertion - programming exercise antispam@fricas.org (Waldek Hebisch) - 2026-10-31 13:34 +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-21 02: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 Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-21 02:41 -0700
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-21 11:22 +0000
          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 Kaz Kylheku <046-301-5902@kylheku.com> - 2026-10-21 23:55 +0000
            malloc() and alignment (was Re: AVL tree insertion - programming exercise) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-22 00:43 +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