C program Linked Lists etc

[SargeRX8]

A particular operating system handles disk I/O by allowing independent user processes
to place I/O request blocks (IORB's) in a linked list. The order in which these requests
are serviced depends on their scheduling priority. The scheduling strategy is adaptive,
which simply means that the OS may carry out different computations at different times
in order to calculate the priority value for each element of the list.
You are rerquired to write a C program on Linux which design, implement and test a
function: sort list(), which will sort such a list according to the priority value computed by
whatever function is passed as its second argument. The First argument is to be a pointer
to the head of the list. Since the OS will have other structures with pointers to IORB's,
the list must be sorted in place.

This is the project we are given. Ive done everything for it except anything related to the priority. Anyone know WTF i have to do or how to do it? Using linux btw(horrid). WTF is that **** priority ****? Teacher is useless, ask for help they mutter words that mean ****.

[Khaless]

It looks like the important considerations are priority, in place, and testing... and explaining design. :P

From the question we get a couple of things

1) The OS may have more then one IO Scheduling strategy it can use. And it can pick and choose which one to use depending on various factors, this makes a lot of sense, and you should try to understand why.

2) You have to write a sort() function. And you know the arguments for this will be the head of the IORB list (struct iorb_item* head) or something of the like. and the second argument will be a function pointer to the function which returns a priority value. ( which could be, conceivably something like this: int (*priFunc)(* struct iorb_item_t))

3) it has to be sorted IN PLACE, due to various other requirements within the OS to access items in this list, you should not be creating new iorb_items! just changing the order of the linked list (next for a singly linked list and prev and next for a double)

4) Test Test Test!!!

[Khaless]

Oh yes, you also may want to think about why you have to sort it in place, i.e. what would happen if you didn't and started creating new IORB's and deleting the old ones? (kaboom/kernel panic, but why?)

Its probable that they expect you to elaborate on why the scheduling policy would be adaptive, and why it needs to be in place when you talk about the design.

[SargeRX8]

Ok i understand that. I was talking with the teacher and she said that if i do not implement that priority **** i will lose 1 mark.

This is my current code:

# include <stdio.h>
# include <stdlib.h>

typedef struct iorb {
        short base_pri;
        struct iorb *link;
        char filler[110];
} IORB;

struct node{
       int inputData;
       struct node *next;
   };

typedef struct node node;

node * head,*save,*current;

   void displayList (struct node *pList)
   {
      struct node *h;
      h = pList;
      printf("List Content: \n");
      if(pList!= NULL)
      {
            do
            {
                printf("%d\n",h->inputData);
                h=h->next;
            } while (h!= pList);
      }
      else
         printf("List content is EMPTY\n");
   }

   void sort_list(struct node *pList){

        /*Code for bubble sort alrogithm for a Array
        Bubble sort will check int X against intX+1.
        If int X is > then int X + 1 then switch
        else leave it as it is and then do the next int*/
        struct node *h;

        int temp;
        h = pList;
        current = save = h;

        if (pList==NULL)
            {
                    printf("\aLinked List Is Empty!\n");
            }
            else
            {
                printf("Well ok list isnt empty, now sort");

            }
        }



   struct node *insert(struct node *pList, int input){
      struct node *h;
      if(pList==NULL){
          pList=(struct node *)malloc(sizeof(struct node));

         if(pList==NULL) {
             printf("Unable to Allocate Memory\n");
         }
         pList-> inputData = input;
         pList-> next = pList;
      } else {
         h = pList;
         while (h-> next != pList)
            h = h-> next;
            h-> next = (struct node *)malloc(sizeof(struct node));
            if(h -> next == NULL){
               printf("Unable to Allocate Memory!\n");
            }
            h = h-> next;
            h-> inputData = input;
            h-> next = pList;
          }
          return (pList);
   }

Can you help me do a bubble sort function? Ive been sitting here for the past 2 hours and i can do it. I have no idea WTF is going on. This is my code from last year and i dont know how to implement a sort. Please, i need ANY help as this is proving to be quite a headache.

[ivo]

A) Write out the algorithm in psuedo-code
B) Write a new, out-of-context example in C, and test it with some numbers
C) Implement it in your project

Why are you bubble sorting? Its like the slowest way around!
Insertion sort or shell sort for the win! Nice demonstrations here.

[SargeRX8]

Ive got the pseudo code. Ive got the code ive used to bubble sort an array. Just implementing into this list **** is proving a mission. Ive got my code so far and this is it:

   struct node *sort_list(struct node *pList){
        struct node *h, *oneUp;
        int temp;
        h = oneUp = pList;

         for (pList=h;(pList != NULL);pList=pList->next)
         {
            for (oneUp=pList->next;(oneUp != NULL);oneUp=oneUp->next)
                {
                    if ( pList->inputData < oneUp->inputData ){

                    temp = oneUp->next;
                    oneUp->next = pList->next;
                    pList->next = temp;

                    }
                }
         }
          return (pList);
   }

Runs into an infinite loop or it just ****s it self(depending on the input).

Bubble sort is slow but thats what we have to use :/

I dont know why its not working...

[ivo]

I haven't done C/struts, so I can't help you much with the syntax.

Since it seems you've been trying to get a sorting alogrithm right for the past x hours, I'd recommend taking a deep breath, try as hard as you possibly can to forget everything you've just done, and start from scratch from the psuedo-code. Get the logic back, rather than keep your brain filled with code.

And to me, that looks like an insertion sort, not a bubble.

[Khaless]

Hey,

Ok I think what is happeing is that the syntax of C is confusing you.

What Ivo has said is a really good idea. Go back to psuedo-code and hammer out a solution.

it also looks like the only struct you need to worry about is 'struct iorb', or IORB (same thing, ...mostly)

So you get a HEAD which is an IORB which points to a next IORB (through link)

something like this (if there are 3 or more in the list)

void
my_function(IORB *head) {
printf("I am the first IORB %x\n", head);
printf("I am the second IORB %x\n", head->link);
printf("I am the third IORB %x\n", head->link->link);
}