Programmer's Blog

Programmer's reference

[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

Advertisements

[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

[vim] settings for .vimrc

set hidden

set nowrap        " don't wrap lines
set tabstop=4     " a tab is four spaces
set backspace=indent,eol,start
                    " allow backspacing over everything in insert mode
set autoindent    " always set autoindenting on
set copyindent    " copy the previous indentation on autoindenting
set number        " always show line numbers
set shiftwidth=4  " number of spaces to use for autoindenting
set shiftround    " use multiple of shiftwidth when indenting with '<' and '>'
set showmatch     " set show matching parenthesis
set ignorecase    " ignore case when searching
set smartcase     " ignore case if search pattern is all lowercase,
                    "    case-sensitive otherwise
set smarttab      " insert tabs on the start of a line according to
                    "    shiftwidth, not tabstop
set hlsearch      " highlight search terms
set incsearch     " show search matches as you type
set history=1000         " remember more commands and search history
set undolevels=1000      " use many muchos levels of undo
set wildignore=*.swp,*.bak,*.pyc,*.class
set title                " change the terminal's title
set visualbell           " don't beep
set noerrorbells         " don't beep
set nobackup
set noswapfile

[SQL] delete duplicated rows

DELETE FROM table
WHERE rowid not in
(SELECT MIN(rowid)
FROM table
GROUP BY column1, column2);

[C] Returnable 2D array and readfile

char** create2DCharArray(int m, int n)
{
   char* values = calloc(m*n, sizeof(char));
   char** rows = malloc(n*sizeof(char*));
   int i;
   for (i=0; i<n; ++i)
   {
       rows[i] = values + i*m;
   }
   return rows;
}

void destroy2DCharArray(char** arr)
{
   free(*arr);
   free(arr);
}

char** readFileInto2DArray ( const char* fileName )
{
   FILE *f;
   f = fopen(fileName,"r");
   char ch, strr[32767], *str;
   int row = 0, column = 0, i = 0, j = 0;
   while(fgets(strr, sizeof strr, f))
   {
      row++;
      if(column < strlen(strr) )
           column = strlen(strr);
   }
   rewind(f);
   char** arr = create2DCharArray(column,row);
   while(i < row)
   {
     do
     {
        ch = fgetc(f);
        if ( ch == '\r')
        ch = fgetc(f);
        arr[i][j] = ch;
        j++;
     }
     while( !( ch == '\n' || ch == EOF ) );
     arr[i][--j] = '\0';
     i++;
     j = 0;
   }
   fclose(f);
   return arr;
}

[regex] inverse selection

/\<\(THEWORD\>\)\@!\k\+\>

[Linux] Useful commands

Execute commands on files found by the find command
$ find -iname "MyCProgram.c" -exec md5sum {} \;

Find all empty files in home directory
# find ~ -empty

converts the DOS file format to Unix file format using sed command.
$sed 's/.$//' filename

Print only specific field from a file.
$ awk '{print $2,$5;}' employee.txt

Go to the 143rd line of file
$ vim +143 filename.txt

Open the file in read only mode.
$ vim -R /etc/passwd

[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;
};