Saturday, January 3, 2009

Interesting Builtin/Macros - Useful for common utility development

OffsetOf(type, var_name)

This MACRO is widely used in networking applications. Offsetof returns the offset of a particular member 'var_name' in the C structure whose type is given in 'type'.

To get hold of offset of variable "myVar" in following structure

typedef struct MyContext_s {
     int a;
     int b;
     int myVar;
     void *Child_p;
     ......
     int lastVar;
    char  c[1];  /** Variable data **/
}MyContext_t;

offsetof can be used by  offsetof(MyContext_t,  myVar).  This returns the offset as a return value. In above example, the return value is 8, assuming that integer size is 4 bytes.

Let us say that myContext_t structure has few fixed variables upto lastVar and the rest of structure is variable sized.  If there is a requirement to clear the memory up to lastVar whenever myContext_t structure is allocated, then it can be done using memset(ptr,  0,  offsetof(MyContext_t,  c);


container_of( ptr,  type, var_name)


container_of MACRO is used to get hold of the parent C structure given the pointer to one of its members.  In the above myContext_t structure,  let us assume some piece of code has pointer value of Child_p (say ptr). To get hold of pointer to parent (MyContext_t instance),  this macro can be used - container_of( ptr,  MyContext_t,  Child_p);  This returns pointer to parent MyContext_t instance.


One use case with DLL:


In any complex network application programs,  you might have the requirement to provide common libraries for data structures - Such as hash table,  Double linked list,  Single linked list,  Red-black tree, trie and many more.  Almost all the data structure work with pointers.  For example double linked list manipulation requires the C structure to have previous and next pointers. To make DLL (Double Linked List) library consisting of DLLInsert, DLLDelete etc..,   it should work with any application C structures. That is,  DLL library developer should not restrict
  • Names of "Previous" and "Next" pointers in the application structure.
  • Placement of "Previous" and "Next" pointers in the application structure.
Let us see with actual implementation of DLL and its usage.

struct DLLNode_s {
    void *Next;
    void *prev;
} DLLNode_t;

DLL Library expects DLLNode_t to be included with in the application C structure if it needs to take advantage of DLL MACROs.  But DLL will not place any restriction on the name of variable in application C structure,  placement of this or even number of DLLs that the C structure need to be part of.


DLLINSERT: 



head:  Head pointer.
type:   Type of structure that require to be placed in DLL.
ptr:    Pointer to the actual structure.
dllnode:  Name of the DLLPointer node in the 'type' structure.

DLLINSERT(  head,  dllnode)  /** DLLNode_t *head,  DLLNode_t *dllnode) **/
{
      if ( head == NULL )
      {
        dllnode->Next = dllnode->prev = NULL;
         head = dllnode;
      }
     else
     {
            dllnode->next = head;
            head->Prev = dllnode;
            dllnode->prev =NULL;
            head = dllnode;
     }
}

DLLREMOVE macro deletes the node from the linked list. head points to the head of the list and dllnode is the one which is removed from the list.

DLLREMOVE(head,  dllnode)
{

      if (dllnode->prev)
          dllnode->prev->next= dllnode->next;
      if (dllnode->next )
         dllnode->next->prev = dllnode->prev;

      if ( head == dllnode)
          head = dllnode->next;

}

DLLSEARCH macro is expected to return the DLLNode_t instance matching the keyValData.This function typically goes through each node and calls application supplied function 'MatchFunc" to match the node with the KeyValData that is passed.  'MatchFunc' is expected to return TRUE if there is a match or return FALSE otherwise.

DLLSEARCH(head,  keyValData,  MatchFunc)   /** DLLNode_t *head,   void *keyValData **/
{
      DLLNode_t *temp = head;

     while(temp)
     {
           if (MatchFunc(temp, KeyValData) == TRUE )
                break;
          temp = temp->Next;
     }
     return(temp);
}
    Let us assume that application has following structure.  
    typedef struct myContext {
         ..........
         int key;
        DLLNode_t  dllNode;    
        ........
    }myContext_t;


    sturct DLLPointers  *HeadP = NULL;
     

    To search for a node that matches key value, say, 5,  then it uses DLLSEARCH in following way:

    DLLNode_t  *matchDLlNode;
    MyContext_t  *matchContext;

    matchNode = DLLSEARCH(HeadP,  5, MyContextMatch);
    matchContext = container_of(matchNode, MyContext_t, dllNode);   
    Note above.  matchNode is pointer to dllNode variable.  To get hold of MyContext_t instance,  container_of() is used.

    Linux MACRO definition of container_of looks like this:

    #define container_of(ptr, type, member) ({                      \
            const typeof(((type *)0)->member) * __mptr = (ptr);     \
            (type *)((char *)__mptr - offsetof(type, member)); })

    typeof(ptr)

    This MACRO gets hold of the type of the 'ptr' whether it is basic type or some structure type.  For use case, look at the above code piece of 'conatainer_of()'.

    No comments: