So, I've attempted to recreate CGAL's Compact_Container. I haven't looked at their source, really. I'm just trying to go by what's in their papers. You can find a pretty good explanation of the container in Section 3.
A quick explanation of the container is basically, we maintain a linked list of blocks. A block is a contiguous allocation of elements. An element is a node that contains user data and a pointer.
The pointer of the element determines its state. Because of some weird architecture hocus pocus, I guess all addresses are 4-byte multiples so the last two bits are guaranteed to be 0 and we can use those two bits to store the state.
00 = occupied
10 = free
11 = boundary
So, when a container wants to write an element, it uses a free list. When a new block is allocated and added into the linked list, it creates a blank array and the elements of the new block can be appended to the free list.
The free list is really a singly-linked list. If an element contains a pointer whose last two bits are 10, the "actual"value of the pointer is the next element in the free list.
So when we insert into the container, we really just pop off the head and continue on. If we clear the queue, we allocate a new block which adds to the free list again.
Now, in that paper they claim they make it thread-safe by just making sure each thread has its own free list. I'm curious how to implement this. I want to make the container transparent to the user.
Is it possible to get the id of the currently running thread? I was thinking that if I could id the currently executing thread, I'd be able to manage whether or not it needs a free list or it already has one.
Adding blocks will be an atomic operation but that shouldn't hinder any performance because of how blocks are added to the list.
I was also wondering if I could get any feedback on my attempt at a partial implementation of the container. Right now, you can only insert elements but I did make a draft of an iterator and I think my way of managing the free list and adding blocks is working too.
Code:#ifndef CONTAINER_H_ #define CONTAINER_H_ #include <iostream> #include <vector> #include <array> #include <cassert> #include <memory> #include <utility> #include <cstddef> #include <list> /* This code is an attempt at replicating CGAL's memory * container. It's probably not as good. * */ template<class T> class Element; template<class T> class Block; template<class T> class Container; template<class T> class ContainerIterator; /* For an element, the last two bits of the next_ pointer define the state 0 = 00 = occupied 2 = 10 = free 3 = 11 = block boundary The value of the non-masked pointer is then equal to either the next pointer in the free list or a pointer to the start of another block */ template<class T> class Element { public: T data; private: Element *next_; public: Element(void) { next_ = (Element* ) 2; new(&data) T(); } Element(T cpy) { next_ = (Element* ) 2; new(&data) T(cpy); } ~Element(void) { data.~T(); } void SetNext(Element *ptr) { size_t p = (size_t ) ptr | ((size_t ) next_ & 3); next_ = (Element* ) p; } void MakeNull(void) { next_ = nullptr; } Element* GetNext(void) { size_t n = (size_t ) next_ & ~3; return (Element* ) n; } void MakeBoundary(void) { size_t n = (size_t ) next_ | 3; next_ = (Element* ) n; } void MakeBoundary(Element* other) { size_t n = (size_t ) other | 3; next_ = (Element* ) n; } bool IsBoundary(void) const { return ((size_t ) next_ & 3) == 3; } void MakeOccupied(void) { size_t n = (size_t ) next_ & ~3; next_ = (Element* ) n; } bool IsOccupied(void) const { return ((size_t ) next_ & 3) == 0; } }; template<class T> class Block { private: Element<T> *elements_; size_t size_; void init(size_t num_elems) { elements_ = (Element<T>* ) malloc(num_elems * sizeof(*elements_)); size_ = num_elems; elements_[0].MakeNull(); elements_[size_ - 1].MakeNull(); elements_[0].MakeBoundary(); elements_[size_ - 1].MakeBoundary(); } public: Block(size_t num_elems) { init(num_elems); for (size_t i = 1; i < (size_ - 1); ++i) { new(elements_ + i) Element<T>(); elements_[i].SetNext(elements_ + i + 1); } elements_[size_ - 2].SetNext(nullptr); } Block(size_t num_elems, const T data) { init(num_elems); for (size_t i = 1; i < size_ - 1; ++i) { new(elements_ + i) Element<T>(data); } elements_[size_ - 2].SetNext(nullptr); } ~Block(void) { for (size_t i = 0; i < size_; ++i) { elements_[i].~Element<T>(); } free(elements_); } Element<T>* Data(const size_t idx) { return elements_ + idx; } size_t size(void) const { return size_; } }; template<class T> class Container { public: typedef ContainerIterator<T> iterator; private: friend class ContainerIterator<T>; std::list<Block<T>*> blocks_; Element<T> *first_; Element<T> *last_; Element<T> *free_list_; size_t block_size_; void PushBack(void) { block_size_ += 16; Block<T> *new_block = new Block<T>(block_size_); auto last = blocks_.back(); blocks_.push_back(new_block); last->Data(last->size() - 1)->SetNext(blocks_.back()->Data(0)); blocks_.back()->Data(0)->SetNext(last->Data(last->size() - 1)); free_list_ = blocks_.back()->Data(1); last_ = blocks_.back()->Data(block_size_ - 1); } public: Container(void) { block_size_ = 16; Block<T> *new_block = new Block<T>(block_size_); blocks_.push_back(new_block); Block<T>* &first_block = blocks_.front(); free_list_ = first_block->Data(1); first_ = first_block->Data(0); last_ = first_block->Data(first_block->size() - 1); } ~Container(void) { blocks_.remove_if([](Block<T> *b) { delete b; return true; }); } void Insert(T tmp) { if (free_list_ == nullptr) { PushBack(); } free_list_->data = tmp; free_list_->MakeOccupied(); free_list_ = free_list_->GetNext(); } ContainerIterator<T> Begin(void) { auto tmp = ContainerIterator<T>(*this); tmp.SetToFirst(); tmp.FindNextOccupied(); return tmp; } ContainerIterator<T> End(void) { auto tmp = ContainerIterator<T>(*this); tmp.SetToLast(); return tmp; } }; template<class T> class ContainerIterator { private: Container<T> &container_; Element<T> *element_; Element<T> *prev_; public: ContainerIterator(Container<T> &container) : container_(container) { element_ = nullptr; prev_ = nullptr; } void SetToFirst(void) { element_ = container_.first_; assert(element_->GetNext() == nullptr); } void SetToLast(void) { element_ = container_.last_; assert(element_->GetNext() == nullptr); assert(container_.last_ != container_.first_); } void FindNextOccupied(void) { while (!element_->IsOccupied() || element_ == prev_) { if (element_->IsBoundary()) { auto next = element_->GetNext(); if (next == nullptr) { if (element_ == container_.last_) { return; } else { ++element_; continue; } } else { element_ = next; } } ++element_; } prev_ = element_; } void operator++(void) { FindNextOccupied(); } void FindPrevOccupied(void) { while (!element_->IsOccupied()) { } } void operator--(void) { FindPrevOccupied(); } bool operator==(const ContainerIterator &other) const { return element_ == other.element_; } bool operator!=(const ContainerIterator &other) const { return !(element_ == other.element_); } T& operator*(void) { return element_->data; } }; #endif // CONTAINER_H_Code:#include "include/container.h" int main(void) { Container<int> container; for (int i = 0; i < 128; ++i) { container.Insert(i); } for (auto it = container.Begin(); it != container.End(); ++it) { std::cout << *it << std::endl; } return 0; }