amdgpu/util_hash.h

   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
  47 #ifdef HAVE_CONFIG_H
  48 #include "config.h"
  49 #endif
  50
  51 #include <stdbool.h>
  52
  53 #include "libdrm_macros.h"
  54
  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
  64 drm_private struct util_hash *util_hash_create(void);
  65 drm_private void util_hash_delete(struct util_hash *hash);
  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  */
  74 drm_private struct util_hash_iter
  75 util_hash_insert(struct util_hash *hash, unsigned key, void *data);
  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  */
  84 drm_private struct util_hash_iter
  85 util_hash_erase(struct util_hash *hash, struct util_hash_iter iter);
  86
  87 drm_private void *util_hash_take(struct util_hash *hash, unsigned key);
  88
  89
  90 drm_private struct util_hash_iter util_hash_first_node(struct util_hash *hash);
  91
  92 /**
  93  * Return an iterator pointing to the first entry in the collision list.
  94  */
  95 drm_private struct util_hash_iter
  96 util_hash_find(struct util_hash *hash, unsigned key);
  97
  98
  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);
 102
 103
 104 drm_private struct util_hash_iter
 105 util_hash_iter_next(struct util_hash_iter iter);
 106
 107 #endif