Friday, December 7, 2012

Linux PM Blocks


Clock Framework
    Manages clocks, i.e. shut it down to save power
    Kernel APIs - clk_get, clk_enable,clk_disable,clk_put, clk_get_rate
    Drivers use clock API to respond to power management notifications

Suspend/Resume infrastructure
    High-level - suspend.c
    Low-level - sleep.S
    platform hooks in kernel
    Requires suspend() & resume() hooks in drivers

CPU Idle
    Kernel needs to be tickless
    Needs CPU driver with idle states managed by governors

Frequency & voltage scaling
    CPUFreq - responsible for defining operating points
    Drivers for low-level HW control, governors

Regulator framework
Power Management Qos

Methods to save power:

  •     Turn on only what's used
  •     DVFS when possible
  •     Manage power with states
  •     PLL Bypass/Power down
  •     Deep sleep mode
  •     RTC-only mode

Tuesday, July 31, 2012

Reverse the bits in an integer

#include <stdio.h>

int revint(int num)
{
    int result=0;
    while(num)
    {
        result<<=1;
        result|=num%2;
        num>>=1;
    }
    return result;
}

char *basecalc(int num,int base)
{
    static char buff[32];
    char *s = &buff[31];
    *s='\0';
    while(num)
    {
        *(--s)="0123456789ABCDEF"[num%base];
        num/=base;
    }
    return s;
}

int main(void)
{
    int num;
    printf("\nEnter the num: ");
    scanf("%d",&num);
    printf("The num: %s\n",basecalc(num,2));
    printf("The rev int: %s\n",basecalc(revint(num),2));
    return 0;
}

Find loop in a single linked list & remove it

/* How would you detect a loop in a linked list & remove it? */


#include <stdio.h>
#include <malloc.h>

typedef struct singlelink node;
struct singlelink
{
                int data;
                node *next;
};

void append(node **q,int num);
void display(node *temp);

void append(node **q,int num)
{
    node *temp=*q,*r;
                r = (node *)malloc(sizeof(node));
                r->data = num;
                r->next = NULL;
                if(temp==NULL) *q=r;
                else
                {
                                while(temp->next!=NULL)
                                                temp = temp->next;
                                temp->next = r;
                }
}

void display(node *temp)
{
                printf("\nThe list:\n");
                while(temp)
                {
                                printf("%d ",temp->data);
                                temp=temp->next;
                }
}

void createloop(node *q);
void createloop(node *q)
{
                node *temp=q;
                node *node2=NULL;
                node2=temp->next;
                while(temp->next !=NULL)
                {              temp=temp->next;}
                temp->next=node2;

}


#define DEBUG2              1
void removeloop(node *p, node *tmp);
void removeloop(node *p, node *tmp)
{
                node *temp1=p;
                node *temp2=p;
                unsigned int cnt=1,i;

                /* Count the no. of nodes in the loop */
                while(temp1->next != temp2)
                {
                                temp1 = temp1->next;
                                cnt++;
                }


                /* Fix one pointer to head & the other to cnt^th node from head */
                temp1=temp2=tmp;
                for(i=0;i
                                temp2=temp2->next;


                /* Move both pointers at the same pace, they will meet at the loop starting node */
                while(temp1 != temp2)
                {
                                temp1=temp1->next;
                                temp2=temp2->next;

                }

                /* Get pointer to the last node of loop & make next of it as NULL */
                temp2=temp2->next;
                while(temp2->next != temp1)
                                temp2 = temp2->next;

                temp2->next=NULL;
}



/* Floyd cycle detection algorithm */
void findloop(node *tmp);
void findloop(node *tmp)
{
                /* Have 2 pointers to start of the linked list.
                   Increment one pointer by 1 node and the other by 2 nodes.
                   If there's a loop, the 2nd pointer will meet the 1st pointer somewhere.
                   If it does, then you know there's one.
                */

                node *p,*q;
                p=q=tmp;

                while(p && q && q->next)
                {
                                p=p->next;
                                q=q->next->next;

                                if(p==q)
                                {
                                                printf("Loop detected..\n");
                                                removeloop(p,tmp);
                                                return;
                                }
                }
}




int main(void)
{
                node *head=NULL;
                int i;
                for(i=0;i<10;i++)
                                append(&head,i);
                display(head);

                createloop(head);
                printf("\nOK...\n");
                findloop(head);
                display(head);
                return 0;
}


/*
void findloop(node *tmp)
{
                // Have 2 pointers to start of the linked list.
                //   Increment one pointer by 1 node and the other by 2 nodes.
                //   If there's a loop, the 2nd pointer will meet the 1st pointer somewhere.
                //   If it does, then you know there's one.


                node *p,*q;
                p=tmp;
                q=p->next;
                while(p!=NULL && q!=NULL)
                {
                                if(p==q)
                                {
                                                printf("Loop detected..\n");
                                                removeloop(p,tmp);
                                                return;
                                }
                                p=p->next;
                                q=(q->next)?(q->next->next):(q->next);
                }

}
*/

Linked List Questions

  1. How do you reverse a singly linked list? How do you reverse a doubly linked list? Write a C program to do the same.
  2. Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
  3. How do you sort a linked list? Write a C program to sort a linked list.
  4. How to declare a structure of a linked list?
  5. Write a C program to implement a Generic Linked List.
  6. How do you reverse a linked list without using any C pointers?
  7. How would you detect a loop in a linked list? Write a C program to detect a loop in a linked list.
  8. How do you find the middle of a linked list? Write a C program to return the middle of a linked list.
  9. If you are using C language to implement the heterogeneous linked list, what pointer type will you use?
  10. How to compare two linked lists? Write a C program to compare two linked lists.
  11. How to create a copy of a linked list? Write a C program to create a copy of a linked list.
  12. Write a C program to free the nodes of a linked list.
  13. Can we do a Binary search on a linked list?
  14. Write a C program to return the nth node from the end of a linked list.
  15. How would you find out if one of the pointers in a linked list is corrupted or not?
  16. Write a C program to insert nodes into a linked list in a sorted fashion.
  17. Write a C program to remove duplicates from a sorted linked list.
  18. How to read a singly linked list backwards?
  19. How can I search for data in a linked list?