Thread: Accessing next entry in a queue.

I'd truly be grateful for insightful feedback on the following functions. Please note that I was instructed to declare the functions the way they are declared, so comments regarding the names and/or types of the variables would simply be irrelevant.

Code:

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


typedef struct driver{
    char name[101];
    int priority;
    struct driver* next;
}Driver;


typedef struct order{
    int orderID;
    int isSpecific;
    char specificDriver[101];
    struct order* next;
}Order;


typedef struct taxiSystem{
    Driver * driversQueue;
    Order * ordersQueue;
    int numOrder;
}TaxiSystem;


int addDriver(TaxiSystem * system, char * name, int priority);
int doesDriverExist(Driver * iter, char * name);
int findOrderByName(Order * iter, char * name);
void EraseOrder(Order ** iter, int ID);
void eraseFirstOrderHelper(Order ** iter);
void eraseOrderHelper(Order * prv);
int isNotSpecificOrder(Order ** iter);
int createDriverAndAddByPriority(TaxiSystem * system, char * name, int priority);


int main(){
	return 0;
}
		
int addDriver(TaxiSystem * system, char * name, int priority){
    int order;
    int spec;
    if (doesDriverExist(system->driversQueue, name))
        return 1;
    order = findOrderByName(system->ordersQueue, name);
    if (order){
        EraseOrder(&system->ordersQueue, order);
        return 1;
    }
    spec = isNotSpecificOrder(&system->ordersQueue);
	if (system->driversQueue == NULL && spec != 0)
		EraseOrder(&system->ordersQueue, spec);
	return(createDriverAndAddByPriority(system, name, priority));	
}


int doesDriverExist(Driver * iter, char * name){
    if (iter == NULL)
		return 0;
    return (strcmp(iter->name, name) == 0 || doesDriverExist(iter->next, name));
}


int findOrderByName(Order * iter, char * name){
    if (iter == NULL)
		return 0;
    return (strcmp(iter->specificDriver, name) == 0 ? iter->orderID : findOrderByName(iter->next, name));
}


void EraseOrder(Order ** iter, int ID){
    Order * cur = *iter, *prv = NULL;
    if (cur->orderID == ID) eraseFirstOrderHelper(iter);
    while (cur->orderID != ID && cur != NULL){
        prv = cur;
        cur = cur->next;
    }
    if (cur != NULL) eraseOrderHelper(prv);
}


void eraseFirstOrderHelper(Order ** iter){
    Order * tmp = *iter;
    *iter = tmp->next;
    free(tmp);
}


void eraseOrderHelper(Order * prv){
    Order * tmp = prv->next;
    prv->next = tmp->next;
    free(tmp);
}


int isNotSpecificOrder(Order ** iter){
	Order * tmp = *iter;
	while (tmp->isSpecific && tmp != NULL)
		tmp = tmp->next;
	if (tmp == NULL) return 0;
	return (tmp->orderID);
}


int createDriverAndAddByPriority(TaxiSystem* system, char* name, int priority){
	Driver *new_node = NULL, *cur = NULL, *prv = NULL;
	new_node = (Driver*) malloc(sizeof(Driver));
	if (new_node == NULL){
		printf("Fatal error: memory allocation failed!\n");
		return EXIT_FAILURE;
	}
	strcpy(new_node->name, name);
	new_node->priority = priority;
	cur = system->driversQueue;
	while (cur && (cur->priority < new_node->priority)){
		prv = cur;
		cur = cur->next;	
	}
	prv->next = new_node;
	new_node->next = cur->next;
	free(cur);
	return EXIT_SUCCESS;
}

Originally Posted by migf1

Please consider adding comments to the code, briefly explaining what each function is supposed to do and return, and how you approach the solution. This way it will be more clear to spot differences between your intention and your actual implementation. This would also increase the odds to get help, I think.

However, even then, I think it is unlikely that anyone will spend time and effort to fill up the main() function and debug the code for you using several test cases (unless you pay him, I guess ).

A better approach imho would be to test & debug your own code, and if you can't figure out why a specific function is not working the way it is supposed to, then post it here along with supporting info & comments so we can help you spot the specific problem.

Alright, I shall try, even though it is somewhat premature to implement main() at this point. These are merely building blocks. However, the following function is expected to create a new Driver node and embed it into the queue based on the driver's priority. Would it be possible for you, or anyone else for that matter, to simply read through and state whether anything seriously wrong meets the eye?

Code:

int createDriverAndAddByPriority(TaxiSystem* system, char* name, int priority){
    Driver *new_node = NULL, *cur = NULL, *prv = NULL;
    new_node = (Driver*) malloc(sizeof(Driver));
    if (new_node == NULL){
        printf("Fatal error: memory allocation failed!\n");
        return EXIT_FAILURE;
    }
    strcpy(new_node->name, name);
    new_node->priority = priority;
    cur = system->driversQueue;
    while (cur && (cur->priority < new_node->priority)){
        prv = cur;
        cur = cur->next; 
    }
    prv->next = new_node;
    new_node->next = cur->next;
    free(cur);
    return EXIT_SUCCESS;
}

state whether anything seriously wrong meets the eye?

Yes there is something obviously wrong.
free(cur); will ruin the queue. What do you want to free upon insertion ?
Kurt

Originally Posted by peripatein

Alright, I shall try, even though it is somewhat premature to implement main() at this point. These are merely building blocks.

I don't think it's premature. On the contrary, I would say it is the norm to test your functions immediately after writing them, before moving on to the next one.

For example, when you want to implement a linked-list, the very first functions you should write is: list_insert(), list_destroy() and list_print().

Then use them in your main() function to test that they work as expected under several test cases. Once they do, you may move say to list_delete_item() and then test that one again in the main(). Then to list_find_item(), and so on.

However, the following function is expected to create a new Driver node and embed it into the queue based on the driver's priority. Would it be possible for you, or anyone else for that matter, to simply read through and state whether anything seriously wrong meets the eye?

Code:

...

At a first glance, there is at least a problem when trying to insert the 1st node (more specifically, prv->next seg-faults).

Also, in all cases you shouldn't free(cur).

Is it okay now?:

Code:

.
.
.
       cur = system->driversQueue;
	while (cur && (cur->priority < new_node->priority)){
		prv = cur;
		cur = cur->next;	
	}
	prv->next = new_node;
	new_node->next = cur;
	return EXIT_SUCCESS;

I am trying to write a function the prime purpose of which is to initialize my main struct, TaxiSystem. The struct is defined thus:

Code:

typedef struct taxiSystem{
    Driver * driversQueue;
    Order * ordersQueue;
    int numOrder;
}TaxiSystem;

And I have so far written the following:

Code:

TaxiSystem* initSystem(){
	TaxiSystem *new_node = NULL;
	new_node = (TaxiSystem*) malloc(sizeof(TaxiSystem));
	new_node->numOrder = 0;
}

Problem is, I am not sure how to initialize the two other fields, namely the pointer to the Drivers' struct and the pointer to the Orders' struct.
I'd be indebted for a bit of guidance with this :-).

Here's an attempt. May I do the following (i.e. will it indeed initialize the desired main struct as needed)?:

Code:

	Driver* drvptr = NULL;
	Order* ordptr = NULL;
	new_node->driversQueue = drvptr;
	new_node->ordersQueue = ordptr;

Shure you can do it this way.
Problem is that your function createDriverAndAddByPriority() expects that driversQueue always points to a valid Driver *.
It's up to you what function you want to change.
I'd take care about tha case of inserting into an empty list in createDriverAndAddByPriority()
Kurt

I am afraid I would need some more concrete help with that one, Kurt. Could you possibly pinpoint exactly what ought to be emended? Furthermore, is there really no need to use more malloc's in the initialization of the prime struct TaxiSystem, that is malloc's for the pointers driversQueue and ordersQueue?

Originally Posted by peripatein

I am afraid I would need some more concrete help with that one, Kurt. Could you possibly pinpoint exactly what ought to be emended?

I'm afraid you rely too much on our help to debug/write your program.
Just try it out yourself. Call your function with system->driversQueue being empty and see what happens (Hint: migf1 told you already what the problem is).

Frankly, if you are unable to write test code for your functions you won't be able to finish your project.

Originally Posted by peripatein

Furthermore, is there really no need to use more malloc's in the initialization of the prime struct TaxiSystem, that is malloc's for the pointers driversQueue and ordersQueue?

IMHO there is no need for that. An init funcion should just prepare your data structures for later use. Setting the members to reasonable initial values like 0 or NULL is sufficient.

BTW:

Code:

Driver* drvptr = NULL;
Order* ordptr = NULL;
new_node->driversQueue = drvptr;
new_node->ordersQueue = ordptr;

why not simply

Code:

new_node->driversQueue = NULL;
new_node->ordersQueue = NULL;

?

Bye, Andreas

Originally Posted by AndiPersti

I'm afraid you rely too much on our help to debug/write your program. Just try it out yourself. Call your function with system->driversQueue being empty and see what happens (Hint: migf1 told you already what the problem is).Frankly, if you are unable to write test code for your functions you won't be able to finish your project.IMHO there is no need for that. An init funcion should just prepare your data structures for later use. Setting the members to reasonable initial values like 0 or NULL is sufficient.BTW:

Code:

Driver* drvptr = NULL;Order* ordptr = NULL;new_node->driversQueue = drvptr;new_node->ordersQueue = ordptr;

why not simply

Code:

new_node->driversQueue = NULL;new_node->ordersQueue = NULL;

?Bye, Andreas

Fellow forum members, I appreciate your concern and your willingness to assist, but telling me how I am unlikely to complete this task is quite redundant, as I am rather aware of the situation myself, and certainly not encouraging. Again, I realise you generally mean well, however repeating that risk will not help me to get there.

OK, so having run the debugger again, the program crashed at the second line of the following function;

Code:

int isNotSpecificOrder(Order ** iter){
 Order * tmp = *iter;
 while (tmp->isSpecific && tmp != NULL)
  tmp = tmp->next;
 if (tmp == NULL)
  return 0;
 return (tmp->orderID);
}
The function was called by:
int addDriver(TaxiSystem * system, char * name, int priority){
    int order;
    int spec;
    if (doesDriverExist(system->driversQueue, name))
        return 1;
    order = findOrderByName(system->ordersQueue, name);
    if (order){
        EraseOrder(&system->ordersQueue, order);
        return 1;
    }
 spec = isNotSpecificOrder(&system->ordersQueue);
    if (system->driversQueue == NULL && spec != 0) 
  EraseOrder(&system->ordersQueue, spec);
 return(createDriverAndAddByPriority(system, name, priority)); 
}

Now, would you please help me figure out why this is happening?

The program does not crash anymore! However, it doesn't update the queues as needed. Would anyone be so kind as to have a look at the relevant functions?

Code:

int isNotSpecificOrder(Order ** iter){
 Order * tmp = *iter;
 while (tmp->isSpecific && tmp != NULL)
  tmp = tmp->next;

Suppose "tmp" points to the last node and "tmp->isSpecific" is true. Now the assignment will store NULL in "tmp" and the program jumps back to the while-condition. Do you see your problem?

And why is "iter" a pointer to pointer to Order?

Bye, Andreas