Monday, November 28, 2016

Digest for comp.lang.c++@googlegroups.com - 25 updates in 6 topics

xerofoify <xerofoify@gmail.com>: Nov 28 01:11PM -0800

Greetings All,
Seems the tree is now segfaulting and can't figure out why. I am getting very annoyed with and have no idea why. I have tried everything I can think of to no result, I will post the code again. But can someone show me a complete working insert and constructor as I have no idea why this doesn't work.
#include <iostream>
using namespace std;
//Threaded Binary Tree Class that is templated to hold Node pointers with data type T
template <class T>
class ThreadedTree{

//Internal Node Class for each Node in the tree
struct Node{
//Constructor for Node Class
//Takes the data to be held as a paramater and Node pointers for left and right elements
//defaults are nullptr for left and right elements and data is set to default value for data type T
Node(const T& data = T{}, Node* left = nullptr, Node* right = nullptr){
data_ = data;
right_ = right;
left_ = left;
}
T data_;
Node*left_;
Node* right_;
bool leftThread;
bool rightThread;
//Finds the leftmost from the struct Node pointer passed in, returns nullptr if the Node is nullptr
struct Node* leftMost(struct Node *n){
if (n == nullptr){
return nullptr;
}
while (n->left_ != nullptr){
n = n->left_;
}
 
return n;
}
//Finds the rightmost from the struct Node pointer passed in, returns nullptr if the Node is nullptr
struct Node* rightMost(struct Node *n){
if (n == nullptr){
return nullptr;
}
 
while (n->right_ != nullptr){
n = n->right_;
}
 
return n;
}
};
Node* root_;
void cleanup(Node* subtreeroot){
if(subtreeroot==root_){
return;
}
if (subtreeroot){
cleanup(subtreeroot->left_);
cleanup(subtreeroot->right_);
delete subtreeroot;
}
}
public:
class const_iterator{
protected:
friend class ThreadedTree;
//Constructor that sets curr_ internal Node for iterator to Node passed in agrument Node* c
const_iterator(Node* c){ curr_ = c; }
Node* curr_;
//Checks current node is not nullptr
bool checkData(){
return curr_ == nullptr;
}
public:
//Constructor that sets curr_ internal iterator Node to nullptr
const_iterator(){
curr_ = nullptr;
}
//Takes a interger and makes iterator point to next right element before returning previous element
const_iterator operator++(int){
if(curr_==nullptr){
}
const_iterator old = *this;
if (curr_->rightThread){
curr_ = curr_->right_;
}
else {
curr_ = curr_->left_;
curr_ = curr_->rightMost(curr_);
}
return const_iterator(old);
}
//Takes a interger and makes iterator point to next left element before returning previous element
const_iterator operator--(int){
const_iterator old =*this;
if(curr_==nullptr){
return nullptr;
}
if (curr_->leftThread){
curr_ = curr_->left_;
}
else{
curr_ = curr_->right_;
curr_ = curr_->leftMost(curr_);
}
return const_iterator(old);
}
//Takes no arguments and makes iterator point to next right element
const_iterator operator++(){
if (curr_==nullptr){
return nullptr;
}
if(curr_->rightThread){
curr_= curr_->right_;
}
else{
curr_ = curr_->left_;
curr_ = curr_->rightMost(curr_);
}
return iterator(curr_);
}
//Takes no arguments and makes iterator point to next left element
const_iterator operator--(){
if(curr_==nullptr){
return nullptr;
}
if(curr_->leftThread){
curr_ = curr_->right_;
}
else{
curr_ = curr_->right_;
curr_ = curr_->leftMost(curr_);
}
return iterator(curr_);
}
//Takes no arguments and returns internal Node of iterator
const T& operator*(){
return curr_->data_;
}
//Takes const_iterator reference and sees if internal element equals passed reference's element
bool operator==(const const_iterator& rhs) const{
return curr_ == rhs.curr_;
}
//Takes const_iterator reference and sees if internal element does not equals passed reference's element
bool operator!=(const const_iterator& rhs) const{
return curr_ != rhs.curr_;
}
friend class ThreadedTree;
};
class iterator :public const_iterator{
protected:
//Constructor that sets curr_ internal iterator Node to Node passsed
iterator(Node* c) :const_iterator(c){}
public:
// Constructor that sets curr_ internal iterator Node to nullptr
iterator() :const_iterator(){}
const T& operator*(){
return this->curr_->data_;
}
 
iterator operator++(int){
iterator old = *this;
if(this->checkData()) {
return nullptr;
}
if (this->curr_->rightThread){
this->curr_ = this->curr_->right_;
}
else{
Node* pass = this->curr_->left_;
this->curr_ = this->curr_->left_;
this->curr_ = this->curr_->rightMost(pass);
}
return iterator(old);
}
//Takes a interger and makes iterator point to left element before returning previous element
iterator operator--(int){
const_iterator old = *this;
if(this->checkData()){
return nullptr;
}
if (this->curr->leftThread){
this->curr = this->curr->right_;
}
else{
Node* pass = this->curr_->left_;
this->curr_ = this->curr_->right_;
this->curr_ = this->curr_->leftMost(pass);
}
return iterator(old);
}
//Takes a interger and makes iterator point to next right element before returning previous element
iterator operator++(){
if(this->checkData()){
return nullptr;
}
if (*this->curr->rightThread){
this->curr = this->curr->right_;
}
else{
this->curr_ = this->curr_->left_;
this->curr_ = this->curr_->rightMost(this->curr_->right_);
}
return iterator(this->curr_);
}
//Takes no arguments and makes iterator point to next right element
iterator operator--(){
if(this->checkData()){
return nullptr;
}
if(this->curr->leftThread){
this->curr = this->curr->right_;
}
else{
this->curr_ = this->curr_->right_;
this->curr_ = this->curr_->leftMost(this->curr_->left_);
}
return iterator(this->curr_);
}
 
friend class ThreadedTree;
};
//Constructor that creates new Tree, takes no arguments and sets tree to new state
ThreadedTree(){
root_ = new Node();
root_->leftThread = true;
root_->leftThread = false;

}
void printTree()
 
{
 
Node *tmp = root_, *p;
 
for (;;)
 
{
 
p = tmp;
 
tmp = tmp->right_;
 
if (!p->rightThread)
 
{
 
while (!tmp->leftThread)
 
{
 
tmp = tmp->left_;
 
}
 
}
 
if (tmp == root_)
 
break;
 
cout<<tmp->data_<<" ";
 
}
 
cout<<endl;
 
}
//Takes const reference of type T and inserts it into tree, returns iterator to inserted Node
iterator insert(const T& data){
Node* p = root_;
for (;;){
if (p->data_ < data){
if (p->leftThread)
break;
p = p->right_;
}
else if (p->data_ > data){
if (p->rightThread)
break;
p = p->left_;
}
}
Node* tmp = new Node();
tmp->data_ = data;
tmp->rightThread = tmp->leftThread = true;
if (p->data_ < data){
tmp->right_ = p->right_;
tmp->left_ = p;
p->right_ = tmp;
p->rightThread = false;
return iterator(p->right_);
}
else{
tmp->right_ = p;
tmp->left_ = p->left_;
p->left_ = tmp;
p->leftThread = false;
return iterator(p->left_);
}
}
//Takes const reference of type T and finds it in table,if not found returns nullptr
iterator find(const T& data) const{
Node *tmp = root_->left_;
for (;;){
if (tmp->data_ > data){
if (tmp->rightThread)
return nullptr;
tmp = tmp->right_;
}
else if (tmp->data_ < data){
if (tmp->leftThread)
return nullptr;
tmp = tmp->left_;
}
else{
return iterator(tmp);
}
}
}
//Takes no arguments and returns leftmost Node in Tree as iterator
iterator begin(){
Node* curr = root_;
if (curr->right_ == nullptr && curr->left_ == nullptr) {
return nullptr;
}
if (curr != nullptr) {
while(curr->left_!=nullptr){
curr = curr->left_;
}
}
return iterator(curr);
}
//Takes no arguments and returns rightmost Node in Tree as iterator
iterator end(){
return nullptr;
}
//Takes no arguments and returns leftmost Node in Tree as const_iterator
const_iterator begin() const{
Node* curr = root_;
if (curr->right_ == nullptr && curr->left_ == nullptr) {
return nullptr;
}
if (curr != nullptr) {
while(curr->left_!=nullptr){
curr = curr->left_;
}
}
return const_iterator(curr);

}
//Takes no arguments and returns rightmost Node in Tree as iterator
const_iterator end() const{
return nullptr;
}
//Destructor that destroys tree
~ThreadedTree(){
cleanup(root_);
}
};
legalize+jeeves@mail.xmission.com (Richard): Nov 28 09:32PM

[Please do not mail me a copy of your followup]
 
xerofoify <xerofoify@gmail.com> spake the secret code
 
>Seems the tree is now segfaulting and can't figure out why.
 
Use a debugger and examine the cause of the segfault. Step through
the code in the debugger leading up the to segfault after you've
discovered the cause.
 
Write unit tests on your code to verify all control paths as you
develop them.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
xerofoify <xerofoify@gmail.com>: Nov 28 01:47PM -0800

On Monday, November 28, 2016 at 4:32:08 PM UTC-5, Richard wrote:
> The Terminals Wiki <http://terminals-wiki.org>
> The Computer Graphics Museum <http://computergraphicsmuseum.org>
> Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
I have tried that everything. I even drew it up hand. I don't get how it's not working. Nothing about that code doesn't make sense to me. I really have no idea how it doesn't as in a debugger it hits:
 
if (p->data_ < data){
before crashing even through roots data is properly set here:
Node(const T& data = T{}, Node* left = nullptr, Node* right = nullptr){
so can to explain how T{} is not setting the data.
legalize+jeeves@mail.xmission.com (Richard): Nov 28 10:22PM

[Please do not mail me a copy of your followup]
 
xerofoify <xerofoify@gmail.com> spake the secret code
 
>> Write unit tests on your code to verify all control paths as you
>> develop them.
 
>I have tried that everything.
 
Upload your source and unit tests to a github repo and post the link.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
Paavo Helde <myfirstname@osa.pri.ee>: Nov 29 12:27AM +0200

On 28.11.2016 23:47, xerofoify wrote:
> I have tried that everything. I even drew it up hand. I don't get how it's not working. Nothing about that code doesn't make sense to me. I really have no idea how it doesn't as in a debugger it hits:
 
> if (p->data_ < data){
> before crashing even through roots data is properly set here:
 
What debugger does not show you that p is null at that point? You are
happily updating p in this loop, without ever checking if it becomes
null or not:
 
Node* p = root_;
for (;;) {
if (p->data_ < data) {
if (p->leftThread)
break;
p = p->right_;
} else if (p->data_ > data) {
if (p->rightThread)
break;
p = p->left_;
}
}
 
Moreover, if here p->data_==data, this thing goes into infinite loop.
"Öö Tiib" <ootiib@hot.ee>: Nov 27 03:43PM -0800

On Sunday, 27 November 2016 23:39:16 UTC+2, Alf P. Steinbach wrote:
> > http://...
 
> That looks like spam.
 
> Even your last name looks like spam.
 
Yes, the author clearly just wanted that we click the link to his blog
about testing zapcc.
 
 
> How about a few words about what zapcc is and what the test showed, and
> why you think it's relevant to discuss here or relevant for us to know
> about?
 
zapcc is AFAIK attempted clone of clang to commercial c++ compiler made
by a company of Israel that tries to achieve improved speed of
compilation. Whatever they have done is closed source and in beta test.
bitrex <bitrex@de.lete.earthlink.net>: Nov 27 07:32PM -0500

On 11/27/2016 06:43 PM, Öö Tiib wrote:
 
> zapcc is AFAIK attempted clone of clang to commercial c++ compiler made
> by a company of Israel that tries to achieve improved speed of
> compilation. Whatever they have done is closed source and in beta test.
 
So people are willing to pay money for a C++ compiler where its main
selling point is compilation speed, and not security or guaranteed
behavior, etc?
 
Weird.
bitrex <bitrex@de.lete.earthlink.net>: Nov 27 07:33PM -0500

On 11/27/2016 07:32 PM, bitrex wrote:
> selling point is compilation speed, and not security or guaranteed
> behavior, etc?
 
> Weird.
 
Is this something targeted at the HFT software industry, maybe?
Vir Campestris <vir.campestris@invalid.invalid>: Nov 28 09:44PM

On 27/11/2016 23:43, Öö Tiib wrote:
> zapcc is AFAIK attempted clone of clang to commercial c++ compiler made
> by a company of Israel that tries to achieve improved speed of
> compilation. Whatever they have done is closed source and in beta test.
 
Is that even legal? Surely Clang's licence requires you to publish
derived works? (asd no, I haven't checked)
 
Andy
legalize+jeeves@mail.xmission.com (Richard): Nov 28 10:24PM

[Please do not mail me a copy of your followup]
 
Vir Campestris <vir.campestris@invalid.invalid> spake the secret code
>> compilation. Whatever they have done is closed source and in beta test.
 
>Is that even legal? Surely Clang's licence requires you to publish
>derived works? (asd no, I haven't checked)
 
Clang uses a BSD license which doesn't forbid commercial derivatives.
 
<http://clang.llvm.org/features.html#license>
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
"Christopher J. Pisz" <cpisz@austin.rr.com>: Nov 27 09:02PM -0600

I am still playing with making custom memory management and learning
about it.
 
Out of the 15 example memory managers I've found Googling things up,
ZERO of them work if you do not know the size of the type you will be
allocating and only allocate that type. In other words, I cannot find a
memory manager that allows me to allocate space for more than one type.
Additionally, the design of the type is coupled to the memory manager,
because it contains an overload of new and delete just for that class type.
 
The idea of having my own memory management seems lucrative, because
there is often a time where I know I might be allocating some
10,000-1000,000 objects. We'd significantly improve performance if we
allocated a large chuck of space up front.
 
For example, this simple memory manager I found on IBM's site, that they
used as their first example.
 
https://www.ibm.com/developerworks/aix/tutorials/au-memorymanager/
(headers only)
 
//------------------------------------------------------------------------------
class SpecificToSimpleMM : public ComplexNumber
{
public:
SpecificToSimpleMM(double realPart, double SpecificToSimpleMMPart);
SpecificToSimpleMM(const SpecificToSimpleMM & rhs);
~SpecificToSimpleMM();
 
// These two operators call on a global instance of the memory
manager to allocated and free space
void * operator new(size_t size);
void operator delete(void * pointerToDelete);
};
 
//------------------------------------------------------------------------------
// Memory Manager that allocates space for multiple objects, of a
specific type, at a time
//
// Customized for objects of type SpecificToSimpleMM and works only in
single-threaded environments.
// Keeps a pool of SpecificToSimpleMM objects available and has future
allocations occur from this pool.
class SimpleMemoryManager : public IMemoryManager
{
// Node in the memory pool
struct FreeStoreNode
{
FreeStoreNode * m_next;
};
 
void expandPoolSize();
void cleanUp();
 
// The memory pool
FreeStoreNode * m_freeStoreHead;
 
public:
 
SimpleMemoryManager();
virtual ~SimpleMemoryManager();
 
virtual void * allocate(size_t);
virtual void free(void *);
};
 
 
They had two more; A "bitmapped memory manager" and a "freelist memory
manager", but reading over thier article, it seems to me that both can
only handle one type of object.
 
 
Can you point me to some memory management techniques that allow for
allocating different amounts of storage and are not designed to work
with one type only?
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Nov 28 06:58AM +0100

On 28.11.2016 04:02, Christopher J. Pisz wrote:
[snip]
 
> Can you point me to some memory management techniques that allow for
> allocating different amounts of storage and are not designed to work
> with one type only?
 
Andrei's Loki library has a fast small objects allocator, as I recall.
 
It's open source.
 
 
Cheers & hth.,
 
- Alf
Paavo Helde <myfirstname@osa.pri.ee>: Nov 28 10:37AM +0200

On 28.11.2016 5:02, Christopher J. Pisz wrote:
> memory manager that allows me to allocate space for more than one type.
> Additionally, the design of the type is coupled to the memory manager,
> because it contains an overload of new and delete just for that class type.
 
What do you mean? A memory allocator often needs to allocate memory for
other types than its "native" type. There is a special rebind mechanism
for that.
 
In C++ a custom memory allocator is a template, exactly because it needs
to be instantiated for different types. In your example there was no
template, so I assume it was illustrating something else than C++ memory
allocators.
 
Maybe you are confused what a memory allocator is in C++. It is not
something which you call from some overridden operator new (though it
may be called from there as well). No, a custom memory allocator is
primarily something which you can pass as a template argument for
std::vector or std::allocate_shared, etc.
 
From what I see in the debugger, my allocator template is often called
through the rebind mechanism for types like 'char' or
std::_Container_proxy, etc.
 
> there is often a time where I know I might be allocating some
> 10,000-1000,000 objects. We'd significantly improve performance if we
> allocated a large chuck of space up front.
 
These are called pooled memory allocators. There are many of them
existing, no need to reinvent wheels.
 
[...]
 
> Can you point me to some memory management techniques that allow for
> allocating different amounts of storage and are not designed to work
> with one type only?
 
http://en.cppreference.com/w/cpp/memory/allocator discusses rebind, with
some examples. In C++17 the rebind mechanism seems to be moved over to
allocator_traits, with some cleaner syntax.
 
hth
Paavo
"Christopher J. Pisz" <cpisz@austin.rr.com>: Nov 28 03:59AM -0600

On 11/28/2016 2:37 AM, Paavo Helde wrote:
> to be instantiated for different types. In your example there was no
> template, so I assume it was illustrating something else than C++ memory
> allocators.
 
Memory Management is not equivalent to C++ std::allocator from what I am
finding, and I have not found any that actually use post C++11 allocator
requirements, that works, beyond simply adding a logging features and
the like.
 
Most everything I find is a stand alone mememory management scheme that
does not use allocators at all.
 
 
> may be called from there as well). No, a custom memory allocator is
> primarily something which you can pass as a template argument for
> std::vector or std::allocate_shared, etc.
 
Nope. I know what it is. I've read up on it for a week now.
Even if I was to find a working example of an Allocator post C++11 that
worked and did anything beneficial, the actual memory management
technique would be separate from the allocator itself.
 
>> allocated a large chuck of space up front.
 
> These are called pooled memory allocators. There are many of them
> existing, no need to reinvent wheels.
 
I'd like to reinvent the wheel to learn how the wheel works if nothing
else. There seems to be demand for this kind of thing.
 
 
 
> http://en.cppreference.com/w/cpp/memory/allocator discusses rebind, with
> some examples. In C++17 the rebind mechanism seems to be moved over to
> allocator_traits, with some cleaner syntax.
 
 
That example doesn't actually accomplish anything though. It just uses
the default. It does not show anyone how they would actually implement
their own allocator, one that contains state, or how to implement the
actual memory management.
 
 
Here are examples of what I am finding:
 
https://www.ibm.com/developerworks/aix/tutorials/au-memorymanager/
http://anki3d.org/cpp-allocators-for-games/
http://www.codinglabs.net/tutorial_memory_pool.aspx
https://jfdube.wordpress.com/2011/10/06/memory-management-part-2-allocations-tracking/
 
All of these are memory managers that all work with particular types.
None of them are actually put to use in an allocator.
 
Then I find links on allocator:
 
http://en.cppreference.com/w/cpp/memory/allocator
http://www.drdobbs.com/the-standard-librarian-what-are-allocato/184403759#1
https://rawgit.com/google/cxx-std-draft/allocator-paper/allocator_user_guide.html#examples
 
None of which have any memory management working with them, or have one
that actually compiles and works without severe problems.
 
 
 
From what I understand this is a two part problem. Firstly, actually
learning the memory management techniques, then finding one I can use
for various types. Secondly, implementing it in a way that it can be
used with an allocator. Neither endevour is going very well...
Paavo Helde <myfirstname@osa.pri.ee>: Nov 28 06:53PM +0200

On 28.11.2016 11:59, Christopher J. Pisz wrote:
> finding, and I have not found any that actually use post C++11 allocator
> requirements, that works, beyond simply adding a logging features and
> the like.
 
If you are interested in how exactly a memory manager works in low level
then I am pretty sure they are just working with bytes of memory, no
object type involved.
 
For a C++-compliant memory allocator, see e.g.
 
"https://www.threadingbuildingblocks.org/tutorial-intel-tbb-scalable-memory-allocator"
 
Their C++-compliant allocator is just a wrapper around C-style interface
using untyped memory blocks: scalable_malloc() and scalable_free(). One
can use these directly as well. Here you have low-level implementation
which does not care about types, and the high-level C++-compliant
allocator template which works for any type (see the rebind member).
 
Quote from TBB scalable_allocator.h:
 
//! Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5
/** The members are ordered the same way they are in section 20.4.1
of the ISO C++ standard.
@ingroup memory_allocation */
template<typename T>
class scalable_allocator {
public:
typedef typename internal::allocator_type<T>::value_type value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
template<class U> struct rebind {
typedef scalable_allocator<U> other;
};
 
scalable_allocator() throw() {}
scalable_allocator( const scalable_allocator& ) throw() {}
template<typename U> scalable_allocator(const
scalable_allocator<U>&) throw() {}
 
pointer address(reference x) const {return &x;}
const_pointer address(const_reference x) const {return &x;}
 
//! Allocate space for n objects.
pointer allocate( size_type n, const void* /*hint*/ =0 ) {
return static_cast<pointer>( scalable_malloc( n *
sizeof(value_type) ) );
}
 
//! Free previously allocated block of memory
void deallocate( pointer p, size_type ) {
scalable_free( p );
}
 
//! Largest value for which method allocate might succeed.
size_type max_size() const throw() {
size_type absolutemax = static_cast<size_type>(-1) / sizeof
(value_type);
return (absolutemax > 0 ? absolutemax : 1);
}
#if __TBB_ALLOCATOR_CONSTRUCT_VARIADIC
template<typename U, typename... Args>
void construct(U *p, Args&&... args)
{ ::new((void *)p) U(std::forward<Args>(args)...); }
#else // __TBB_ALLOCATOR_CONSTRUCT_VARIADIC
#if __TBB_CPP11_RVALUE_REF_PRESENT
void construct( pointer p, value_type&& value ) { ::new((void*)(p))
value_type( std::move( value ) ); }
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)