[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [ipchat-devel] pqueue
Re: [ipchat-devel] pqueue
Wed, 23 Mar 2005 23:21:52 +0100
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:
(127*2)+1 = 255
It should be:
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 :-)
Powered by Debian GNU/Linux
Description: Digital signature