Link to home
Start Free TrialLog in
Avatar of redsar
redsar

asked on

splitting a linked list

That is what I want to do:
linked list:
2->4->3->18->15->7->9->NULL

the number is track number
a pointer called q_head points to 2
a pointer called q_tail points to 9

I wanna do SCAN disk algorithum...
If the track number, say, 14, split the linked list into two:
the request order would be 15->18->9->7->4->3->2
so I decide split the original link list to two:
1. higher track number order and sorted it i.e 15->18->NULL
2. lower track number order and sorted it i.e 2->3->4->7->9->NULL. then reverse it and combine to the 1 makes the request order....

I haven't sorted it..

typedef struct disk_rec disk;

struct disk_rec {
      int            proc;
      int            track;
      disk            *next;
      ReadOrWrite      type;
};
...
...
static      disk      *disk_q_head, *disk_q_tail;
...
get request and put in into the linked list...

void
scan_schedule(int current_time, int *delay, int *nextproc)
{
    disk *target, *low_queue, *high_queue, *ptlow;
    int disk_head = 14;

    target = disk_q_head;
    low_queue =  (disk *) malloc(sizeof(disk));
    low_queue->proc = 0;    /dummy node/
    low_queue->track = 0;
    low_queue->type = 0;
    high_queue =  (disk *) malloc(sizeof(disk));
    high_queue->proc = 0;
    high_queue->track = 0;
    high_queue->type = 0;
    ptlow = low_queue;
    while (target != NULL)
    {
      if (target->track < disk_head)
      {
        low_queue->next = target;
        low_queue = low_queue->next;
       }
      if(target->track > disk_head)
      {
       high_queue->next = target;
       high_queue = high_queue->next;
       }
       target = target->next;
     }
     while(ptlow != NULL)
     {
       high_queue->next = ptlow;
       high_queue = high_queue->next;
       ptlow = ptlow->next;
      }
 }

I don't think it is working and I have no idea about the sorting...do I need another two list to do insertion sort.?

Thanks in advance.
Avatar of ankuratvb
ankuratvb
Flag of United States of America image

Ok.
So what you want to do is:
from the current track position,take all higher track positions till end of platter and sort the,
Take all smaller track positions than the current pos.,sort them descending and attach them to the first sorted list.
Avatar of redsar
redsar

ASKER

yes...
Avatar of redsar

ASKER

but i'm not sure whether it works or how to do the sorting
Also,what you could consider is keeping the list sorted by changing your insert routine.

Then,form a new list by deleting nodes having larger track numbers than the current position by deleting these nodes from the original list and inserting them in the new list.

Now,the original list has the nodes less than the current position in ascending order.

If you use doubly linked list,you could traverse the list in reverse order,insering each node into the other list.

Or sort the LL in reverse order and insert the head of this list to the tail of the other.
Avatar of redsar

ASKER

btu did I create the two linked list properly and combine them? I don;t want the dummy node...
i think i get the idea, but technically, I can't make that run properly.thanks a lot...
You are allocating memory only for the header node for low_queue and high_queue.

if (target->track < disk_head)
     {
       low_queue->next = target;
       low_queue = low_queue->next;
      }

the first time this is executed,low_queue is an allocated node so its ok.
>low_queue = low_queue->next;
now,low_queue points to the node in the target node.
next time around:

>low_queue->next = target;

This modifies the target list since you are not allocating memory for nodes in low_queue.

the same goes for high_queue as well
Avatar of redsar

ASKER

sorry, can't really get the point...
but i guess i need to allocate memory for the target..
may be i should so something like

if (target->track < disk_head)
     {
         target = (disk *)malloc(sizeof(disk));
       low_queue->next = target;
       low_queue = low_queue->next;
      }

See,target points to your initial list.

You are constructing the other two lists:low_queue and high_queue.

What you could do is:

if (target->track < disk_head)
     {
       low_queue->next =(disk *)malloc(sizeof(disk));
//allocate a new node and make low_queue->next point to it.

//set the field values in the new allocated node.since low_queue->next points to the node,low_queue->next->proc points to its proc field
       low_queue->next->proc=target->proc;


>if (target->track < disk_head)
>    {
>        target = (disk *)malloc(sizeof(disk));
>      low_queue->next = target;
>      low_queue = low_queue->next;
>     }

Here what you would be doing is allocating a new node and making target point to it.After this you wouldnt be able to traverse the original list as the reference you had of that list was target and you now made it point to a new node.

       low_queue->next->track=target->track;
       low_queue->next->type=target->type;

//set the next pointer for this node to NULL.
       low_queue->next->next=NULL;

      }
I dont know what happened to the formatting of my prev post:

Here it is again:

See,target points to your initial list.

You are constructing the other two lists:low_queue and high_queue.

What you could do is:

if (target->track < disk_head)
    {
      low_queue->next =(disk *)malloc(sizeof(disk));
//allocate a new node and make low_queue->next point to it.

//set the field values in the new allocated node.since low_queue->next points to the node,low_queue->next->proc points to its proc field
      low_queue->next->proc=target->proc;
      low_queue->next->track=target->track;
      low_queue->next->type=target->type;

//set the next pointer for this node to NULL.
      low_queue->next->next=NULL;

     }

>if (target->track < disk_head)
>    {
>        target = (disk *)malloc(sizeof(disk));
>      low_queue->next = target;
>      low_queue = low_queue->next;
>     }

Here what you would be doing is allocating a new node and making target point to it.After this you wouldnt be able to traverse the original list as the reference you had of that list was target and you now made it point to a new node.
Avatar of redsar

ASKER

thanks....I hope that's ok...

void
scan_schedule(int current_time, int *delay, int *nextproc)
{
 disk *target, *low_q_head, low_q_tail, *high_q_head, *high_q_tail;
..

target = disk_q_head;

low_q_head = low_q_tail = NULL;
high_q_head = high_q_tail = NULL;

while(target != NULL){
    if ( target->track < diskhead){
    low_q_tail->next = (disk *)malloc(sizaeof(disk));
    low_q_tail->next->proc = target->proc;
    low_q_tail->next->track = target->track;
    low_q_tail->next->type = target->type;
    low_q_tail->next->next =NULL;
    low_q_tail = low_q_tail->next;
   }
   if (target->track >diskhead){
   //the same procedure as low_q_tail;
   }
  //sort both link list, reverse the low_q
   //then attach
   low_q_head = low_q_head->next //point to the first node
   while(low_q_head != NULL)
   {
      high_q_tail->next =(disk *)malloc(sizeof(disk));
      high_q_tail->proc =  low_q_head->proc;
     ...
     ..
     high_q_tail = high_q_tail->next;  
     low_q_head = low_q_head ->next;
}
}


This wont work as you have eliminated the dummy node and i didnt take care of that.
Initially low_q_tail is NULL and we use low_q_tail->next which hasnt been allocated.

Try this:

void
scan_schedule(int current_time, int *delay, int *nextproc)
{
disk *target, *low_q_head, low_q_tail, *high_q_head, *high_q_tail;
disk *low_h,*high_h; //points to the header of the lists.
int flag=0;
..

target = disk_q_head;

low_q_head = low_q_tail = NULL;
high_q_head = high_q_tail = NULL;

while(target != NULL){
   if( target->track < diskhead){
   low_q_tail = (disk *)malloc(sizeof(disk));
   if(flag==0)
   {
     low_h=low_q_tail;flag=1;
   }
   low_q_tail->proc = target->proc;
   low_q_tail->track = target->track;
   low_q_tail->type = target->type;
   low_q_tail->next =NULL;
   low_q_tail = low_q_tail->next;
  }
   if(target->track>diskhead){
   if(flag==0)
   {
     low_h=low_q_tail;flag=1;
   }
 //the same procedure as low_q_tail;
  }
 flag=0;
while(low_q_head != NULL)
  {
     high_q_tail=(disk *)malloc(sizeof(disk));
     if(flag==0)
    {
      high_h=low_q_tail;flag=1;
    }
     high_q_tail->proc =  low_q_head->proc;
    ...
    ..
    high_q_tail = high_q_tail->next;  
    low_q_head = low_q_head ->next;
}
}


I thought you might've needed the dummy node for header info. but the above code should work.

You need low_h and high_h to refer to the list from the start coz you advance low_q_tail everytime you insert a new node so low_q_tail points to the last node.

Also,in your code,

>low_q_head = low_q_head->next //point to the first node

What does this statement do.Is this to jump over the dummy node?
If this is the case,you dont need it any more,just use low_h.

To attach the second list at the end of the first one,just do:

high_q_tail->next=low_h;

high_q_tail points to the last node in this list.Initially its next pointer is NULL.
Just make its NEXT pointer point to the first node of the low_q list.

Thats all.You dont need to attach node by node.

Avatar of redsar

ASKER

thanks for your help,
I got another  idea, why don't simply pick the next element to serve in the disk_q, like this:
34>6->19->32->78->NULL
disk head = 10
the disk head moves up initially

disk *x, *target;
x = target = diskhead;
int foundtarget = 0
while (x !=NULL)
{
   if ( x->track > diskhead)
{
  if ( foundtarget == 0)
  {
      target = x;
      foundtarget = 1;
      break;
   }
  if (foundtarget == 1)
  {
    if (target ->track > x->track)
       traget = x;
    else
      break;
   }
}
   x = x->next;  
}
free(target);
Sorry.I couldnt get your point in your last post.

And if free(target) is meant to remove the node from the Queue list,you need to reassign the pointers as well otherwise u'd have a broken list.

For e.g.:

Original List:
34>6->19->32->78->NULL

You want to delete 19.free(19) just frees the memory allocated for the node 19.
But 6's next pointer still points to the location where 19 was allocated.you need to assign 6's next pointer to 19's next pointer before freeing it.



Sorry.I couldnt get your point in your last post.

And if free(target) is meant to remove the node from the Queue list,you need to reassign the pointers as well otherwise u'd have a broken list.

For e.g.:

Original List:
34>6->19->32->78->NULL

You want to delete 19.free(19) just frees the memory allocated for the node 19.
But 6's next pointer still points to the location where 19 was allocated.you need to assign 19's next pointer to 6's next pointer before freeing it.



The second post is correct.
>you need to assign 19's next pointer to 6's next pointer before freeing it.
Avatar of redsar

ASKER

thanks....
I think I'm lost...
this is my code so far..
void
scan_schedule(int current_time, int *delay, int *nextproc)
{
   disk *x, *target, *curr, *diskend;
   x = curr = target = disk_q_head;
   int foundtarget = 0;
   int diskhead = curr_track;
   /* There are no requests left and nothing for the disk to do */
   if(x == NULL) {
               idle = 1;
               last_busy = current_time;
               *nextproc = -1;
               return;
      }
      /* How long has the disk been idle? */
      if(idle == 1) {
                  time_waiting += (current_time-last_busy);
      }
      idle = 0;

   /*keep testing if there are requests in the queue */
   while(x != NULL  && curr_direction == 1){
         /* find a node that has a higher tracks in the current direction */
         if (x->track > diskhead){
               /* If the algorithm has not found any target yet. */
               if (foundtarget == 0){
                     target = x;
                     foundtarget = 1;
                     break;
           }

            /* If the algorithm has found target then compare the track number */
                  if (foundtarget == 1){
                        if(target->track > x->track)
                           target = x;
                        else
                           break;
                   }
       }
      x = x->next;
   }

   if (foundtarget == 1){
         /* remove the process form linked list */
         while(curr->next != target)
                         curr = curr->next;
         curr->next = target->next;

         /* is the data in the cache ? */
            if ((in_cache = is_in_cache(target->track))) {
                  if (target->type == Read)
                        num_cache_hits++;
            } else {
                  add_to_cache(target->track);
                  if (target->type == Read)
                        num_cache_misses++;
            }
            /* decide if we have to move the disk head */
                  /* note that we are not doing write-behind caching */
                  if ((target->type == Write) || !in_cache)
                        mustmove = abs(curr_track-target->track);
                  num_tracks += mustmove;
                  if(mustmove > 0) {
                        num_seeks++;
                        *delay = mustmove*track_cost + start_cost;
                        curr_track = target->track;
                  } else
                        *delay = 0;
                  /* (Getting data from the cache or the current track takes "no time") */
                  *nextproc = target->proc;
            free(target);
}
            /*
            * if the algorithm did not find any requests have higher track number in the current direction
            * seek to disk end and then change the direction
            */
         diskend = (disk *)malloc(sizeof(disk));
         if(diskend == NULL) {
                  fprintf(stderr, "Ran out of memory.\n");
                  exit(1);
            }
            diskend->proc = 0
            diskend->track = 99;
            diskend->type = 0;

         if (foundtarget == 0){
              curr_track = diskend->track;
              curr_direction  = 0
              free(diskend);
   }
Repeating my comment in your other thread,

Keeping the list sorted would be a better and much efficient option.
Here,you are scanning the entire list everytime a request is to be selected.
If you have the list sorted,traverse till the track number becomes greater than the current position,then delete all subsequent nodes from the original list.This can be done in O(1) time.

Form a list of the deleted nodes.This can also be done in O(1) time as you just have to point to the start of the deleted nodes.

Reverse the list and attach to the first list.

Avatar of redsar

ASKER

I guess, there may be more and more requests keep coming in...so even if I sorted the linked list, and i can only process one request at a time...I don;t know how to explain...
If I scanning the entire list evertime...I can handle the coming requests properly, because i pick the element in the current link list...
foe example
Initially, the requests are
3->4->34->23->21->NULL;
disk head = 5
execute the scan_schedule
pick 21 then more requests come in
3->4->34->23->20->80->NULL;
pick 20 when exe another time
then 23...34...80...

If I sorted the origianlly linked list...
1. 3->4->NULL
2. 21->23->34->NULL
combine
21->23->34->4->3->NULL
I would serve the request in this order no matter the more requests coming in...so I just ignore the coming requests even if they are closer to the current disk head...

sorry for the english...I'm not sure wether I'm on the right track...
Avatar of redsar

ASKER

hi, i don't quite understand some part of the code
void
scan_schedule(int current_time, int *delay, int *nextproc)
{
disk *target, *low_q_head, low_q_tail, *high_q_head, *high_q_tail;
disk *low_h,*high_h; //points to the header of the lists.
int flag=0;
..

target = disk_q_head;

low_q_head = low_q_tail = NULL;
high_q_head = high_q_tail = NULL;

while(target != NULL){
   if( target->track < diskhead){
   low_q_tail = (disk *)malloc(sizeof(disk));
   if(flag==0)
   {
     low_h=low_q_tail;flag=1;
   }
   low_q_tail->proc = target->proc;
   low_q_tail->track = target->track;
   low_q_tail->type = target->type;
   low_q_tail->next =NULL;
   low_q_tail = low_q_tail->next;
  }
   if(target->track>diskhead){
   if(flag==0)
   {
     low_h=low_q_tail;flag=1;  //IS that high_h = high_q_tail; flag =1;
   }
 //the same procedure as low_q_tail;  
  }
 flag=0; //why?
while(low_q_head != NULL)
  {
     high_q_tail=(disk *)malloc(sizeof(disk));
     if(flag==0)
    {
      high_h=low_q_tail;flag=1; //why  pount low_q_tail to high_h???
    }
     high_q_tail->proc =  low_q_head->proc;
    ...
    ..
    high_q_tail = high_q_tail->next;  
    low_q_head = low_q_head ->next;
}  //missing target = target->next???
}
thanks for your help again
ASKER CERTIFIED SOLUTION
Avatar of sunnycoder
sunnycoder
Flag of India image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of redsar

ASKER

i don;t think all the splitting, sorting working all right...
post your most recent code and the problems you are having with it
Have you tried executing your code?
Avatar of redsar

ASKER

void
scan_schedule(int current_time, int *delay, int *nextproc)
{
      disk *x, *target, *curr, *diskend;
      int foundtarget = 0;
      int diskhead = curr_track;
    int      mustmove = 0;
      int      in_cache = FALSE;
    x = curr = target = disk_q_head;

      /* There are no requests left and nothing for the disk to do */
      if(x == NULL) {
            idle = 1;
            last_busy = current_time;
            *nextproc = -1;
            return;
      }
      /* How long has the disk been idle? */
      if(idle == 1) {
            time_waiting += (current_time-last_busy);
      }
      idle = 0;

   /*find the next requsts that has higher track number*/
   while(x != NULL  && curr_direction == 1){
         if (x->track > diskhead){
               /* If the algorithm has not found any target yet. */
               if (foundtarget == 0){
                     target = x;
                     foundtarget = 1;
               }

            /* If the algorithm has found target then compare the track number */
                  if (foundtarget == 1){
                        if(target->track > x->track)
                           target = x;
                        else
                           break;
                   }
       }
      x = x->next;
   }
   if (foundtarget == 1){
   while( x !=NULL && curr_direction == 0){
         if ( x->track < diskhead){
               target  = x;
               foundtarget =1;
         }
        if (foundtarget == 1){
              if(target->track < x->track)
                    target = x;
          }
                   x= x->next;
     }
         /* remove the process form linked list */
         while(curr->next != target)
                         curr = curr->next;
         curr->next = target->next;

         /* is the data in the cache ? */
            if ((in_cache = is_in_cache(target->track))) {
                  if (target->type == Read)
                        num_cache_hits++;
            } else {
                  add_to_cache(target->track);
                  if (target->type == Read)
                        num_cache_misses++;
            }
            /* decide if we have to move the disk head */
        /* note that we are not doing write-behind caching */
                  if ((target->type == Write) || !in_cache)
                        mustmove = abs(curr_track-target->track);
                  num_tracks += mustmove;
                  if(mustmove > 0) {
                        num_seeks++;
                        *delay = mustmove*track_cost + start_cost;
                        curr_track = target->track;
                  } else
                        *delay = 0;
                  /* (Getting data from the cache or the current track takes "no time") */
                  *nextproc = target->proc;
            free(target);
  }

            /*
            * if the algorithm did not find any requests have higher track number in the current direction
            * seek to disk end and then change the direction
            */
         diskend = (disk *)malloc(sizeof(disk));
         if(diskend == NULL) {
                  fprintf(stderr, "Ran out of memory.\n");
                  exit(1);
            }
            diskend->proc = 0;
            diskend->track = 99;
            diskend->type = 0;

         if (foundtarget == 0 && curr_direction == 1){
              curr_track = diskend->track;
              curr_direction  = 0;
              free(diskend);
           }
        /* if no requests on the left side then change the direction to up again */
         if (foundtarget == 0 && curr_direction == 0){
                   curr_track = diskend->track;
                   curr_direction  = 1;
                   free(diskend);
           }

}  /* scan_schedule() */
post your most recent code ******and the problems you are having with it******

Makes my task a bit easier if you do not mind :o)
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Redsar,

If the problem is not solved as yet, I can reopen the question and we can continue discussion

sunnycoder
C'mon redsar,thats not fair.You are not supposed to accept an answer until your prolem is solved.

If its the code you cant understand,i'll try again.

Give us a chance.

I request sunny on the OP's behalf to unaccept the answers of this question as well as the other question:

http://oldlook.experts-exchange.com/questions/20958636/linked-list-problem.html
Avatar of redsar

ASKER

Thanks guys, basically the thing is i don't really understand the project...I can't implement what I want...I got segmentation fault when running...and the project package consist of many files, i can't post all the related file here, so it's hard to explain what the problems are...I wanna learn...how can I post all the realted files to u guys and post my code to see what's going wrong?
Put it up on a site,there are lots of free web hosting sites going around.

You can try www.freewebs.com

Are the source files large enough that they cant be posted here?
Avatar of redsar

ASKER

how can i attach the source files here?
you cannot attach the files here .... post them in some other site which gives you free web space e.g. geocities or freewebs and post the link here
I meant copy the code from your source file and paste it here. in a post.

The website idea is much better.

Redsar,

that is quite a bit of code .. I may have sometime during the weekend

1. point out what functions you need help with (just the name will suffice) and what help (what is not working)
2. Do you want me to reopen this question ?

sunnycoder
Avatar of redsar

ASKER

Thanks, I just need to implement three types disk scheduling, what i have done is in my code. I understand the disk scheduling, but the projects seems working for multiprocess in one time...my code obviously not working...

I guess I'll give points to u guys , cos u guys help a lot.
Hi redsar,

>that is quite a bit of code.
Seriously. :~))

To help you a little bit(this isnt the exact program you want),
I wrote my own program for SCAN based on the same structure defn as yours.

Here it is.Its quite simple and i've documented it as well.

//SCAN Schedule Implementation
#include<stdio.h>
#include<alloc.h>
struct node
{
      int proc;
      int track;
      struct node *next;
      int type;
}*p;
//p is the global reference to start of list
void scan_schedule(struct node *,int);
void store(struct node *,int,int,int);//param.(start of list,proc,track,type)
void disp(struct node *);
void del(struct node *,int);//param.(start of list,node number)
void main()
{
      int curr_track=30;
      p=NULL;
      store(p,1,70,1);
      store(p,1,60,1);
      store(p,1,50,1);
      store(p,1,40,1);
      store(p,1,30,1);
      store(p,1,20,1);
      store(p,1,10,1);
      scan_schedule(p,curr_track);
}
void store(struct node *q,int pr,int tr,int ty)
{
      if(q==NULL)
      {
            p=malloc(sizeof(struct node));
            p->proc=pr;
            p->track=tr;
            p->type=ty;
            p->next=NULL;
      }
      else
      {
            while(q->next!=NULL)
            {
                  q=q->next;
            }
            q->next=malloc(sizeof(struct node));
            q->next->proc=pr;
            q->next->track=tr;
            q->next->type=ty;
            q->next->next=NULL;
      }
}

void disp(struct node *q)
{
      printf("\nValues:");
      while(q!=NULL)
      {
            printf("\n%d %d %d ",q->proc,q->track,q->type);
            q=q->next;
      }
      getch();
}

void del(struct node *q,int n)
{
      int c=1;
      struct node *temp;
      if(n==1)
      {
            if(p==NULL)
            {
                  printf("Error");getch();return;
            }
            else
            p=p->next;
      }
      else
      {
            while(c<n-1)
            {
                  if(q->next==NULL)
                  {
                        printf("Error");getch();return;
                  }
                  q=q->next;c++;
            }
            if(q->next==NULL)
            {
                  printf("Error");getch();return;
            }
            q->next=q->next->next;
      }
}

void scan_schedule(struct node *q,int curr_track)
{
      int nc,deln;
      int start=0;//define start of platter
      int end=100;//define end of platter
      struct node *target;
      //node to store the target node which is to be serviced

      while(p!=NULL)//keep looping till there are nodes in the list
      {
            //this do loop services all nodes higher than current pos
            do
            {
                  target=NULL;
                  //target set to NULL to avoid changes to existing nodes
                  //since i use target to point to nodes in the list
                  //if i dont remove the reference,all serviced nodes
                  //would get track number=end
                  target->track=end;
                  //set target's track number to end of platter
                  nc=1;//counts node number starting from 1
                  while(q!=NULL)
                  {
                        if(q->track >= curr_track && q->track <= target->track)
                        {
                              target=q;deln=nc;//select target,set node number to be deleted
                        }
                        q=q->next;nc++;
                  }
                  if(target->track!=end)
                  {
                        curr_track=target->track;printf("\nService:%d",curr_track);
                        del(p,deln);//delete serviced node
                        q=p;//set q to point to start of list
                  }
            }
            while(target->track!=end);

            q=p;nc=1;
            //this do loop works backward servicing all nodes
            //less than current position
            do
            {
                  target=NULL;
                  target->track=start;
                  nc=1;
                  while(q!=NULL)
                  {
                        if(q->track <= curr_track && q->track >= target->track)
                        {
                              target=q;deln=nc;
                        }
                        q=q->next;nc++;
                  }
                  if(target->track!=start)
                  {
                        curr_track=target->track;printf("\nService:%d",curr_track);
                        del(p,deln);
                        q=p;
                  }
            }
            while(target->track!=start);
      }
}

The logic is what you wanted,keep scanning from one end to the other till you have nodes in the list,and always pick up the node that is closest to the current position in the direction that we are scanning.


Difference to your problem:

I delete nodes according to node number not according to node address.

HTH atleast a little bit.