How Do I Make This Container Thread-Safe?

[MutantJohn]

Okay, I think the underlying issue is that I need to separate construction from initialization. Constructing a block could simply mean just calling the constructor which would trigger all nested constructors, right? That still leaves the elements' free list to be built. And the boundaries need to be set as well.

I hope I'm starting to get it now but I should just have a simple constructor for an element that initializes everything to 0. I'm assuming the memset on the data member was okay though.

So, let's talk about making the second bit of each pointer 1. The only way I could get C++ to compile silently was by doing stuff like,

Element<T> *n = // ...
(size_t ) n | 3 == 2
// or
n = (Element<T>* ) ((size_t ) n | 2)

I guess that's why I was okay with writing,

n = (Element<T>* ) 2

because I assumed it would become the address 2 which is perfect because non-masked, that's all 0's.

[Dave11]

You don't set the pointer to some random data, even if you give that random human meaning.
pointers should either point to legit - living variables or to null. that's it.
when you're doing anything else you're reproducing bugs that where common in the 80's C. don't do it.

[MutantJohn]

But CGAL did it!

[Dave11]

good for them. there are better ways of doing things.

[MutantJohn]

Got any ideas as to how? I'll post more about what I needo from a container tonight.

[Dave11]

Well, let's think a minute on what you want.
you want to mark the pointer for when it's occupied, when it's freed and when it points to some boundry:

so when the pointer is null - it's free.
when the pointer is not null :
create two members variables, one is the "head" , the other is the "tail". this concept is called "A Sentry".
if the pointer points to one of these 2 - it's pointing to a boundry
if not - the pointer is occupied.

[King Mir]

Well, let's think a minute on what you want.
you want to mark the pointer for when it's occupied, when it's freed and when it points to some boundry:

so when the pointer is null - it's free.
when the pointer is not null :
create two members variables, one is the "head" , the other is the "tail". this concept is called "A Sentry".
if the pointer points to one of these 2 - it's pointing to a boundry
if not - the pointer is occupied.

So I admit I did not actually read the code in the OP. But if the objective is to create a free list, then this method doesn't work. The point of a free list is to keep track of freed memory in your application and resue it next time you need an similar object. So when you release memory, it doesn't actually get returned to the os routines. It needs to be kept around, and so you need to keep around a pointer to it. But you need to mark that pointer as free. Therefore replacing the pointer with a sentry would not work, because that would loose track of the memory it points to. That's why an extra bit is used to mark the pointer as free. This technique works, provided that you always clear those extra bits before you use it.

Of course a simpler aproach would be to keep an extra boolean or two around with the pointer, but that would use more memory.

[MutantJohn]

King Mir has the right idea. Sorry I didn't post last night. Will try tonight. But yes, I need an actual list of addresses.

[MutantJohn]

You don't set the pointer to some random data, even if you give that random human meaning.
pointers should either point to legit - living variables or to null. that's it.
when you're doing anything else you're reproducing bugs that where common in the 80's C. don't do it.

This post actually resonated with me pretty well. I agree with your sentiment. It feels exactly like some dirty 'hack' from the 80's. Alright, I'll just store the state in some extra enumeration in the class.

Okay, so let's talk about why this container is awesome for CGAL and why it's the main motivation for them creating it in the first place. It's because when you refine elements of a mesh, you often times wind up doing a delete and then a create. The number of creates and deletes hardly ever matches.

It's also common for triangulation softwares to insert points in a spatially-sequenced order. This way, point insertions and triangle refinement happen in a localized area. This means all your calculations are typically with the same set of data so cache coherency is actually quite high.

So, this generates a set of requirements that is, we need a container that supports deletion as well as it does insertion and one that also plays to spatial locality. Hence, we allocate contiguous blocks and generate the free list by simply storing a pointer in each element of a block.

I've been thinking about this and I think I have something a little more naive but maybe more pure:

std::vector<Tetra*> free_list_;
std::vector<Tetra*> tetra_list_;

But this comes with a set of stipulations. This is more pseudo-code than anything else in the sense that when I say use std::vector for the tetra_list_, just use a contiguous block because we're going to delete random elements and by that I mean, we're probably just going to call the destructor on an element and then push_back that address to the free list which we always access with a pop_back() because you can pop_back() on a std::vector all day and not suffer the performance of a reallocation or a copy like you would with a normal std::vector::erase or whatever it's called.

It seems a lot simpler, I think.

[MutantJohn]

Hey phantom and other posters who are awesome, is this at all even a tiny bit better? Let's forget about error handling and stuff for now (stuff like malloc/new failing) :

#ifndef CONTAINER_HH_
#define CONTAINER_HH_


#include "globals.hh"


template<class T>
class Block {
private:
  T *elements_;
  size_t capacity_;


public:
  Block(size_t num_elements) {
    elements_ = new T[num_elements];
    capacity_ = num_elements;
  }


  Block(Block &&other) : elements_(other.elements_), capacity_(other.capacity_) {
    other.elements_ = nullptr;
    other.capacity_ = 0;
  }


  ~Block(void) {
    if (elements_)
      delete[] elements_;
  }


  T* data(void) {
    return elements_;
  }
};


template<class T>
class Container {
private:
  std::list<Block<T>> blocks_;
  std::vector<T*> free_list_;
  size_t block_size_ = 16;


  void appendBlock(void) {
    blocks_.push_back(Block<T>(block_size_));


    T *tmp = blocks_.back().data();


    for (size_t i = 0; i < block_size_; ++i) {
      free_list_.push_back(tmp + i);
    }


    block_size_ += 16;
  }


public:
  Container(void) {
    free_list_.reserve(block_size_);
  }


  ~Container(void) {


  }


  void insert(const T &t) {
    if (free_list_.size() == 0) {
      appendBlock();
    }


    T *tmp = *(free_list_.end() - 1);
    new(tmp) T(t);


    free_list_.pop_back();
  }


  void insert(T &&t) {
    if (free_list_.size() == 0) {
      appendBlock();
    }


    T *tmp = *(free_list_.end() - 1);
    new(tmp) T(std::move(t));


    free_list_.pop_back();
  }
};


#endif

main.cc

#include "include/container.hh"


struct nontrivial {
  int *data;


  nontrivial(void) {
    data = new int[256];
  }


  nontrivial(const nontrivial &other) {
    data = other.data;
  }


  nontrivial(nontrivial &&other) {
    delete[] data;
    data = other.data;
    other.data = nullptr;
  }


  ~nontrivial(void) {
    if (data)
      delete[] data;
  }
};




int main(void) {
  Container<nontrivial> c;
  c.insert(nontrivial()); 


  return 0;
}

[Yarin]

MutantJohn, why do you want to use a linked list? An array/vector would be easier.

[MutantJohn]

Actually, it really would be.

I also had a different thought and I think this might be what phantom was alluding to. It's the concept of ownership. Who owns what and what are they responsible for doing?

He said, I wasn't calling new and delete when I needed to and now I think I'm starting to get it. Also, his comment about me abusing placement new.

It was because I didn't understand the constructor semantics and how that relates to what owning the emplaced objects really means. It was never an issue with malloc() or free() but with my lack of understanding of my responsibilities as a programmer.

To illustrate my growing understanding, I need to maintain the list of objects that I own. In this case, I can only own an object when it's constructed. There's only 3 types of constructors I need to implement. The default, copy and move. The default may never be necessary to define as the interface for the container is basically an insert() method which will get passed either an rvalue or an lvalue (I think, this nomenclature is new to me).

When I construct an object in the pool using placement new, I need to track this object so that it can be properly destructed because free() doesn't call destructors. I had the thought, what if I used a hash table to keep track of alive objects? I can use something like std::set or std::unordered_set and this way, I'd be guaranteed to call the desctructor of each object that the container owns.

[phantomotap]

O_o

I want an explanation for every line I've marked (//?) as well as the behaviour of the application when executed.

Of course, I can only make a request.

On the other hand, I will be adding you to my ignore list if you don't provide a satisfactory explanation.

Soma

#ifndef CONTAINER_HH_
#define CONTAINER_HH_

#include <iostream>
#include <vector>
#include <list>
#include <map>

template<class T>
class Block {
private:
  T *elements_;
  size_t capacity_;


public:
  Block(size_t num_elements) {
    elements_ = new T[num_elements];
    capacity_ = num_elements;
  }


  Block(Block &&other) : elements_(other.elements_), capacity_(other.capacity_) {
    other.elements_ = nullptr;
    other.capacity_ = 0;
  }


  ~Block(void) {
    if (elements_) //?$
      delete[] elements_;
  }


  T* data(void) {
    return elements_;
  }
};


template<class T>
class Container {
private:
  std::list<Block<T>> blocks_;
  std::vector<T*> free_list_;
  size_t block_size_ = 16;


  void appendBlock(void) {
    blocks_.push_back(Block<T>(block_size_));


    T *tmp = blocks_.back().data();


    for (size_t i = 0; i < block_size_; ++i) {
      free_list_.push_back(tmp + i);
    }


    block_size_ += 16;
  }


public:
  Container(void) {
    free_list_.reserve(block_size_);
  }


  ~Container(void) {


  }


  void insert(const T &t) {
    if (free_list_.size() == 0) {
      appendBlock();
    }


    T *tmp = *(free_list_.end() - 1);
    new(tmp) T(t); //?1


    free_list_.pop_back();
  }


  void insert(T &&t) {
    if (free_list_.size() == 0) {
      appendBlock();
    }


    T *tmp = *(free_list_.end() - 1);
    new(tmp) T(std::move(t)); //?1


    free_list_.pop_back();
  }
};


#endif


std::map<void *, int> flag;

void mark(void * f) { //?!
  if (flag.end() == flag.find(f))
    flag[f] = 1;
  else {
    ++flag[f];
    std::cout << "what? (con): (" << f << ", " << flag[f] << ")\n";
  }
}

void unmark(void * f) { //?!
  if (flag.end() != flag.find(f))
    if (flag[f] == 1)
      flag.erase(f);
    else {
      std::cout << "what? (dec): (" << f << ", " << flag[f] << ")\n";
      --flag[f];
    }
  else {
    std::cout << "what? (dec): (" << f << ", " << flag[f] << ")\n";
    --flag[f];
  }
}

struct nontrivial {
  int *data;
  int m;


  nontrivial(void) {
    data = new int[256]; //?2
    mark(this);
  }


  nontrivial(const nontrivial &other) {
    data = other.data; //?2
    mark(this);
  }


  nontrivial(nontrivial &&other) {
    delete[] data; //?3
    data = other.data;
    other.data = nullptr;
    mark(this);
  }


  ~nontrivial(void) {
    unmark(this);
    if (data) //?$
      delete[] data; //?2
  }
};




int main(void) {
  {
    Container<nontrivial> c;
    c.insert(nontrivial());
  }
  std::cout << '\n';
  {
    Container<nontrivial> c;
    c.insert(nontrivial());
    c.insert(nontrivial());
  }
  std::cout << '\n';

  return 0;
}

[MutantJohn]

  ~Block(void) {    if (elements_) //?$
      delete[] elements_;
  }

I think this actually might've been my code. I think it's something that needs to be trashed, tbh. It was my attempt at preventing a double free/delete but I think delete is 'safe' in the sense that if you pass in a nullptr or something logically equivalent, it just returns harmlessly.

    new(tmp) T(t); //?1

I think this is supposed to create an element in-place using the copy constructor of the specified type. Again, this is my own code. This is actually what we want to use though. Inserting an element is logically equivalent to constructing an element in the container so this is acceptable. We're constructing a new element using a copy of an old one.

    new(tmp) T(std::move(t)); //?1

This is similar to above, just this time we're using the move constructor to construct a new element. This is so data without a more permanent address can be transferred to data that is assignable. I think that's how lvalue and rvalue stuff works. lvalues were assignable while rvalues were objects unwind from the stack before current scope changes clean them up automatically. Like, values that disappear after a calculation, for example. 1 + 2 destructs immediately upon its assignment to something more permanent.

void mark(void * f) { //?!
  if (flag.end() == flag.find(f))
    flag[f] = 1;
  else {
    ++flag[f];
    std::cout << "what? (con): (" << f << ", " << flag[f] << ")\n";
  }
}

Hmm...

You're doing a look-up based on an address. If the address does not exist in the map, the flag is set to 1 (therefore free). Otherwise, if the value is there, increment the value and by doing so, you're making this address as one that points to an object whose destructor needs to be called. It's the implementation of the idea I threw out there towards the end of my post. I think std::map is iterable too.

void unmark(void * f) { //?!
  if (flag.end() != flag.find(f)) // if (address is in map)
    if (flag[f] == 1) // if element is 'free', just harmlessly erase (no destructors need to be called)
      flag.erase(f);
    else {
      std::cout << "what? (dec): (" << f << ", " << flag[f] << ")\n";
      --flag[f]; // else set this address back to its free state (I really hope a destructor is called sometime near when this one is)
    }
  else { // this part I don't get... if flag isn't in the map, does writing flag[f] implicitly add it there?
// Oh, it does. Ha! How neat! Anyway, if the address we're looking to unmark isn't in the map,
// we go ahead and yolo add it. Now, as to why we go ahead and it anyway, I guess it's because
// we're drawing attention to an address and it'd be good to track its state in some way.
    std::cout << "what? (dec): (" << f << ", " << flag[f] << ")\n";
    --flag[f];
  }
}

[Yarin]

std::map<void *, int> flag;

void mark(void * f) {
  if (flag.end() == flag.find(f))
    flag[f] = 1;
  else {
    ++flag[f];
    std::cout << "what? (con): (" << f << ", " << flag[f] << ")\n";
  }
}

void unmark(void * f) {
  if (flag.end() != flag.find(f))
    if (flag[f] == 1)
      flag.erase(f);
    else {
      std::cout << "what? (dec): (" << f << ", " << flag[f] << ")\n";
      --flag[f];
    }
  else {
    std::cout << "what? (dec): (" << f << ", " << flag[f] << ")\n";
    --flag[f];
  }
}

The STL has a multiset, you know.