From: Junio C Hamano <gitster@pobox.com>
Date: Sat, 04 Aug 2012 22:58:10 GMT
Subject: Re: [PATCH 1/8] implement generic key/value map
Message-ID: <7vehnm8dbv.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20120804171038.GA19378@sigill.intra.peff.net>

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.

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.