Thursday, December 15, 2016

Digest for comp.lang.c++@googlegroups.com - 15 updates in 3 topics

Tim Rentsch <txr@alumni.caltech.edu>: Dec 14 04:59PM -0800

> function calls. In implementation where each tree node has a pointer
> to its parent node, recursion is not necessary, and the the pointers
> to parent nodes can be explicitly used.
 
Even in cases where height changes propagate all the way to the
root, it is a remarkable result for AVL trees than no stack is
needed, nor are parent pointers or recursion. Inserting into an
AVL tree (with two bits per node of balance information) can be
done with only O(1) space. Along the path from the root to the
insertion point, the node farthest from the insertion point such
that all subsequent nodes along the path are balanced is the only
node where rebalancing might be needed. Because that node, which
might be called "the tipping point", can be identified during the
initial walk (and remembered for later) from the root to the
insertion point, height adjustments can be done after the new
node is inserted, by starting at the tipping point and re-walking
the child links to the newly inserted node. It is after the
downstream heights are adjusted that a rebalance may need to take
place, but only at one point in the tree, ie, at "the tipping
point" node.
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 15 06:25AM +0100

On 14.12.2016 00:33, Tim Rentsch wrote:
> stopping at the freshly added node (which of course needs
> height_diff set to zero). Doing that correctly updates the
> height_diff's for all nodes that need it.
 
Nice! The presented code stops propagating at the point one should
remember with this new scheme. But I just didn't think of that
optimizaton: it was more natural to me to just add a couple of lines of
tracking code.
 
 
> When it comes time to do rebalancing, the above algorithm needs
> to be adjusted slightly to take that into account, but for now
> this simpler version can do the job.
 
Uh huh. :)
 
 
> Is this description clear enough, or should I try to write
> some pseudo-code?
 
Sounds clear enough.
 
I guess it's time to read up on AVL and so forth.
 
Oh, "Adelson-Velsky Landis", the inventors. I thought it would surely be
a silly acronym. The Wikipedia articles mentions `split` and `join`
operations, and I guess it's important to cover those.
 
 
Cheers, & thanks!,
 
- Alf
"A. Bolmarcich" <aggedor@earl-grey.cloud9.net>: Dec 15 07:44PM

> downstream heights are adjusted that a rebalance may need to take
> place, but only at one point in the tree, ie, at "the tipping
> point" node.
 
That approach is not what I have seen as the usual described of an
AVL tree. The resulting tree may have nodes in different places
that they would be in what is usually described as an AVL tree.
Tim Rentsch <txr@alumni.caltech.edu>: Dec 15 01:13PM -0800


> That approach is not what I have seen as the usual described of an
> AVL tree. The resulting tree may have nodes in different places
> that they would be in what is usually described as an AVL tree.
 
I don't know what you think of as the usual description of
AVL trees, so I can't evaluate whether what you're saying
is right or not. My comments are based on the description
of AVL trees in Knuth TAOCP volume 3, Sorting and Searching.
Can you provide a reference for AVL trees that describes the
insertion process in enough detail so I can compare them?
Tim Rentsch <txr@alumni.caltech.edu>: Dec 15 01:40PM -0800

> remember with this new scheme. But I just didn't think of that
> optimizaton: it was more natural to me to just add a couple of lines
> of tracking code.
 
Yes, well, it isn't like I came up with the idea to start with,
it occurred to me only after working through the section on AVL
trees in Knuth.
 
 
>> to be adjusted slightly to take that into account, but for now
>> this simpler version can do the job.
 
> Uh huh. :)
 
As long as we're here let me describe the algorithm for finding
"the tipping point", as I call it, for AVL tree insertion, which
is pretty close to the above.
 
For AVL tree insertion, we do like the above and walk the path
starting at the root and down to the insertion point. In this
case though the "tipping point" node is the node along that path
that is farthest from the insertion point where all subsequent
nodes on the path are balanced. This means, fairly obviously,
that the tipping point node either is itself not balanced, or is
the node at the very top of the tree. (It may of course be
both.) In addition, besides remembering the (address of) the
tipping point node, we also need to remember the address of the
pointer that got us to the tipping point node. This second
address will be either: one of the child pointers in the node
just above the tipping point node (if the tipping point node is
not the top of the tree); or, in the case that the tipping point
node is at the top of the tree, whatever root pointer got us to
the top of the tree in the first place.
 
The reason we need to remember the address of that pointer is
that, if the tree needs rebalancing, that pointer needs to be
updated to point to a different node.
 
For now I won't say any more about updating heights or how to do
rebalancing for the AVL case, but I thought it would be helpful
to explain about finding the tipping point node in that
situation.
 
 
>> some pseudo-code?
 
> Sounds clear enough.
 
> I guess it's time to read up on AVL and so forth.
 
Before you do that you might try implementing the scheme I
sketched above, for no-rebalancing trees. That will get your
feet wet, and I think is a good introduction to the full-on
AVL insertion.
 
> The Wikipedia articles mentions `split` and `join`
> operations, and I guess it's important to cover those.
 
Before you get to split and join, you will want to do delete,
which is challenging enough. I think all the explanations of
balanced trees (of various kinds) that I've read gloss over how
to do deletion, and having implemented it now a few times I know
why: compared to deletion, insertion is a cake walk. :p
bitrex <bitrex@de.lete.earthlink.net>: Dec 14 08:02PM -0500

On 12/14/2016 12:13 PM, bitrex wrote:
 
> I'm wondering if anyone could provide a reference for an example
> implementation of smart pointers that are known to be semantically
> correct, but would be more suitable for my narrow application.
 
This policy based implementation looks like a good starting point:
 
http://axter.com/smartptr/classsmart__ptr.htm
Paavo Helde <myfirstname@osa.pri.ee>: Dec 15 04:36PM +0200

On 14.12.2016 19:13, bitrex wrote:
> they appear fairly complex, with a lot of excess #ifdefs for conditional
> compilation for architecture features that don't seem to be really
> relevant for my application.
 
If you can use STL in your project, then it looks like you are finished.
Just use std::allocate_shared(your_allocator(), ...) for creating your
objects.
 
> I'm wondering if anyone could provide a reference for an example
> implementation of smart pointers that are known to be semantically
> correct, but would be more suitable for my narrow application.
 
If you need to create a new smartpointer class from scratch, then this
is not so hard (certainly simpler than creating a threaded binary tree,
discussed else-thread).
 
Do you need weak pointers? Do you need thread-safe refcounting? Do you
need const-correctness? Do you need automatic conversions from derived
class smartpointers to base class smartpointers? Do you need to support
any other classes than your own?
 
If answer to all of these questions is no, then the smart pointer class
becomes pretty trivial. You can use "internal reference counting",
meaning that the reference counter is placed directly inside your
objects (in a common base class). This makes things a bit simpler. The
smartpointer class itself is straightforward, one just needs to take
care to define *all* needed operations and get the self-assignment and
cycle breaking assignments correct.
 
Example:
 
#include <cstddef>
 
// Base class for refcounted objects.
class RefCountedBase {
int refcount_;
public:
RefCountedBase(): refcount_(0) {}
RefCountedBase(const RefCountedBase& b): refcount_(0) {}
RefCountedBase& operator=(const RefCountedBase& b) { return *this; }
RefCountedBase& operator=(RefCountedBase&& b) { return *this; }
virtual ~RefCountedBase() {}
void Capture() {
++refcount_;
}
void Release() {
if (--refcount_==0) {
// destroy the object
delete this;
}
}
};
 
template<typename T>
class SmartPointer {
T* p_;
public:
SmartPointer(): p_(nullptr) {}
SmartPointer(std::nullptr_t): p_(nullptr) {}
explicit SmartPointer(const T* p): p_(const_cast<T*>(p)) {
if (p_) {
p_->Capture();
}
}
SmartPointer(const SmartPointer& b): p_(b.p_) {
if (p_) {
p_->Capture();
}
}
SmartPointer(SmartPointer&& b): p_(b.p_) {
b.p_ = nullptr;
}
~SmartPointer() {
if (p_) {
p_->Release();
}
}
const SmartPointer& operator=(const SmartPointer& b) {
// Support self assignment
if (b.p_) {
b.p_->Capture();
}
// Support cycle breaking
T* q = p_;
p_ = b.p_;
if (q) {
q->Release();
}
return *this;
}
const SmartPointer& operator=(SmartPointer&& b) {
// Detect self assignment
if (p_!=b.p_) {
// Support cycle breaking
T* q = p_;
p_ = b.p_;
b.p_ = nullptr;
if (q) {
q->Release();
}
}
return *this;
}
T& operator*() const {
return *p_;
}
T* operator->() const {
return p_;
}
T* get() const {
return p_;
}
bool operator<(const SmartPointer& b) const {
return p_<b.p_;
}
explicit operator bool() const { return p_!=nullptr; }
};
 
class A;
typedef SmartPointer<A> APtr;
 
class A: public RefCountedBase {
};
 
#include <vector>
int main() {
APtr a1(new A());
std::vector<APtr> test1(100, a1);
test1.push_back(APtr(new A()));
test1.push_back(APtr(new A()));
a1 = nullptr;
test1.clear();
// all A-s now deleted, however many there were.
}
bitrex <bitrex@de.lete.earthlink.net>: Dec 15 10:25AM -0500

On 12/15/2016 09:36 AM, Paavo Helde wrote:
 
> If you can use STL in your project, then it looks like you are finished.
> Just use std::allocate_shared(your_allocator(), ...) for creating your
> objects.
 
On an ARM this may be possible. If I wanted to use this pool on
something like a high-end AVR 8 bit it wouldn't be, as unfortunately the
STL that is available for that platform is not entirely C++11 compatible
or complete (it just doesn't have the horsepower for many STL
structures, anyway.)
 
Containers like std::vector seem to perform admirably on a "modern" 8
bit architecture, but something like std::map I would be more cautious
about.
 
The C++11 STL smart pointers are out, as I guess they assume nobody
would be using them on an architecture with no MMU, where you shouldn't
really be dynamically allocating objects in raw form to the heap.
 
> smartpointer class itself is straightforward, one just needs to take
> care to define *all* needed operations and get the self-assignment and
> cycle breaking assignments correct.
 
Thanks so much! AFAIK right now, for my intended application the answers
to those questions is no, except I'm not entirely sure about thread-safe
reference counting. I'm hoping to use the code in a message queue for an
event-driven real time system, sort of like the "observer pattern": one
object needs to pass a message with some data to another, so it
instantiates a data package in its pool, plops a reference to the
package in a shared queue (like a vector of smart pointers), the
intended receiver listens for it, consumes the data, pops the reference
off the queue and everything is cleaned up.
 
I've taken some stabs at doing this using "straight C++", like using
abstract classes which all the message packages inherit from and
polymorphism, but it's seemed difficult to implement this type of system
cleanly and extensibly (and without a lot of vtable overhead) without
some fashion of dynamic memory allocation and smart pointer which can
handle generic types.
 
So there will likely be threads of a fashion, but it will be more in the
vein of a cooperative multitasking/round robin scheduler "protothreads"
type situation than full-fledged threads where there's context-switching
and the entire register set and state is stored in a stack frame.
Paavo Helde <myfirstname@osa.pri.ee>: Dec 15 05:48PM +0200

On 15.12.2016 17:25, bitrex wrote:
> to those questions is no, except I'm not entirely sure about thread-safe
> reference counting.
 
Making this schema thread-safe is pretty simple, in C++11 one just needs
to declare the refcounter as std::atomic<int> instead of int.
Alternatively, I imagine that there might be some read-and-update atomic
operations present also on embedded platforms. One only needs to
increment and decrement the refcounter atomically and detect when it
drops to zero.
 
Cheers
Paavo
bitrex <bitrex@de.lete.earthlink.net>: Dec 15 01:46PM -0500

On 12/15/2016 10:48 AM, Paavo Helde wrote:
> drops to zero.
 
> Cheers
> Paavo
 
Thanks. Often on small uPs simply disabling interrupts (assuming that a
timer interrupt is where the scheduler "tick" is coming from) and
re-enabling after read/write is enough to ensure the operation is atomic.
Jorgen Grahn <grahn+nntp@snipabacken.se>: Dec 15 08:39PM

On Thu, 2016-12-15, bitrex wrote:
...
> The C++11 STL smart pointers are out, as I guess they assume nobody
> would be using them on an architecture with no MMU, where you shouldn't
> really be dynamically allocating objects in raw form to the heap.
 
I was happily using dynamic allocation on such systems in the early
1990s. So was anyone else programming e.g. the Commodore-Amiga. An
MMU is not a requirement for malloc/new.
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 15 09:38PM +0100

On 15.12.2016 21:39, Jorgen Grahn wrote:
 
> I was happily using dynamic allocation on such systems in the early
> 1990s. So was anyone else programming e.g. the Commodore-Amiga. An
> MMU is not a requirement for malloc/new.
 
As I recall the original Amiga used an MC68000 processor, with a 24-bit
address bus and MMU?
 
The 68000 was very nice.
 
:)
 
 
Cheers!,
 
- Alf
scott@slp53.sl.home (Scott Lurndal): Dec 15 08:57PM


>As I recall the original Amiga used an MC68000 processor, with a 24-bit
>address bus and MMU?
 
>The 68000 was very nice.
 
IIRC, 68030 was the first 68k with an integrated MMU. Even the
88100 needed an 88200 for the MMU functionality.
 
The Amiga 1000 (sold mine recently) had a 7mhz 68000.
bitrex <bitrex@de.lete.earthlink.net>: Dec 15 04:29PM -0500

On 12/15/2016 03:39 PM, Jorgen Grahn wrote:
> 1990s. So was anyone else programming e.g. the Commodore-Amiga. An
> MMU is not a requirement for malloc/new.
 
> /Jorgen
 
Sure, new works just fine with the Arduino/AVR environment, etc. For
example if you want to have some object ready to use on main loop start
you can do:
 
#include <stdint.h>
#include <new>
 
struct MyObject {
void do_stuff() { etc.. }
};
 
MyObject* my_object1 = nullptr;
MyObject* my_object2 = nullptr;
 
static uint8_t my_object_buf[sizeof(MyObject)];
static uint8_t *const buf_ptr = &my_object_buf[0];
 
void setup() {
//someplace in heap determined by compiler
my_object1 = new MyObject();

//placed in static buffer
my_object2 = new (buf_ptr) MyObject();
}
 
void loop() {
my_object1->do_stuff();
my_object2->do_stuff();
}
 
I can delete and new objects from and into buf_ptr as much as I want
with no problems if they're of type MyObject. But I don't think using
"raw" new and delete as with my_object1 would be a good idea over and
over again from a fragmentation standpoint...
Tim Rentsch <txr@alumni.caltech.edu>: Dec 14 04:41PM -0800

> where this trick would make sense at all. If there are no const
> members or references then everything can be done by a normal
> assignment operator, can't it?
 
It looks to me like normal assignment can do the job, yes.
Although it might be more convenient, code-wise, to use an
in-place constructor than to simulate what the constructor
would do.
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)