Padraig O'Sullivan wrote: > On Tue, Feb 17, 2009 at 8:32 PM, Monty Taylor <[email protected]> wrote: >> Padraig O'Sullivan wrote: >>> On Tue, Feb 17, 2009 at 4:43 PM, Monty Taylor <[email protected]> wrote: >>>> Padraig O'Sullivan wrote: >>>>> On Tue, Feb 17, 2009 at 3:22 PM, Monty Taylor <[email protected]> wrote: >>>>>> Hey Padraig, >>>>>> >>>>>> I think you're moving in the right direction so far. Some things to >>>>>> think about: >>>>>> >>>>>> Perhaps if you did: >>>>>> >>>>>> class buffpek_compare >>>>>> { >>>>>> qsort_cmp2 key_compare; >>>>>> void *key_compare_arg; >>>>>> >>>>>> public: >>>>>> buffpek_compare(qsort_cmp2 in_key_compare, void* in_compare_arg) >>>>>> : key_compare(in_key_compare), key_compare_arg(in_compare_arg) { } >>>>>> inline bool operator()(BUFFPEK *i, BUFFPEK *j) >>>>>> { >>>>>> return key_compare(key_compare_arg, >>>>>> *((unsigned char **) i->key), *((unsigned >>>>>> char **) j->key)); >>>>>> } >>>>>> }; >>>>>> >>>>>> instead, you could remove the need for the extra Context struct, since >>>>>> your function object has its own way to store context. >>>>> heh, that's interesting. I actually started moving towards the above >>>>> last night when I was working on this some more. >>>>> >>>>>> The next step being to get rid of buffpek_compare all together and >>>>>> replace the qsort_cmp2 that's passed in with a function object itself >>>>>> which could be directly handed to std::sort() or to priority_queue as >>>>>> its sort function param. >>>>>> >>>>>> resuse_freed_buff() looks more like memory management "cleverness" that >>>>>> would be unneeded if you used priority_queue in the first place. It >>>>>> sounds like you're guessing the same thing already - but good choice to >>>>>> take it slow and deal with it piece by piece. >>>>> I've really been wanting to use a priority queue here as you said. The >>>>> one thing stopping me at the moment is the reuse_freed_buff() >>>>> function. I had guessed that the function was moving memory from an >>>>> element that has just been removed from the queue to other elements >>>>> still in the queue but I wasn't sure. Is that roughly what it does? >>>>> >>>>> If you think that reuse_freed_buff() will be un-needed if I switch to >>>>> a priority queue here then I might just start on that tonight. It >>>>> should be pretty straightforward to change what I have done now to use >>>>> a priority queue instead. Sound like a good idea? >>>> Do it. It sounds like the reuse_freed_buff() is trying to do the same >>>> thing that the remove_if() algorithm does for vectors... but I think >>>> we're better off not doing this by hand once we've got priority_queue >>>> managing that behind the scenes. >>> I have this done now but there is one thing I want to be sure of. So >>> the QUEUE in the current implementation is a queue of structures >>> (BUFFPEK) sorted on a key. A few times in the current code, a re-heap >>> is explicitly called on the queue - this happens when the key is >>> changed. The question I have is when does the STL implementation of >>> priority queue re-heap itself? >>> >>> For example, in the current implementation, there is a piece of code like >>> this: >>> >>> top= (BUFFPEK *) queue_top(&queue); >>> ... >>> /* >>> read next key from the cache or from the file and push it to the >>> queue; this gives new top. >>> */ >>> top->key+= key_length; >>> if (--top->mem_count) >>> queue_replaced(&queue); >>> >>> Will the STL implementation of priority queue re-heap itself after the >>> key is changed here? Or does it only re-heap itself after elements are >>> inserted and removed? >> If you change the struct that an element of the priority queue is >> pointing to, it will not, AIUI, re-heap. > > Yeah, you're right. I threw together a simple test case which exhibits > this behavior i.e. an element of the priority queue changes but the > priority queue does not re-heap. > > This means I need to think a bit more and make sure the semantics of > merge_walk() are still correct when I replace QUEUE with priority > queue. By the way, if I had to re-heap a priority queue here, is there > a preferred method of doing that?
Not really. On the other hand - if the element in the queue has fundamentally changed, is the priority_queue really the right thing to manage those objects? I'd say no. OTOH, if you take your code from above and make it: top= queue.pop(); /* read next key from the cache or from the file and push it to the queue; this gives new top. */ top->key+= key_length; if (--top->mem_count) queue.push(top); Then it should work, no? >> Perhaps: >> http://www.cplusplus.com/reference/stl/priority_queue/push.html >> and then >> http://www.cplusplus.com/reference/algorithm/push_heap.html >> >> May give more details ...(in case I'm not reading your question correctly) >> >> Monyt >> >>>>>> Where was the tree you had the changes in again? >>>>> Its in lp:~posulliv/drizzle/code-cleanup-c++-replace-queue but I >>>>> havn't pushed my changes to it yet. I've been committing everything I >>>>> do to my local branch so I'll probably push it to launchpad when I get >>>>> things a little more cleaned up and am more confident in what I've >>>>> done. >>>> Let me know when it's in decent shape and I'll run some performance >>>> diffs on it. >>>> >>>>> Thanks for your input and taking the time to look at what I wrote! >>>> Thanks for the work. >>>> >>>> Monty >>>> >>>> >> > _______________________________________________ Mailing list: https://launchpad.net/~drizzle-discuss Post to : [email protected] Unsubscribe : https://launchpad.net/~drizzle-discuss More help : https://help.launchpad.net/ListHelp
