Programmer's Blog

Programmer's reference

Category Archives: C++

[C++] HashMap Implementation

template <typename K, typename V, size_t tableSize, typename F = KeyHash<K, tableSize> >
class HashMap
{
 public:
    HashMap() :
       table(),
       hashFunc()
 {
 }

~HashMap()
{
 // destroy all buckets one by one
 for (size_t i = 0; i < tableSize; ++i) {
     HashNode<K, V> *entry = table[i];

     while (entry != NULL) {
        HashNode<K, V> *prev = entry;
        entry = entry->getNext();
         delete prev;
}

 table[i] = NULL;
 }
}

bool get(const K &key, V &value)
{
     unsigned long hashValue = hashFunc(key);
     HashNode<K, V> *entry = table[hashValue];

     while (entry != NULL) {
         if (entry->getKey() == key) {
             value = entry->getValue();
             return true;
         }

     entry = entry->getNext();
     }

     return false;
}

void put(const K &key, const V &value)
{
   unsigned long hashValue = hashFunc(key);
   HashNode<K, V> *prev = NULL;
   HashNode<K, V> *entry = table[hashValue];

   while (entry != NULL && entry->getKey() != key) {
       prev = entry;
       entry = entry->getNext();
   }

   if (entry == NULL) {
       entry = new HashNode<K, V>(key, value);

       if (prev == NULL) {
            // insert as first bucket
            table[hashValue] = entry;

       } else {
            prev->setNext(entry);
       }
  } else {
       // just update the value
       entry->setValue(value);
  }
}

void remove(const K &key)
{
   unsigned long hashValue = hashFunc(key);
   HashNode<K, V> *prev = NULL;
   HashNode<K, V> *entry = table[hashValue];

   while (entry != NULL && entry->getKey() != key) {
       prev = entry;
       entry = entry->getNext();
   }

   if (entry == NULL) {
      // key not found
      return;

   } else {
       if (prev == NULL) {
       // remove first bucket of the list
       table[hashValue] = entry->getNext();

   } else {
       prev->setNext(entry->getNext());
   }

   delete entry;
 }
}

private:
   HashMap(const HashMap & other);
   const HashMap & operator=(const HashMap & other);
   // hash table
   HashNode<K, V> *table[tableSize];
   F hashFunc;
};
Advertisements

[C++] Basic Binary Search Tree

struct node
{
   int data;
   node * left;
   node * right;
};

//insert elements
node * insert(node * root, int value) {
 
   node *newnode = new node();
   newnode->data = value;
 
   if (!root)
   {
     newnode->left = newnode->right = NULL;
     return newnode;
   } 
   else
   {
     node *tmp = root;
     while (tmp->left != NULL || tmp->right != NULL)
     {
         if (value <= tmp->data)
         tmp = tmp->left;
         else if (value > tmp->data)
         tmp = tmp->right; 
     }
     if (tmp->left) tmp->right = newnode;
     else tmp->left = newnode;
 }

 return root;
}

//inorder search
void inOrder(node *root) {

  if (!root) return;
  if(root->left) inOrder(root->left);
      cout << root->data << " ";
  if(root->right) inOrder(root->right);
}

int max(int i , int j)
{
   return i > j ? i : j;
}

//retrieve height of BST
int height(Node* root)
{
 
  if (!root) return 0;
  else if (!root->left && !root->right) return 0;
  int i = height(root->left) +1;
  int j = height(root->right) +1;
  return max(i,j);
 
}

//Level Order Search
void printLevel(node* root, int h)
{
  if (!root) return;
  if (h == 1)
    cout << root->data << " ";
  else if (h > 1)
  {
     printLevel(root->left, h - 1);
     printLevel(root->right, h - 1);
  }
}

void printLevelOrder(node * root)
{
  if (!root) return;
  int h = height(root);
  for (int i = 0 ; i <= h ; i++)
     printLevel(root, i);
}

//lowest common ancestor
node * lca(node * root, int v1, int v2)
{
   if (!root) return NULL;
 
   if (root->data == v1 || root->data == v2)
       return root;
 
   node* lcaLeft = lca(root->left, v1, v2);
   node* lcaRight = lca(root->right, v1, v2);
 
   if (lcaLeft && lcaRight) return root;
       return (!lcaLeft) ? lcaRight : lcaLeft;
 
}


bool processBST(Node* root, int& min, int& max)
 {
   if (!root) return true;
 
   if(root->data > min && root->data < max &&
     processBST(root->left, min, root->data) && processBST(root->right, root->data, max))
   return true;
     else
   return false;
 
 }

//check if a tree is BST
bool checkBST(Node* root) {
 
 if (!root) return true;
 
 int min = -2147483648;
 int max = 2147483647;
 
 bool a = processBST(root, min, max);
 return a;
}

[C++] (LCS) Longest common sequence problem

 string k = String1;
 string g = String2;
 k.insert(0,1,' ');
 g.insert(0,1,' ');
 
 int m = k.length();
 int n = g.length();
 int arr[m][n];
 
 for (int i = 0 ; i < m ; i++) arr[i][0] = 0;
 for (int j = 0 ; j < n ; j++) arr[0][j] = 0;
 
 for (int i = 1 ; i < m ; i++ )
 {
     for (int j = 1 ; j < n ; j++)
     {
         if (k[i] == g[j])
         {
             arr[i][j] = arr[i-1][j-1] + 1;
         }
         else
         {
             arr[i][j] = arr[i][j-1] > arr[i-1][j] ? arr[i][j-1] : arr[i-1][j];
         }
     }
 } 
 
 cout << arr[m-1][n-1] << endl;

[gdb] Commands for examining program in assembly

i r
i all-r
i f
i proc m
disas 
x/4xw (10w) $sp
x/5i
x/i $pc

[C++]single consumer lock_free_queue implementation

#include \<iostream\>
#include \<atomic\>
#include \<thread\>
#include \<chrono\>
#include \<mutex\>

template\
class lock_free_queue
{
private:
    struct node
    {
        std::shared_ptr\<T\> data;
        node* next;
        node(): next(nullptr) {}
    };

    std::atomic\<node*\> head;
    std::atomic\<node*\> tail;
    node* pop_head()
    {
        node* const old_head=head.load();
        if(old_head==tail.load())
        {
            return nullptr;
        }
    head.store(old_head-\>next);
    return old_head;
    }

public:
    lock_free_queue():
    head(new node),tail(head.load()) {}
    lock_free_queue(const lock_free_queue& other)=delete;
    lock_free_queue& operator=(const lock_free_queue& other)=delete;
    ~lock_free_queue()
    {
        while(node* const old_head=head.load())
        {
            head.store(old_head-\>next);
            delete old_head;
        }
    }
    std::shared_ptr\<T\> pop()
    {
        node* old_head=pop_head();
        if(!old_head)
        {
            return std::shared_ptr\<T\>();
        }
        std::shared_ptr\<T\> const res(old_head-\>data);
        delete old_head;
        return res;
    }

    void push(T new_value)
    {
        std::shared_ptr\<T\> new_data(std::make_shared\<T\>(new_value));
        node* p=new node;
        node* const old_tail=tail.load();
        old_tail-\>data.swap(new_data);
        old_tail-\>next=p;
        tail.store(p);
    }
};

int main()
{
    lock_free_queue\<int\> queue;
    queue.push(1);
    queue.push(2);
    queue.push(3);
    std::cout \<\< *queue.pop() \<\< "\n";
    std::cout \<\< *queue.pop() \<\< "\n";
    queue.push(4);
    std::cout \<\< *queue.pop() \<\< "\n";
    std::cout \<\< *queue.pop() \<\< "\n";
}

//result: 1 2 3 4

[C++]Simple lock-free stack implementation

#include \<iostream\>
#include \<atomic\>

using namespace std;

template \<typename T\>
struct node
{
    T data;
    node* next;
    node* previous;
    node(const T& data) : data(data), next(nullptr), previous(nullptr) {}
};

template \<T\>
class stack
{
    std::atomic\<node\<T\>*\> head;
public:
    void push(const T& data)
    {
        node\<T\>* new_node = new node\<T\>(data);

        new_node->previous = head.load(std::memory_order_relaxed);
        new_node->next = head.load(std::memory_order_relaxed);

        while(!head.compare_exchange_weak(new_node->next, new_node,
        std::memory_order_release,
        std::memory_order_relaxed));
    }

    T pop_front()
    {
        node\<T*\> read_node;
        read_node = head.load(std::memory_order_relaxed);
        T ret = read_node->data;

        while(!head.compare_exchange_weak(read_node, read_node->previous,
        std::memory_order_release,
        std::memory_order_relaxed));

        return ret;
    }
};

int main()
{
    stack\<int\> s;
    s.push(1);
    s.push(2);
    s.push(3);

    cout << s.pop_front() << "\n";
    cout << s.pop_front() << "\n";

    s.push(4);
    cout << s.pop_front() << "\n";
    cout << s.pop_front() << "\n";

} 

//result: 3 2 4 1

[C++] check hardware concurrency

unsigned int n = std::thread::hardware_concurrency();

[C++] Scoped thread class

class scoped_thread
{
  std::thread t;
public:
  explicit scoped_thread(std::thread t_) : t(std::move(t_))
  {
    if(!t.joinable())
      throw std::logic_error(“No thread”);
  }

  ~scoped_thread()
  {
    t.join();
  }
  scoped_thread(scoped_thread const&)=delete;
  scoped_thread& operator=(scoped_thread const&)=delete;
};

[C++] RAII thread guard class

 

class thread_guard
{
  std::thread& t;
public:
  explicit thread_guard(std::thread& t_) : t(t_) {}
  ~thread_guard()
  {
    if(t.joinable())
    {
      t.join();
    }
  }
  thread_guard(thread_guard const&)=delete;
  thread_guard& operator=(thread_guard const&)=delete;
};

 

[C++] Check memory leaks by top

top -b -n 1

To see applications which are leaking memory, look at the following columns:

RPRVT – resident private address space size
RSHRD – resident shared address space size
RSIZE – resident memory size
VPRVT – private address space size
VSIZE – total memory size