Re: Joy of this, Joy of that

The Natural Philosopher <tnp@invalid.invalid> wrote:

On 27/11/2024 16:33, Rich wrote:

The Natural Philosopher <tnp@invalid.invalid> wrote:

On 27/11/2024 01:48, Rich wrote:

The only two guarantees given in that paragraph are:
>
1) if ptr was returned by one of the malloc's, the space referenced by
      ptr is deallocated (albeit only for the first call of free(ptr), per
      the second sentence);
and
2) if ptr is NULL, nothing occurs.

>
Exactly.  The result of anything else is implementation dependent on the
library.
>
One might write a free that says 'look at our list of allocated blocks,
compare with the pointer and if no match do nothing'
>
Or one that says  'look at our list of allocated block compare with the
pointer and if no match, segfault'
>
I am not au fait with the internal of 'free()' so I cannot comment as to
why the first is not always the case.

>
I can hazzard a guess.  The time taken to perform the search, or the
effort needed to maintain an "index structure" to perform an optimized
search, plus the time for the optimized search, was felt to be
excessive and wasteful when the "spec" says "don't ever do this".
>

>
Look I don't know how memory allocation and de allocation is done
but my instinct would be to hold a long list of pointers to allocated
blocks.  Possibly in order of the allocated addresses, which would make
allocating a new block a case of finding the first gap in the list that
is [required blocksize] and inserting a new list element, and de
allocation a question of searching the list for a matching allocation,
and deleting it from the list.
>
It would be trivial to get to the end of the list and discover that that
was the end, and, with no match found simply ignore the free call

 Yes, but now you burden /every/ free(ptr) call with an O(N) linear
search of all allocated blocks to determine if "ptr" has been
previously freed.  With today's CPU's one could be excused in thinking
"not such a big deal".  In the days of a PDP-11 or VAX-11/780 CPU
performance levels, doing an O(N) linear search, on every call to free,
to catch something the programmer was never supposed to do in the first
place, was likely viewed as too much overhead.