[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [ipchat-devel] pqueue

From: Maximiliano Pin
Subject: Re: [ipchat-devel] pqueue
Date: Wed, 23 Mar 2005 23:21:52 +0100
User-agent: Mutt/1.5.6+20040907i


I saw your changes :-), I also commited changes to demux, removing the id
field in timer nodes. It's no longer needed, and it should never have

I only have a few comments:

* In pq_requeue(), power of two is being lost:

... realloc(q->heap,((q->size<<1)+1)*sizeof(pq_node*))

(127*2)+1 = 255

It should be:

... realloc(q->heap,((q->size+1)<<1)*sizeof(pq_node*))

So: (127+1)*2 = 256

The later: q->size<<=1;
Should be: q->size=(q->size<<1)+1;

(or, if u want to be cooler: q->size=(q->size<<1)|0x1;  :-) )

So it goes to 255. (note that's the same as reserved size minus one).

* In pq_add(), you call positionate(). I'd call float_node() instead,
because the new node is the last, it will never sink. So if you call
float_node() directly, you save a call and some checks.

* In pq_del_func() and pq_get_func(), you have two for's like these:

    if(pq->heap[i] && ...

I think this check should not be done. If there is a bug in pqueue, and you
get a hole (a NULL in the range 1..csize), it's much better to get a
reproducible segmentation fault, than ignoring the NULL pointer and get
extrange, difficult to reproduce, bugs later. If you get a segfault here,
you can debug pqueue easily.

> You are right and wrong, the sorting fails but it works fine, if you
> keep using the queue (like a priority queue must be used) you will see
> that the nodes come in the correct sequence. But I agree that it's
> better an intelligent (direction select) sorting (like pq_chpri do).
> Thanks for noting this.

Well, I believe than removing any element (different to the first) in a
priority queue is not extrange. For example, in an operating system, a
process could be removed from the priority queue (killed) before it gets
to run. The same happens with timers in ipchat (if a connection is
established before the timeout raises, for example).

> I already have a little fight with the realloc function, and as you
> can see it was the winner (don't repet please, jeje). But I have
> already seen that the code produced by usign this function was really
> nice. As far I can see you won the fight, now the pqueue will use
> realloc, jeje.

Hehe. Realloc is a nice function, it's good to get to know it. I have some
nice code in the transport module, using realloc to resize the input or
output buffers on demand.

> > * 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
> > ...
> The *trick* is a great idea, but it's a good idea to improve
> efficiency in ipchat. I'm agree with the idea of took some source and
> modify it to work in the better way for my program.

This trick will both simplify the code, and increase the efficiency a lot.
I'll send you a patch (maybe tomorrow) and you may decide. Note it removes
one level of indirection all around, i.e., a LOT of pointer dereferences.
And I think it has no disadvantage.

I hope to release 0.4 this weekend. There have been a lot of improvements
from 0.3, and it's time for a new release. We later can move on to
cryptography issues :-)
Maximiliano Pin
Powered by Debian GNU/Linux

Attachment: signature.asc
Description: Digital signature

reply via email to

[Prev in Thread] Current Thread [Next in Thread]