samedi 17 août 2019

Circular LinkList using a custom shared Allocator

I have been given the following skeleton to implement.

template <typename DataType>
class ListAllocator {
 public:
  DataType* allocate(size_t size) {
    // TODO: implement
  }

  void deallocate() {
    // TODO: implement
  }

 private:
  static constexpr unsigned int MAX_DATA_SIZE = 2048;
  unsigned char storage[MAX_DATA_SIZE];
};

template <typename DataType, typename Allocator = 
ListAllocator<DataType>>
class CircularList {
  // TODO: implement CircularList
 public:
  // Adds new element to the end of the list
  void push_back(DataType value) {
    // TODO: implement
  }

  // Adds new element to the beginning of the list
  void push_front(DataType value) {
    // TODO: implement
  }

  // Inserts new element after provided node
  void insert_after(Node* node, DataType value) {
    // TODO: implement
  }

  // Removes last element from the list and returns it
  DataType pop_back() {
    // TODO: implement
  }

  // Removes first element from the list end returns it
  DataType pop_front() {
    // TODO: implement
  }

 private:
  static Allocator allocator;
};

Here are the constraints -

  • No dynamic allocation (new, malloc, etc.)
  • There is one allocator for multiple CircularList objects Solution has to be thread safe.
  • Make it as cache friendly as possible
  • Make it as optimal as you can
  • You can add new members to classes/structs if needed but you shouldn't Change prototypes of existing member functions

I am looking for starting points to implement the Allocator. Perhaps I can use the placement new operator but then what do I deallocate ? Since allocator is shared how would circular list will keep track of memory being used by particular Circular list.

Aucun commentaire:

Enregistrer un commentaire