SIP SUBSCRIBE and NOTIFY Requests

SUBSCRIBE and NOTIFY (rfc 3265) 

1. ability to receive asynchronous notification of events, on subscription
2. general concept is that the entities in the network can SUBSCRIBE (which needs to be refreshed periodically) to resource or call state, and be notified when the state changes
3. SUBSCRIBE requests create a dialog
4. terms and definitions
   1. Event Package, set of state info to be reported by a notifier to a SUBSCRIBEr
   2. Event Template Package, special kind of event package which defines a set of event packages with a set od states which may be applied to all possible event packages
   3. Notification, act of sending a NOTIFY message to the SUBSCRIBER, informaing the state of resource
   4. Notifier, UA which generates the NOTIFY request, and typically accepts SUBSCRIBE request to create subscriptions
   5. State Agent, notifier which publishes the state on behalf of a resource, they may need to gather such info from multiple sources
   6. SUBSCRIBER, UA which receives a NOTIFY request, typically generate SUBSCRIBE request
   7. subscription is a set of application state associated with a dialog, containing a pointer to the associate dialog, the even package name, and an identifiction token
   8. Subscription Migration, act of moving a subscription from one notifier to another
5. "Expires" Header
   1. SUBSCRIBE requests should contain an "Expires" header, indicating the duration of subscription 
   2. if no "Expires" header is present then the implied default defined in the even package is used
   3. 200 class response to a SUBSCRIBE request must contain an "Expires" header, the period can be shorter(but not longer) than specified in the request
   4. SUBSCRIBE with an "Expires" of 0 means
      1. the request is for unSUBSCRIBE from an event
      2. can also cause a fetch of state
      3. successful unsubscription will also trigger a final NOTIFY message

SIP Dialog

1. peer to peer SIP relationship between two user agents
2. facilitate sequencing messages between UA and proper routing of requests between them
3. provides a context in which to interpret SIP messages
4. dialogs can be created by
   1. INVITE method (rfc 3261)
   2. SUBSCRIBE and NOTIFY method (rfc 3265)
5. a dialog is identified with a Dialog-ID
   1. the dialog-ID at each UA involved in the dialog is not the same, the local tag at one UA are identical to the remote tag at the peer UA
   2. dialog-ID is also associated with all the responses and with any request that contain a tag in To filed
   3. the rules for computing the dialog-ID of a message depends on whether SIP element is a UAS or UAC. 
   4. for a UAC the dialog-ID is composed of 
      1. call-ID
      2. remote tag (tag in the To field)
      3. local tag (tag in the From field), as this is added by the UAC on sending the request
   5. for a UAS the dialog-ID is composed of
      1. call-ID
      2. remote tag (tag in the From field)
      3. local tag (tag in the To field), added by UAS in the response

Embedded System Development ( linking process )

1. cross-platform development methodology, includes 
   
   1. host system
   2. target embedded system
   3. connectivity solutions between host and target (Joint Test Action Group/Background Debug Module)
2. development tools in the host environment are
   1. cross compiler
      
   2. linker
      
   3. source level debugger
      
3. tools in the target embedded system
   
   1. dynamic loader
   2. link loader
   3. debug agent
      
4. journey from code to executable
   1. developer writes in C/C++ and assembly
   2. make-file is created, to automate the process of building/rebuilding on modification
   3. compiler and assembler produce object file containing both machine binary code and data in the target system
   4. linker take these object files, and produces either a executable or an object file, used to additional linking with other object fiies
   5. the linker command file (linker script) instructs linker on how to combine the object files and where to place the binary code and data in the target embedded system
   6. the main
      
5. symbol table  
   1. created by compiler and contains the symbol name to address mapping
   2. contains the global symbols defined in the file being compiled and the external symbols referenced in the file that the linker needs to resolve
      
6. symbol resolution, part of linking process
   1. find where (in other object files) the external symbols are defined
      
   2. the statically linked library (in which the external symbols are defined) are copied to the final image
      
7. symbol relocation, mapping a symbol reference to its defination
   
   1. done using a fix-up table or relocation table
      
   2. for fixing up references to addresses in other segments, as when multiple object files are linked together some addressed must be relocated
      
   3. because of the assumption of the assembler that each object file begins at address 0.
      
8. for an executable image, all external symbols must be resolved such that each symbol has an absolute memory address (exception to this rule is DLL)
9. a relocatable object file is concatenation of multiple object files and is partially resolved, so that it can be linked with other object files at run-time

References:
http://www.cs.princeton.edu/courses/archive/spr03/cs217/lectures/Linker.pdf

SIP Messages

1. request from a client and response from a server are SIP messages
   
2. SIP requests are distinguished by having a request line which contains a method name, a Request URI and protocol version
   
   1. RFC 3261 defines six methods (SIP extensions contains others)
      1. REGISTER for registering contact information
      2. INVITE, ACK and CANCEL for setting up session
         
      3. BYE for terminating sessions
      4. OPTIONS for querying server capabilities
         
   2. Request URI is a SIP or SIPS URI, it indicates the user or service to which this request is being addressed, SIP elements may support other URI types like tel URI
   3. SIP version is "SIP/2.0" 
      


3. SIP Responses have a status line as their start line, which consist of protocol version, numeric status code and its associated text
   
   
   
   1. Status code is a three digit integer result code, indicating the outcome of an attempt to understand and satisfy a request.
   2. the first digit of the status code defines the class of the response, there can be six values for the first digit, ie six response categories
      
      1. 1XX: Provisional , the request is received and is in process
      2. 2XX: Success , the request was successfully received, understood, and accepted
      3. 3XX: Redirection , the request needs to be redirected, one reason for that is, the recipient has changed its location
      4. 4XX: Client Error , bad syntax in the request, thus cant be fulfilled at this server
      5. 5XX: Server Error , server failed to fulfill the request (a valid one)
         
      6. 6XX: Global failure , the request cant be fulfilled at any server
         
   3. reason phrase is to give a short textual description of the status code, for the human user
      

Structure of SIP Protocol Stack

1. fairly independent processing stages
2. element "containing" a layer means elements compliance with the rules defined by that layer
3. lowest layer is "syntax and encoding" layer
   
   1. encoding is specified using BCNF (Backus-Naur form grammar)
      
4. second layer is "transport layer"
   
   1. defines how a client sends requests and receives responses
   2. defines how a server receives requests and sends responses
   3. all SIP elements contain a transport layer
      


5. third layer is "transaction layer"
   
   1. transaction is a 
      1. request send by client transaction (using transport layer) to a server transaction
      2. along with all the responses to that request send by the server transaction back to the client
         
   2. handles application layer retransmissions
   3. matching of responses to request
   4. handles application layer timeouts
   5. statefull proxies, and User Agents have a transaction layer
      
   6. stateless proxies don't have a transaction layer
      
   7. Transaction layer has two components, which are represented by a finite state machine constructed to process a particular requests
      
      1. Client Component (client transaction)
         
      2. Server Component (server transaction)
         
6. the fourth layer is "transaction user"
   
   1. each of the SIP entities except a stateless proxy is a transaction user
      1. when a TU wishes to send a request it creates a client transaction instance and passes it the request, along with destination IP address, port, and transport to which to send the request
         
      2. a TU that creates a client transaction can also cancel it, using a CANCEL request, which constitute its own transaction, but references the transaction to be canceled
         
      3. on canceling the server stops further processing, revert to the state that existed before the transaction was initiated, and generate a specific error response to that transaction
7. the SIP elements, UA clients and servers, stateless and stateful proxies, and registrar, contains a core that distinguish them from each other. Cores except for the state less proxies are TU. 
   

Loosely coupled and highly cohesive

1. Coupling
   1. among classes
   2. among subsystems, modules
   3. related classes knowing the internal details of each other
   4. when one is changed, other has to be changed
   5. makes the system difficult to understand
   6. no possibility of reuse of the entwined code
2. Cohesion
   1. inside the class, among the class attributes and behavior
   2. well defined roles for the classes within the system
   3. the data is closely related with the functions which the class is providing

 

3. Law of Demeter (more specific case of "low coupling", LoD)
   1. motto is "only talk to your immediate friends"
   2. each unit should have only limited knowledge about other units "closely" related to the current unit (method/function "f")
   3. in context of OOD, closely related
      1. are the functions of the class in which unit (function "f") exists
      2. other argument classes of unit (function "f")
      3. functions of immediate part classes (computed and stored) of class of unit (function "f")
         1. computed classes are the classes that are the return type of functions of this class
         2. stored classes are the classes of the data members of this class

Overview Of SIP Operation I

1. basic functions of SIP (HTTP like request/response transaction model)
   
   
   1. Location of an endpoint
      
   2. signal of a desire to communicate
      
   3. negotiation of session parameters for the session
      
   4. teardown of session once established
      
2. Request handling in SIP is often classified as either INVITE or non-INVITE (an ACK is only sent in response to a response for an INVITE request,INVITE/200/ACK)
   
3. SIP messages are text-encoded
   

INVITE message example, with header fields (minimum required set)

1. INVITE sip:bob@biloxi.com SIP/2.0
   
2. Via: SIP/2.0/UDP pc33.atlanta.com;branch=z9hG4bK776asdhds
   
3. Max-Forwards: 70
   
4. To: Bob <sip:bob@biloxi.com>
   
5. From: Alice <sip:alice@atlanta.com>;tag=1928301774
   
6. Call-ID: a84b4c76e66710@pc33.atlanta.com
   
7. CSeq: 314159 INVITE
   
8. Contact: <sip:alice@pc33.atlanta.com>
   
9. Content-Type: application/sdp
   
10. Content-Length: 142

Pointers to pointers, and arrays and strings II

1. (*ptoStruct).member; is same as ptoStruct->member
   
2. char name[40] = “mithun”, allocate 40 bytes on static memory block, and occupy the first 7 bytes (6 + ‘\0’), and “name” is a array constant, un modifiable lvalue
   
3. char name[] = “mithun” , count number of chars, allocate memory for count+1 on static memory block, and “name” is a array constant un modifiable lvalue
   
4. char* name = “mithun” ,  allocate the memory for number of characters + 1 for nul, and also 4 bytes for the pointer variable “name”, and “name” is a variable
   
5. in the array notation name is the address of the first element i.e. &name[0], and will always point to the same location (a constant).

SIP Overview

1. An application layer control protocol (works with both IPv4 and IPv6), that can
   
   
   1. establish modify and terminate multimedia sessions (conferences), such as IP telephony calls
      
   2. invite participants to existing sessions (like multicast conferences)
      
   3. existing sessions can be modified by adding/removing media from an existing session
      
   4. transparently supports name mapping and redirection services (support to personal mobility)
      
   5. a single externally visible ID can be maintained regardless of the network location (SIP URI)

Symptoms of Problems in Design, and Design Principles to follow

Symptoms

• difficult to change
• every change cascades changes in other dependent modules
• software break in many places, with every change
•  inability to reuse from other projects or from the same project
• design preserving changes are harder than hacks

Causes

• changing requirements
• improper dependencies between the modules

UNIX process

UNIX process

process is a running instance of a program,identified with "pid"

process consist of

• allocated system resources
• a section of memory
• security attributes (like its owner and set of permissions)
• the process state(running,blocked,waiting)
• process can also be called as execution context of a running program in the current time slice, which is given by the OS as part of scheduling the processes running in the CPU
• process can also be defined in terms of data structure which stores the information about the process
• new process is created by "fork" command in Unix
• program is an executable file in binary format that can be read by the CPU, and process is a program in action (execution)

process control system provides services for

• process scheduling, giving cpu time(divided into time slice) to each process, context switch(when time slice ends or the process waiting for a resource) from one process to other when execution context changes
• context is the contents of the CPU register and the program counter
• when context switch occur
• when scheduling multiple tasks(from one process or thread to another), handling the hardware interrupt,user and kernel mode switching

Unix File System

Unix filesystem

1. Unix has only files (directory,special file or device file) and processes
2. Tree like structure (hierarchy)
3. root node topmost (only one root)
4. all data in files is a stream of bytes, for the kernel
5. files dynamically grow

Internal View

1. made up of blocks (eg 512 or 1024 bytes blocks)
2. block 0 is boot block (used for booting)
3. block 1 is super block (store info about file system, like type,free and used space)
4. then comes the i-list blocks (contains the i-node blocks for all the files in the system)
5. then comes the data block (storing the actual data)

some string manipulation functions in C

  1: #include <stdio.h>
  2: #include <string.h>
  3: 
  4: char* my_strcpy(char* dest,const char* src);
  5: char* my_strncpy(char* dest,const char* src, size_t num);
  6: char* my_strcat(char* dest,const char* src);
  7: char* my_strncat(char* dest,const char* src,size_t num);
  8: int my_strcmp(const char* str1, const char* str2);
  9: int my_strncmp(const char* str1, const char* str2, size_t num);
 10: 
 11: main()
 12: {
 13:  
 14:  char arr1[] = "mithun";
 15:  char arr2[] = "my name is mithun";
 16:  char arr3[40] = "";
 17:  char* temp = arr3;
 18:  printf("%s \n",my_strncpy(arr1,arr2,6)?arr1:"dest size not adequate");  
 19:  printf("%s \n",my_strncpy(arr2,arr2,6)?arr2:"dest size not adequate");
 20:  printf("%s \n",arr2);  
 21:  printf("%s \n",my_strncpy(arr1,arr2,7)?arr1:"dest size not adequate");  
 22:  printf("%s \n",arr1);
 23:  
 24:  while(*temp)
 25:  printf("%p %c \n",temp,*temp++);
 26:  printf("%p --> %c \n",temp,*temp);
 27:   
 28:  printf("%s \n",my_strcat(arr3,arr1));  
 29:  printf("%s \n",my_strcat(arr3," hi to all of you"));
 30:  printf("%s \n",my_strncat(arr3," again hello, milo, bolo to all of you",7));
 31:  printf("%s \n",my_strncat(arr3,"you",6));
 32:  printf("%d \n",my_strcmp("abc","abc")); 
 33:  printf("%d \n",my_strcmp("abc","abcd")); 
 34:  printf("%d \n",my_strcmp("abcd","abc"));
 35:  printf("%d \n",my_strcmp("abc","xyz"));
 36:  printf("%d \n",my_strcmp("abc","abz"));
 37:  printf("%d \n",my_strcmp("a","a"));    
 38:  
 39:  printf("%d \n",my_strncmp("abc","axc",2)); 
 40:  printf("%d \n",my_strncmp("abc","abc",3)); 
 41:  printf("%d \n",my_strncmp("abc","abc",6));
 42:  
 43:  getchar();
 44: }
 45: 
 46: int my_strncmp(const char* str1, const char* str2,size_t num)
 47: {
 48:  while(*str1++ == *str2++ && num--)
 49:  {
 50:    if(!(*str1) && !(*str2) || !num)//both reached to NULL
 51:     return 0;  
 52:  }
 53:   str1--;
 54:   str2--;
 55:   if(*str1 > *str2)
 56:    return 1;
 57:   else if(*str1 < *str2)
 58:    return -1;  
 59: }
 60: 
 61: int my_strcmp(const char* str1, const char* str2)
 62: {
 63:  while(*str1++ == *str2++)
 64:  {
 65:    if(!(*str1) && !(*str2))//both reached to NULL
 66:     return 0;  
 67:  }
 68:   str1--;
 69:   str2--;
 70:   if(*str1 > *str2)
 71:    return 1;
 72:   else if(*str1 < *str2)
 73:    return -1;
 74: }
 75: 
 76: char* my_strcat(char* dest,const char* src)
 77: {
 78:  char* temp = dest;
 79:  while(*dest != '\0'){dest++;}
 80:  while(*dest++ = *src++);
 81:  return temp;
 82: 
 83: }
 84: 
 85: char* my_strncat(char* dest,const char* src,size_t num)
 86: {
 87:  char* temp = dest;
 88:  while(*dest != '\0'){dest++;}
 89:  
 90:  while(num-- && *src)
 91:   *dest++ = *src++;
 92:   *dest = '\0';
 93: 
 94:  return temp;
 95: 
 96: }
 97: 
 98: char* my_strncpy(char* dest,const char* src, size_t num)
 99: {
100:  if(dest == src)
101:   return NULL;
102: 
103:  char* temp = dest;
104:  while(num--)
105:   {
106:    if(*dest == '\0')
107:     return NULL;
108:    *dest++ = *src++;
109:   }
110:  return temp;
111: }
112: 
113: char* my_strcpy(char* dest,const char* src)
114: {
115:  char *temp = dest;
116:  while(*dest++ = *src++);
117:  return temp;  
118: }
119: 

Pointers to pointers,and arrays and strings I

1. the value stored (rvalue) and the address (lvalue) at which the value is stored and the name(variable name) which is mapped(in symbol table) to this address
2. variable for storing lvalue i.e. address is “pointer”
3. address of operator is ‘&’ , to get the address of any variable
4. dereferencing operator is ‘*’ , to get the value which the pointer variable is pointing
5. pointer arithmetic involves modifying address 
   
   1. so for a char* cptr saying cptr + 1, will increment the address by one (sizeof char)
   2. for a int* iptr saying iptr + 1, will increment the address by four (sizeof int) 

A sip of SIP

1. Session Initiation Protocol (application layer protocol)
2. communication session between two endpoints(single entity in the networked cloud which wants to initiate the session)
3. how to start talking (transfer voice data between), how to initiate, what are the things to agree upon
   
   1. some central entity to coordinate
   2. willingness to send and receive
   3. agreeing on same protocol
   4. knowledge of the location of each other (location can change at run time)
   5. ability to inform each other of some change
   6. some quality with regards to the data (voice,text,video) packets
   7. subscription to services, reception of change notification

Find Zeros and One

1: #include <stdio.h>
2: 
3: main()
4: {
5:   int val = 1;
6:   int data = 10;
7:   int OneCount = 0;
8:   int ZeroCount = 0;
9:   while(val)
10:   {
11:     if(data & val)
12:       OneCount++;
13:     else
14:       ZeroCount++;
15:       
16:     val = val << 1;  
17:   }
18:   printf("Number of ones %d \n",OneCount);
19:   printf("Number of zeroes %d \n",ZeroCount);
20:   getchar();
21: }

malloc(0), why is it working ?

1: #include <stdio.h>
2: #include <malloc.h>
3: 
4: char* reverse(char *data);
5: void my_Strcpy(char* dest,char* source);
6: main()
7: {
8:   char* p_Name = "Mithun P";
9:   char a_Name[] = "Mithun P";
10:   char *pd_Name = malloc(0);
11:   my_Strcpy(pd_Name,"Mithun P");
12:   
13: //printf("reverse of p_Name is %s \n",reverse(p_Name));
14:   printf("reverse of a_Name is %s \n",reverse(a_Name));
15:   printf("reverse of pd_Name is %s \n",reverse(pd_Name));
16:   
17:   getchar();
18: }
19: 

char[] and char*

1. char data[] = “data”;
1. data: [D] [A] [T] [A] [\0]
2. so , char data[] is a array holding the data\0
3. the individual characters can be modified
4. but data will always refer to the same storage

 

1. char *data = “data”;
1. [data] –> [D] [A] [T] [A] [\0]
2. so, char *data is a pointing to a string constant
3. the pointer can be modified to point to other location
4. modifying the string constant gives undefined result (SIGSEGV in gcc)

Deep Copy

1. needed when the class has dynamically allocated members
2. always remember the explicit this pointer of c++
3. copy constructor is implemented (algorithm)
   
   1. allocate memory for dynamically allocated members
   2. copy the data from const_argument.member to this.member
4. assignment operator is implemented (algorithm)
   
   1. check for self assignment
   2. delete memory for this.member
   3. allocate new memory for this.member
   4. copy the data from const_argument.member to this.member
   5. return this
5. when copy constructor is called
   
   1. doing initialization with objects, like
      
      1. class1 object1(“value”);
      2. class1 object2 = object1; //object to object assignment
   2. passing a object by value
   3. returning a object by value
6. when assignment operator is called
   
   1. assigning a existing object(object with memory for its data members) a new object

Composition, a type of aggregation

1. composition,  ( composite aggregation in UML), is part – whole relationship
2. Winston et al describes describes several kind composition, with three basic properties 
   1. configuration  (functional or structural relationship between part and whole)
   2. homeomerous (parts are the same kind of as the whole or not)
   3. invariance (parts can be separated from the whole or not)
3. based in these three properties the following kind of composition can be ascertained
   1. component – integral object composition (the integral whole is formed by the individual components, which can be removed but removing them will disintegrate the whole, like a laptop is made of different hardware components)
   2. material – object composition (the object is made is up the material, and the material cant be removed from the object, or it can be said that the object is made up of the material, like a cooking pan is made of steel)
   3. portion – object composition (portions are homeomeric with the object, like a link list is made up of individual nodes, in which each node can be considered as portion of the link list, each portion can be removed from the object)
   4. place – area composition (place within the area, and place cant be removed from the area, like pune is in India)
   5. member – bunch composition (members are just a collection which forms a bunch, like flowers in a bouquet)
   6. member – partnership composition (members are invariant part of the partnership, if parts are removed whole is destroyed)

Reference :

• Winston, Morton E., Roger Chaffin, and Douglas Herrmann, "A Taxonomy of Part-Whole Relations," Cognitive Science, 11, 1987, pp. 417-444.
• Six Different Kinds of Composition, by James J. Odell 

UML Class diagram notation

1. name
2. attributes (data)
3. behavior (messages and operations)
4. constraints
5. tagged values
6. stereotypes

Giving name to a architecture

1. before deciding on the style we need to find
   1. the components of the system
   2. the interaction between these components (what connects them)
   3. the constraints regarding the way components can combine and interact
   4. the underlying computational model
   5. essential invariants
   6. where it can be used, some examples
   7. advantages and disadvantages
   8. common specialization

Reference : cs.cmu.edu

UML Class Diagram

1. static view of the model
2. describes what the class attributes (data) are, and also the behavior in terms of
   1. how to use (create, modify) the data
   2. what are the messages the class understand
   3. operations appropriate for each message
3. very good at depicting
   1. relationship among the classes and interfaces
   2. generalization
      • inheritance
      • base-derived
      • type-of relationship
   3. aggregation
      • lighter aggregation
      • stronger composition
      • whole-part relationship
   4. association
      • connections
      • have-a relationship
      • cardinality, whether the association is compulsory or not
      • modality, how many instances of class “A” for a given instance of class “B” when class “A” and “B” are in association (zero, one or many)
      • role, each class has with respect to the other class in the association

Software Architecture

1. Organization of the system
2. With increasing size and complexity what is to be specified ?
   
   1. gross organization
   2. global control structure
   3. protocols for communication
   4. synchronization, and data access
   5. functionality of each design element
   6. physical distribution
   7. composition of each design element
   8. scaling and performance consideration
   9. design alternatives
3. Abstraction, the techniques how they grow
   
   1. high level programming languages abstract in the form of
      
      1. evaluation of arithmetic expression in conditional evaluation for deciding looping and procedure call
      2. modules which have related procedures
      3. data structures
      4. separation of module specification from its implementation
   2. abstract data types, to find what level of detail is sufficient for the task at hand, for this we need to segregate
      
      1. representation and operators
      2. specifications (what is expected from the software system)
      3. user defined types (classes ?)
      4. modules containing the user defined types
      5. the invariants of data structure (asserting that the structure remain consistent)
      6. protection of data structure from modification by other than the valid methods, of valid ADT
      7. access to the data, what is visible to all, what is selectively visible, and what is not
   3. recognizing the organization of a system, and giving a name to it, like
      
      1. client server model
      2. distributed object oriented approach
      3. pipeline
      4. ISO OSI Reference model (layered network)
      5. NIST/ECMA Reference model (layered communication substrates)
      6. X window system (event triggering and call-back)

Reference : www.cs.cmu.edu

UML Interaction Diagram

1. sequence diagram
2. communication diagram
3. timing diagram
4. interaction overview diagram

UML Behavior Diagrams

1. use case diagram
2. activity diagram
3. state machine diagram

UML Structure Diagrams

1. class diagram
2. object diagram
3. component diagram
4. composite structure diagram
5. package diagram
6. deployment diagram

UML

1. Unified Modelling Language
2. Specified by OMG (Object Management Group)
3. How to express what you have in mind about the
   
   1. design of a software system
   2. components of a software system and their behaviour
   3. interactions between the components of a software system
4. An abstract view of what the software system is intended to be
5. Express the results of your analysis and design using
   
   1. structure diagrams (6)
   2. behaviour diagrams (3)
   3. interaction diagrams (4)

Mth from the last of Link List in C

1: #include <stdio.h>
2: 
3: typedef struct node
4: {
5:   struct node *next;
6:   int data;
7: }listNode;
8: 
9: //passing the **head so that head can be modified
10: int insert(listNode **head,listNode *node)
11: {
12:   if(*head == NULL)
13:     *head = node;
14:   else
15:   {
16:     node->next = *head;
17:     *head = node;
18:   }    
19:   return 1;
20: }
21: 

Link List In C++

1: #include <stdio.h>
2: #include <iostream>
3: 
4: using namespace std;
5: 
6: class linkList
7: {
8:   typedef struct node
9:   {
10:     struct node *next;
11:     int data;
12:     node():next(NULL),data(-1){}
13:   }listNode;
14:   listNode *head;
15:   listNode *end;
16:   int m_nSize;
17: public:
18:   linkList(int size = 0);
19:   int insert(int data);
20:   //how many times find is in the list
21:   int count(int find);
22:   int getNth(int index);//index starting from 0
23:   //removes all the nodes, frees and set head null
24:   void deleteList();
25:   //pop the head, changes the head
26:   int pop();
27:   //inser data at nth index
28:   int insertAtNth(int index,int data);
29:   int sortedInsert(int data);
30:   void display();
31: };
32: 

Queue in C++, without passing pointers

1: #include <stdio.h>
2: #include <iostream>
3: 
4: #define CAP 10
5: //in case of c++, if there is no need to pass the pointers
6: //of head and tail as they are members of the class itself
7: //and the member functions can access them and modify them
8: class queue
9: {
10:   typedef struct node
11:   {
12:     struct node *next;
13:     int data;
14:   }qNode;
15:   
16:   qNode *head;
17:   qNode *end;
18:   int cap;
19:   int size;
20: public:
21:   queue(int cap = CAP);
22:   int dequeue();
23:   int enqueue(int data);
24:   void show();
25: };
26: 

Queue In C++ using link list

1: #include <stdio.h>
2: #include <iostream>
3: 
4: #define CAP 10
5: //if we are passing the pointers then they have to passed by 
6: //reference ie *&
7: 
8: class queue
9: {
10:   typedef struct node
11:   {
12:     struct node *next;
13:     int data;
14:   }qNode;
15:   
16:   qNode *head;
17:   qNode *end;
18:   int cap;
19:   int size;
20: public:
21:   queue(int cap = CAP);
22:   int dequeue(qNode *&head);
23:   int enqueue(qNode *&end, int data);
24:   void show();
25: };
26: 

Simple Queue in C using Fixed size array

1: #include <stdio.h>
2: 
3: //implementing a queue(fifo) structure
4: //using array with constant size
5: //not using dynamic memory
6: 
7: #define CAP 10
8: 
9: int enqueue(int *q,int *size,int data)
10: {
11:   if(*size == CAP)
12:     return 0;
13:     
14:   q[(*size)++] = data;
15:   return 1;
16: }
17: 
18: int dequeue(int *q, int *head)
19: {
20:   return q[(*head)++];
21: }
22: 
23: int main(int argc, char **argv)
24: {
25:   int arr[CAP];
26:   int head = 0;//starting index of the queue
27:   int size = 0;//size of the queue
28:   int i = 0;
29: 
30:   while(enqueue(arr,&size,i++));
31:   
32:   for(;;)
33:   {
34:     if (head == size)
35:       break;
36:     else  
37:       printf("element is %d \n",dequeue(arr,&head));
38:   }
39:   getchar();
40:   printf("hello world\n");
41:   return 0;
42: }
43: 

Stack using list in C++

In case of c++ we have a different way of passing the head pointer to the push and pop functions

If we are using the **head notation to pass a reference to the head pointer, then we have to explicitly use *head in the functions and &head while calling the functions. But if we are using the *&head to pass the c++ compiler will take care of the extra *and we don't have to put the extra * and & while using the head reference in the function or passing the reference argument respectively.

1: #include <stdio.h>
2: #include <iostream>
3: 
4: using namespace std;
5: 
6: //stack in c++ using link list
7: //using c++ style reference passing for head pointer
8: //ie passing *&head
9: 
10: #define INCREMENT 10
11: class stack
12: {
13:   typedef struct node
14:   {
15:     struct node *next;
16:     int data;
17:   }stackNode;
18:   
19:   int m_nCapacity;
20:   int m_nSize;
21:   stackNode *m_pHead;
22: public:
23:   stack(int capacity = INCREMENT);
24:   stack(const stack &theStack);
25:   stack& operator = (const stack &theStack);
26:   bool push(stackNode *&head,int data);
27:   int pop(stackNode *&head);
28:   stackNode*& getHead(){return m_pHead;}
29:   void show();
30: };
31: 

Stack Using Dynamic Array in C

1: #include <stdio.h>
2: #include <malloc.h>
3: 
4: #define INCREMENT 30
5: 
6: int capacity = 0;
7: int size = 0;//this will also be used as a index
8: //number of elements popped, 
9: //used in reducing the size of the array
10: int popCount = 0;
11: 

Stack using link list in C

1: #include <stdio.h>
2: #include <malloc.h>
3: #include <ctype.h>
4: 
5: //stack implementation using link list
6: typedef struct node
7: {
8:   int data;
9:   struct node *next;
11: }stackNode;
12: 
13: stackNode *head = NULL;
14: int size = 0;
15: