Re: [ipchat-devel] pqueue

[Matías Aguirre]

I'll submmit the changes soon.


On Sat, 19 Mar 2005 09:41:20 -0300, Matías Aguirre
<address@hidden> wrote:
> Hi!
> 
> On Sat, 12 Mar 2005 21:12:24 +0100, Maximiliano Pin <address@hidden> wrote:
> > I've been studying the priority queue. It's a good algorithm.
> > I took some annotations:
> 
> Congratulations for looking at the priority queue, as you say it's a
> good algorithm, and really nice when you take hands on it.
> 
> 
> > * I think I found a case where the sorting fails:
> > ...
> 
> 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.
> 
> 
> > * The function pq_requeue could be simplified and optimized a lot.
> > I suggest something like:
> > ...
> 
> 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.
> 
> 
> > * 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.
> 
> 
> > * 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.
> > ...
> 
> DEFAULT_SZ=127
> Yes it's nice, I defined it to 100 in some moment of pqueue life, and
> never saw it again.
> 
> 
> > * 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:
> > ...
> 
> Yes, it looks like it's impossible to have a hole, and yes it's a bug.
> 
> > * I noted the macro
> > ...
> 
> My mmacro's (and variable's) names are the worst in the programming
> history, so any rename are welcome.
> 
> 
> > * In new_heap(), you initialize all the pointers to NULL, but calloc()
> > already initializes the whole buffer to zero, so this is not needed.
> 
> Yes.
> 
> > * 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'ts a good idea, so there musn't be to make the timer_id managment, and it's 
> e
> 
> > Nice job!! See you soon.
> 
> Thanks.
> 
> Bye
> 
> --
> Matías Aguirre
> 


-- 
Matías Aguirre