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? > >>> 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
