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

[PATCH v5] generalizing sorted-array handling

From
Yann Dirson <ydirson@altern.org>
Date
Dec 5, 2010, 10:34 UTC
Message-ID
<1291545247-4151-1-git-send-email-ydirson@altern.org>
Changes from v4:
* better API documentation (was previously lacking or plain obsolete)
* added one more wrapper (used by yet-to-be-resent bulk-* series
Notes on current API:
* The macro names are a bit heavy-weight.  Better ideas welcome.
* This API is very verbose, and I'm not happy with that aspect.

It could be made less so, eg. causing insert wrappers to auto-declare the required generic insert func, and causing the latter auto-declare the required generic search func. That would cause duplication of the generic search func in many cases.

The duplication problem would not be an issue if we add an automatic call to declare_gen_sorted_insert() in declare_sorted_array_insert_*, but we would loose the symetry with the search API.

Adding "simple" API variants that would call all the necessary stuff would help code readability, but adding yet more entry points seems a dubious approach.

Or is that just the "use cpp for templating" just inadequate here ?
* could gain a dealloc API, to minimize the explicit use of the _nr
  and _alloc vars
The following binary-search occurences were not converted:
* read-cache.c::index_name_pos has widely-used API with 2 low-coupled
  cmp/init params: sorted-array could be generalized at the cost of
  using stdarg, but is it worth it ?
* pack-revindex.c::find_pack_revindex is a bit special and needs more
  thought
* cache-tree.c::subtree_pos and sha1_file::find_pack_entry_one too
* sha1_lookup.c stuff probably too special
Next: Yann Dirson
Message 1 of 9 in “generalizing sorted-array handling”
  1. generalizing sorted-array handlingYann Dirson, Dec 5, 2010
  2. 1/6 Introduce sorted-array binary-search function.Yann Dirson, Dec 5, 2010
  3. 2/6 Convert diffcore-rename's rename_dst to the new sorted-array API.Yann Dirson, Dec 5, 2010
  4. 3/6 Convert diffcore-rename's rename_src to the new sorted-array API.Yann Dirson, Dec 5, 2010
  5. 4/6 Convert pack-objects.c to the new sorted-array API.Yann Dirson, Dec 5, 2010
  6. 5/6 Use sorted-array API for commit.c's commit_graft.Yann Dirson, Dec 5, 2010
  7. 6/6 [WIP] subvert sorted-array to replace binary-search in unpack-objects.Yann Dirson, Dec 5, 2010
  8. Jonathan NiederDec 5, 2010
  9. Yann DirsonDec 5, 2010

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.