Linked List rearrangement Example 1

/* re-arrange nodes in the LL inplace as below
head : 1->2->3->4->5
output: 1->5->2->4->3
 */

#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
    int num;
    struct Node *next;
} Node;

Node *newNode(int num)
{
    Node *temp = (Node*) malloc(sizeof(Node));
    temp->num = num;
    temp->next = NULL;
    return temp;
}

void reverse (Node** head)
{
    Node *prev = NULL,  *cur = *head, *next;
    while(cur) {
    next = cur->next;
    cur->next = prev;
    prev = cur;
    cur = next;
    }
    *head = prev;
}

void reArrangeNodes( Node** head)
{
    Node *slow = *head;
    Node *fast = slow->next;
    // find the mid point
    while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    }
    Node *head1 = *head;
    Node *head2 = slow->next;
    slow->next = NULL;

    reverse(&head2);
    *head = newNode(0);
    Node* cur = *head;
    while(head1 || head2) {
    if (head1) {
        cur->next = head1;
        cur = cur->next;
        head1 = head1->next;
    }

    if (head2) {
        cur->next = head2;
        cur = cur->next;
        head2 = head2->next;
    }
    }
    *head = (*head)->next;
}
int main()
{
    Node *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    head->next->next->next->next->next = newNode(6);
    head->next->next->next->next->next = newNode(7);
    printf("Input: ");
    Node *temp = head;
    while(temp) {
    printf ("%d ", temp->num);
    temp = temp->next;
    }
    printf("\n");
    reArrangeNodes(&head);
    printf("output: ");
    while(head) {
    printf("%d ", head->num);
    head=head->next;
    }
    printf("\n");
    return 0;
}

compare two string represented as Linked List similar to strcmp

/* compare two string represented as LL similar to strcmp */

#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
  char c;
  struct Node *next;
}Node;

Node* newNode(char c)
{
  Node *temp = (Node*) malloc (sizeof(Node));
  temp->c = c;
  temp->next = NULL;
  return temp;
};

int compare( Node *list1, Node *list2)
{
  while (list1 && list2 && (list1->c == list2->c))
      {
        list1 = list1->next;
        list2 = list2->next;
      }

   if (list1 && list2)
      return (list1->c >  list2->c) ? 1 : -1;

   if (list1 && !list2)
      return 1;
   if (!list1 && list2)
       return -1;
   return 0;
}

int main()
{
  Node *list1 = newNode('p');
  list1->next = newNode('e');
  list1->next->next = newNode('a');
  list1->next->next->next = newNode('c');

  Node *list2 = newNode('p');
  list2->next = newNode('e');
  list2->next->next = newNode('a');
  list2->next->next->next = newNode('c');
  list2->next->next->next->next = newNode('e');
  printf("compare result %d\n", compare(list1, list2));
  return 0;
}

remove all duplicates from the input string

/* remove all duplicates from the input string */

#include<stdio.h>
void removeDup(char *str) {
    int str_hash[256] ={0};
    int i;
    int count = 0;
    for (i=0; str[i] != '\0'; i++)
    {
    str_hash[str[i]]++;
        if (str_hash[str[i]] == 1)
            str[count++] = str[i];
    }
    str[count] = '\0';
}

int main() {
    char str[]= "pppppeeeeeeeeeeaaaaaaaaaaaccccccceeeeeee";
    removeDup(str);
    printf("the result string is %s\n", str);
    return 0;
}

remove spaces from a given string

/* remove spaces from a given string */

#include <stdio.h>
void removeSpaces(char *str)
{
 int count =0;
 int i;
 for (i =0; str[i] != '\0';i++){
      if(str[i] != ' ')
         str[count++]=str[i];
 }
 str[count] = '\0';
}
int main()
{
 char str[] = "A    w   eso m  e  ";
 removeSpaces(str);
 printf("result string is %s\n", str);
 return 0;
}

Given an array A[] and a number x, check for pair in A[] with sum as x

/* Given an array A[] and a number x, check for pair in A[] with sum as x */

#include <stdio.h>
void quickSort(int*, int, int);
void printSumPair(int A[], int arr_size, int sum) {
    int l, r;
    // sort in increasing order
    quickSort(A, 0, arr_size - 1);
    l = 0;
    r = arr_size-1;
    while (l < r) {
        if (A[l] + A[r] > sum)
            r --;
        else if (A[l] + A[r] < sum)
            l++;
        else {
            printf("%d + %d equals %d\n", A[l], A[r], sum);
            break;
        }
    }
}

int main() {
    int arr[] = {1,4,45,6,10,8};  // sorted would be : {1,4,6,8,10,45}
    int x = 16;
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    printSumPair(arr, arr_size, x);
    return 0;
}

void exchange (int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int partition (int A[], int si, int ei ) {
    int x  = A[ei];
    int i = si - 1;
    int j;
    for (j = si; j <= ei - 1; j++) {
       if(A[j] <= x) {
         i++;
         exchange (&A[j], &A[i]);
       }
    }
    exchange (&A[i+1], &A[ei]);
    return (i+1);
}

void quickSort (int A[], int si, int ei) {
    int pi;
    if (si < ei ) {
       pi = partition(A, si, ei);
       quickSort(A, si, pi-1);
       quickSort(A, pi+1, ei);
    }
}

if binary representation of a given number is pallindrom or not

/*  test if binary representation of a given number is pallindrom */

#include<stdio.h>
#include <stdbool.h>
bool isBinPallindrom(unsigned int num) {
    if (num == 0)
       return true;
    int posL = 1;
    int posR = 1;
    int temp = num;
    while(temp>>1) {
        temp >>=1;
        posR++;
    }
    printf("num is %d, MSB pos %d\n", num, posR);
    while (posR > posL) {
        if (((num & (1 << (posR -1))) >> (posR -1)) != ((num & (1 << (posL -1))) >> (posL -1))) {
              printf ("not pallindrom\n");
              return false;
        }
        posL++;
        posR--;
    }
    return true;
}
int main()
{
    unsigned int x = 22;
    printf("The number %d is %s\n", x, isBinPallindrom(x) ? "pallindrom": "not pallindrom");
    x = 0xFF;
    printf("The number %d is %s\n", x, isBinPallindrom(x) ? "pallindrom": "not pallindrom");
    return 0;
}

Least Recently Used Cache working example implementation in C

/* program to implement Least Recently Used (LRU) Cache */

#include<stdio.h>
#include<stdlib.h>
// define node for doubly linked list holds pageNumber
typedef struct QNode
{
    struct QNode *prev, *next;
    unsigned int pageNumber;
} QNode;

// Queue - collection of QNodes
typedef struct Queue
{
    unsigned count;
    unsigned numberofFrames;
    QNode *front, *rear;
} Queue;

// hash as collection of pointers to Qnodes and size
typedef struct Hash
{
    int capacity;
    QNode* *array;
}Hash;

QNode* createQNode(int pageNumber)
{
    QNode* qNode = (QNode*) malloc (sizeof(QNode));
    qNode->pageNumber = pageNumber;
    qNode->prev = qNode->next = NULL;
    return qNode;
}

Queue* createQueue(int numberofFrames)
{
    Queue* queue = (Queue*) malloc (sizeof(Queue));
    queue->count = 0;
    queue->front = queue->rear = NULL;
    queue->numberofFrames = numberofFrames;
    return queue;
}

Hash* createHash(int capacity)
{
    Hash *hash = (Hash*) malloc (sizeof(Hash));
    hash->capacity = capacity;

    hash->array = (QNode**) malloc( hash->capacity * sizeof(QNode*));
    int i;
    for(i =0; i< hash->capacity;++i)
    hash->array[i] = NULL;
    return hash;
}

void deQueue (Queue* queue) {
    if (queue->count == 0)
        return ;
    if (queue->front == queue->rear)
        queue->front = queue->rear = NULL;
    QNode* temp = queue->rear;
    queue->rear = queue->rear->prev;

    if(queue->rear)
       queue->rear->next = NULL;

    free(temp);
    if (queue->count > 0)
    queue->count--;
}

void Enqueue (Queue* queue, Hash* hash, unsigned pageNumber)
{
    if (queue->count == queue->numberofFrames) {
        hash->array[queue->rear->pageNumber] = NULL;
        deQueue(queue);
    }

    QNode* temp = createQNode(pageNumber);
    temp->next = queue->front;

    if (queue->count == 0) {
        queue->rear = queue->front = temp;
    } else {
        queue->front->prev = temp;
        queue->front = temp;
    }

    hash->array[pageNumber] = temp;
    queue->count++;
}
// when a page with pageNumber is referenced from cache:
// 1) frame is not present in memory,which needs to be added
//in memory (add at front of queue)
// 2) if page is present with given page number then needs to
// be moved to the front of queue.
void ReferencePage(Queue* queue, Hash* hash, unsigned pageNumber)
{
    QNode* reqPage = hash->array[pageNumber];
    // page is not in cache, add to the queue
    if (reqPage == NULL)
        Enqueue( queue, hash, pageNumber);
    // page is there and not at front, need to move to front
    else if (reqPage != queue->front) {
        reqPage->prev->next = reqPage->next;
        if (reqPage->next)
            reqPage->next->prev =  reqPage->prev;
        if(reqPage == queue->rear)
         {
             queue->rear = reqPage->prev;
             queue->rear->next = NULL;
         }

         reqPage->next = queue->front;
         reqPage->prev = NULL;

         reqPage->next->prev = reqPage;
         queue->front = reqPage;
     }
}


int main()
{
    // create a queue for number of pages to be hold by cache
    Queue* q = createQueue(4);  // 4 pages

    // create hash to reference pages
    Hash* hash = createHash(10);

    ReferencePage( q, hash, 1);
    ReferencePage( q, hash, 2);
    ReferencePage( q, hash, 3);
    ReferencePage (q, hash, 1);
    ReferencePage (q, hash, 4);
    ReferencePage (q, hash, 5);

    // print the cache page frames after the referencing
    printf ("%d", q->front->pageNumber);
    printf("%d", q->front->next->pageNumber);
    printf("%d", q->front->next->next->pageNumber);
    printf("%d\n", q->front->next->next->next->pageNumber);

    return 0;
}

Object Oriented Programming (OOP) Concepts

   Object Oriented Programming (OOP)

Lets start with "Object" . What is it? Object is anything which you can see around or which has some set of  identity, behavior , property to show.  like all living & non-living things - human , dog, car, book etc.  then for its definition, identity, classifications we needed a schematics used to represent  these details & data about it. And this schematic is termed as Class in OOP concepts.  So if you and me (humans) are objects then home sapiens is our class. So essentially object comes first then the class. Class defines relationship, behavior and inheritance for objects.

There's different models to explore this interesting concept (Object) & its implementation (Class) -

Object Oriented Analysis (OOA) :
Field to explore the problem and requirements from the perspective of objects & classes present in
the given problem case.

Object Oriented Design (OOD) :
Field to represent, conceptualize, design process of the object oriented abstraction, notation/symbols to show the logical/physical model of the system, which fulfills the problem requirement.

Object Oriented Programming (OOP) :
Finally, We need to implement our conceptual solution or the design made out of the abstracted problem requirement into working model. In this process, there's programming which shows the collection of objects, and each would be the instance of some classes linked together directly or indirectly, and these classes would be either parent, present in some hierarchy, or associated with other classes.

In object-oriented programming, a class is an extensible program-code-template for creating objects, providing initial values for state (member variables) and implementations of behavior (member functions, methods)

A class may have three kinds of members:
–Attributes (fields, data members) are data variables associated with a class and its objects. They store results of computation performed by the class methods and also the state of the object.
–Methods define behaviors for object & contain the executable code of a class.
–Classes can be members of other classes.

for ex-


class Dog{
   int name;
   int breed;
   int age;

   printName(name);
   matchBreed(breed);
   happyBday(age++);
}


OOP relationships among Objects :

DEBUGGING

Android Logging

- user space logging

adb logcat  > logcat.txt

To enable meta data option with logcat , -v option can be used which includes :

ex- adb logcat -v threadtime > logcat.txt
brief — Display priority/tag and PID of originating process (the default format).
process — Display PID only.
tag — Display the priority/tag only.
thread — Display process:thread and priority/tag only.
raw — Display the raw log message, with no other metadata fields.
time — Display the date, invocation time, priority/tag, and PID of the originating process.

long — Display all metadata fields and separate messages with a blank lines.

alternative logging using -b option 

ex - adb logcat -b events > events.txt
radio — View the buffer that contains radio/telephony related messages.
events — View the buffer containing events-related messages.
main — View the main log buffer (default)

- kernel space logging

adb shell dmesg

or ,

adb root

adb shell cat /proc/kmsg > kernel.txt

Process CPU utilization :

adb shell top 

with -m option , the number of process can be selected for which % is needed.

ex  - adb shell top -m 5

Memory Info

adb shell cat proc/meminfo

Procrank ( courtesy http://elinux.org/Android_Memory_Usage) :

procrank shows you a quick summary of process memory utilization. By default, it shows Vss, Rss, Pss and Uss, and sorts by Vss. However, you can control the sorting order.

procrank source is included in system/extras/procrank, and the binary is located in /system/xbin on an android device.

• Vss = virtual set size
• Rss = resident set size
• Pss = proportional set size
• Uss = unique set size

In general, the two numbers you want to watch are the Pss and Uss (Vss and Rss are generally worthless, because they don't accurately reflect a process's usage of pages shared with other processes.)

• Uss is the set of pages that are unique to a process. This is the amount of memory that would be freed if the application was terminated right now.
• Pss is the amount of memory shared with other processes, accounted in a way that the amount is divided evenly between the processes that share it. This is memory that would not be released if the process was terminated, but is indicative of the amount that this process is "contributing"

to the overall memory load.

You can also use procrank to view the working set size of each process, and to reset the working set size counters.

Here is procrank's usage:

# procrank -h
Usage: procrank [ -W ] [ -v | -r | -p | -u | -h ]
    -v  Sort by VSS.
    -r  Sort by RSS.
    -p  Sort by PSS.
    -u  Sort by USS.
        (Default sort order is PSS.)
    -R  Reverse sort order (default is descending).
    -w  Display statistics for working set only.
    -W  Reset working set of all processes.
    -h  Display this help screen.

And here is some sample output:

# procrank
  PID      Vss      Rss      Pss      Uss  cmdline
 1217   36848K   35648K   17983K   13956K  system_server
 1276   32200K   32200K   14048K   10116K  android.process.acore
 1189   26920K   26920K    9293K    5500K  zygote
 1321   20328K   20328K    4743K    2344K  android.process.media
 1356   20360K   20360K    4621K    2148K  com.android.email
 1303   20184K   20184K    4381K    1724K  com.android.settings
 1271   19888K   19888K    4297K    1764K  com.android.inputmethod.latin
 1332   19560K   19560K    3993K    1620K  com.android.alarmclock
 1187    5068K    5068K    2119K    1476K  /system/bin/mediaserver
 1384     436K     436K     248K     236K  procrank
    1     212K     212K     200K     200K  /init
  753     572K     572K     171K     136K  /system/bin/rild
  748     340K     340K     163K     152K  /system/bin/sh
  751     388K     388K     156K     140K  /system/bin/vold
 1215     148K     148K     136K     136K  /sbin/adbd
  757     352K     352K     117K      92K  /system/bin/dbus-daemon
  760     404K     404K     104K      80K  /system/bin/keystore
  759     312K     312K     102K      88K  /system/bin/installd
  749     288K     288K      96K      84K  /system/bin/servicemanager
  752     244K     244K      71K      60K  /system/bin/debuggerd

How to debug native process memory allocations

 adb root

 adb shell setprop libc.debug.malloc 1

adb shell stop

adb shell start

Supported values for libc.debug.malloc (debug level values) are:

• 1 - perform leak detection
• 5 - fill allocated memory to detect overruns
• 10 - fill memory and add sentinels to detect overruns
• 20 - use special instrumented malloc/free routines for the emulator

loglevel

loglevel — Set the default console log level.
The console log level can also be changed by the klogd program, or by writing the specified level to the /proc/sys/kernel/printk file.

The kernel log levels are:

0 (KERN_EMERG)

The system is unusable.

1 (KERN_ALERT)

Actions that must be taken care of immediately.

2 (KERN_CRIT)

Critical conditions.

3 (KERN_ERR)

Non-critical error conditions.

4 (KERN_WARNING)

Warning conditions that should be taken care of.

5 (KERN_NOTICE)

Normal, but significant events.

6 (KERN_INFO)

Informational messages that require no action.

7 (KERN_DEBUG)

Kernel debugging messages, output by the kernel if the developer enabled debugging at compile time.

log_buf_len

log_buf_len — Set the size of the kernel log buffer.
 Set the size of the kernel's internal log buffer. n must be a power of 2, if not, it will be rounded up to be a power of two.
 
  

GDB Debugging :   

http://dirac.org/linux/gdb/

http://www.yolinux.com/TUTORIALS/GDB-Commands.html

 copy  <build_path>obj/EXECUTABLES/gdbserver_intermediates/gdbserver. to the device

 host:> adb forward tcp:5039 tcp:5039

host:> adb shell

<device># gdbserver :5039 </path/to/executable> [<cmd line params>]

host:> cd </path/to/unstripped/executable>

host:> arm-eabi-gdb

  (gdb) file <executable>

  (gdb) set solib-absolute-prefix <android product out>/symbols (optional - may not be required)

  (gdb) set solib-search-path <android product out>/system/lib  (optional - may not be required)

  (gdb) target remote :5039

  (gdb) shared (optional - may not be required)

  (gdb) b main

  (gdb) cont

or for remote

1) adb forward tcp:5039 tcp:5039

2) adb shell ps mediaserver

3) adb shell gdbserver :5039 --attach <pid>

4) gdbclient mediaserver :5039

5) (gdb) b <filename>:<line_num>

6) (gdb) cont

for core dump analysis :

$arm-linux-androideabi-gdb symbols/system/bin/app_process

(gdb) set solib-absolute-prefix ./symbols

(gdb) set solib-search-path ./symbols/system/lib:./symbols/system/lib/egl:./symbols/system/lib/hw:

(gdb) core <core_file>

(gdb) backtrace full  or bt

(gdb) info register

(gdb) disassemble <addr>