Skip to content

crux: compact sorted slice serialization #176

@skhal

Description

@skhal

Serialize a sorted slice of paths in compact form by sharing prefix from the previous item found in Google codesearch:
https://github.com/google/codesearch/blob/b34f2a0c5ce12be3c9dc28038640afece6bee523/index/path.go#L123-L129

For example, a slice ["/foo/bar/a", "/foo/bar/b"] would store:

<a-size>/foo/bar/a\0<a-prefix-len><b-size>b\0

That is two data structures:

{
  size: 10,
  path: "/foo/bar/a",
}
{
  prefixSize: 9,
  size: 1
  path: "b"
}

When read it does the following (conceptually equivalent code):

var paths string[2]
paths[0] = "/foo/bar/a"
paths[1] = paths[0][:9] + "b"  // "/foo/bar/" + "b"

It allows to share prefix path between sorted items in the list.

Metadata

Metadata

Assignees

No one assigned

    Labels

    newNew binary, feature, functionality.

    Projects

    No projects

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions