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

Re: [PATCH 1/8] implement generic key/value map

From
Junio C Hamano <gitster@pobox.com>
Date
Aug 4, 2012, 22:58 UTC
Message-ID
<7vehnm8dbv.fsf@alter.siamese.dyndns.org>
In-Reply-To
<20120804171038.GA19378@sigill.intra.peff.net>
Jeff King <peff@peff.net> writes:
Show 14 quoted lines
> It is frequently useful to have a fast, generic data
> structure mapping keys to values. We already have something
> like this in the "decorate" API, but it has two downsides:
>
>   1. The key type must always be a "struct object *".
>
>   2. The value type is a void pointer, which means it is
>      inefficient and cumbersome for storing small values.
>      One must either encode their value inside the void
>      pointer, or allocate additional storage for the pointer
>      to point to.
>
> This patch introduces a generic map data structure, mapping
> keys of arbitrary type to values of arbitrary type.

Does the type of keys in a map have to be of the same size, or can a key of a type with variable size (e.g. struct with a flex member at the end)? Same question for the type of values.

Is the type of keys in a map required to have a total order over it, or is it suffice only to have equality defined?

The latter might matter once we start talking about a huge map that we may not want to hold in-core.

Previous: Jeff KingNext: Jeff King
Message 24 of 35 in “Manual rename correction”
  1. Manual rename correctionNguyen Thai Ngoc Duy, Jul 31, 2012
  2. Junio C HamanoJul 31, 2012
  3. Jeff KingJul 31, 2012
  4. Junio C HamanoJul 31, 2012
  5. Jeff KingAug 1, 2012
  6. Junio C HamanoAug 1, 2012
  7. Jeff KingAug 1, 2012
  8. Junio C HamanoAug 1, 2012
  9. Jeff KingAug 2, 2012
  10. Junio C HamanoAug 2, 2012
  11. Jeff KingAug 2, 2012
  12. Junio C HamanoAug 2, 2012
  13. Nguyen Thai Ngoc DuyAug 1, 2012
  14. Jeff KingAug 1, 2012
  15. Nguyen Thai Ngoc DuyAug 1, 2012
  16. Junio C HamanoAug 1, 2012
  17. Nguyen Thai Ngoc DuyAug 1, 2012
  18. Jeff KingAug 1, 2012
  19. Jeff KingAug 1, 2012
  20. Nguyen Thai Ngoc DuyAug 2, 2012
  21. Jeff KingAug 2, 2012
  22. 0/8 caching rename resultsJeff King, Aug 4, 2012
  23. 1/8 implement generic key/value mapJeff King, Aug 4, 2012
  24. Junio C HamanoAug 4, 2012
  25. Jeff KingAug 6, 2012
  26. 2/8 map: add helper functions for objects as keysJeff King, Aug 4, 2012
  27. 3/8 fast-export: use object to uint32 map instead of "decorate"Jeff King, Aug 4, 2012
  28. 4/8 decorate: use "map" for the underlying implementationJeff King, Aug 4, 2012
  29. 5/8 map: implement persistent mapsJeff King, Aug 4, 2012
  30. 6/8 implement metadata cache subsystemJeff King, Aug 4, 2012
  31. Junio C HamanoAug 4, 2012
  32. Jeff KingAug 6, 2012
  33. Jeff KingAug 6, 2012
  34. 7/8 implement rename cacheJeff King, Aug 4, 2012
  35. 8/8 diff: optionally use rename cacheJeff King, Aug 4, 2012

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.