/*
 * Copyright (c) 2020 Red Hat, Inc.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA. 
 *
 * $Id: //eng/vdo-releases/aluminum/src/c++/vdo/base/pointerMap.h#1 $
 */

#ifndef POINTER_MAP_H
#define POINTER_MAP_H

#include "common.h"

/**
 * PointerMap associates pointer values (<code>void *</code>) with the data
 * referenced by pointer keys (<code>void *</code>). <code>NULL</code> pointer
 * values are not supported. A <code>NULL</code> key value is supported when
 * the instance's key comparator and hasher functions support it.
 *
 * The map is implemented as hash table, which should provide constant-time
 * insert, query, and remove operations, although the insert may occasionally
 * grow the table, which is linear in the number of entries in the map. The
 * table will grow as needed to hold new entries, but will not shrink as
 * entries are removed.
 *
 * The key and value pointers passed to the map are retained and used by the
 * map, but are not owned by the map. Freeing the map does not attempt to free
 * the pointers. The client is entirely responsible for the memory managment
 * of the keys and values. The current interface and implementation assume
 * that keys will be properties of the values, or that keys will not be memory
 * managed, or that keys will not need to be freed as a result of being
 * replaced when a key is re-mapped.
 **/

typedef struct pointerMap PointerMap;

/**
 * The prototype of functions that compare the referents of two pointer keys
 * for equality. If two keys are equal, then both keys must have the same the
 * hash code associated with them by the hasher function defined below.

 * @param thisKey  The first element to compare
 * @param thatKey  The second element to compare
 *
 * @return <code>true</code> if and only if the referents of the two
 *         key pointers are to be treated as the same key by the map
 **/
typedef bool PointerKeyComparator(const void *thisKey, const void *thatKey);

/**
 * The prototype of functions that get or calculate a hash code associated
 * with the referent of pointer key. The hash code must be uniformly
 * distributed over all uint32_t values. The hash code associated with a given
 * key must not change while the key is in the map. If the comparator function
 * says two keys are equal, then this function must return the same hash code
 * for both keys. This function may be called many times for a key while an
 * entry is stored for it in the map.
 *
 * @param key  The pointer key to hash
 *
 * @return the hash code for the key
 **/
typedef uint32_t PointerKeyHasher(const void *key);

/**
 * Allocate and initialize a PointerMap.
 *
 * @param [in]  initialCapacity  The number of entries the map should
 *                               initially be capable of holding (zero tells
 *                               the map to use its own small default)
 * @param [in]  initialLoad      The load factor of the map, expressed as an
 *                               integer percentage (typically in the range
 *                               50 to 90, with zero telling the map to use
 *                               its own default)
 * @param [in]  comparator       The function to use to compare the referents
 *                               of two pointer keys for equality
 * @param [in]  hasher           The function to use obtain the hash code
 *                               associated with each pointer key
 * @param [out] mapPtr           A pointer to hold the new PointerMap
 *
 * @return UDS_SUCCESS or an error code
 **/
int makePointerMap(size_t                 initialCapacity,
                   unsigned int           initialLoad,
                   PointerKeyComparator   comparator,
                   PointerKeyHasher       hasher,
                   PointerMap           **mapPtr)
  __attribute__((warn_unused_result));

/**
 * Free a PointerMap and null out the reference to it. NOTE: The map does not
 * own the pointer keys and values stored in the map and they are not freed by
 * this call.
 *
 * @param [in,out] mapPtr  The reference to the PointerMap to free
 **/
void freePointerMap(PointerMap **mapPtr);

/**
 * Get the number of entries stored in a PointerMap.
 *
 * @param map  The PointerMap to query
 *
 * @return the number of entries in the map
 **/
size_t pointerMapSize(const PointerMap *map);

/**
 * Retrieve the value associated with a given key from the PointerMap.
 *
 * @param map  The PointerMap to query
 * @param key  The key to look up (may be <code>NULL</code> if the
 *             comparator and hasher functions support it)
 *
 * @return the value associated with the given key, or <code>NULL</code>
 *         if the key is not mapped to any value
 **/
void *pointerMapGet(PointerMap *map, const void *key);

/**
 * Try to associate a value (a pointer) with an integer in a PointerMap.
 * If the map already contains a mapping for the provided key, the old value is
 * only replaced with the specified value if update is true. In either case
 * the old value is returned. If the map does not already contain a value for
 * the specified key, the new value is added regardless of the value of update.
 *
 * If the value stored in the map is updated, then the key stored in the map
 * will also be updated with the key provided by this call. The old key will
 * not be returned due to the memory managment assumptions described in the
 * interface header comment.
 *
 * @param [in]  map          The PointerMap to attempt to modify
 * @param [in]  key          The key with which to associate the new value
 *                           (may be <code>NULL</code> if the comparator and
 *                           hasher functions support it)
 * @param [in]  newValue     The value to be associated with the key
 * @param [in]  update       Whether to overwrite an existing value
 * @param [out] oldValuePtr  A pointer in which to store either the old value
 *                           (if the key was already mapped) or
 *                           <code>NULL</code> if the map did not contain the
 *                           key; <code>NULL</code> may be provided if the
 *                           caller does not need to know the old value
 *
 * @return UDS_SUCCESS or an error code
 **/
int pointerMapPut(PointerMap  *map,
                  const void  *key,
                  void        *newValue,
                  bool         update,
                  void       **oldValuePtr)
  __attribute__((warn_unused_result));

/**
 * Remove the mapping for a given key from the PointerMap.
 *
 * @param map  The PointerMap from which to remove the mapping
 * @param key  The key whose mapping is to be removed (may be <code>NULL</code>
 *             if the comparator and hasher functions support it)
 *
 * @return the value that was associated with the key, or
 *         <code>NULL</code> if it was not mapped
 **/
void *pointerMapRemove(PointerMap *map, const void *key);

#endif /* POINTER_MAP_H */