Listing 1 The header file hashmap.h

/*--------------------------------------------------------------*
 *       class Map<>
 *
 * The map class maps keys to values.
 * (an associative array class)
 *--------------------------------------------------------------*/

#include <stddef.h>
#define HASHSIZE 31

struct VPAssoc {
    VPAssoc *next;   // next key/value pair in bucket
    void *   key;    // pointer to the key
    void *   value;  // pointer to the value
};


class VPmap {
protected:
    typedef int (*KeyCompareEqProc)
                    (const void *a,
                     const void *b);

    typedef unsigned (*KeyHashProc)
                    (const void *key);

    typedef void (*KeyValCreateProc)
                    (const VPmap *dict,
                     const void * currentKey,
                     void *&      keyCopy,

                     void *&      newValue);

    typedef void (*KeyValDestroyProc)
                    (void *key,
                     void *value);

    KeyCompareEqProc  isEqual;
    KeyHashProc       hash;
    KeyValCreateProc  CreateKeyAndValue;
    KeyValDestroyProc DestroyKeyAndValue;
    VPAssoc **        keys;
    size_t            hashsize;

    /// constructor
    VPmap(size_t,
         KeyHashProc,
         KeyCompareEqProc,
         KeyValCreateProc,
         KeyValDestroyProc);

    ~VPmap();

private:
    VPmap(const VPmap &); // copy and assignment illegal
    VPmap &operator= (const VPmap &);

protected:
    void *index(const void *);

    /// apply a function to each key and value
    typedef void (*VPiterProc)(const void *, void *, void *);
    void apply(VPiterProc, void *);
};

/*------------------------------------------------------------*
 * Templates
 *------------------------------------------------------------*/

template <class KEY, class VAL>
struct Map : private VPmap {
    typedef unsigned (*KeyHashFunction)(const KEY &);
    Map(KeyHashFunction,
       const VAL & = VAL(),
       size_t = HASHSIZE);

    VAL &operator[](const KEY &key)
       {
       return * (VAL *) index(&key);
       }

    typedef void (*IterProc)(const KEY &, VAL &, void *);
    void apply(IterProc proc, void *data)
       {
       VPmap::apply(VPiterProc(proc), data);
       }

private:
    VAL default_value;

    static void CreateKeyVal
       (const Map<KEY, VAL> &,
        const KEY &,
        KEY *&,
        VAL *&);

    static void DestroyKeyVal(KEY *key, VAL *value);
    static int CmpKeys(const KEY &a, const KEY &b);
};

  /* some compilers instantiate templates in header files */
#if defined __BCPLUSPLUS__ || defined __GNUC__
#include "hashmap.cc"
#endif

/* End of File */