C++ 11 Semaphore

#include <mutex>
#include <condition_variable>

class Semaphore {
public:
    Semaphore (int count_ = 0)
        : count(count_) {}

    inline void notify()
    {
        std::unique_lock<std::mutex> lock(mtx);
        count++;
        cv.notify_one();
    }

    inline void wait()
    {
        std::unique_lock<std::mutex> lock(mtx);

        while(count == 0){
            cv.wait(lock);
        }
        count--;
    }

private:
    std::mutex mtx;
    std::condition_variable cv;
    int count;
};

Deadlock

deadlock condition
all 4 required:
 Mutual exclusion.
 Hold and wait.
 No preemption.
 Circular wait.

prevantion : avoid above 4
avoidance  : bankers alogrithm
detection  : detect and get resource, kill process

Condition Variable C++ 11

#include <chrono>
#include <condition_variable>
#include <iostream>
#include <mutex>
#include <thread>

bool is_ready(false);
std::mutex m;
std::condition_variable cv;

void
test()
{
    std::this_thread::sleep_for(std::chrono::seconds(30));
    std::unique_lock<std::mutex> lk(m);
    is_ready = true;
    cv.notify_one();
}

int
main()
{
    std::thread t(test);
    std::unique_lock<std::mutex> lk(m);
    while (!is_ready)
    {
        cv.wait(lk);
        if (!is_ready)
            std::cout << "Spurious wake up!\n";
    }
    t.join();
}

Multi Read Single Write (Reader Writer Problem's Solution)

https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock


Begin Read

Lock r.
Increment b.
If b = 1, lock g.
Unlock r.
End Read


Lock r.
Decrement b.
If b = 0, unlock g.
Unlock r.
Begin Write

Lock g.
End Write

Unlock g.

Imp Summary

Summary

Searching

Linear Search [O(n)]

Binary Search [O(log(n))]

?DFS(Depth First Search) [O(|E| + |V|)]

?BFS (Breadth First Search) [O(|E| + |V|)]

?Shortest Path Dijkstra [O(|E| + |V|) log |V|]

______________________________________________________________________________

Sorting

Selection Sort [O(n2)]

Insertion Sort [O(n2)]

Bubble Sort [O(n2)]

QuickSort [O(n2)]

Merge Sort [O(n logn)]

Heap Sort [O(n logn)]

Create Heap

Sort Heap

?Bucket Sort [O(n2)]

?Radix Sort [O(nk)]

______________________________________________________________________________

Tree

Binary Tree

Full/Strict/Perfect

Complete

BST (Binary Search Tree)

AVL Tree (Adelson-Velskii and Landis Tree)

Inventor Name: Adelson-Velskii and Landis

?B Tree

______________________________________________________________________________

Network Layers

Layer |Level |Headers |Device |HeaderLen

Physical Layer | L1 | Wire | Hub |0

Data Link Layer | L2 | EtherNet | Switch |24

Network Layer | L3 | IP | Router |20

Transport Layer | L4 | TCP/UDP | |20/8

Session Layer | L5 | | |

Presentation Layer | L6 | | |

Application Layer | L7 | Http | |

EtherNet Header ( 24 Bytes)

|Preamble(8) |Dst Mac(6) |Src Mac(6) |ethernet type(2) |

IP Header (20 Byte)

|Ver,IHL,ToS (2) |IP Len(2) |

|Identification (2) |flags, Fragmentation (2) |

|TTL, Protocol (2) |Header Checksum(2) |

| Src IP(4) |

| Dst IP(4) |

TCP Header (20 Bytes)

|Src Port (2) | Dst Port(2) |

| Seq No.(4) |

| Ack No.(4) |

|Data offset, resrv, urg,ack,psh, rst, syn, fin (2) |window(2) |

|checksum(2) | urgent ptr(2) |

UDP Header (8 Bytes)

|Src Port (2) | Dst Port (2) |

|Length (2) | Checksum(2) |

______________________________________________________________________________

Protocols

L2

Ethernet

L2TP(Layer 2 Tunneling Protocol)

L3

IP(Internet Protocol)

?ATM(Asynchronous Transfer Mode)

?Framerelay

ARP(Address Resolution Protocol)

RARP(Reverse Address Resolution Protocol)

MPLS(Multi Protocol Label Switching

L4

TCP(Transport Control Protocol)

UDP(User Data Protocol)

L7

SIP(Session Initiation Protocol)

RTSP(Real Time Session Protocol)

RTP(Real Time Protocol)

RTCP(Real Time Control Protocol)

DNS(Domain Name System)

HTTP(Hyper Text Transport Protocol)

IAX(Inter Asterisk Protocol)

Radius(Remote Authentication Dial In User Service)

Diameter

DHCP(Dynamic Host Configuration Protocol)

HTTPS(Hyper Text Transport Protocol Secure)

IMAP(Internet Message Access Protocol)

MIME(Multipurpose Internet Mail Exchange)

NNTP(Network News Transfer Protocol)

POP3(Post Office Protocol)

SSH(Secure Shell)

SMTP(Simple Mail Transport Protocol)

SOAP(Simple Object Access Protocol)

STUN(Session Traversal Utilities for NAT)

XMPP(Extensible Messaging and Presence Protocol)

______________________________________________________________________________

Big O

O (log N) < O(N) < O(N log N) < O(N2) < O(Nk) <O(en) < O(n!)

______________________________________________________________________________

Design Patterns

Creational Pattern

Singleton

Builder

Factory Method

?Abstract Factory

Prototype: using clone

Structural Pattern

Adapter(Wrapper)

Strategic Pattern

Decorator

?Bridge

Facade

Proxy

Composite

Behaviour Pattern

Chain of responsibility(Pipeline)

Observer

Command

Interpreter

Iterator

State

Mediator

visitor: B(D1, D2, D3), accept(visitor v){v.visit(this)}  |  V(V1, V2, V3), visit(visitor*);

______________________________________________________________________________

Gates

OR A+B

AND A.B

NOT Bar on top of A !A

NOR NOT + OR !(A+B)

NAND NOT+ AND !(A.B)

XOR (A+B).(!A+!B)

XNOR !((A+B).(!A+!B))

______________________________________________________________________________

Calling Convention

__cdecl

default calling convention of c

c type convention

foo(int i) = _foo

Stack cleanup by caller

argument push into stack right to left

__stdcall

foo(int i) = _foo@8

stack cleanup by calle

argument push into stack right to left

__fastcall

usg register for argument

foo(int i) = @_foo@8

stack cleanup by callee

argument push into stack right to left

__this call

default calling convention of c++

store this pointer also

foo(int i) = @fooadflakdfjk#ldjo30

stack cleanup by callee

argument push into stack right to left

______________________________________________________________________________

Multi-Threading

POSICS(Linux) | Windows

#include <pthread.h> |#include <windows.h>

pthread_t thread_handle; |HANDLE thread_handle;

int retVal = pthread_create(&thread_handle, |thread_handle = CreateThread(NULL,

NULL, | 0,

thread_fun, | thread_fun,

NULL); | NULL,

| 0,

pthread_join(thread_handle, NULL); | thread_id);

|WaitForSingleObject(thread_handle, INFINITE);

|

|

|

|

|

|

______________________________________________________________________________

Mutex

POSICS(Linux) | Windows

#include <pthread.h> |#include <windows.h>

pthread_mutext_t mutex_handle = |HANDLE mutex_handle;

PTHREAD_MUTEX_INITIALIZER; |mutex_handle = CreateMutex(NULL,

pthread_mutex_lock(&mutex_handle); | FALSE,

cnt++ | NULL);

pthread_mutex_unlock(&mutex_handle); |WaitForSingleObject(mutex_handle, INFINITE);

|cnt++;

|ReleaseMutex(mutex_handle);

|

______________________________________________________________________________

Programming

1. Next Square Root of any number: N+2*x+1 here N given Sqr number, x is sqrt of N

ex: N=4 its sqr as its sqrt is 2 hence 4+2*2+1 = 9, 9 is also sqr number as its sqrt is 3

2. 1+2+3+4+...n = n*(n+1)/2

3.