#include "pth_p.h"
#if cpp
struct pth_pqueue_st {
pth_t q_head;
int q_num;
};
typedef struct pth_pqueue_st pth_pqueue_t;
#endif
intern void pth_pqueue_init(pth_pqueue_t *q)
{
if (q != NULL) {
q->q_head = NULL;
q->q_num = 0;
}
return;
}
intern void pth_pqueue_insert(pth_pqueue_t *q, int prio, pth_t t)
{
pth_t c;
int p;
if (q == NULL)
return;
if (q->q_head == NULL || q->q_num == 0) {
t->q_prev = t;
t->q_next = t;
t->q_prio = prio;
q->q_head = t;
}
else if (q->q_head->q_prio < prio) {
t->q_prev = q->q_head->q_prev;
t->q_next = q->q_head;
t->q_prev->q_next = t;
t->q_next->q_prev = t;
t->q_prio = prio;
t->q_next->q_prio = prio - t->q_next->q_prio;
q->q_head = t;
}
else {
c = q->q_head;
p = c->q_prio;
while ((p - c->q_next->q_prio) >= prio && c->q_next != q->q_head) {
c = c->q_next;
p -= c->q_prio;
}
t->q_prev = c;
t->q_next = c->q_next;
t->q_prev->q_next = t;
t->q_next->q_prev = t;
t->q_prio = p - prio;
if (t->q_next != q->q_head)
t->q_next->q_prio -= t->q_prio;
}
q->q_num++;
return;
}
intern pth_t pth_pqueue_delmax(pth_pqueue_t *q)
{
pth_t t;
if (q == NULL)
return NULL;
if (q->q_head == NULL)
t = NULL;
else if (q->q_head->q_next == q->q_head) {
t = q->q_head;
t->q_next = NULL;
t->q_prev = NULL;
t->q_prio = 0;
q->q_head = NULL;
q->q_num = 0;
}
else {
t = q->q_head;
t->q_prev->q_next = t->q_next;
t->q_next->q_prev = t->q_prev;
t->q_next->q_prio = t->q_prio - t->q_next->q_prio;
t->q_prio = 0;
q->q_head = t->q_next;
q->q_num--;
}
return t;
}
intern void pth_pqueue_delete(pth_pqueue_t *q, pth_t t)
{
if (q == NULL)
return;
if (q->q_head == NULL)
return;
else if (q->q_head == t) {
if (t->q_next == t) {
t->q_next = NULL;
t->q_prev = NULL;
t->q_prio = 0;
q->q_head = NULL;
q->q_num = 0;
}
else {
t->q_prev->q_next = t->q_next;
t->q_next->q_prev = t->q_prev;
t->q_next->q_prio = t->q_prio - t->q_next->q_prio;
t->q_prio = 0;
q->q_head = t->q_next;
q->q_num--;
}
}
else {
t->q_prev->q_next = t->q_next;
t->q_next->q_prev = t->q_prev;
if (t->q_next != q->q_head)
t->q_next->q_prio += t->q_prio;
t->q_prio = 0;
q->q_num--;
}
return;
}
#if cpp
#define pth_pqueue_favorite_prio(q) \
((q)->q_head != NULL ? (q)->q_head->q_prio + 1 : PTH_PRIO_MAX)
#endif
intern int pth_pqueue_favorite(pth_pqueue_t *q, pth_t t)
{
if (q == NULL)
return FALSE;
if (q->q_head == NULL || q->q_num == 0)
return FALSE;
if (q->q_num == 1)
return TRUE;
pth_pqueue_delete(q, t);
pth_pqueue_insert(q, pth_pqueue_favorite_prio(q), t);
return TRUE;
}
intern void pth_pqueue_increase(pth_pqueue_t *q)
{
if (q == NULL)
return;
if (q->q_head == NULL)
return;
q->q_head->q_prio += 1;
return;
}
#if cpp
#define pth_pqueue_elements(q) \
((q) == NULL ? (-1) : (q)->q_num)
#endif
#if cpp
#define pth_pqueue_head(q) \
((q) == NULL ? NULL : (q)->q_head)
#endif
intern pth_t pth_pqueue_tail(pth_pqueue_t *q)
{
if (q == NULL)
return NULL;
if (q->q_head == NULL)
return NULL;
return q->q_head->q_prev;
}
intern pth_t pth_pqueue_walk(pth_pqueue_t *q, pth_t t, int direction)
{
pth_t tn;
if (q == NULL || t == NULL)
return NULL;
tn = NULL;
if (direction == PTH_WALK_PREV) {
if (t != q->q_head)
tn = t->q_prev;
}
else if (direction == PTH_WALK_NEXT) {
tn = t->q_next;
if (tn == q->q_head)
tn = NULL;
}
return tn;
}
intern int pth_pqueue_contains(pth_pqueue_t *q, pth_t t)
{
pth_t tc;
int found;
found = FALSE;
for (tc = pth_pqueue_head(q); tc != NULL;
tc = pth_pqueue_walk(q, tc, PTH_WALK_NEXT)) {
if (tc == t) {
found = TRUE;
break;
}
}
return found;
}