Semaphores

Found one simple example in web at http://www.amparo.net/ce155/sem-ex.html

This program demonstrates the use of semaphores to solve the critical region problem.
int sem_init(sem_t *sem, int pshared, unsigned int value);
The sem_init() function is used to initialize the semaphore's value. The pshared argument must be 0 for semaphores local to a process.
int sem_wait(sem_t * sem);
The sem_wait() function performs the equivalent of the down semaphore operation.
int sem_post(sem_t * sem);
The sem_post() function performs the equivalent of the up semaphore operation.
int sem_destroy(sem_t * sem);
The sem_destroy() function is used to properly deallocate resources alloted to a semaphore. The semaphore in this program is used as a mutex, a binary semaphore, to implement mutual exclusion between two processes which use a shared resource.
To compile and link the program:

gcc -o sem-ex sem-ex.c -Wall -Werror -lpthread

/* Includes */
#include <unistd.h>     /* Symbolic Constants */
#include <sys/types.h>  /* Primitive System Data Types */ 
#include <errno.h>      /* Errors */
#include <stdio.h>      /* Input/Output */
#include <stdlib.h>     /* General Utilities */
#include <pthread.h>    /* POSIX Threads */
#include <string.h>     /* String handling */
#include <semaphore.h>  /* Semaphore */

/* prototype for thread routine */
void handler ( void *ptr );

/* global vars */
/* semaphores are declared global so they can be accessed 
   in main() and in thread routine,
   here, the semaphore is used as a mutex */
sem_t mutex;
int counter; /* shared variable */

int main()
{
    int i[2];
    pthread_t thread_a;
    pthread_t thread_b;
    
    i[0] = 0; /* argument to threads */
    i[1] = 1;
    
    sem_init(&mutex, 0, 1);      /* initialize mutex to 1 - binary semaphore */
                                 /* second param = 0 - semaphore is local */
                                 
    /* Note: you can check if thread has been successfully created by checking return value of
       pthread_create */                                 
    pthread_create (&thread_a, NULL, (void *) &handler, (void *) &i[0]);
    pthread_create (&thread_b, NULL, (void *) &handler, (void *) &i[1]);
    
    pthread_join(thread_a, NULL);
    pthread_join(thread_b, NULL);

    sem_destroy(&mutex); /* destroy semaphore */
                  
    /* exit */  
    exit(0);
} /* main() */

void handler ( void *ptr )
{
    int x; 
    x = *((int *) ptr);
    printf("Thread %d: Waiting to enter critical region...\n", x);
    sem_wait(&mutex);       /* down semaphore */
    /* START CRITICAL REGION */
    printf("Thread %d: Now in critical region...\n", x);
    printf("Thread %d: Counter Value: %d\n", x, counter);
    printf("Thread %d: Incrementing Counter...\n", x);
    counter++;
    printf("Thread %d: New Counter Value: %d\n", x, counter);
    printf("Thread %d: Exiting critical region...\n", x);
    /* END CRITICAL REGION */    
    sem_post(&mutex);       /* up semaphore */
    
    pthread_exit(0); /* exit thread */
}

Singleton without code

Class ABC
{
int a;
int b;
static int c;
}ABC;

ABC::c=10;

void fun()
{
cout<<" Value of a is "<<ABC.a<<endl;
}

No need to write logic to handle singleton, this was you'll have only one object in the program ABC.

Example:

#include<stdio.h>
class singleton
{
    public:
static int value;
    void print()
    {
        printf("hello %d\n",value);
    }
    int a;
}singleton;
singleton::value=5;

int main()
{
//    singleton s;  #cannot define a new instant like this anymore.
    singleton.a=5;
    printf("a=%d\n",singleton.a);
    singleton.print();
    return 0;
}

TRIE Data Structure

Good Example I found in web/blog.

C++ Tries

What is a Trie? How to implement Tries in C++?

• Tries are used to index and search strings in a text.
• Some examples of tries usage include, finding the longest prefix match in a routing table, auto complete of web addresses in browser etc.
• Trie is a tree where each vertex represents a word or prefix.
• The root represents an empty string.
• Markers are used to indicate end of words.
• A typical node in a trie includes the content (a char), marker for end of word and acollection of children.
• An example of trie. (Using words Hello, Balloon, Ball)
  
  

EXAMPLE:- Demonstrate a simple implementation of search in a Trie

#include <iostream>
#include <vector>
using namespace std;

class Node {
public:
    Node() { mContent = ' '; mMarker = false; }
    ~Node() {}
    char content() { return mContent; }
    void setContent(char c) { mContent = c; }
    bool wordMarker() { return mMarker; }
    void setWordMarker() { mMarker = true; }
    Node* findChild(char c);
    void appendChild(Node* child) { mChildren.push_back(child); }
    vector<Node*> children() { return mChildren; }

private:
    char mContent;
    bool mMarker;
    vector<Node*> mChildren;
};

class Trie {
public:
    Trie();
    ~Trie();
    void addWord(string s);
    bool searchWord(string s);
    void deleteWord(string s);
private:
    Node* root;
};

Node* Node::findChild(char c)
{
    for ( int i = 0; i < mChildren.size(); i++ )
    {
        Node* tmp = mChildren.at(i);
        if ( tmp->content() == c )
        {
            return tmp;
        }
    }

    return NULL;
}

Trie::Trie()
{
    root = new Node();
}

Trie::~Trie()
{
    // Free memory
}

void Trie::addWord(string s)
{
    Node* current = root;

    if ( s.length() == 0 )
    {
        current->setWordMarker(); // an empty word
        return;
    }

    for ( int i = 0; i < s.length(); i++ )
    {        
        Node* child = current->findChild(s[i]);
        if ( child != NULL )
        {
            current = child;
        }
        else
        {
            Node* tmp = new Node();
            tmp->setContent(s[i]);
            current->appendChild(tmp);
            current = tmp;
        }
        if ( i == s.length() - 1 )
            current->setWordMarker();
    }
}


bool Trie::searchWord(string s)
{
    Node* current = root;

    while ( current != NULL )
    {
        for ( int i = 0; i < s.length(); i++ )
        {
            Node* tmp = current->findChild(s[i]);
            if ( tmp == NULL )
                return false;
            current = tmp;
        }

        if ( current->wordMarker() )
            return true;
        else
            return false;
    }

    return false;
}


// Test program
int main()
{
    Trie* trie = new Trie();
    trie->addWord("Hello");
    trie->addWord("Balloon");
    trie->addWord("Ball");

    if ( trie->searchWord("Hell") )
        cout << "Found Hell" << endl;

    if ( trie->searchWord("Hello") )
        cout << "Found Hello" << endl;

    if ( trie->searchWord("Helloo") )
        cout << "Found Helloo" << endl;

    if ( trie->searchWord("Ball") )
        cout << "Found Ball" << endl;

    if ( trie->searchWord("Balloon") )
        cout << "Found Balloon" << endl;

    delete trie;
}

OUTPUT:-
Found Hello
Found Ball
Found Balloon

()Operator example on Template

 #include <iostream>
 template <class I>
 class B
 {
 public:
   static B b;
  I data;
I operator()()
{
data=10;
return data;
}
static B& instance()
{
return b;
}
};

template<class T>
B<T> B<T>::b;
template class B<int>;
typedef B<int> type;

 int main()
 {
   std::cout << type::b()<< std::endl; // 0
   return 0;
 }

Shared Data Example

How to share the data between two program.

Program 1:
=======
#include<iostream.h>
#include<sys/wait.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include<unistd.h>
#include <stddef.h>
#include <stdio.h>
#define SHMSZ    1024
int write(int *b){
char c;
int shmid;
key_t key;
int *shm;
char *s;
/*    * We'll name our shared memory segment    * "5678".    */
key = 5678;
/*    * Create the segment.    */
if ((shmid = shmget(key, SHMSZ, IPC_CREAT | 0666)) < 0) {
cerr<<"shmget";        exit(1);
}
/*    * Now we attach the segment to our data space.    */
if ((shm = (int *)/*(char *)*/shmat(shmid, 0, 0)) == /*(char *)*/(int *) -1) {
cerr<<"shmat";        exit(1);
}
/*    * Now put some things into the memory for the    * other process to read.    */
// s = shm;
int i;
for (i=0; i<=1000; i++,shm++)
*shm = i;    *b=0;
cout<<"write is complited"<<endl;
cout<<*b<<endl;
return(*b);
}

main(){
char c;
int shmid;
key_t key;
static int *b;
key = 5679;
/*    * Create the one bit  segment.    */
if ((shmid = shmget(key, 1, IPC_CREAT | 0666)) < 0) {
cerr<<"shmget";
exit(1);
 }

/*    * Now we attach the segment to our data space.    */

if ((b = ( int *)shmat(shmid, 0, 0)) == (int *) -1)

{

cerr<<"shmat";

exit(1);    }

cout<<*b<<endl;

int *w=new int;

*w=10;

//while(1)    {

if(*b==1)

{

write(b);

}

else

wait(w);

//}

}

Prgram 2:

======

#include<iostream.h>

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/shm.h>

#include<unistd.h>

#include<sys/wait.h>

#define SHMSZ    1024

int read(int *b){

char c;

int shmid;

key_t key;

int *shm;

char *s;

/*    * We'll name our shared memory segment    * "5678".    */

key = 5678;

/*    * Create the segment.    */

if ((shmid = shmget(key, SHMSZ, IPC_CREAT | 0666)) < 0) {

cerr<<"shmget";

exit(1);

}

/*    * Now we attach the segment to our data space.    */

if ((shm = (int *)shmat(shmid, 0, 0)) == (int *) -1) {

cerr<<"shmat";

exit(1);

}

/*now read what the server put in the memory.    */

int i;

for (i=0; i<=1000; i++,shm++)

cout<<*shm<<endl;

cout<<"read is completed"<<endl;

*b=1;

cout<<"*b is "<<*b<<endl;

return(*b);

}

main(){

char c;

int shmid;

key_t key;

static int *b;

key = 5679;

/*    * Create the one bit  segment.    */

if ((shmid = shmget(key, 1, IPC_CREAT | 0666)) < 0) {

cerr<<"shmget";

exit(1);

}

/*    * Now we attach the segment to our data space.    */

if ((b = (int *)shmat(shmid, 0, 0)) == (int *) -1) {

cerr<<"shmat";

exit(1);

}

cout<<" *b is "<<*b<<endl;

int *w=new int;

*w=10;

while(1)

{

if(*b==0)

{

read(b);

}

else

wait(w);

}

}