/*

 * 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 (void *) with the data

 * referenced by pointer keys (void *). NULL pointer

 * values are not supported. A NULL 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 true 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 NULL if the

 *             comparator and hasher functions support it)

 *

 * @return the value associated with the given key, or NULL

 *         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 NULL 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

 *                           NULL if the map did not contain the

 *                           key; NULL 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 NULL

 *             if the comparator and hasher functions support it)

 *

 * @return the value that was associated with the key, or

 *         NULL if it was not mapped

 **/

void *pointerMapRemove(PointerMap *map, const void *key);

#endif /* POINTER_MAP_H */