Hi Jonathan, Jonathan Nieder <jrnieder@xxxxxxxxx> wrote: > From: Jason Evans <jasone@xxxxxxxxxxxxx> > > Treaps provide a memory-efficient binary search tree structure. > Insertion/deletion/search are about as about as fast in the average > case as red-black trees and the chances of worst-case behavior are > vanishingly small, thanks to (pseudo-)randomness. That is a small > price to pay, given that treaps are much simpler to implement. > > [db: Altered to reference nodes by offset from a common base pointer] > [db: Bob Jenkins' hashing implementation dropped for Knuth's] > [db: Methods unnecessary for search and insert dropped] > > Signed-off-by: David Barr <david.barr@xxxxxxxxxxxx> > Signed-off-by: Ramkumar Ramachandra <artagnon@xxxxxxxxx> Thanks. This can go into the commit message when I re-send the series. > I don’t know if style nitpicking is welcome here, given that the > code comes from elsewhere. Should we be trying to keep the code > close to Jason’s version (and sending patches upstream as needed), > or is that not worth the trouble? In my opinion, style nitpicks are welcome: it should conform to the git.git style. I'm anyway maintaining a separate branch of master just for changes specific to the git.git merge- Jason and David are welcome to pull patches from there. > #include "../git-compat-util.h" would be more portable. Right, this should be one major change in all the files in the git-merge branch. > These are defined in obj_pool.h? Maybe this would be easier to > understand if the patch to add that file came sooner in the series. Okay. Note that in the revision history, trp.h was first imported, and then culled to use obj_pool.h by David. > Where does this magic number come from? (I assume Knuth, but it > would be nice to include a reference or explanation.) Indeed. 2654435761 is the golden ratio number corresponding with 2^32. See http://bit.ly/cwAfD4 > Neat. Maybe this description should go in a file in > Documentation/technical, to make trp.h itself a little less daunting. Okay, I'll put it in a separate file then. > Also: http://www.canonware.com/trp/ seems to provide a test program; > do you think it would make sense to include it as well? Probably in documentation/technical? > [1] http://t-t-travails.blogspot.com/2008/07/treaps-versus-red-black-trees.html This is a good read, thanks. -- Ram -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html