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

Re: [PATCH v4 02/14] add a hashtable implementation that supports O(1) removal

From
Philip Oakley <philipoakley@iee.org>
Date
Nov 8, 2013, 14:13 UTC
Message-ID
<2BEA8A50DFB9411BA89CAB9236687F5B@PhilipOakley>
In-Reply-To
<527CBC8E.6050507@gmail.com>
From: "Karsten Blees" <karsten.blees@gmail.com>
Show 8 quoted lines
> However, defining the constants inversely is a bit unintuitive (i.e. 
> 1.25 instead of 0.8, 6 instead of 0.166). Perhaps the thresholds 
> should also be calculated once on resize, not on every add / remove.
>
> What about this:
>
> #define HASHMAP_GROW_AT 80
> #define HASHMAP_SHRINK_AT 16
mico-bikeshed adding a code comment...
 #define HASHMAP_GROW_AT 80    /* percent */
 #define HASHMAP_SHRINK_AT 16    /* percent */
Show 8 quoted lines
>
> ...in rehash:
>
> map->grow_at = (unsigned int)((uint64_t) map->tablesize * 
> HASHMAP_GROW_AT / 100);
> map->shrink_at = (unsigned int)((uint64_t) map->tablesize * 
> HASHMAP_SHRINK_AT / 100);
>
[No need to add to cc...]
regards
Philip 
Previous: Karsten BleesNext: Junio C Hamano
Message 7 of 26 in “New hash table implementation”
  1. 00/14 New hash table implementationKarsten Blees, Nov 7, 2013
  2. 01/14 submodule: don't access the .gitmodules cache entry after removing itKarsten Blees, Nov 7, 2013
  3. Heiko VoigtNov 7, 2013
  4. 02/14 add a hashtable implementation that supports O(1) removalKarsten Blees, Nov 7, 2013
  5. Junio C HamanoNov 7, 2013
  6. Karsten BleesNov 8, 2013
  7. Philip OakleyNov 8, 2013
  8. Junio C HamanoNov 8, 2013
  9. Karsten BleesNov 13, 2013
  10. 03/14 buitin/describe.c: use new hash map implementationKarsten Blees, Nov 7, 2013
  11. 04/14 diffcore-rename.c: move code around to prepare for the next patchKarsten Blees, Nov 7, 2013
  12. 05/14 diffcore-rename.c: simplify finding exact renamesKarsten Blees, Nov 7, 2013
  13. 06/14 diffcore-rename.c: use new hash map implementationKarsten Blees, Nov 7, 2013
  14. 07/14 name-hash.c: use new hash map implementation for directoriesKarsten Blees, Nov 7, 2013
  15. 08/14 name-hash.c: remove unreferenced directory entriesKarsten Blees, Nov 7, 2013
  16. 09/14 name-hash.c: use new hash map implementation for cache entriesKarsten Blees, Nov 7, 2013
  17. 10/14 name-hash.c: remove cache entries instead of marking them CE_UNHASHEDKarsten Blees, Nov 7, 2013
  18. 11/14 remove old hash.[ch] implementationKarsten Blees, Nov 7, 2013
  19. 12/14 fix 'git update-index --verbose --again' outputKarsten Blees, Nov 7, 2013
  20. Junio C HamanoNov 7, 2013
  21. Karsten BleesNov 8, 2013
  22. 13/14 builtin/update-index.c: cleanup update_oneKarsten Blees, Nov 7, 2013
  23. Junio C HamanoNov 7, 2013
  24. Karsten BleesNov 8, 2013
  25. 14/14 read-cache.c: fix memory leaks caused by removed cache entriesKarsten Blees, Nov 7, 2013
  26. Junio C HamanoNov 7, 2013

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.