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

From: Jeff King <peff@peff.net>
Date: Aug 6, 2012, 20:35 UTC
Message-ID: <20120806203558.GB11977@sigill.intra.peff.net>
In-Reply-To: <7vehnm8dbv.fsf@alter.siamese.dyndns.org>

On Sat, Aug 04, 2012 at 03:58:10PM -0700, Junio C Hamano wrote:

Show 20 quoted lines

> Jeff King <peff@peff.net> writes:
> 
> > 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.

Both have to be fixed size, since we represent the hash table using an array. But there is nothing stopping you from storing a fixed-size pointer to a variable-sized item (that is what is happening with "struct object *", anyway; the actual storage is inside a "struct commit", "struct tree", etc). But then you get the accompanying memory-management issues (which are easy for "struct object", as our policy is to keep a global valid-until-the-program-exits store of all objects we ever see).

> 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?

No, you only have to define equality. However, for the later patch which adds a persistent backing store, you need to be able to serialize keys to a byte representation, which provides an implicit total order (by sorting the bytes).

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

Right. See patch 5/8.

-Peff