Skip to content
Advertisements

Categoryprogramming

Untyped Constants in Golang

Golang is extremely explicit with types. It supports constants of a type. But how about a const 2 or hello. What type would they assume!?
Go solved this problem with untyped constants. Untyped means:

  1. A constant’s type depends on the type of assignee variable.
  2. The assignee’s type must have compatibility to hold constant’s value.

Example

package main

import (
    "fmt"
)

const (
    myconst      = `a untyped constant`
    anotherConst = "a typed const"
)

type myStrType string

func main() {
    fmt.Println("vim-go")

    var name string
    var number int

    // Since name is of type string, both untype & typed string
    // constants work fine.
    name = myconst
    name = anotherConst

    // Doesn't work because a untyped string still is a string.
    // We can't assign it to an integer.
    // number = myconst

    fmt.Println(name, number)

    // This is the use case of untyped consts.
    // A compatible type can hold an untyped constant.
    var newStr myStrType // <---------
    newStr = myconst
    fmt.Println(newStr)
}

Output

$ go run untyped_consts.go                                                                                                                                                                                                              vim-go
a typed const 0
a untyped constant

Remember

  • An untyped constant still has the type.
  • Only a typedef of original type can hold a untyped constant.

References

Design Internals of UNIX Non Blocking Sockets

Fundamental of asynchronous programming: Non Blocking Sockets

Why async socket programming

  • An application can create thousands of sockets but creating a thread per socket becomes infeasible for a large number (e.g. 100k sockets)
  • An async framework consists non-blocking sockets and an event loop
    * The kernel allows applications to seek for an event
    * Application registers a callback to be called when the event occur
    * Callback runs by the same application thread after kernel intimates
      that an event happened on a socket
    
  • This model uses a single thread to poll many sockets for various events and calls the callback.
  • It is concurrent that is runs many tasks but not parallel execution of tasks.

How do a socket turn into non-blocking?

  • A socket is a file, read and written with standard POSIX calls.
  • A system call for read operation uses the kernel BIO (Block I/O). A BIO provides an interface to access a block device.

    FIONBIO int
    Set non-blocking I/O mode if the argument is non-zero. In non-
    blocking mode, read(2) or write(2) calls return -1 and set errno
    to EAGAIN immediately when no data is available (This is
    equivalent to fcntl() F_SETFL O_NONBLOCK and the fcntl() form
    should be preferred)

Written with StackEdit.

Golang Essentials for C & C++ Developers: Part I

I have been a C/C++ developer for more than a decade and now getting a chance to work in Go. There are many past references of C, C++, and Python to learn the language quickly. but there are some new syntax that appear unfamiliar. We share such language specific nuances, used widely in production quality code, to help us browsing Golang code.

Methods

  • A method is similar to a member function of a class (user defined type).
package main
import "fmt"

type Node struct {
    val int64
}

// Returns a pointer of Node type
//
func (n *Node) addNode() *Node {
    newNode := new(Node)
    newNode.val = 10

    return newNode
}

func main() {
        n := &Node {10}
        m := n.addNode()

        fmt.Print(m)
}

A sample program of a linked list in Go with comments explaining the code.

package main

import "fmt"

type Node struct {
        prev *Node
        next *Node

        // key can assume any standard type
        key  interface{}
}

type List struct {
        head *Node
        tail *Node
}
// A method defined for type List, returns nothing
// and accepts a key
//
func (L *List) Insert(key interface{}) {
        // Create a new node with 'next' pointing
        // to Head. The 'prev' is by default zero.
        //
        list := &Node{
                next: L.head,
                prev: nil,
                key:  key,
        }

        // Attaching the new node at the head by
        // updating prev of current head to the
        // newly created node.
        //
        if L.head != nil {
                L.head.prev = list
        }

        // List is the first node so prev is nil
        list.prev = nil

        // Update the head
        L.head = list

        l := L.head

        // Now find the last node and update its tail link
        // to the newly added node.
        //
        for l.next != nil {
                l = l.next
        }

        L.tail = l

        fmt.Printf("head->%d\n", L.head.key)
        fmt.Printf("tail->%d\n", L.tail.key)
}
// Another method defined for type List
//
func (l *List) Display() {
        list := l.head

        for list != nil {
                fmt.Printf("%+v->", list.key)
                list = list.next
        }
        fmt.Println()
}

// A function defined for type List
//
func Display(l *List) {
        list := l.head

        for list != nil {
                fmt.Printf("%+v->", list.key)
                list = list.next
        }
        fmt.Println()
}
func main() {
        link := List{}
        link.Insert(1)
        link.Insert(2)
        link.Insert(3)
        link.Insert(4)
        link.Insert(5)

        // Calling a method
        link.Display()

        // Calling a function
        Display(&link)
}

References

Written with StackEdit.

Linux Device Driver Development: Block Device Driver

It is my very first interaction with Linux kernel at device driver level. My objective is to develop a block device driver, very simple, that just forward I/O requests to a virtual device. This post explains my observations limited to attacking the problem.

Block v/s Character Device

Linux support block and character device drivers. Only block devices can host and support a filesystem. Block devices support random read/write operations. Each block is composed of sectors, usually 512 bytes long and uniquely addressable. Block is a logical entity. Filesystems usually use 4096 bytes blocks (8*512) or 8 sectors. In Linux kernel, a block device is represented as a logical entity (actually just a C structure). So, we can export anything as a device as long as we can facilitate read/writes operations on sector level.

Device driver is the layer that glues Linux kernel and the device. Kernel receives device targeted I/O requests from an application. All I/O requests pass through buffer cache and I/O scheduler. The latter arranges I/O requests optimally to improve seek time, assuming requests would run on a disk. In fact, Linux kernel has various I/O schedulers and hence multiple type of I/O request order could exist.

A device driver always implement a request queue. The Linux I/O scheduler enqueues requests in driver’s queue. How to serve these requests? That is device driver’s headache. The request queue is represented by the request_queue structure and is defined in “blkdev.h". Driver dequeues requests from this queue and send them to device. It then acknowledgement to each requests with error status.

If a device do not need optimal I/O order, it may opt for direct handing of I/O requests. An excellent example of such driver is loopback driver (loop.c, loop,h). It handles struct bio that stands for block I/O. A bio structure is a scatter gather list of page aligned buffer (usually 4K). Handling of bio structure is almost same as a struct req.

What are requirements for my driver

 

  • Runs on flash storage drives
  • Perform plain I/O forwarding
  • Minimal overhead, minimal code size

In my next post, I will discuss design of my driver.

Dissecting Python List allocator (CPython)

List is one of the most frequently used data structure in Python applications. The code for Python list object allocator is present in Python-2.7.5/Objects/listobject.c.

Python allocates list objects in heap and uses underlying malloc based APIs. List is a container of Python object references. In plain C terminology. it is a dynamic array of pointers.

Let’s understand basic creation and insertion APIs.

  • list_resize(): A list is of type PyListObject and is equivalent to PyObject. Every resize request allocates more than asked size.

Allocation unit size is : (size_requested + (size_requested << 3 + (size_requested < 9 : 3 or 6) ).

It gives a growth pattern of (0, 4, 8, 16, 25, 35, 46, 58, 72, 88).

  • free_list: Python keeps PyList_MAXFREELIST (defined to value 80) of free lists to save on lists allocation and deallocation.
  • PyList_New(): A new list allocation requests is served from either a free list or a new GC tracked object creation of type PyListObject. Next, a malloc request is made for requested list size.

Size calculated: nbytes = size * sizeof(PyObject *);

Object allocation: PyListObject *op = free_list[numfree] OR PyObject_GC_New(PyListObject, &PyList_Type);

Memory allocation for references: op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);

Openstack swift: EADDRNOTAVAIL error

Problem

swift-bench keeps EADDRNOTAVAIL error with a highly concurrency setting and multiple swift-bench clients.

Setup

Ubuntu 13, Swift single machine installation (refer SAIO), swift-client runs local with no-proxy mode.

Solution

  • EADDRNOTAVAIL stands for either unavailability of ephemeral ports and a known kernel bug.
  • Check your range of ports: $cat /proc/sys/net/ipv4/ip_local_port_range
  • swift-bench in no-proxy mode uses direct client class based on Python’s HTTPLib. I saw that code for object write and read did not have connection close call. So, I added that. Please refer swift/common/direct_client.py.
  • The kernel bug is based on usage of bind() call during a connection setup from client. swift-bench so not use bind. So this possibility is ruled out.
  • Swift administration guide advises of following setting:
The following settings should be in /etc/sysctl.conf:
# disable TIME_WAIT.. wait..
net.ipv4.tcp_tw_recycle=1
net.ipv4.tcp_tw_reuse=1# disable syn cookies
net.ipv4.tcp_syncookies = 0
To load the updated sysctl settings, run $sudo sysctl -p

The above mentioned solutions reduced the problem significantly. If there is a better solution, let me know.

Best Python memcache client: Python-memcached v/s Pylibmc

Recently, I tried to access memcached server on local and remote setup in a Python application. I am sharing my experience with two of most popular clients.

Python-memcached

  • The first choice was a pure  Python solution to access memcached, that is python-memcached. It is a simple to install, understand and use solution.
  • It do not offer many customization setting, at least on its README 🙂
  • Very less or non-existent, useful documentation
  • Fails consistently for a high frequency request to memcached server. Failures are for simultaneous read on a file xxx.  I could not find an easy fix for this problem.
  • I do not suggest using it for a highly scalable application.

Pylibmc

  • Bare minimum Python wrapper to C/C++ API to memcached
  • Installation was simple similar to Python-memcached
  • Offers many useful options during connection setup (such as non-blocking requests, TCP no-delay disable)
  • Shows no problem in demanding and highly scalable application
  • Shows better performance than Python-memcached

My verdict: Pylibmc is a clear winner 🙂

Parenthesize an expression in Python

    def pref(op):
        print "called with op", op
        ret = -1
        if op == '+':
            print "matched +"
            ret = 1
        if op == '-':
            print "matched -"
            ret = 2
        if op == '*':
            print "matched *"
            ret = 3
        if op == '/':
            print "matched /"
            ret = 4
    
        return ret
    
    def evaluate(expr, operand_stack, operator_stack):
        print "**In evaluate**"
        print operator_stack
        print operand_stack
    
        expr1 = operand_stack.pop()
        expr2 = operand_stack.pop()
        op    = operator_stack.pop()
    
        # Parenthesize the expression
        expr = "(" + expr2 + op + expr1 + ")"
        print "expr1", expr1
        print "expr2", expr2
        print "expr", expr
    
        # Push the result back on the stack
        operand_stack.append(expr)
    
        print operator_stack
        print operand_stack
        print "**Out evaluate**"
        return expr
    
    def looper(str, expr, operator_stack, operand_stack):
        l = 0
        cnt = len(str)
    
        # Loop over the input string
        while  l < cnt:
            if str[l] in ('+', '-', '*', '/'):
                print "operator found: op, index", str[l], l
                print operator_stack, len(operator_stack)
    
                x = len(operator_stack) - 1
                if x > 0:
                    print "Comparing:", operator_stack[x], str[l]
    
                    # If op on stack has higher preference than the op in question
                    if (pref(operator_stack[x]) > pref(str[l])):
                        expr = evaluate(expr, operand_stack, operator_stack)
                operator_stack.append(str[l])
            else:
                # Add the operand to operand stack
                operand_stack.append(str[l])
            l += 1
    
        print operator_stack
        print operand_stack
    
        print "Take care of last elements"
        op_cnt = len(operator_stack)
        while op_cnt:
            expr = evaluate(expr, operand_stack, operator_stack)
            op_cnt -= 1
    
        print operator_stack
        print operand_stack
    
    if __name__ == '__main__':
        str = "a+c*d-e/w*x+a-s"
        cnt = len(str)
    
        operand_stack  = []
        operator_stack  = []
        expr = ""
        looper(str, expr, operator_stack, operand_stack)
    
        print "Output=>", operand_stack[0]

Pylucene- Part III: Hightlighting in Search

The search result can be customized to highlight the phrases that contain the requested keyword. The following code uses “Highlighter” class from Pylucene. We emit result in HTML formatted syntax.

from lucene import \
            QueryParser, IndexSearcher, IndexReader, StandardAnalyzer, \
        TermPositionVector, SimpleFSDirectory, File, SimpleSpanFragmenter, Highlighter, \
    QueryScorer, StringReader, SimpleHTMLFormatter, \
            VERSION, initVM, Version
import sys

FIELD_CONTENTS = "contents"
FIELD_PATH = "path"
#QUERY_STRING = "lucene and restored"
QUERY_STRING = sys.argv[1]
STORE_DIR = "/home/kanaujia/lucene_index"

if __name__ == '__main__':
    initVM()
    print 'lucene', VERSION

    # Get handle to index directory
    directory = SimpleFSDirectory(File(STORE_DIR))

    # Creates a searcher searching the provided index.
    ireader  = IndexReader.open(directory, True)

    # Implements search over a single IndexReader.
    # Use a single instance and use it across queries
    # to improve performance.
    searcher = IndexSearcher(ireader)

    # Get the analyzer
    analyzer = StandardAnalyzer(Version.LUCENE_CURRENT)

    # Constructs a query parser.
    queryParser = QueryParser(Version.LUCENE_CURRENT, FIELD_CONTENTS, analyzer)

    # Create a query
    query = queryParser.parse(QUERY_STRING)

    topDocs = searcher.search(query, 50)

    # Get top hits
    scoreDocs = topDocs.scoreDocs
    print "%s total matching documents." % len(scoreDocs)

    HighlightFormatter = SimpleHTMLFormatter();
    query_score = QueryScorer (query)

    highlighter = Highlighter(HighlightFormatter, query_score)

    # Set the fragment size. We break text in to fragment of 64 characters
    fragmenter  = SimpleSpanFragmenter(query_score, 64);
    highlighter.setTextFragmenter(fragmenter); 

    for scoreDoc in scoreDocs:
        doc = searcher.doc(scoreDoc.doc)
    text = doc.get(FIELD_CONTENTS)
    ts = analyzer.tokenStream(FIELD_CONTENTS, StringReader(text))
        print doc.get(FIELD_PATH)
        print highlighter.getBestFragments(ts, text, 3, "...")
    print ""

The code is an extension of search code discussed in Part-II.

We create a HTML formatter with SimpleHTMLFormatter. We create a QueryScorer to iterate over resulting documents in non-decreasing doc ID.

HighlightFormatter = SimpleHTMLFormatter();
query_score = QueryScorer (query)

highlighter = Highlighter(HighlightFormatter, query_score)

We break the text content into 64 bytes character set.
fragmenter  = SimpleSpanFragmenter(query_score, 64);
highlighter.setTextFragmenter(fragmenter);

for scoreDoc in scoreDocs:
doc = searcher.doc(scoreDoc.doc)
text = doc.get(FIELD_CONTENTS)
ts = analyzer.tokenStream(FIELD_CONTENTS, StringReader(text))
print doc.get(FIELD_PATH)

Now we set number of lines for phrases in a document.

print highlighter.getBestFragments(ts, text, 3, “…”)

Results

kanaujia@ubuntu:~/work/Py/pylucy2/pylucy$ python searcher_highlight.py hello
lucene 3.6.1
50 total matching documents.
/home/kanaujia/Dropbox/PyConIndia/fsMgr/root/hello
hi hello

/home/kanaujia/Dropbox/PyConIndia/fsMgr.v4/root/hello
hi hello

/home/kanaujia/Dropbox/.dropbox.cache/2012-09-27/hello (deleted 505bda23-9-e8756a51)
hi hello

/home/kanaujia/Dropbox/PyConIndia/fsMgr.v1/root/hello.html

Hello htmls

{% module Hello() %}

Pylucene- Part II: Searching index

In the last post, we discussed how to create an index over a directory. Now, let’s search our index.

from lucene import \
            QueryParser, IndexSearcher, IndexReader, StandardAnalyzer, \
        TermPositionVector, SimpleFSDirectory, File, MoreLikeThis, \
            VERSION, initVM, Version
import sys

FIELD_CONTENTS = "contents"
FIELD_PATH = "path"

QUERY_STRING = "lucene and restored"

STORE_DIR = "/home/kanaujia/lucene_index"

if __name__ == '__main__':
    initVM()
    print 'lucene', VERSION

    # Get handle to index directory
    directory = SimpleFSDirectory(File(STORE_DIR))

    # Creates a searcher searching the provided index.
    ireader  = IndexReader.open(directory, True)

    # Implements search over a single IndexReader.
    # Use a single instance and use it across queries
    # to improve performance.
    searcher = IndexSearcher(ireader)

    # Get the analyzer
    analyzer = StandardAnalyzer(Version.LUCENE_CURRENT)

    # Constructs a query parser. We specify what field to search into.
    queryParser = QueryParser(Version.LUCENE_CURRENT,
                              FIELD_CONTENTS, analyzer)

    # Create the query
    query = queryParser.parse(QUERY_STRING)

    # Run the query and get top 50 results
    topDocs = searcher.search(query, 50)

    # Get top hits
    scoreDocs = topDocs.scoreDocs
    print "%s total matching documents." % len(scoreDocs)

    for scoreDoc in scoreDocs:
        doc = searcher.doc(scoreDoc.doc)
        print doc.get(FIELD_PATH)

Pylucene- Part I: Creating index

How to write a simple index generator with pylucene

  1 import lucene
  2 
  3 if __name__ == '__main__':
  4     INDEX_DIR = "/home/kanaujia/lucene_index"
  5 
  6     # Initialize lucene and JVM
  7     lucene.initVM()
  8 
  9     print "lucene version is:", lucene.VERSION
 10 
 11     # Get the analyzer
 12     analyzer = lucene.StandardAnalyzer(lucene.Version.LUCENE_CURRENT)
 13 
 14     # Get index storage
 15     store = lucene.SimpleFSDirectory(lucene.File(INDEX_DIR))
 16 
 17     # Get index writer
 18     writer = lucene.IndexWriter(store, analyzer, True, lucene.IndexWriter.MaxFieldLength.LIMITED)
 19 
 20     try:
 21         # create a document that would we added to the index
 22         doc = lucene.Document()
 23 
 24         # Add a field to this document
 25         field = lucene.Field("title", "India", lucene.Field.Store.YES, lucene.Field.Index.ANALYZED)
 26 
 27         # Add this field to the document
 28         doc.add(field)
 29 
 30         # Add the document to the index
 31         writer.addDocument(doc)
 32     except Exception, e:
 33         print "Failed in indexDocs:", e

Fundamentals

  • An index is created with an IndexWriter
  • An index is a collection of documents
  • A document represents a file, or data in terms of fields
  • A field is a tuple of field name, data

Let’s understand the above program:

  1. We provide a location of index as INDEX_DIR = “/home/kanaujia/lucene_index”
  2. Start and initialize the Java VM
  3. Get the lucene’s standard analyzer for fields
  4. This example keeps the index on disk, so the SimpleFSDirectory class is used to get a handle to this index.
  5. IndexWriter creates and maintains an index. The constructor is as follows:

IndexWriter(Directory d, Analyzer a, boolean create, IndexDeletionPolicy deletionPolicy, IndexWriter.MaxFieldLength mfl)

  • Directory is handle to index location
  • ‘create’ tells if a new index object is created for every user request
# Get index writer
    writer = lucene.IndexWriter(store, analyzer, True, lucene.IndexWriter.MaxFieldLength.LIMITED)
  • Create a document that would become part in the index
  • Create a field, add it to a document.
  • Add the document to the index.
  • Run the program
kanaujia@ubuntu:~/work/Py$ python example1.py
lucene version is: 3.6.1
kanaujia@ubuntu:~/work/Py$ ls /home/kanaujia/lucene_index/
_0.fdt  _0.fdx  write.lock

Pitfall of C array

CODE

int main()
{
int my_array[4] = {11,12,13,14};
int next = 15;
printf("\nSurprise = %d", my_array[4]);
}

What should it print?

Well, although illegal, the above code does legal things. The array “my_array” has four integers allocated on the stack. The next integer “next” is allocated adjacent to the stack memory. So the address of “next” would be (my_array + 5).


-----------------------
11| 12| 13| 14| 15|
-----------------------
^
|
The memory layout on stack is linear and hence our array and the integer are adjacent to each other.

It is a subtle error and you should know it.

A priority queue with O(1) operations: C, Linux implementation

I have implemented a priority queue that enable O(1) time complexity for major operations i.e. enqueue and dequeue.
It is C, POSIX compliant code.

Things to note
– It uses buffer pools
– Its behavior is to return the highest priority node from the queue
– If queue is empty/full, we use conditional waits
– Priorities are defined from 0..PRIMAX-1 as an array
– Each priority bucket has a list of node that share that priority
– It is thread-safe implementation
– It could be used between two threads for data exchange (producer/consumer)

Here is the GitHub link

/* queue.h */

#include "stdlib.h"
#include "stdio.h"
#include "pthread.h"
#include "assert.h"
#include "string.h"

#define ASSERT(x) assert(x)
#define PRI_MAX 10
#define BUF_POOL_SIZE 1024
#define uint32_t int
#define LOG printf
#define LOG2 printf
#define LOG3 printf
#define LOCK(x) pthread_mutex_lock(&x)
#define UNLOCK(x) pthread_mutex_unlock(&x)

typedef enum bool_ {
  false,
  true
} bool;

typedef struct queue_stats_ {
  int enqueue;
  int dequeue;
  int wait_time;
} queue_stats;

int priority[PRI_MAX];

/*
 * List of nodes in a hash bucket
 */
 typedef struct node_ {
  int key;
  int priority;
  struct node_* next;
} node;

/*
 * Define the hash table
 * |p1| ->|a|->|b|->|c|
 * |p2|->|e|->|f|
 */
 typedef struct ptable_entry_ {
  int priority;
  node* n;
} ptable_entry;

typedef struct ptable_ {
  ptable_entry entry[PRI_MAX];
  node* last[PRI_MAX];
  node* buf_pool;
  node* free_bbuf_pool;
  int ent_count;
  pthread_mutex_t lock;
  pthread_cond_t cv;
  bool is_available;
  queue_stats *stats;
} ptable;

void create(ptable*);
void get_data(ptable*, int*, int*);
void put_data(ptable*, int key, int priority);
void destroy(ptable*);
void display(ptable*);
void put_buf(ptable* p, void* buf);
void create_pool(ptable** p, uint32_t num);
void* get_buf(ptable* p);
void display_buf_pool(ptable* p);

/*
 * Helper functions
 */

void add_a_node(ptable* p, node** last, node** m, int key, int priority);

/* queue.c */

#include "queue.h"

/*
 * Adds a node of a given priority to the queue. Since a node is
 * allocated from a fixed size buffer pool, this function blocks
 * if pool has no free buffer object. 
 */
void add_a_node(ptable* p, node** last, node** m, int key, int priority)
{
  ASSERT(p);

  LOCK(p->lock);
  node *n = NULL;

  n = (node*)get_buf(p);

  LOG3("oo-get_data-oo\n");
  display_buf_pool(p);
  LOG3("---get_data--\n");

  if (NULL == n) {
    LOG2("Buf pool is over. Waiting for dequeue\n");
    pthread_cond_wait(&p->cv, &p->lock);
    n = (node*)get_buf(p);
    LOG2("Producer: wait over. Got a buffer back\n");
  }

  /*
   * Collided nodes are arranged in a list (queue)
   */
  n->key = key;
  n->priority = priority;
  n->next = NULL;

  if (NULL == *m) {
    *m = n;
  } else {
    (*last)->next = n;
  }

  *last = n;
  LOG("Enqueue: %d\n", p->stats->enqueue++);

  p->is_available = true;
  pthread_cond_signal(&p->cv);
  UNLOCK(p->lock);
}

/*
 * Gets a buffer from the buffer pool
 */
void* get_buf(ptable *p)
{
  /*
   * Check if we have at least two nodes
   */
  node* head = p->buf_pool;

  if(p->buf_pool != NULL) {
    p->buf_pool = head->next;
    LOG2("Stealing a buffer %p\n", head);
    return head;
  } else {
    LOG2("\nBuffer overrun\n");
    return NULL;
  }
}

/*
 * Returns a buffer to buffer pool
 */
void put_buf(ptable* p, void* buf)
{
  if (p->buf_pool) {
    node* head = (node*)buf;
    head->next = p->buf_pool;
    p->buf_pool = head;
    LOG2("Unstealing a buffer %p\n", buf);
  } else {
    p->buf_pool = buf;
    LOG2("Unstealing the last buffer %p\n", buf);
  }
}

void display_buf_pool(ptable* p)
{
  ASSERT(p);

  int i = 1;
  node* temp = p->buf_pool;

  while(temp) {
    LOG2("Buf %d: %p\n", i++, temp);
    temp = temp->next;
  }
}

void create_pool(ptable** p, uint32_t num)
{
  node* head= NULL;
  node* temp = NULL;

  int i = 0;

  head = malloc(sizeof(node));

  temp = head;

  for(i = 1; i < num; i++) {
    temp->next = malloc(sizeof(node));
    temp = temp->next;
  }
  temp->next = NULL;

  /*
   * Set the buf pool
   */
  if (NULL == (*p)->buf_pool) {
    (*p)->buf_pool = head;
  }

#ifdef DEBUG
  display_buf_pool(*p);
#endif

}

/*
 * Create a priority queue object of priority ranging from 0..PRIMAX-1
 */
void create(ptable* p)
{
  ASSERT(p);

  int i = 0;

  /*
   * Initialize the entries
   */
  for(i = 0; i < PRI_MAX; i++) {
    p->entry[i].priority = i;
    p->entry[i].n = NULL;
    p->last[i] = NULL;
  }

  create_pool(&p, BUF_POOL_SIZE);

  p->stats = malloc(sizeof(queue_stats));

  memset ( &(p->lock), 0, sizeof(pthread_mutex_t));
  memset ( &(p->cv), 0, sizeof(pthread_cond_t));

  p->is_available = false;
  p->ent_count = PRI_MAX;
}

/*
 * Adds a node to the queue 
 */
void put_data(ptable* p, int key, int priority)
{
  ASSERT(p);
  ASSERT(priority < PRI_MAX);

  add_a_node(p, &(p->last[priority]), &(p->entry[priority].n),
                key, priority);
}

/*
 * Gets the highest priority node from the queue. If queue is empty,
 * then this routine blocks.
 */
void get_data(ptable* p, int* key, int* pri)
{
  ASSERT(p);

  LOCK(p->lock);
  int i = 0;
  node* temp = NULL;

wait_again:
  while (false == p->is_available) {
    /*
     * Else wait for the next element to get in
     */
    LOG2("Nothing in queue; waiting for data\n");
    pthread_cond_wait(&p->cv, &p->lock);
    LOG2("Waiting completed: got data\n");
  }

  for (i = 0; i < PRI_MAX; i++) {
    if (NULL != p->entry[i].n) {
      temp = (p->entry[i].n);

      *key = p->entry[i].n->key;
      *pri = p->entry[i].n->priority;

      p->entry[i].n = temp->next;

      LOG(" Dequeued: %d\n", p->stats->dequeue++);
      put_buf(p, temp);
#ifdef DEBUG
      LOG3("oo-put_data-oo\n");
      display_buf_pool(p);
      LOG3("---put_data--\n");
#endif
      pthread_cond_signal(&p->cv);
      UNLOCK(p->lock);
      return;
    }
  }
  p->is_available = false;
  goto wait_again;
}

/*
 * Test code
 * Uses two threads, acting as producer and consumer
 */
void* producer(void* p)
{
  ASSERT(p);

  ptable *table = (ptable*)p;

  printf("Thread producer\n");
  int i = 0;
  while(1) {
    /*
     * We break the producer after enqueuing 16 messages
     */
    if (i == 16) {
      break;
    }
    printf("Calling put_data %d\n\t", i);
    /*
     * Using max bucket as (MAX_PRI - 1)
     */ 
    put_data(p, i++, (i % 9));
  }
}

void* consumer(void* p)
{
  sleep(2);
  ptable *table = (ptable*)p;

  int key, priority;

  printf("Thread consumer\n");
  int i = 0;
  while(1) {
     printf("Calling get_data\n");
     get_data(p, &key, &priority);
     printf("\nSearch-> Priority=%d key= %d\n", priority, key);
    /*
     * We break the consumer after dequeuing 16 messages.
     * The next call to get_data will block since there
     * will be no data from the producer
     */
      if (i == 15) {
        break;
      }
  }
}

void cleanup(ptable *p)
{
  node *n = p->buf_pool;

  while(n) {
    node* temp = n;
    n = n->next;
    free(temp);
  }
  free(p);
}

int main()
{
  ptable *p = malloc(sizeof(ptable));
  create(p);

  pthread_t thread1, thread2;

  int iret1, iret2;

  iret1 = pthread_create( &thread1, NULL, producer, (void*) p);
  iret2 = pthread_create( &thread2, NULL, consumer, (void*) p);

  display(p);

  pthread_join( thread1, NULL);
  pthread_join( thread2, NULL);

  cleanup(p);
}

/*
 * Function to display the queue
 */
void display(ptable* p)
{
  ASSERT(p);
  int i = 0;
  node* t = NULL;
  for(i = 0; i < PRI_MAX; i++) {
    t = p->entry[i].n;
    while(t) {
      printf("\nBucket=%d|Key=%d|Priority=%d\n", p->entry[i].priority,
          t->key,
          t->priority);
      t = t->next;
    }
  }
}

Synchronize two threads to print ordered even and odd numbers in C

Problem:You have two threads, that independently print even and odd values. The goal is to synchronize these threads so as to get an non-decreasing ordered set of numbers and order should preserve natural ordering of numbers. So the output should be 1,2,3,4,5,6,7,8…..

It is an interesting problem and could be solved with a conditional variable.

Following is C implementation of the solution:

#include "stdio.h"
#include "stdlib.h"
#include "pthread.h"

pthread_mutex_t count_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t condition_var = PTHREAD_COND_INITIALIZER;
void *functionCount1();
void *functionCount2();
int count = 0;
#define COUNT_DONE 200

void main()
{
 pthread_t thread1, thread2;
 pthread_create( &thread1, NULL, &functionCount1, NULL);
 pthread_create( &thread2, NULL, &functionCount2, NULL);
 pthread_join( thread1, NULL);
 pthread_join( thread2, NULL);
 exit(0);
}

// Print odd numbers
void *functionCount1()
{
  for(;;) {
   // Lock mutex and then wait for signal to relase mutex
   pthread_mutex_lock( &count_mutex );
   if ( count % 2 != 0 ) {
     pthread_cond_wait( &condition_var, &count_mutex );
   }
   count++;
   printf("Counter value functionCount1: %d\n",count);
   pthread_cond_signal( &condition_var );
   if ( count >= COUNT_DONE ) {
     pthread_mutex_unlock( &count_mutex );
     return(NULL);
   }
   pthread_mutex_unlock( &count_mutex );
 }
}

// print even numbers
void *functionCount2()
{
  for(;;) {
  // Lock mutex and then wait for signal to relase mutex
  pthread_mutex_lock( &count_mutex );
  if ( count % 2 == 0 ) {
    pthread_cond_wait( &condition_var, &count_mutex );
  }
  count++;
  printf("Counter value functionCount2: %d\n",count);
  pthread_cond_signal( &condition_var );
  if( count >= COUNT_DONE ) {
    pthread_mutex_unlock( &count_mutex );
    return(NULL);
  }
  pthread_mutex_unlock( &count_mutex );
 }
}

Python goof ups of a C/C++ programmer

Python is a new age language when compared to good old C. Writing code in Python needs a subtle shift from C mindset. Python offers so many things ready-made that make you feel that you wrote very less code. Anyway, I goofed up while using a very common feature of C: pass by reference.

Python too offers it, but with a caveat: you should know mutable and immutable data objects. When you pass a mutable object like list, dictionary; they can be changed. But, if you pass an immutable data object like string, tuple; they are kept unchanged in caller’s scope. This is very similar to passing “references” (C++) or constant pointers.

  1 class Node:
  2     def __init__(self, value, data=[]):
  3         self.char = value
  4         # We intend to keep a list of values for a key
  5         self.data = data
  6         # XXX: List of Node
  7         self.children = []
  8
  9
 10 n = Node('a')
 11 m = Node('b')
 12
 13 (n.data).append("north")
 14 (m.data).append("south")
 15
 16 print n.data
 17 print m.data

The output of the above code is:

ubuntu@ubuntu:~/Desktop/ToKeep/cprogs/pycon$ python pybug.py
['north', 'south']
['north', 'south']

I don’t quite understand why Python keeps a single instance of default argument(list). Nonetheless, it is interesting.

This thread on Stackoverflow is very informational.

  • Omitting “this” pointer

In C++, “this” which is pointer to the object is passed implicitly. Python has similar keyword “self” for this. But, contrary to an implicit understanding, “self” should be an argument to a function, else you would see an error:

NameError: global name ‘self’ is not defined

  1 class pydbg:
  2     def __init__(self, modname=None):
  3         self.level = 0
  4         self.modname = modname
  5
  6     def DLOG(self, lvl=None, fmt=None, *args):
  7         self.level = lvl
  8         print '%s' %self.modname
  9         print fmt
 10         for arg in args:
 11             print arg

So, always add the “self” argument while adding a function in your class.

%d bloggers like this: