git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 5/6] Do linear-time/space rename logic for exact renames

From
Daniel Barkalow <barkalow@iabervon.org>
Date
Oct 25, 2007, 21:37 UTC
Message-ID
<Pine.LNX.4.64.0710251722290.7345@iabervon.org>
In-Reply-To
<alpine.LFD.0.999.0710251317020.30120@woody.linux-foundation.org>
On Thu, 25 Oct 2007, Linus Torvalds wrote:
Show 12 quoted lines
> On Thu, 25 Oct 2007, Daniel Barkalow wrote:
> > 
> > Creating a list of the pointers doesn't work correctly with the grow 
> > implementation, because growing the hash may turn a collision into a 
> > non-collision, at which point items other than the first cannot be found 
> > (since they're listed inside a bucket that's now wrong for them). AFAIK, 
> > resizing a hash table requires being able to figure out what happened with 
> > collisions.
> 
> Nope. 
> 
> The hash algorithm is much smarter than that.

Ah, yes. I was just confused by the comment suggesting the possibility of a collision when the only way to have two calls get the same bucket is when the key that the library gets is actually identical.

	-Daniel
*This .sig left intentionally blank*
Previous: Linus TorvaldsNext: Linus Torvalds
Message 15 of 18 in “Cleaned-up rename detection patch-series”
  1. 0/6 Cleaned-up rename detection patch-seriesLinus Torvalds, Oct 25, 2007
  2. 1/6 Add 'diffcore.h' to LIB_HLinus Torvalds, Oct 25, 2007
  3. 2/6 Split out "exact content match" phase of rename detectionLinus Torvalds, Oct 25, 2007
  4. 3/6 Ref-count the filespecs used by diffcoreLinus Torvalds, Oct 25, 2007
  5. 4/6 copy vs rename detection: avoid unnecessary O(n*m) loopsLinus Torvalds, Oct 25, 2007
  6. Junio C HamanoOct 26, 2007
  7. Linus TorvaldsOct 26, 2007
  8. Junio C HamanoOct 26, 2007
  9. Linus TorvaldsOct 26, 2007
  10. 5/6 Do linear-time/space rename logic for exact renamesLinus Torvalds, Oct 25, 2007
  11. Daniel BarkalowOct 25, 2007
  12. Jeff KingOct 25, 2007
  13. Daniel BarkalowOct 25, 2007
  14. Linus TorvaldsOct 25, 2007
  15. Daniel BarkalowOct 25, 2007
  16. 6/6 Do exact rename detection regardless of rename limitsLinus Torvalds, Oct 25, 2007
  17. Linus TorvaldsOct 25, 2007
  18. Jeff KingOct 25, 2007

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.