Re: Simple question, err... I think

* Jon Harrop:
Alf P. Steinbach wrote:
* Jon Harrop:
Alf P. Steinbach wrote:
* Jon Harrop:
Doing so would violate the assumptions of this function.
One assumption is then that client code should leak memory.
Given that there's no deallocation for these RB trees, that's pretty
obvious.
You're using 'delete'. That's deallocation, opposite of "no
deallocation".

No. You are confusing the deallocation of nodes with the deallocation of
trees.

Your code leaks memory (see below for definition).

I understand that /why that should be a problem/ isn't entirely obvious to you.

Just trust me, it is. And the remedy, as mentioned in my first posting in this thread, namely using smart pointers, (1) shortens and simplifies the code, and (2) would make it more usable in practice, except for other bugs such as degenerate tree, which has O(n) search time.


My code deallocates nodes internally when they can no longer be
used. It does not provide deallocation for trees (or removal of elements).
Consequently, this data structure can only ever grow and you are calling
this a "leak".

A "leak" is when it becomes impossible to deallocate previously allocated memory that's no longer used, or when such deallocation is not performed in spite of being possible, in short, when the code for some reason or other accumulates unused memory.

That is the case for your code, for reasons explained below.

Do you understand the general definition of "leak" given above, so that we're talking about the same thing?


The other errors were in your code.
Unsubstantiated and misleading: skip the rhetoric, please.

I already substantiated it in detail, with code.

Unfortunately, that posting does not appear on my news-server, nor in Google.


Such semantics are
no different from violating the assumptions of an iterator, for
example.
Sorry, that's incorrect.
How do you believe the lack of safety in my function is different from
that in the STL?
Presumably you mean the C++ standard library.

The standard library containers are safe when used correctly.

Tautology. Safety is about what happens when things go wrong.

No, it's not a tautology. Your code is unsafe no matter how it's used. Standard library containers are unsafe only when used in incorrect ways, like a powertool that's unsafe if you apply it to your own body, say. Compare the ordinary chain-saw (standard library container) to the exploding chain-saw. Both are unsafe if used incorrectly, but only the exploding one is also unsafe if used per the intention of the designer.


Your function appears to be unsafe no matter how it's used --

Yes, of course: C++ is unsafe => my C++ function is unsafe. You can pass it
a pointer to an invalid tree and it might segfault.

Your C++ function is unsafe because it's written by someone who, at the time of writing, ignored and didn't understand the C++ safety aspects. It's no big deal for a competent programmer to change it so that it's "safe", without affecting its (lack of) correctness. And in my very first posting in this thread I told you how -- e.g. to use smart pointers, which perform deallocation much like GC in Perl, by reference counting.


memory can't be reclaimed without Undefined Behavior due to invalid pointer
values

Your test code was the only source of invalid pointers.

No, AFAIK my code did not generate any invalid pointers. That code was only a test harness for your function. With all pointer values produced by your function.


My code never generated invalid pointers AFAIK.

When you do

delete p;

you generate an invalid pointer p, because the value of p does not change, but the object it referred to is gone, eradicated.

That's not of itself a cause for concern, for somewhere there must be one 'delete' for every 'new', lest the program should leak memory.

However, using p afterwards incurs Undefined Behavior, and there's no way to check and avoid that /unless/ you have also done something like

p = 0;

If you haven't, and you didn't, zeroed the pointer: when p is a left-pointer in a node, say, then that node can be deallocated on its own (if you magically knows that it needs deallocation), but the possible subtrees can't be safely deallocated, because it's Undefined Behavior to follow the left and right node pointers.

That doesn't mean that in C++ it's a good idea to always zero a pointer after a 'delete': in general it isn't, because it leads to sloppy coding (relying on the knowledge that pointer values can be checked, which leads to unnecessary and fragile checking and conditional execution), which leads to bugs. But in a linked data structure it is essential to zero out links that are no longer valid, so that the structure can be safely traversed -- e.g. for purposes of deallocation.

When you use smart pointers zeroing is the way of telling the smart pointer that this instance is no longer active.

When the reference count reaches zero, the referred object is destroyed and the memory deallocated.

A very common such smart pointer is boost::shared_ptr; check out the Boost library.

boost::shared_ptr will become std::shared_ptr, part of the standard library, in the next version of the C++ standard.


-- and it also produces incorrect results. As demonstrated, it's a meaningless novice's attempt at coding. The C++ standard
library, on the other hand, is usually implemented by experts, is fairly
rigorously specified, and for any commonly used implementation, well
tested, by hundreds of thousands up to millions of users.

And it has equivalent semantics.

?


The OCaml I posted supports persistence. You can't do that in C++ without
writing or using a GC. There are two simple alternatives: in-place
modification or invalidation. I chose the latter.
That's so meaningless that it's not even wrong. First, persistence and
GC are orthogonal concepts: one can be tied to the other in a given
implementation, but that's about it (however, if my impression of you is
correct, this is likely to spur you off on a tangent on how persistence
can be coupled to to GC: don't, we're discussing your erronous code, not
persistence). Second, you forgot to do the invalidation you claim.

Perhaps you labor under a misconception that 'delete' in C++ invalidates?

It does, but not in the sense that something can be detected as invalid
afterwards: it destroys and deallocates, and does not change the pointer
value -- which after this operation yields UB if used in any way.

Same semantics as an STL iterator into a vector after it is reallocated: it
is invalidated but will not necessarily be "detected as invalid
afterwards".

You're definitely on to the basic concept here. Let's not squibble about your particular example. Just note in passing that it's highly relevant but absolutely not "same semantics":

* A std lib container guarantees eventual deallocation of all memory
it allocates -- your abstraction (data structure + func) does not.

* An iterator into a std lib container is not needed for deallocation;
the pointers in your tree structure are.

This wouldn't be too bad except for two (potential) issues:

* The calls to 'delete', which invalidate pointers in the nodes, which
in turn makes it impossible to check whether a node to be destroyed
has child nodes (to also be destroyed).

* The lack of information about which nodes are no longer part of the
structure, i.e., to be destroyed.

It might be that the logic of the problem is such that these two issues can never arise. In about the same way that your redundant checking for pointer equality will always yields false, due to the underlying logic. However, in quality code the assumptions are made explicit, and statements that serve to screw up things, such as the 'delete' calls, are not introduced: instead statements that serve to sort out things, such as zeroing pointers that would otherwise be invalid, are included.

The challenge for you is first and foremost to show in concrete code, a small program that can be compiled and run, how the function can be used /without/ leaking memory. And of course without Undefined Behavior. Feel free to reuse my instance counting class.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
.

Relevant Pages

  • Re: Reading from invalid memory
    ... from the same invalid memory location I do not get any errors. ... since constructing or dereferencing an invalid pointer ... Undefined behavior can be anything, ...
    (comp.unix.programmer)
  • Re: segmentation fault in strcmp()
    ... What is the meaning of such an error like invalid next size/ ... It means that the freeis trying to figure out the size of the next block of memory in the heap; information it needs in order to complete the process of freeing the memory you've asked it to release. ... Since the place where it looks is determined in part by the pointer that you pass to free, one possibility is that you're passing the wrong pointer to free; ... If p is not a pointer returned by a call to malloc() or realloc), then freecould cause this problem. ...
    (comp.lang.c)
  • Re: validity of a pointer
    ... only "invalid" pointer in terms of C is the null pointer, ... An indeterminate pointer is more invalid than a null pointer. ... However dereferencing a null pointer is invalid, ... Without a operating system, memory protection ...
    (comp.lang.c)
  • Re: Checking pointers
    ... know is that the pointer points "where it ought to," which is much harder to characterize. ... Using assorted non-portable tricks you might be able to learn whether a pointer points to a valid memory location, whether it's correctly aligned for its type, whether the memory is readable and/or writeable, and maybe other things, too. ... your test is reliable only if `p' is valid; if `p' is invalid there is no telling what might happen. ... I have not personally used things like Purify or valgrind and cannot speak to their effectiveness -- but certainly a "spot-check" test unsupported by considerable additional machinery is of limited effectiveness.) ...
    (comp.lang.c)
  • Re: Calling functions of derived types, pointers and memory leakage
    ... > memory is in the calling program to my function? ... through this or any other pointer. ... programmer cannot rely on the compiler to arrange for deallocation. ... there is no memory leakage, it is necessary to use functions on the ...
    (comp.lang.fortran)
Loading