{"thread":{"id":"3312","subject":"Fix object re-hashing","startedAt":"2006-02-12T18:04:26Z","lastAt":"2006-02-13T00:31:23Z","messageCount":13,"participants":["Linus Torvalds","Junio C Hamano","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"15978","messageId":"Pine.LNX.4.64.0602120956130.3691@g5.osdl.org","threadId":"3312","inReplyTo":null,"subject":"Fix object re-hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-12T18:04:26Z","receivedAt":"2006-02-12T18:04:26Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThe hashed object lookup had a subtle bug in re-hashing: it did\n\n\tfor (i = 0; i < count; i++)\n\t\tif (objs[i]) {\n\t\t\t.. rehash ..\n\nwhere \"count\" was the old hash couny. Oon the face of it is obvious, since \nit clearly re-hashes all the old objects.\n\nHowever, it's wrong.\n\nIf the last old hash entry before re-hashing was in use (or became in use \nby the re-hashing), then when re-hashing could have inserted an object \ninto the hash entries with idx >= count due to overflow. When we then \nrehash the last old entry, that old entry might become empty, which means \nthat the overflow entries should be re-hashed again.\n\nIn other words, the loop has to be fixed to either traverse the whole \narray, rather than just the old count.\n\n(There's room for a slight optimization: instead of counting all the way \nup, we can break when we see the first empty slot that is above the old \n\"count\". At that point we know we don't have any collissions that we might \nhave to fix up any more. This patch only does the trivial fix)\n\nSigned-off-by: Linus Torvalds \n---\n\nI actually didn't see any of this trigger in real life, so maybe my \nanalysis is wrong. Junio? Johannes?\n\ndiff --git a/object.c b/object.c\nindex 59e5e36..aeda228 100644\n--- a/object.c\n+++ b/object.c\n@@ -65,7 +65,7 @@ void created_object(const unsigned char \n \t\tobjs = xrealloc(objs, obj_allocs * sizeof(struct object *));\n \t\tmemset(objs + count, 0, (obj_allocs - count)\n \t\t\t\t* sizeof(struct object *));\n-\t\tfor (i = 0; i < count; i++)\n+\t\tfor (i = 0; obj_allocs ; i++)\n \t\t\tif (objs[i]) {\n \t\t\t\tint j = find_object(objs[i]->sha1);\n \t\t\t\tif (j != i) {\n"},{"id":"15980","messageId":"Pine.LNX.4.64.0602121006360.3691@g5.osdl.org","threadId":"3312","inReplyTo":"Pine.LNX.4.64.0602120956130.3691@g5.osdl.org","subject":"Re: Fix object re-hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-12T18:10:02Z","receivedAt":"2006-02-12T18:10:02Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Feb 2006, Linus Torvalds wrote:\n> \n> I actually didn't see any of this trigger in real life, so maybe my \n> analysis is wrong. Junio? Johannes?\n\nBtw, if it does trigger, the behaviour would be that a subsequent object \nlookup will fail, because the last old slot would be NULL, and a few \nentries following it (likely just a couple - never mind that the event \ntriggering in the first place is probably fairly rare) wouldn't have \ngotten re-hashed down.\n\nAs a result, we'd allocate a new object, and have _two_ \"struct object\"s \nthat describe the same real object. I don't know what would get upset, but \ngit-fsck-index certainly would be (one of them would likely be marked \nunreachable, because lookup wouldn't find it, but you might have other \nissues too).\n\n\t\t\tLinus\n"},{"id":"15981","messageId":"Pine.LNX.4.64.0602121015020.3691@g5.osdl.org","threadId":"3312","inReplyTo":"Pine.LNX.4.64.0602120956130.3691@g5.osdl.org","subject":"Re: Fix object re-hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-12T18:16:46Z","receivedAt":"2006-02-12T18:16:46Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Feb 2006, Linus Torvalds wrote:\n> -\t\tfor (i = 0; i < count; i++)\n> +\t\tfor (i = 0; obj_allocs ; i++)\n\nGAAH. \n\nThat should obviously be \"i < obj_allocs\".\n\nThat's what I get for editing the patch in-place to remove the optimized \nversion that I felt wasn't worth worrying about due to being subtle. So \ninstead I sent out a patch that was not-so-subtly obvious crap!\n\nSorry about that.\n\n\t\tLinus\n"},{"id":"15982","messageId":"Pine.LNX.4.64.0602121017290.3691@g5.osdl.org","threadId":"3312","inReplyTo":"Pine.LNX.4.64.0602121015020.3691@g5.osdl.org","subject":"Re: Fix object re-hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-12T18:18:47Z","receivedAt":"2006-02-12T18:18:47Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Feb 2006, Linus Torvalds wrote:\n> \n> That's what I get for editing the patch in-place to remove the optimized \n> version that I felt wasn't worth worrying about due to being subtle. So \n> instead I sent out a patch that was not-so-subtly obvious crap!\n\nBtw: the reason I edited out the optimization is that it doesn't actually \nmatter. Re-hashing the whole thing is a trivial thing, and has basically \nzero overhead in my testing. The costs are all elsewhere now.\n\n\t\tLinus\n"},{"id":"15983","messageId":"7vaccwbf6v.fsf@assigned-by-dhcp.cox.net","threadId":"3312","inReplyTo":"Pine.LNX.4.64.0602121006360.3691@g5.osdl.org","subject":"Re: Fix object re-hashing","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-12T18:32:56Z","receivedAt":"2006-02-12T18:32:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Sun, 12 Feb 2006, Linus Torvalds wrote:\n>> \n>> I actually didn't see any of this trigger in real life, so maybe my \n>> analysis is wrong. Junio? Johannes?\n>\n> Btw, if it does trigger, the behaviour would be that a subsequent object \n> lookup will fail, because the last old slot would be NULL, and a few \n> entries following it (likely just a couple - never mind that the event \n> triggering in the first place is probably fairly rare) wouldn't have \n> gotten re-hashed down.\n>\n> As a result, we'd allocate a new object, and have _two_ \"struct object\"s \n> that describe the same real object. I don't know what would get upset, but \n> git-fsck-index certainly would be (one of them would likely be marked \n> unreachable, because lookup wouldn't find it, but you might have other \n> issues too).\n\nThis \"fix\" makes the symptom that me fire two (maybe three)\nGrrrrr messages earlier this morning disappear. I haven't had\nmy caffeine nor nicotine yet after my short sleep, so I need to\ntake some time understanding your explanation first, but I am\nreasonably sure this must be it (not that I do not trust you,\nnot at all -- it is that I do not trust *me* applying a patch\nwithout understanding when I have a bug reproducible).\n\nThanks.\n"},{"id":"15985","messageId":"Pine.LNX.4.64.0602121037460.3691@g5.osdl.org","threadId":"3312","inReplyTo":"7vaccwbf6v.fsf@assigned-by-dhcp.cox.net","subject":"Re: Fix object re-hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-12T18:53:18Z","receivedAt":"2006-02-12T18:53:18Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Feb 2006, Junio C Hamano wrote:\n> \n> This \"fix\" makes the symptom that me fire two (maybe three)\n> Grrrrr messages earlier this morning disappear.\n\nGoodie. I assume that was the fixed fix, not my original \"edit out the \nuseless optimization and then break it totally\" fix ;)\n\n> I haven't had my caffeine nor nicotine yet after my short sleep, so I \n> need to take some time understanding your explanation first, but I am \n> reasonably sure this must be it (not that I do not trust you, not at all \n> -- it is that I do not trust *me* applying a patch without understanding \n> when I have a bug reproducible).\n\nThe basic notion is that this hashing algorithm uses a normal \"linear \nprobing\" overflow approach, which basically means that overflows in \na hash bucket always just probe the next few buckets to find an empty one.\n\nThat's a really simple (and fairly cache-friendly) approach, and it makes \ntons of sense, especially since we always re-size the hash to guarantee \nthat we'll have empty slots. It's a bit more subtle - especially when \nre-hashing - than the probably more common \"collission chain\" approach, \nthough.\n\nNow, when we re-hash, the important rule is:\n\n - the re-hashing has to walk in the same direction as the overflow.\n\nThis is important, because when we move a hashed entry, that automatically \nmeans that even otherwise _already_correctly_ hashed entries may need to \nbe moved down (ie even if their \"inherent hash\" does not change, their \n_effective_ hash address changes because their overflow position needs to \nbe fixed up).\n\nThere are two interesting cases:\n\n - the \"overflow of the overflow\": when the linear probing itself \n overflows the size of the hash queue, it will \"change direction\" by \n overflowing back to index zero.\n\n Happily, the re-hashing does not need to care about this case, because \n the new hash is bigger: the rule we have when doing the re-hashing is \n that as we re-hash, the \"i\" entries we have already re-hashed are all \n valid in the new hash, so even if overflow occurs, it will occur the \n right way (and if it overflows all the way past the current \"i\", we'll \n re-hash the already re-hashed entry anyway).\n\n - the old/new border case. In particular, the trivial logic says that we \n only need to re-hash entries that were hashed with the old hash. That's \n what the broken code did: it only traversed \"0..oldcount-1\", because \n any entries that had an index bigger than or equal to \"oldcount\" were \n obviously _already_ re-hashed.\n\n That logic sounds obvious, but it falls down on exactly the fact that \n we may indeed have to re-hash even entries that already were re-hashed \n with the new algorithm, exactly because of the overflow changes.\n\nSo the boundary for old/new is really: \"you need to rehash all entries \nthat were old, but then you _also_ need to rehash the list of entries that \nyou rehashed that might need to be moved down to an empty spot vacated by \nan old hash\".\n\nSo the stop condition really ends up being: \"stop when you have seen all \nold hash entries _and_ at least one empty entry after that\", since an \nempty entry means that there was no overflow from earlier positions past \nthat position. But it's just simpler to walk the whole damn new thing and \nnot worry about it.\n\n\t\tLinus\n"},{"id":"15987","messageId":"Pine.LNX.4.64.0602121101040.3691@g5.osdl.org","threadId":"3312","inReplyTo":"Pine.LNX.4.64.0602121037460.3691@g5.osdl.org","subject":"Re: Fix object re-hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-12T19:10:11Z","receivedAt":"2006-02-12T19:10:11Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Feb 2006, Linus Torvalds wrote:\n> \n> - the \"overflow of the overflow\": when the linear probing itself \n> overflows the size of the hash queue, it will \"change direction\" by \n> overflowing back to index zero.\n> \n> Happily, the re-hashing does not need to care about this case, because \n> the new hash is bigger: the rule we have when doing the re-hashing is \n> that as we re-hash, the \"i\" entries we have already re-hashed are all \n> valid in the new hash, so even if overflow occurs, it will occur the \n> right way (and if it overflows all the way past the current \"i\", we'll \n> re-hash the already re-hashed entry anyway).\n\nBtw, this is only always true if the new hash is at least twice the size \nof the old hash, I think. Otherwise a re-hash can fill up the new entries \nand overflow entirely before we've actually even re-hashed all the old \nentries, and then we'd need to re-hash even the overflowed entries (which \nare now below \"i\").\n\nIf the new size is at least twice the old size, the \"upper area\" cannot \noverflow completely (there has to be empty room), and we cannot be in the \nsituation that we need to move even the overflowed entries when we remove \nan old hash entry.\n\nAnyway, if all this makes you nervous, the conceptually much simpler way \nto do the re-sizing is to not do the in-place re-hashing. Instead of doing \nthe xrealloc(), just do a \"xmalloc()\" of the new area, do the re-hashing \n(which now _must_ re-hash in just the \"0..oldcount-1\" old area) into the \nnew area, and then free the old area after rehashing.\n\nThat would make things more obviously correct, and perhaps simpler.\n\nJohannes, do you want to try that?\n\nBtw, as it currently stands, I worry a tiny tiny bit about the\n\n\tobj_allocs = (obj_allocs < 32 ? 32 : 2 * obj_allocs)\n\nthing, because I think that second \"32\" needs to be a \"64\" to be really \nsafe (ie guarantee that the new obj_allocs value is always at least twice \nthe old one).\n\nAnyway, I'm pretty sure people smarter than me have already codified \nexactly what needs to be done for a in-place rehash of a linear probe hash \noverflow algorithm. This must all be in some \"hashing 101\" book. I had to \nthink it through from first principles rather than \"knowing\" what the \nright answer was (which probably means that I slept through some \nfundamental algorithms class in University ;)\n\n\t\tLinus\n"},{"id":"15988","messageId":"7vpsls9yq0.fsf@assigned-by-dhcp.cox.net","threadId":"3312","inReplyTo":"Pine.LNX.4.64.0602121037460.3691@g5.osdl.org","subject":"Re: Fix object re-hashing","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-12T19:13:59Z","receivedAt":"2006-02-12T19:13:59Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Sun, 12 Feb 2006, Junio C Hamano wrote:\n>> \n>> This \"fix\" makes the symptom that me fire two (maybe three)\n>> Grrrrr messages earlier this morning disappear.\n>\n> Goodie. I assume that was the fixed fix, not my original \"edit out the \n> useless optimization and then break it totally\" fix ;)\n>\n>> I haven't had my caffeine nor nicotine yet after my short sleep, so I \n>> need to take some time understanding your explanation first, but I am \n>> reasonably sure this must be it (not that I do not trust you, not at all \n>> -- it is that I do not trust *me* applying a patch without understanding \n>> when I have a bug reproducible).\n\nYour explanation finally made sense to me, without caffeine nor\nnicotine yet, but when I tried to do an illustration.\n\nIf the initial obj_allocs were 4 instead of 32, we may have\nsomething lie this before rehashing.\n\nslot value\n 0 3\n 1 -\n 2 -\n 3 7\n\nRehash to double the hash goes like this:\n\n step1 step2 step3 fixup rehash\n enlarge rehash rehash missing from\n array \"3%8\" \"7%8\" the original\n 0 3 - - -\n 1 - - - -\n 2 - - - -\n 3 7 7 - 3\n 4 - 3 3 -\n 5 - - - -\n 6 - - - -\n 7 - - 7 7\n\nWe cannot find \"3%8\" without the fix.\n\nThanks for the fix. Will do an updated \"master\" soon.\n"},{"id":"15989","messageId":"7vlkwg9ye0.fsf@assigned-by-dhcp.cox.net","threadId":"3312","inReplyTo":"Pine.LNX.4.64.0602121101040.3691@g5.osdl.org","subject":"Re: Fix object re-hashing","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-12T19:21:11Z","receivedAt":"2006-02-12T19:21:11Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Anyway, if all this makes you nervous,...\n\nI did draw an illustration like the one I sent in my previous\nmessage when I received the first patch from Johannes, and it was\nreasonably obvious to me that it was meant to redistribute about\nhalf of the existing entries to the upper area, always going\nupwards, so modulo that wraparound corner case you fixed, I\nthink doubling is fine.\n\n> Btw, as it currently stands, I worry a tiny tiny bit about the\n>\n> \tobj_allocs = (obj_allocs < 32 ? 32 : 2 * obj_allocs)\n>\n> thing, because I think that second \"32\" needs to be a \"64\" to be really \n> safe (ie guarantee that the new obj_allocs value is always at least twice \n> the old one).\n\nobj_allocs starts out as 0 so the first value it gets is 32 when\nyou need to insert the first element.\n"},{"id":"15991","messageId":"Pine.LNX.4.64.0602121137330.3691@g5.osdl.org","threadId":"3312","inReplyTo":"7vlkwg9ye0.fsf@assigned-by-dhcp.cox.net","subject":"Re: Fix object re-hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-12T19:39:58Z","receivedAt":"2006-02-12T19:39:58Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Feb 2006, Junio C Hamano wrote:\n> \n> > Btw, as it currently stands, I worry a tiny tiny bit about the\n> >\n> > \tobj_allocs = (obj_allocs < 32 ? 32 : 2 * obj_allocs)\n> >\n> > thing, because I think that second \"32\" needs to be a \"64\" to be really \n> > safe (ie guarantee that the new obj_allocs value is always at least twice \n> > the old one).\n> \n> obj_allocs starts out as 0 so the first value it gets is 32 when\n> you need to insert the first element.\n\nYes. The point being that the code is \"conceptually wrong\", not that it \ndoesn't work in practice. If we somehow could get into the situation that \nwe had a hash size of 31, resizing it to 32 would be incorrect.\n\nOf course, if we just make it a rule that the hash size must always be a \npower-of-two (add a comment, and enforce the rule by changing the modulus \ninto a bitwise \"and\"), then that issue too goes away.\n\n\t\t\tLinus\n"},{"id":"16003","messageId":"Pine.LNX.4.63.0602130007320.9507@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"3312","inReplyTo":"Pine.LNX.4.64.0602121101040.3691@g5.osdl.org","subject":"Re: Fix object re-hashing","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-02-12T23:55:40Z","receivedAt":"2006-02-12T23:55:40Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 12 Feb 2006, Linus Torvalds wrote:\n\n> [something about the overflow in another mail]\n\nThank you for thinking it through! I was soooo stuck with my original \nidea: Ideally (i.e. if there are no collisions), if the hashtable is \ndoubled in size, then each offset should either stay the same, or be just \nincremented by the original size (since the index is the hash modulo the \nhashtable size).\n\nSo I wanted to be clever about resizing, and just increment the offset if \nnecessary. As it turns out, it's more complicated than that. You have to \nmake sure that those entries which collided with another entry, but do no \nlonger, are adjusted appropriately.\n\nAnd the overflow problem eluded my attention entirely. (I feel quite silly \nabout it, because I fixed so many buffer-overflow problems myself, and \nthe cause of the problem is the same there.)\n\n> On Sun, 12 Feb 2006, Linus Torvalds wrote:\n> > \n> > - the \"overflow of the overflow\": when the linear probing itself \n> > overflows the size of the hash queue, it will \"change direction\" by \n> > overflowing back to index zero.\n> > \n> > Happily, the re-hashing does not need to care about this case, because \n> > the new hash is bigger: the rule we have when doing the re-hashing is \n> > that as we re-hash, the \"i\" entries we have already re-hashed are all \n> > valid in the new hash, so even if overflow occurs, it will occur the \n> > right way (and if it overflows all the way past the current \"i\", we'll \n> > re-hash the already re-hashed entry anyway).\n> \n> Btw, this is only always true if the new hash is at least twice the size \n> of the old hash, I think. Otherwise a re-hash can fill up the new entries \n> and overflow entirely before we've actually even re-hashed all the old \n> entries, and then we'd need to re-hash even the overflowed entries (which \n> are now below \"i\").\n\nAfter thinking long and hard about it, I tend to agree.\n\nNote: I chose the factor 2 because hashtables tend to have *awful* \nperformance when space becomes scarce. So, 2 is not only a wise choice for \nrehashing, but for the operation in general.\n\n> Anyway, if all this makes you nervous, the conceptually much simpler way \n> to do the re-sizing is to not do the in-place re-hashing. Instead of doing \n> the xrealloc(), just do a \"xmalloc()\" of the new area, do the re-hashing \n> (which now _must_ re-hash in just the \"0..oldcount-1\" old area) into the \n> new area, and then free the old area after rehashing.\n> \n> That would make things more obviously correct, and perhaps simpler.\n> \n> Johannes, do you want to try that?\n\nI do not particularly like it, since doubling the hashtable size is not \nparticularly space efficient, and this makes it worse. Anyway, see below.\n\n> Btw, as it currently stands, I worry a tiny tiny bit about the\n> \n> \tobj_allocs = (obj_allocs < 32 ? 32 : 2 * obj_allocs)\n> \n> thing, because I think that second \"32\" needs to be a \"64\" to be really \n> safe (ie guarantee that the new obj_allocs value is always at least twice \n> the old one).\n\nAs Junio already pointed out: obj_allocs is initially set to 0. But you're \nright, it is conceptually wrong.\n\n> Anyway, I'm pretty sure people smarter than me have already codified \n> exactly what needs to be done for a in-place rehash of a linear probe hash \n> overflow algorithm. This must all be in some \"hashing 101\" book. I had to \n> think it through from first principles rather than \"knowing\" what the \n> right answer was (which probably means that I slept through some \n> fundamental algorithms class in University ;)\n\nWell, it seems like a long time, doesn't it? But I always liked the \nFibonacci numbers, and therefore the Fibonacci heap.\n\n---\n\nMake hashtable resizing more robust AKA do not resize in-place\n\ndiff --git a/object.c b/object.c\nindex c9ca481..94f0f5d 100644\n--- a/object.c\n+++ b/object.c\n@@ -56,18 +56,14 @@ void created_object(const unsigned char \n \n \tif (obj_allocs - 1 <= nr_objs * 2) {\n \t\tint i, count = obj_allocs;\n-\t\tobj_allocs = (obj_allocs < 32 ? 32 : 2 * obj_allocs);\n-\t\tobjs = xrealloc(objs, obj_allocs * sizeof(struct object *));\n-\t\tmemset(objs + count, 0, (obj_allocs - count)\n-\t\t\t\t* sizeof(struct object *));\n-\t\tfor (i = 0; i < obj_allocs; i++)\n-\t\t\tif (objs[i]) {\n-\t\t\t\tint j = find_object(objs[i]->sha1);\n-\t\t\t\tif (j != i) {\n-\t\t\t\t\tj = -1 - j;\n-\t\t\t\t\tobjs[j] = objs[i];\n-\t\t\t\t\tobjs[i] = NULL;\n-\t\t\t\t}\n+\t\tstruct object** old_objs = objs;\n+\t\tobj_allocs = (obj_allocs < 32 ? 64 : 2 * obj_allocs);\n+\t\tobjs = xcalloc(obj_allocs, sizeof(struct object *));\n+\t\tfor (i = 0; i < count; i++)\n+\t\t\tif (old_objs[i]) {\n+\t\t\t\t/* it is guaranteed to be new */\n+\t\t\t\tint j = -1 - find_object(old_objs[i]->sha1);\n+\t\t\t\tobjs[j] = old_objs[i];\n \t\t\t}\n \t}\n \n"},{"id":"16005","messageId":"Pine.LNX.4.64.0602121614340.3691@g5.osdl.org","threadId":"3312","inReplyTo":"Pine.LNX.4.63.0602130007320.9507@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: Fix object re-hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-13T00:16:17Z","receivedAt":"2006-02-13T00:16:17Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 13 Feb 2006, Johannes Schindelin wrote:\n> \n> Make hashtable resizing more robust AKA do not resize in-place\n\nYou forgot to release the old array afterwards.\n\nAnyway, I think the in-place version is fine now, even if it has a few \nsubtleties. So this isn't needed, but keep it in mind if we find another \nbug, or if somebody wants to shrink the hash table less aggressively than \nwith doubling it every time.\n\n\t\tLinus\n"},{"id":"16007","messageId":"Pine.LNX.4.63.0602130130360.22638@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"3312","inReplyTo":"Pine.LNX.4.64.0602121614340.3691@g5.osdl.org","subject":"Re: Fix object re-hashing","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-02-13T00:31:23Z","receivedAt":"2006-02-13T00:31:23Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 12 Feb 2006, Linus Torvalds wrote:\n\n> On Mon, 13 Feb 2006, Johannes Schindelin wrote:\n> > \n> > Make hashtable resizing more robust AKA do not resize in-place\n> \n> You forgot to release the old array afterwards.\n\nD'oh! I am going to bed now.\n\n> Anyway, I think the in-place version is fine now, even if it has a few \n> subtleties. So this isn't needed, but keep it in mind if we find another \n> bug, or if somebody wants to shrink the hash table less aggressively than \n> with doubling it every time.\n\nSounds fine to me.\n\nGood night,\nDscho\n"}]}