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);
}
}
