Alex Deucher | 0936139 | 2015-04-20 12:04:22 -0400 | [diff] [blame] | 1 | /************************************************************************** |
| 2 | * |
| 3 | * Copyright 2007 VMware, Inc. |
| 4 | * All Rights Reserved. |
| 5 | * |
| 6 | * Permission is hereby granted, free of charge, to any person obtaining a |
| 7 | * copy of this software and associated documentation files (the |
| 8 | * "Software"), to deal in the Software without restriction, including |
| 9 | * without limitation the rights to use, copy, modify, merge, publish, |
| 10 | * distribute, sub license, and/or sell copies of the Software, and to |
| 11 | * permit persons to whom the Software is furnished to do so, subject to |
| 12 | * the following conditions: |
| 13 | * |
| 14 | * The above copyright notice and this permission notice (including the |
| 15 | * next paragraph) shall be included in all copies or substantial portions |
| 16 | * of the Software. |
| 17 | * |
| 18 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS |
| 19 | * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
| 20 | * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. |
| 21 | * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR |
| 22 | * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, |
| 23 | * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE |
| 24 | * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| 25 | * |
| 26 | **************************************************************************/ |
| 27 | |
| 28 | /** |
| 29 | * @file |
| 30 | * Hash implementation. |
| 31 | * |
| 32 | * This file provides a hash implementation that is capable of dealing |
| 33 | * with collisions. It stores colliding entries in linked list. All |
| 34 | * functions operating on the hash return an iterator. The iterator |
| 35 | * itself points to the collision list. If there wasn't any collision |
| 36 | * the list will have just one entry, otherwise client code should |
| 37 | * iterate over the entries to find the exact entry among ones that |
| 38 | * had the same key (e.g. memcmp could be used on the data to check |
| 39 | * that) |
| 40 | * |
| 41 | * @author Zack Rusin <zackr@vmware.com> |
| 42 | */ |
| 43 | |
| 44 | #ifndef UTIL_HASH_H |
| 45 | #define UTIL_HASH_H |
| 46 | |
Emil Velikov | 5f0f638 | 2015-08-07 16:40:45 +0100 | [diff] [blame] | 47 | #ifdef HAVE_CONFIG_H |
| 48 | #include "config.h" |
| 49 | #endif |
| 50 | |
Alex Deucher | 0936139 | 2015-04-20 12:04:22 -0400 | [diff] [blame] | 51 | #include <stdbool.h> |
| 52 | |
Emil Velikov | 5f0f638 | 2015-08-07 16:40:45 +0100 | [diff] [blame] | 53 | #include "libdrm_macros.h" |
| 54 | |
Alex Deucher | 0936139 | 2015-04-20 12:04:22 -0400 | [diff] [blame] | 55 | struct util_hash; |
| 56 | struct util_node; |
| 57 | |
| 58 | struct util_hash_iter { |
| 59 | struct util_hash *hash; |
| 60 | struct util_node *node; |
| 61 | }; |
| 62 | |
| 63 | |
Emil Velikov | 5f0f638 | 2015-08-07 16:40:45 +0100 | [diff] [blame] | 64 | drm_private struct util_hash *util_hash_create(void); |
| 65 | drm_private void util_hash_delete(struct util_hash *hash); |
Alex Deucher | 0936139 | 2015-04-20 12:04:22 -0400 | [diff] [blame] | 66 | |
| 67 | |
| 68 | /** |
| 69 | * Adds a data with the given key to the hash. If entry with the given |
| 70 | * key is already in the hash, this current entry is instered before it |
| 71 | * in the collision list. |
| 72 | * Function returns iterator pointing to the inserted item in the hash. |
| 73 | */ |
Emil Velikov | 5f0f638 | 2015-08-07 16:40:45 +0100 | [diff] [blame] | 74 | drm_private struct util_hash_iter |
| 75 | util_hash_insert(struct util_hash *hash, unsigned key, void *data); |
Alex Deucher | 0936139 | 2015-04-20 12:04:22 -0400 | [diff] [blame] | 76 | |
| 77 | /** |
| 78 | * Removes the item pointed to by the current iterator from the hash. |
| 79 | * Note that the data itself is not erased and if it was a malloc'ed pointer |
| 80 | * it will have to be freed after calling this function by the callee. |
| 81 | * Function returns iterator pointing to the item after the removed one in |
| 82 | * the hash. |
| 83 | */ |
Emil Velikov | 5f0f638 | 2015-08-07 16:40:45 +0100 | [diff] [blame] | 84 | drm_private struct util_hash_iter |
| 85 | util_hash_erase(struct util_hash *hash, struct util_hash_iter iter); |
Alex Deucher | 0936139 | 2015-04-20 12:04:22 -0400 | [diff] [blame] | 86 | |
Emil Velikov | 5f0f638 | 2015-08-07 16:40:45 +0100 | [diff] [blame] | 87 | drm_private void *util_hash_take(struct util_hash *hash, unsigned key); |
Alex Deucher | 0936139 | 2015-04-20 12:04:22 -0400 | [diff] [blame] | 88 | |
| 89 | |
Emil Velikov | 5f0f638 | 2015-08-07 16:40:45 +0100 | [diff] [blame] | 90 | drm_private struct util_hash_iter util_hash_first_node(struct util_hash *hash); |
Alex Deucher | 0936139 | 2015-04-20 12:04:22 -0400 | [diff] [blame] | 91 | |
| 92 | /** |
| 93 | * Return an iterator pointing to the first entry in the collision list. |
| 94 | */ |
Emil Velikov | 5f0f638 | 2015-08-07 16:40:45 +0100 | [diff] [blame] | 95 | drm_private struct util_hash_iter |
| 96 | util_hash_find(struct util_hash *hash, unsigned key); |
Alex Deucher | 0936139 | 2015-04-20 12:04:22 -0400 | [diff] [blame] | 97 | |
| 98 | |
Emil Velikov | 5f0f638 | 2015-08-07 16:40:45 +0100 | [diff] [blame] | 99 | drm_private int util_hash_iter_is_null(struct util_hash_iter iter); |
| 100 | drm_private unsigned util_hash_iter_key(struct util_hash_iter iter); |
| 101 | drm_private void *util_hash_iter_data(struct util_hash_iter iter); |
Alex Deucher | 0936139 | 2015-04-20 12:04:22 -0400 | [diff] [blame] | 102 | |
| 103 | |
Emil Velikov | 5f0f638 | 2015-08-07 16:40:45 +0100 | [diff] [blame] | 104 | drm_private struct util_hash_iter |
| 105 | util_hash_iter_next(struct util_hash_iter iter); |
Alex Deucher | 0936139 | 2015-04-20 12:04:22 -0400 | [diff] [blame] | 106 | |
| 107 | #endif |