1 /****************************************************************************** 2 * 3 * Copyright (C) 2014 Google, Inc. 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at: 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 ******************************************************************************/ 18 19 #pragma once 20 21 #include <stdbool.h> 22 #include <stddef.h> 23 #include <stdint.h> 24 25 struct hash_map_t; 26 typedef struct hash_map_t hash_map_t; 27 28 typedef struct hash_map_entry_t { 29 const void *key; 30 void *data; 31 const hash_map_t *hash_map; 32 } hash_map_entry_t; 33 34 typedef size_t hash_index_t; 35 36 // Takes a key structure and returns a hash value. 37 typedef hash_index_t (*hash_index_fn)(const void *key); 38 typedef bool (*hash_map_iter_cb)(hash_map_entry_t *hash_entry, void *context); 39 40 typedef bool (*key_equality_fn)(const void *x, const void *y); 41 42 typedef void (*key_free_fn)(void *key); 43 typedef void (*data_free_fn)(void *data); 44 45 // Returns a new, empty hash_map. Returns NULL if not enough memory could be allocated 46 // for the hash_map structure. The returned hash_map must be freed with |hash_map_free|. 47 // The |num_bucket| specifies the number of hashable buckets for the map and must not 48 // be zero. The |hash_fn| specifies a hash function to be used and must not be NULL. 49 // The |key_fn| and |data_fn| are called whenever a hash_map element is removed from 50 // the hash_map. They can be used to release resources held by the hash_map element, 51 // e.g. memory or file descriptor. |key_fn| and |data_fn| may be NULL if no cleanup 52 // is necessary on element removal. |equality_fn| is used to check for key equality. 53 // If |equality_fn| is NULL, default pointer equality is used. 54 hash_map_t *hash_map_new( 55 size_t size, 56 hash_index_fn hash_fn, 57 key_free_fn key_fn, 58 data_free_fn data_fn, 59 key_equality_fn equality_fn); 60 61 // Frees the hash_map. This function accepts NULL as an argument, in which case it 62 // behaves like a no-op. 63 void hash_map_free(hash_map_t *hash_map); 64 65 // Returns true if the hash_map is empty (has no elements), false otherwise. 66 // Note that a NULL |hash_map| is not the same as an empty |hash_map|. This function 67 // does not accept a NULL |hash_map|. 68 bool hash_map_is_empty(const hash_map_t *hash_map); 69 70 // Returns the number of elements in the hash map. This function does not accept a 71 // NULL |hash_map|. 72 size_t hash_map_size(const hash_map_t *hash_map); 73 74 // Returns the number of buckets in the hash map. This function does not accept a 75 // NULL |hash_map|. 76 size_t hash_map_num_buckets(const hash_map_t *hash_map); 77 78 // Returns true if the hash_map has a valid entry for the presented key. 79 // This function does not accept a NULL |hash_map|. 80 bool hash_map_has_key(const hash_map_t *hash_map, const void *key); 81 82 // Returns the element indexed by |key| in the hash_map without removing it. |hash_map| 83 // may not be NULL. Returns NULL if no entry indexed by |key|. 84 void *hash_map_get(const hash_map_t *hash_map, const void *key); 85 86 // Sets the value |data| indexed by |key| into the |hash_map|. Neither |data| nor 87 // |hash_map| may be NULL. This function does not make copies of |data| nor |key| 88 // so the pointers must remain valid at least until the element is removed from the 89 // hash_map or the hash_map is freed. Returns true if |data| could be set, false 90 // otherwise (e.g. out of memory). 91 bool hash_map_set(hash_map_t *hash_map, const void *key, void *data); 92 93 // Removes data indexed by |key| from the hash_map. |hash_map| may not be NULL. 94 // If |key_fn| or |data_fn| functions were specified in |hash_map_new|, they 95 // will be called back with |key| or |data| respectively. This function returns true 96 // if |key| was found in the hash_map and removed, false otherwise. 97 bool hash_map_erase(hash_map_t *hash_map, const void *key); 98 99 // Removes all elements in the hash_map. Calling this function will return the hash_map 100 // to the same state it was in after |hash_map_new|. |hash_map| may not be NULL. 101 void hash_map_clear(hash_map_t *hash_map); 102 103 // Iterates through the entire |hash_map| and calls |callback| for each data 104 // element and passes through the |context| argument. If the hash_map is 105 // empty, |callback| will never be called. It is not safe to mutate the 106 // hash_map inside the callback. Neither |hash_map| nor |callback| may be NULL. 107 // If |callback| returns false, the iteration loop will immediately exit. 108 void hash_map_foreach(hash_map_t *hash_map, hash_map_iter_cb callback, void *context); 109