stuck in Infinite-loop


J

James

arnuld said:
WANTED: To add a duplicate element into the Priority Queue (PQ)
GOT: Infinite loop



Check this very simple single linked list implementation of a priority
queue:




struct pqueue
{
struct pqueue* next;
unsigned int priority;
};




void
pqueue_push(struct pqueue** pq,
struct pqueue* node)
{
struct pqueue* cur = *pq;
struct pqueue* prev = NULL;

while (cur)
{
if (node->priority >= cur->priority) break;
prev = cur;
cur = cur->next;
}

if (prev)
{
node->next = prev->next;
prev->next = node;
}

else
{
node->next = cur;
*pq = node;
}
}


struct pqueue*
pqueue_pop_max(struct pqueue** pq)
{
struct pqueue* node = *pq;
unsigned int priority = (node) ? node->priority : 0;

while (node && node->priority == priority)
{
node = node->next;
}

*pq = node;

return node;
}


struct pqueue*
pqueue_pop(struct pqueue** pq,
unsigned int priority)
{
struct pqueue* cur = *pq;
struct pqueue* prev = NULL;

while (cur)
{
if (cur->priority == priority)
{
struct pqueue* eprev = cur;
struct pqueue* end = cur->next;

while (end && end->priority == priority)
{
eprev = end;
end = end->next;
}

if (! prev)
{
*pq = end;
}

else
{
prev->next = end;
}

eprev->next = NULL;

break;
}

prev = cur;
cur = cur->next;
}

return cur;
}


struct pqueue*
pqueue_find_max(struct pqueue const* pq)
{
return (struct pqueue*)pq;
}


struct pqueue*
pqueue_find(struct pqueue const* pq,
unsigned int priority)
{
while (pq)
{
if (pq->priority == priority) break;
}

return (struct pqueue*)pq;
}





The pqueue_push function will insert an item into the list, and handle
duplicate priorities.


The pqueue_pop_max removes all of the items with max priority.


The pqueue_pop functions removes all items with a given priority and returns
them in a NULL terminated linked list.


The pqueue_find_max returns a item chain with the highest priority.


The pqueue_find returns a item chain with a given priority.



you can scan item chains by iterating through them until the priority
changes.



Does that help you?


[...]
 
Ad

Advertisements

A

arnuld

WANTED: To add a duplicate element into the Priority Queue (PQ)
GOT: Infinite loop


If I insert an element into the PQ then its works fine. The problem
occurs only when I add a duplicate element, a condition handled by
PQL_add_element_duplicate() function.

I am using printf() statements and know where the error occurs, some
pointer which is supposed to be NULL is not getting set to NULL.




/* A Priority Queue (PQ) implemented as singly linked list where elements
are always added according to the priority and the element
* with highest priority is always at the beginning. Removal is done
only by removing the element with highest priority. Priority
* is an /int/.
*
*
* Insertion: O(N) in worst case.
* Find Max: 0(1)
* Deletion: O(1)
*
* VERSION 0.0
*
*/



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


enum BOOL { NO = 0,
YES = 1,
VAL_FAIL = NO,
VAL_SUCC = YES};


enum { SIZE_NAME = 30 };

struct pq_element
{
int priority;
struct pq_element* next;
};

struct pql
{
struct pq_element* head;
};



struct pql* PQL_init(void);
struct pq_element* PQL_create_element(int d);


void PQL_push(struct pql* s, struct pq_element* e);
void PQ_add_element(struct pql* s, struct pq_element* e);
void PQL_add_element_duplicate(struct pq_element* head, struct
pq_element* t);
void PQL_pop(struct pql* s);
void PQL_free_single(struct pq_element* e);

void PQL_print(struct pql* s);
void PQL_print_single(struct pq_element* p);



int main(void)
{
struct pql* pql = PQL_init();

struct pq_element* a1 = PQL_create_element(1);
struct pq_element* a2 = PQL_create_element(2);
struct pq_element* a0 = PQL_create_element(0);
struct pq_element* a6 = PQL_create_element(6);

if(NULL == pql)
{
/* fprintf(stderr, "IN: %s: malloc() failed\n", __func__); */
exit(EXIT_FAILURE);
}
else if(NULL == a1 ||
NULL == a2 ||
NULL == a0 ||
NULL == a6 )
{
/* fprintf(stderr, "LINE: %d, IN: %s: malloc() failed\n",
__LINE__, __func__); */
exit(EXIT_FAILURE);
}

PQL_push(pql, a1);
/*
PQL_push(pql, a2);
PQL_push(pql, a6);
PQL_push(pql, a0);
*/
PQL_print(pql);

printf("\n-------------- Adding 1 Duplicate ----------------\n\n");
PQL_push(pql, a1);
PQL_print(pql);


return 0;
}





struct pq_element* PQL_create_element(int d)
{
struct pq_element* p = malloc(1 * sizeof*p);

if(p)
{
p->priority = d;
p->next = NULL;
}

return p;
}


void PQL_push(struct pql* s, struct pq_element* e)
{
if(NULL == s)
{
/* fprintf(stderr, "IN: %s: Can not add element to a NULL list
\n", __func__); */
return;
}
else if(NULL == e)
{
/* fprintf(stderr, "IN: %s: Can not add NULL element to a list
\n", __func__); */
return;
}
else if(NULL == s->head) /* adding very first element */
{
/* printf("IN: %s: Adding very first element\n", __func__); */
s->head = e;
}
else
{
/* printf("IN: %s: Adding element to PQL\n", __func__); */
PQ_add_element(s,e);
}
}



/* This function works in conjuction with PQ_insert(), hecne there is no
need to check the arguments for NULL */
void PQ_add_element(struct pql* s, struct pq_element* e)
{
struct pq_element* h;

for( h = s->head; h; h = h->next)
{
if(e->priority > h->priority) /* given element has higher priroity
than head of list */
{
struct pq_element* temp = h->next;

if( temp && temp->priority == e->priority)
{
/* fprintf(stderr, "IN: %s: Element already exists, can not
add\n", __func__); */
return;
}
else
{
s->head = e;
e->next = h;
break;
}
}
else if(e->priority == h->priority) /* We got a duplicate */
{
PQL_add_element_duplicate(h, e);
}
else if(NULL == h->next) /* we have reached the end of list and
all elements have higher priority then given element */
{
h->next = e;
e->next = NULL;
break;
}
}
}


/* This function depends on the argumenst provided from PQ_add_element(),
it does not work standalone. Both arguments have already
been checked for NULL values in PQL_push() & PQL_add_element(). Hence
there is no need for a check here.

The phenomenon is little out of ordinary, hence I will explain. There are
basically 4 cases of duplication:

(1) PQL's Head is NULL and we are adding an element
(2) PQL's has only 1 element (the head) and it has same priority as the
inserting element.
(3) PQL's has 2 or more elements and the head has same priority as the
inserting element.
(4) PQL's has 2 or more elements and the last element has same priority
as the inserting element.
(5) PQL's has 2 or more elements and element other than the last has
same priority as of inserting element.

CASE (1) is simply not a duplicate-addition and is handled in PQL_push
().
CASE (2) will be done by just adding the element next to head.
CASE (3) will be done same as (2) except that the added element's next
will point to what head was pointing to earlier.
CASE (4) will be solved in simple manner by adding the element to the
end (and updating the tail of the queue, if we are working
with a queue which it does not apply in our case)
CASE (5) is a generic case, this is what most programmers think of
first when they code. Just insert the element between 2 elements.

I don't see any 6th case, if you have any, please mail me the CASE along
with code: (e-mail address removed) or see me in person, when
you and I both will have time. I will do by best to listen to you as long
you follow ISO C standard.
*/
void PQL_add_element_duplicate(struct pq_element* p, struct pq_element* t)
{
struct pq_element* q;

for( ; p; p = p->next)
{
printf("** p->priority: %d\n", p->priority);
printf("** t->priority: %d\n", t->priority);
printf("** p->next: %p\n", (void*)p->next);
if(p->priority == t->priority)
{
printf("p and t have == priority\n");

if(NULL == p->next) /* CASE (2) and (4) */
{
printf("p and t have == priority and p->next == NULL\n");
p->next = t;
break;
}
else
{
printf("p and t have == priority and p->next != NULL\n");
q = p;
}
printf("\n\n");
}
else if(p->priority < t->priority) /* CASE (3) and (5) */
{
q->next = t;
t->next = p;
break;
}
else
{
printf("IN: %s: , this condition must never reach\n", __func__);
return;
}
}


printf("\n----------------------------------\n\n");
}



/* Right now I don't know for what purpose the PQL_pop() will be used for
so I just made it generic, it removes the elemtn and free()es
the memory by itself. Later we may need to return the element or dom
something else. But I insist we should free the memory all by
ourselves in this library rather than forcing the 3rd party or other
library to free() the returned element.
*/
void PQL_pop(struct pql* s)
{
if(s && s->head)
{
struct pq_element* h = s->head;
s->head = s->head->next;
PQL_free_single(h);

if(NULL == s->head)
{
s->head = NULL;
}
}
}





/* ------------------ printing and small functions ------------------- */
struct pql* PQL_init(void)
{
struct pql* p = malloc(1 * sizeof*p);
if(p) p->head = NULL;

return p;
}


void PQL_free_single(struct pq_element* e)
{
free(e);
}


void PQL_print(struct pql* s)
{
struct pq_element* h = NULL;

for( h = s->head; h; h = h->next)
{
PQL_print_single(h);
}
}


void PQL_print_single(struct pq_element* p)
{
if(p)
{
printf("%d\n", p->priority);
}
}
 
B

Ben Bacarisse

arnuld said:
WANTED: To add a duplicate element into the Priority Queue (PQ)
GOT: Infinite loop

I am pretty sure your add_duplicate function accidentally builds a
loop in the list, but it is so fiddly (you use an extra pointer
variable, q, that is not easy to track) that I gave up trying to
follow exactly what it is doing.

Somehow you have manage to convince your self that this is complex
with lots of special cases. It isn't -- trust me! You just need to
scan the list to find where the new element goes. Finding the right
place for an element with priority p is usually a loop that stops when
an element with priority <= p is found. You just need to change that
to <. I'd have only one function too, rather than the three that you
have (and I don't think push is a good name for a queue operation).

<snip>
 
B

Barry Schwarz

WANTED: To add a duplicate element into the Priority Queue (PQ)
GOT: Infinite loop


If I insert an element into the PQ then its works fine. The problem
occurs only when I add a duplicate element, a condition handled by
PQL_add_element_duplicate() function.

I did not look at duplicate in detail because the function is
superfluous. There were enough problems with the other functions that
need to be solved first.
I am using printf() statements and know where the error occurs, some
pointer which is supposed to be NULL is not getting set to NULL.




/* A Priority Queue (PQ) implemented as singly linked list where elements
are always added according to the priority and the element
* with highest priority is always at the beginning. Removal is done
only by removing the element with highest priority. Priority
* is an /int/.
*
*
* Insertion: O(N) in worst case.
* Find Max: 0(1)
* Deletion: O(1)
*
* VERSION 0.0
*
*/



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


enum BOOL { NO = 0,
YES = 1,
VAL_FAIL = NO,
VAL_SUCC = YES};


enum { SIZE_NAME = 30 };

struct pq_element
{
int priority;
struct pq_element* next;
};

struct pql
{
struct pq_element* head;
};

I have never understood structures with only a single member.
struct pql* PQL_init(void);
struct pq_element* PQL_create_element(int d);


void PQL_push(struct pql* s, struct pq_element* e);
void PQ_add_element(struct pql* s, struct pq_element* e);
void PQL_add_element_duplicate(struct pq_element* head, struct
pq_element* t);
void PQL_pop(struct pql* s);
void PQL_free_single(struct pq_element* e);

void PQL_print(struct pql* s);
void PQL_print_single(struct pq_element* p);



int main(void)
{
struct pql* pql = PQL_init();

struct pq_element* a1 = PQL_create_element(1);
struct pq_element* a2 = PQL_create_element(2);
struct pq_element* a0 = PQL_create_element(0);
struct pq_element* a6 = PQL_create_element(6);

if(NULL == pql)
{
/* fprintf(stderr, "IN: %s: malloc() failed\n", __func__); */

This will print main as the function name and the malloc that failed
is not in main.
exit(EXIT_FAILURE);
}
else if(NULL == a1 ||

When the statement following an "if (expression)" ends with an
unconditional jump (such as exit, return, goto), there is no point in
following it with an else.
NULL == a2 ||
NULL == a0 ||
NULL == a6 )
{
/* fprintf(stderr, "LINE: %d, IN: %s: malloc() failed\n",
__LINE__, __func__); */

And this malloc didn't fail in main either nor at this line.
exit(EXIT_FAILURE);
}

PQL_push(pql, a1);
/*
PQL_push(pql, a2);
PQL_push(pql, a6);
PQL_push(pql, a0);
*/
PQL_print(pql);

printf("\n-------------- Adding 1 Duplicate ----------------\n\n");
PQL_push(pql, a1);
PQL_print(pql);


return 0;
}





struct pq_element* PQL_create_element(int d)
{
struct pq_element* p = malloc(1 * sizeof*p);

if(p)
{
p->priority = d;
p->next = NULL;
}

return p;
}


void PQL_push(struct pql* s, struct pq_element* e)
{
if(NULL == s)
{
/* fprintf(stderr, "IN: %s: Can not add element to a NULL list
\n", __func__); */
return;
}
else if(NULL == e)
{
/* fprintf(stderr, "IN: %s: Can not add NULL element to a list
\n", __func__); */
return;
}
else if(NULL == s->head) /* adding very first element */
{
/* printf("IN: %s: Adding very first element\n", __func__); */
s->head = e;
}
else
{
/* printf("IN: %s: Adding element to PQL\n", __func__); */
PQ_add_element(s,e);
}
}



/* This function works in conjuction with PQ_insert(), hecne there is no
need to check the arguments for NULL */

Since there is no PQ_insert function, should we assume you meant
PQ_push?
void PQ_add_element(struct pql* s, struct pq_element* e)
{
struct pq_element* h;

for( h = s->head; h; h = h->next)
{
if(e->priority > h->priority) /* given element has higher priroity
than head of list */

While the comment is true for the first iteration of the for loop, the
test is performed for every iteration.
{
struct pq_element* temp = h->next;

if( temp && temp->priority == e->priority)

Since you store elements in descending priority order, h->priority
must be greater than h->next->priority. Since e->priority is greater
than h->priority, it cannot possibly be equal to temp->priority.
{
/* fprintf(stderr, "IN: %s: Element already exists, can not
add\n", __func__); */
return;
}
else
{
s->head = e;

This only works if you never add a priority between two existing
priorities. In main up to the first PQL_print, you are always adding
a new highest priority or a new lowest priority
e->next = h;
break;
}
}
else if(e->priority == h->priority) /* We got a duplicate */
{
PQL_add_element_duplicate(h, e);
}
else if(NULL == h->next) /* we have reached the end of list and
all elements have higher priority then given element */
{
h->next = e;
e->next = NULL;

e->next is already NULL courtesy of PQL_create_element.
break;
}
}
}


/* This function depends on the argumenst provided from PQ_add_element(),
it does not work standalone. Both arguments have already
been checked for NULL values in PQL_push() & PQL_add_element(). Hence
there is no need for a check here.

The phenomenon is little out of ordinary, hence I will explain. There are
basically 4 cases of duplication:

(1) PQL's Head is NULL and we are adding an element

How do you think adding an element to an empty list can ever result in
duplication?
(2) PQL's has only 1 element (the head) and it has same priority as the
inserting element.
(3) PQL's has 2 or more elements and the head has same priority as the
inserting element.
(4) PQL's has 2 or more elements and the last element has same priority
as the inserting element.
(5) PQL's has 2 or more elements and element other than the last has
same priority as of inserting element.

CASE (1) is simply not a duplicate-addition and is handled in PQL_push
().

Apparently you don't so why bother even discussing it?
CASE (2) will be done by just adding the element next to head.

Since the two have the same priority, what difference does it make if
you point head to the new element (insert the new element at the head
of the list) or you point the existing element to the new element
(insert the new element after the existing one)? One difference is if
you choose the latter, you don't need this function at all.
CASE (3) will be done same as (2) except that the added element's next
will point to what head was pointing to earlier.
CASE (4) will be solved in simple manner by adding the element to the
end (and updating the tail of the queue, if we are working
with a queue which it does not apply in our case)

Then why mention it?
CASE (5) is a generic case, this is what most programmers think of
first when they code. Just insert the element between 2 elements.

I don't see any 6th case, if you have any, please mail me the CASE along
with code: (e-mail address removed) or see me in person, when
you and I both will have time. I will do by best to listen to you as long
you follow ISO C standard.
*/
void PQL_add_element_duplicate(struct pq_element* p, struct pq_element* t)
{
struct pq_element* q;

for( ; p; p = p->next)
{
printf("** p->priority: %d\n", p->priority);
printf("** t->priority: %d\n", t->priority);
printf("** p->next: %p\n", (void*)p->next);
if(p->priority == t->priority)
{
printf("p and t have == priority\n");

if(NULL == p->next) /* CASE (2) and (4) */
{
printf("p and t have == priority and p->next == NULL\n");
p->next = t;
break;
}
else
{
printf("p and t have == priority and p->next != NULL\n");
q = p;
}
printf("\n\n");
}
else if(p->priority < t->priority) /* CASE (3) and (5) */
{
q->next = t;
t->next = p;
break;
}
else
{
printf("IN: %s: , this condition must never reach\n", __func__);
return;
}
}


printf("\n----------------------------------\n\n");
}



/* Right now I don't know for what purpose the PQL_pop() will be used for
so I just made it generic, it removes the elemtn and free()es
the memory by itself. Later we may need to return the element or dom
something else. But I insist we should free the memory all by
ourselves in this library rather than forcing the 3rd party or other
library to free() the returned element.
*/
void PQL_pop(struct pql* s)

Usually, a pop function returns the element to the caller to do
whatever is needed..
{
if(s && s->head)
{
struct pq_element* h = s->head;
s->head = s->head->next;
PQL_free_single(h);

if(NULL == s->head)
{
s->head = NULL;

If s->head is already NULL, why set it to NULL again?
 
B

Ben Bacarisse

arnuld said:
WANTED: To add a duplicate element into the Priority Queue (PQ)
GOT: Infinite loop

Update! You get a loop because you trying to add the same element
twice, not to elements with the same priority. Since the element
includes that "next" link all sorts of odd things can happen if you do
that. You need to copy the element or change the structures so that
the element does not contain the "next" link.

My comments about the loops and special cases stand. You can simplify
the code a lot.

<snip>
 
A

arnuld

I did not look at duplicate in detail because the function is
superfluous. There were enough problems with the other functions that
need to be solved first.

:-\



I have never understood structures with only a single member.

It will keep track of the head of the list. I am doing addition and
removal from the head of the list. I got this idea from CLC itself. I was
given choice of IIRC 3 ways to use linked lists and I liked this one.



This will print main as the function name and the malloc that failed is
not in main.


But I was told only calling function checks the return value and here main
() is calling PQ_init() and that is why I did not put that check in
PQ_init() itself.



When the statement following an "if (expression)" ends with an
unconditional jump (such as exit, return, goto), there is no point in
following it with an else.

what if the if condition fails and then it goes to else. Isn't that
useful ?





Since there is no PQ_insert function, should we assume you meant
PQ_push?


Oh.. sorry.. leftover from an earlier try to write code. Earlier I was
using both head/tail (like a FIFO) so I named it enqueue() and then insert
() but now I am using only head of the list to add/remove elements hence
the push() and pop().

While the comment is true for the first iteration of the for loop, the
test is performed for every iteration.


Which is what I want, every element has to be checked for priority.
Perhaps the comment is wrong. It should read "given element has higher
priority than list element".



Since you store elements in descending priority order, h->priority must
be greater than h->next->priority. Since e->priority is greater than
h->priority, it cannot possibly be equal to temp->priority.


Corrected that.


This only works if you never add a priority between two existing
priorities. In main up to the first PQL_print, you are always adding a
new highest priority or a new lowest priority

Corrected.


e->next is already NULL courtesy of PQL_create_element.

Corrected.




How do you think adding an element to an empty list can ever result in
duplication?


Apparently you don't so why bother even discussing it?

statement removed.

Since the two have the same priority, what difference does it make if
you point head to the new element (insert the new element at the head of
the list) or you point the existing element to the new element (insert
the new element after the existing one)? One difference is if you
choose the latter, you don't need this function at all.


Because of the requirements I have on my desk. If there are 2 elements
which are added with same priority then one which was added earlier in
time will be removed first and then the other (just like LIFO). Since
elements are always being removed from the head, so it made sense to add
the duplicate after the original.




Then why mention it?

Corrected.




Usually, a pop function returns the element to the caller to do whatever
is needed..


If I return the element then I am forcing the 3rd party to free() it
which does not look like a god idea (at least to me). If I have malloc()
ed then I must free it. The caller can copy the contents and do whatever
he wishes but he is under no obligation to understand where and how I
mallod()ed the different things.


If s->head is already NULL, why set it to NULL again?

Aye... that was a typo, though quite big one ;)


I am rewriting some parts based on what you have advised. I will post it
as soon as I am satisfied with my rewrite.
 
Ad

Advertisements

A

arnuld

Check this very simple single linked list implementation of a priority
queue:
void
pqueue_push(struct pqueue** pq,
struct pqueue* node)
{
struct pqueue* cur = *pq;
struct pqueue* prev = NULL;

while (cur)
{
if (node->priority >= cur->priority) break; prev = cur;
cur = cur->next;
}

if (prev)
{
node->next = prev->next;
prev->next = node;
}

else
{
node->next = cur;
*pq = node;
}
}


This works fine as long as I am adding new elements, when I add a
duplicate it goes into infinite loop:


/* A Priority Queue (PQ) implemented as singly linked list where elements
are always added according to the priority and the element
* with highest priority is always at the beginning. Removal is done
only by removing the element with highest priority. Priority
* is an /int/.
*
*
* Insertion: O(N) in worst case.
* Find Max: 0(1)
* Deletion: O(1)
*
* VERSION 0.1
*
*/



#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stddef.h>
#include <limits.h>
#include <unistd.h>

enum BOOL { NO = 0,
YES = 1,
VAL_FAIL = NO,
VAL_SUCC = YES};


enum { SIZE_NAME = 30 };

struct pq_element
{
int priority;
struct pq_element* next;
};

struct pql
{
struct pq_element* head;
};



struct pql* PQL_init(void);
struct pq_element* PQL_create_element(int d);


void PQL_push(struct pql* s, struct pq_element* e);
void PQL_add_element(struct pq_element** , struct pq_element* );
void PQL_pop(struct pql* s);
void PQL_free_single(struct pq_element* e);

void PQL_print(struct pql* s);
void PQL_print_single(struct pq_element* p);



int main(void)
{
struct pql* pql = PQL_init();

struct pq_element* a1 = PQL_create_element(1);
struct pq_element* a2 = PQL_create_element(2);
struct pq_element* a0 = PQL_create_element(0);
struct pq_element* a6 = PQL_create_element(6);

if(NULL == pql)
{
/* fprintf(stderr, "IN: %s: malloc() failed\n", __func__); */
exit(EXIT_FAILURE);
}
else if(NULL == a1 ||
NULL == a2 ||
NULL == a0 ||
NULL == a6 )
{
/* fprintf(stderr, "LINE: %d, IN: %s: malloc() failed\n",
__LINE__, __func__); */
exit(EXIT_FAILURE);
}

PQL_push(pql, a1);
PQL_push(pql, a2);
PQL_push(pql, a6);
PQL_push(pql, a0);

PQL_print(pql);

printf("\n-------------- Adding 1 Duplicate ----------------\n\n");
PQL_push(pql, a1);
PQL_print(pql);


return 0;
}



struct pq_element* PQL_create_element(int d)
{
struct pq_element* p = malloc(1 * sizeof*p);

if(p)
{
p->priority = d;
p->next = NULL;
}

return p;
}


void PQL_push(struct pql* s, struct pq_element* e)
{
if(NULL == s)
{
/* fprintf(stderr, "IN: %s: Can not add element to a NULL list
\n", __func__); */
return;
}
else if(NULL == e)
{
/* fprintf(stderr, "IN: %s: Can not add NULL element to a list
\n", __func__); */
return;
}
else if(NULL == s->head) /* adding very first element */
{
/* printf("IN: %s: Adding very first element\n", __func__); */
s->head = e;
}
else
{
/* printf("IN: %s: Adding element to PQL\n", __func__); */
PQL_add_element(&(s->head),e);
}
}


void PQL_add_element(struct pq_element** p, struct pq_element* node)
{
struct pq_element* cur = *p;
struct pq_element* prev = NULL;

for( ; cur; cur = cur->next)
{
if(node->priority >= cur->priority)
{
break;
}

prev = cur;
}

if(prev)
{
node->next = prev->next;
prev->next = node;
}
else
{
node->next = cur;
*p = node;
}
}




/* Right now I don't know for what purpose the PQL_pop() will be used for
so I just made it generic, it removes the elemtn and free()es
the memory by itself. Later we may need to return the element or dom
something else. But I insist we should free the memory all by
ourselves in this library rather than forcing the 3rd party or other
library to free() the returned element.
*/
void PQL_pop(struct pql* s)
{
if(s && s->head)
{
struct pq_element* h = s->head;
s->head = s->head->next;
PQL_free_single(h);

}
}







/* ------------------ printing and small functions ------------------- */
struct pql* PQL_init(void)
{
struct pql* p = malloc(1 * sizeof*p);
if(p) p->head = NULL;

return p;
}


void PQL_free_single(struct pq_element* e)
{
free(e);
}


void PQL_print(struct pql* s)
{
struct pq_element* h = NULL;

for( h = s->head; h; h = h->next)
{
PQL_print_single(h);
}
}


void PQL_print_single(struct pq_element* p)
{
if(p)
{
printf("%d\n", p->priority);
}
}
 
J

James

arnuld said:
This works fine as long as I am adding new elements, when I add a
duplicate it goes into infinite loop:

[...]

The code I posted does not go into infinite loop when adding multiple items
with the same priority. However, I made a mistake in the pqueue_pop_max
function. Here is fully compliable code which demonstrates inserting
multiple items with the same priority:




#include <stddef.h>
#include <assert.h>




struct pqueue
{
struct pqueue* next;
unsigned int priority;
};




void
pqueue_push(struct pqueue** pq,
struct pqueue* node)
{
struct pqueue* cur = *pq;
struct pqueue* prev = NULL;

while (cur)
{
if (node->priority >= cur->priority) break;
prev = cur;
cur = cur->next;
}

if (prev)
{
node->next = prev->next;
prev->next = node;
}

else
{
node->next = cur;
*pq = node;
}
}


struct pqueue*
pqueue_pop(struct pqueue** pq,
unsigned int priority)
{
struct pqueue* cur = *pq;
struct pqueue* prev = NULL;

while (cur)
{
if (cur->priority == priority)
{
struct pqueue* eprev = cur;
struct pqueue* end = cur->next;

while (end && end->priority == priority)
{
eprev = end;
end = end->next;
}

if (! prev)
{
*pq = end;
}

else
{
prev->next = end;
}

eprev->next = NULL;

break;
}

prev = cur;
cur = cur->next;
}

return cur;
}


struct pqueue*
pqueue_pop_max(struct pqueue** pq)
{
struct pqueue* node = *pq;

if (node) return pqueue_pop(pq, node->priority);

return NULL;
}


struct pqueue*
pqueue_find_max(struct pqueue const* pq)
{
return (struct pqueue*)pq;
}


struct pqueue*
pqueue_find(struct pqueue const* pq,
unsigned int priority)
{
while (pq)
{
if (pq->priority == priority) break;
}

return (struct pqueue*)pq;
}




int
main(void)
{
#define DEPTH 20

size_t i;
struct pqueue* node;
struct pqueue* pq = NULL;
static struct pqueue nodes[DEPTH];

for (i = 0; i < DEPTH; ++i)
{
nodes.priority = i % 2;
pqueue_push(&pq, nodes + i);
}

node = pqueue_pop_max(&pq);
while (node)
{
assert(node->priority == 1);
node = node->next;
}

node = pqueue_pop_max(&pq);
while (node)
{
assert(node->priority == 0);
node = node->next;
}

return 0;
}




Does that work for you at all?
 
B

Ben Bacarisse

arnuld said:
This works fine as long as I am adding new elements, when I add a
duplicate it goes into infinite loop:

What could it possibly mean to have a linked list with duplicate
elements? You can have the same data in a list many times, but you
are trying to insert the same link node twice. It has only one next
pointer -- where should this pointer point?

This has been said before, and by more than one person, but I venture
to post an alternate phrasing of it because you seems to have missed
the problem that is being pointed out.

<snip>
 
B

Barry Schwarz

It will keep track of the head of the list. I am doing addition and
removal from the head of the list. I got this idea from CLC itself. I was
given choice of IIRC 3 ways to use linked lists and I liked this one.

How is that any different from having the scalar object
struct pq_element *head1;

Every place you use "struct pql" you would now use
"struct pq_element*". In your function calls where you pass the
address of the structure object you would pass the address of the
scalar object In your functions where you dereference the parameter
with the -> operator you would dereference the parameter with the *
operator.

If your structure had additional members, such as a tail pointer, it
would make more sense but a single member structure buys you nothing.
If you replaced your structure with a union, everything would remain
exactly the same so you are not benefiting from using a structure.
But I was told only calling function checks the return value and here main
() is calling PQ_init() and that is why I did not put that check in
PQ_init() itself.

Which calling function? The function which calls malloc or the
function which calls the function which calls malloc?

In any event, at this point you know which function called the malloc
that failed and you can print that function's name rather than
__func__.

Who is the message intended for. If it is a debugging message for the
programmer, then the function name is reasonable. If it is a status
message for the user telling him why the program is terminating, then
the function name (and even the word malloc) may be useless. In that
case, something like "Allocation failed for control table - run with
more memory available." may be more meaningful.
what if the if condition fails and then it goes to else. Isn't that
useful ?

Remove the else from the above code. What is the difference in
execution between the two versions?

If you look at the generated assembly, after the call to exit your
version will have a branch to skip the else (unless the compiler is
smart enough to realize that exit never returns). Since that branch
can never execute (either you don't enter the if or exit never
returns), it is unreachable code.

Oh.. sorry.. leftover from an earlier try to write code. Earlier I was
using both head/tail (like a FIFO) so I named it enqueue() and then insert
() but now I am using only head of the list to add/remove elements hence
the push() and pop().





Which is what I want, every element has to be checked for priority.
Perhaps the comment is wrong. It should read "given element has higher
priority than list element".

Exactly. When you look at the code in a couple of months, you don't
want the comment confusing you.
Corrected that.




statement removed.





Because of the requirements I have on my desk. If there are 2 elements
which are added with same priority then one which was added earlier in
time will be removed first and then the other (just like LIFO). Since
elements are always being removed from the head, so it made sense to add
the duplicate after the original.








If I return the element then I am forcing the 3rd party to free() it
which does not look like a god idea (at least to me). If I have malloc()
ed then I must free it. The caller can copy the contents and do whatever
he wishes but he is under no obligation to understand where and how I
mallod()ed the different things.

If you don't return the element to the caller, how does he ever
process it?
 
C

Chad

What could it possibly mean to have a linked list with duplicate
elements?  You can have the same data in a list many times, but you
are trying to insert the same link node twice.  It has only one next
pointer -- where should this pointer point?

This has been said before, and by more than one person, but I venture
to post an alternate phrasing of it because you seems to have missed
the problem that is being pointed out.

<OT>
</OT
 
Ad

Advertisements

C

Chad

What could it possibly mean to have a linked list with duplicate
elements?  You can have the same data in a list many times, but you
are trying to insert the same link node twice.  It has only one next
pointer -- where should this pointer point?

This has been said before, and by more than one person, but I venture
to post an alternate phrasing of it because you seems to have missed
the problem that is being pointed out.

<OT RANT>
I think my IQ actually drops 5 points every time I read some brain
dead arnuld code. Seriously, I really really hope he/she is joking
when he/she says he/she does this for a living because my impressions
is that he/she isn't bright enough to grasp something the first 6
times around. And if by some strange chance this moron does do this
for a living, I would seriously suggest that he/she find an easier
line of work.
</OT RANT>
 
B

bartc

Chad said:
<OT RANT>
I think my IQ actually drops 5 points every time I read some brain
dead arnuld code. Seriously, I really really hope he/she is joking
when he/she says he/she does this for a living because my impressions
is that he/she isn't bright enough to grasp something the first 6
times around. And if by some strange chance this moron does do this
for a living, I would seriously suggest that he/she find an easier
line of work.

Arnuld is apparently employed by a company to write these programs.

What is intriguing is that there exists a company whose purpose seems to be
to produce experimental programs for assorted linked list, tree and queue
implementations. I wonder what they're selling?
 
J

James

Ben Bacarisse said:
What could it possibly mean to have a linked list with duplicate
elements? You can have the same data in a list many times, but you
are trying to insert the same link node twice. It has only one next
pointer -- where should this pointer point?

I was 100% confused by arnuld's requirements. See, I thought that a
"duplicate" meant a unique item with the exact same priority of another item
which is _already_ in the list. Well, I guess you could have a counter
per-node. If the address of a "new" node is equal to a node in the list,
well, then the counter would be incremented by one. Deletions would
decrement the counter, only removing it on zero?

;^/

[...]
 
A

arnuld

Add this:

struct pq_element* a1dup = PQL_create_element(1);

Oh.. no. I was adding the same element again and again :-\ .

You're not modularising enough. That's why you have so much difficulty
understanding your own code.

I think I was confusing pointers and other variables like int and char.
My code is complex enough anyway. I am really amazed at how James came
with a so simple and straightforward solution of just one small function.

Though James solution has problem. e.g. head has the highest priority and
if I have 3 elements with same priority as the head then the head of the
list should be the one which was added first (oldest) but James solution
makes the latest one the head which is not what I want.
 
A

arnuld

..SNIP...
void
pqueue_push(struct pqueue** pq,
struct pqueue* node)
{
struct pqueue* cur = *pq;
struct pqueue* prev = NULL;

while (cur)
{
if (node->priority >= cur->priority) break; prev = cur;
cur = cur->next;
}

if (prev)
{
node->next = prev->next;
prev->next = node;
}

else
{
node->next = cur;
*pq = node;
}
}


You add the new node (with same priority as head) to the top and push the
current head as second element. This is not what I want to do. If an
element was added first and then an element with same priority comes then
the new element must be positioned after the older element but we are
doing opposite here.
 
Ad

Advertisements

C

Chris M. Thomasson

arnuld said:
[...]
You add the new node (with same priority as head) to the top and push the
current head as second element. This is not what I want to do. If an
element was added first and then an element with same priority comes then
the new element must be positioned after the older element but we are
doing opposite here.

It's a priority stack?

;^)
 
A

arnuld

How is that any different from having the scalar object
struct pq_element *head1;

Every place you use "struct pql" you would now use "struct pq_element*".
In your function calls where you pass the address of the structure
object you would pass the address of the scalar object


I don't know what exactly you mean by above statement. The scalar
variable (object) is actually a struct pointer varibale (object).



If your structure had additional members, such as a tail pointer, it
would make more sense but a single member structure buys you nothing. If
you replaced your structure with a union, everything would remain
exactly the same so you are not benefiting from using a structure.

I don't know why unions exists in C, I never saw anyone using that data
structure (except in K&R2 where authors tell us that the malloc() is
implemented internally using union of struct, section 8.7)



Which calling function? The function which calls malloc or the function
which calls the function which calls malloc?


Later one.


In any event, at this point you know which function called the malloc
that failed and you can print that function's name rather than __func__.

__func__ prints a function's name. (or you don't like C99 ?)


Who is the message intended for. If it is a debugging message for the
programmer, then the function name is reasonable. If it is a status
message for the user telling him why the program is terminating, then
the function name (and even the word malloc) may be useless. In that
case, something like "Allocation failed for control table - run with
more memory available." may be more meaningful.

All the statements/messages are intended for programmers only.


Remove the else from the above code. What is the difference in
execution between the two versions?

If you look at the generated assembly, after the call to exit your
version will have a branch to skip the else (unless the compiler is
smart enough to realize that exit never returns). Since that branch can
never execute (either you don't enter the if or exit never returns), it
is unreachable code.

I have thrown away my push() and using James version now, which still has
one problem I need to work on. Check my reply to James for that.

If you don't return the element to the caller, how does he ever process
it?

IIRC, the process included only copying of the elements by the caller of
pop(). Don't remember how exactly I did it but I never ever put the
liability (of free()ing the malloc() created by my library) on 3rd party.
I don't think its a good idea. Do you ?
 
Ad

Advertisements


Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top