ipchat-devel
[Top][All Lists]

## [ipchat-devel] pqueue

 From: Maximiliano Pin Subject: [ipchat-devel] pqueue Date: Sat, 12 Mar 2005 21:12:24 +0100 User-agent: Mutt/1.5.6+20040907i

```Hello list!

I've been studying the priority queue. It's a good algorithm.
I took some annotations:

* I think I found a case where the sorting fails:

1
10 20
12 14 30 32
16

Then remove the node with priority 30. Since the 16 is the last node, it goes
to its place, and the heap goes like this:
1
10 20
12 14 16 32

Then the sink() function is called. But this only moves nodes down, and
this node should be moved up, because 16 is lower than its parent, with
priority 20.

So it seems the sink() function is not enough, and we have to do something
like pq_chpri() does.

* The function pq_requeue could be simplified and optimized a lot.
I suggest something like:

int pq_requeue (pqueue *q)
{
int i;

if (!q)
return PQERR;

q->size *= 2;
q->heap = realloc (q->heap, (q->size + 1) * sizeof(pq_node *));

for (i = q->csize + 1; i <= q->size; i++)
q->heap[i] = NULL;
}

Note realloc() copies data to the new allocated buffer.
BTW Maybe this function should be static.

* There is a nice trick I learned from the autobook. You may increase the
efficiency a lot, and reduce the code size, by removing one level of
indirection in the nodes. Here it is:
http://sourceware.org/autobook/autobook/autobook_56.html

So, this is what I would do:
- Declare pq_node as:

typedef struct {
prio_t pri;
} pq_node;

(ie. remove the data field)

- Force the user data struct to begin with a prio_t. In our case (in demux):
struct timer_pq_node {
prio_t   next_alarm;  // must be the first field
timer_id id;
unsigned long int time_incr;
...
};

- The heap is an array of pointers to pq_node. There is no need to change
this, but these pointers will in fact be pointing to timer_pq_node's.
For example, this is what pq_add() would have to do:

prio_t pq_add(prio_t p,void * d,pqueue *q){
...
// this malloc is no longer needed :-)
// pq_node *node=(pq_node*)malloc(sizeof(pq_node));
// node->pri=p;
// node->data=d;

...

// q->heap[pos]=node;

// we can do this:
q->heap[pos] = (pq_node *)d;
...
}

- Finally, wherever we used q->heap[x]->data, you can use (void*)q->heap[x].
This includes, for example, the return value of pq_min(), or calls to
pq->equals_f().

- Note how many malloc()s, free()s, and pointer dereferences we save! :-)

* I'd change DEFAULT_SZ to 127 so a power of 2 is reserved ((127+1)*4 =
512). Also, in pq_requeue, put "+1" in: q->heap=new_heap(q->size*2);
so the new size is also power of 2.

* If I understood the algorithm well, it is impossible to have a hole (a
NULL pointer) among heap[1] and heap[csize]. So, there are a few functions
which could be optimized. For example, I'd change pos() to:

int pos(prio_t p,pqueue *q){
if(!q || !q->heap)
return PQERR;
int i=1;
for(; i<=(q->csize) && !PRI_EQ(p,q->heap[i]->pri) ;i++)
;
return (i > q->csize) ? PRIERR : i;
}

(
moreover, i think there is a bug in the current implementation:
return i==q->size ? PRIERR : i;
should be:
return i>q->size ? PRIERR : i;
since heap[q->size] is a valid element
)

* I noted the macro

#define MAX_PRI_EQ(A,B,C) PRI_EQ(MAX_PRI(A,B),C)

could be changed to an easier to understand:

#define PRI_GREATER(A,B) ((A) < (B))

Or something like that. The code will be simplier since you don't have to
repeat a parameter, and probably the generated machine code will be
simplier and faster as well.

* In new_heap(), you initialize all the pointers to NULL, but calloc()
already initializes the whole buffer to zero, so this is not needed.

* I think I will make timer_id's be timer_pq_node pointers, and remove the
current sequential identifiers (which may overflow). This will make it
unnecesary to create a temporal node for comparisons, and the timer_eq
function will be reduced to a comparison of pointers.

* I just commited demux with some fixes and improvements, and pqueue with
some typos corrected.

Nice job!! See you soon.
--
Maximiliano Pin