cutils/hashmap.h

   1 /*
   2  * Copyright (C) 2007 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /**
  18  * Hash map.
  19  */
  20
  21 #ifndef __HASHMAP_H
  22 #define __HASHMAP_H
  23
  24 #include <stdbool.h>
  25 #include <stdlib.h>
  26
  27 #ifdef __cplusplus
  28 extern "C" {
  29 #endif
  30
  31 /** A hash map. */
  32 typedef struct Hashmap Hashmap;
  33
  34 /**
  35  * Creates a new hash map. Returns NULL if memory allocation fails.
  36  *
  37  * @param initialCapacity number of expected entries
  38  * @param hash function which hashes keys
  39  * @param equals function which compares keys for equality
  40  */
  41 Hashmap* hashmapCreate(size_t initialCapacity,
  42         int (*hash)(void* key), bool (*equals)(void* keyA, void* keyB));
  43
  44 /**
  45  * Frees the hash map. Does not free the keys or values themselves.
  46  */
  47 void hashmapFree(Hashmap* map);
  48
  49 /**
  50  * Hashes the memory pointed to by key with the given size. Useful for
  51  * implementing hash functions.
  52  */
  53 int hashmapHash(void* key, size_t keySize);
  54
  55 /**
  56  * Puts value for the given key in the map. Returns pre-existing value if
  57  * any.
  58  *
  59  * If memory allocation fails, this function returns NULL, the map's size
  60  * does not increase, and errno is set to ENOMEM.
  61  */
  62 void* hashmapPut(Hashmap* map, void* key, void* value);
  63
  64 /**
  65  * Gets a value from the map. Returns NULL if no entry for the given key is
  66  * found or if the value itself is NULL.
  67  */
  68 void* hashmapGet(Hashmap* map, void* key);
  69
  70 /**
  71  * Returns true if the map contains an entry for the given key.
  72  */
  73 bool hashmapContainsKey(Hashmap* map, void* key);
  74
  75 /**
  76  * Gets the value for a key. If a value is not found, this function gets a
  77  * value and creates an entry using the given callback.
  78  *
  79  * If memory allocation fails, the callback is not called, this function
  80  * returns NULL, and errno is set to ENOMEM.
  81  */
  82 void* hashmapMemoize(Hashmap* map, void* key,
  83         void* (*initialValue)(void* key, void* context), void* context);
  84
  85 /**
  86  * Removes an entry from the map. Returns the removed value or NULL if no
  87  * entry was present.
  88  */
  89 void* hashmapRemove(Hashmap* map, void* key);
  90
  91 /**
  92  * Gets the number of entries in this map.
  93  */
  94 size_t hashmapSize(Hashmap* map);
  95
  96 /**
  97  * Invokes the given callback on each entry in the map. Stops iterating if
  98  * the callback returns false.
  99  */
 100 void hashmapForEach(Hashmap* map,
 101         bool (*callback)(void* key, void* value, void* context),
 102         void* context);
 103
 104 /**
 105  * Concurrency support.
 106  */
 107
 108 /**
 109  * Locks the hash map so only the current thread can access it.
 110  */
 111 void hashmapLock(Hashmap* map);
 112
 113 /**
 114  * Unlocks the hash map so other threads can access it.
 115  */
 116 void hashmapUnlock(Hashmap* map);
 117
 118 /**
 119  * Key utilities.
 120  */
 121
 122 /**
 123  * Hashes int keys. 'key' is a pointer to int.
 124  */
 125 int hashmapIntHash(void* key);
 126
 127 /**
 128  * Compares two int keys for equality.
 129  */
 130 bool hashmapIntEquals(void* keyA, void* keyB);
 131
 132 /**
 133  * For debugging.
 134  */
 135
 136 /**
 137  * Gets current capacity.
 138  */
 139 size_t hashmapCurrentCapacity(Hashmap* map);
 140
 141 /**
 142  * Counts the number of entry collisions.
 143  */
 144 size_t hashmapCountCollisions(Hashmap* map);
 145
 146 #ifdef __cplusplus
 147 }
 148 #endif
 149
 150 #endif /* __HASHMAP_H */