1272343Sngie/************************************************************************** 2272343Sngie * 3272343Sngie * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA. 4272343Sngie * All Rights Reserved. 5272343Sngie * 6272343Sngie * Permission is hereby granted, free of charge, to any person obtaining a 7272343Sngie * copy of this software and associated documentation files (the 8272343Sngie * "Software"), to deal in the Software without restriction, including 9272343Sngie * without limitation the rights to use, copy, modify, merge, publish, 10272343Sngie * distribute, sub license, and/or sell copies of the Software, and to 11272343Sngie * permit persons to whom the Software is furnished to do so, subject to 12272343Sngie * the following conditions: 13272343Sngie * 14272343Sngie * The above copyright notice and this permission notice (including the 15272343Sngie * next paragraph) shall be included in all copies or substantial portions 16272343Sngie * of the Software. 17272343Sngie * 18272343Sngie * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19272343Sngie * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 20272343Sngie * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL 21272343Sngie * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, 22272343Sngie * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 23272343Sngie * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE 24272343Sngie * USE OR OTHER DEALINGS IN THE SOFTWARE. 25272343Sngie * 26272343Sngie * 27272343Sngie **************************************************************************/ 28272343Sngie 29272343Sngie#include <sys/cdefs.h> 30272343Sngie__KERNEL_RCSID(0, "$NetBSD$"); 31272343Sngie 32272343Sngie/* 33272343Sngie * Simple open hash tab implementation. 34272343Sngie * 35272343Sngie * Authors: 36272343Sngie * Thomas Hellstr��m <thomas-at-tungstengraphics-dot-com> 37272343Sngie */ 38272343Sngie 39272343Sngie#include "drmP.h" 40272343Sngie#include "drm_hashtab.h" 41272343Sngie 42#include <sys/hash.h> 43 44int drm_ht_create(struct drm_open_hash *ht, unsigned int order) 45{ 46 ht->size = 1 << order; 47 ht->order = order; 48 ht->table = NULL; 49 ht->table = hashinit(ht->size, HASH_LIST, false, &ht->mask); 50 if (!ht->table) { 51 DRM_ERROR("Out of memory for hash table\n"); 52 return -ENOMEM; 53 } 54 return 0; 55} 56 57void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key) 58{ 59 struct drm_hash_item *entry; 60 struct drm_hash_item_list *h_list; 61 unsigned int hashed_key; 62 int count = 0; 63 64 hashed_key = hash32_buf(&key, sizeof(key), ht->order); 65 DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key); 66 h_list = &ht->table[hashed_key & ht->mask]; 67 LIST_FOREACH(entry, h_list, head) 68 DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key); 69} 70 71static struct drm_hash_item * 72drm_ht_find_key(struct drm_open_hash *ht, unsigned long key) 73{ 74 struct drm_hash_item *entry; 75 struct drm_hash_item_list *h_list; 76 unsigned int hashed_key; 77 78 hashed_key = hash32_buf(&key, sizeof(key), ht->order); 79 h_list = &ht->table[hashed_key & ht->mask]; 80 LIST_FOREACH(entry, h_list, head) { 81 if (entry->key == key) 82 return entry; 83 if (entry->key > key) 84 break; 85 } 86 return NULL; 87} 88 89 90int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item) 91{ 92 struct drm_hash_item *entry, *parent; 93 struct drm_hash_item_list *h_list; 94 unsigned int hashed_key; 95 unsigned long key = item->key; 96 97 hashed_key = hash32_buf(&key, sizeof(key), ht->order); 98 h_list = &ht->table[hashed_key & ht->mask]; 99 parent = NULL; 100 LIST_FOREACH(entry, h_list, head) { 101 if (entry->key == key) 102 return -EINVAL; 103 if (entry->key > key) 104 break; 105 parent = entry; 106 } 107 if (parent) { 108 LIST_INSERT_AFTER(parent, item, head); 109 } else { 110 LIST_INSERT_HEAD(h_list, item, head); 111 } 112 return 0; 113} 114 115/* 116 * Just insert an item and return any "bits" bit key that hasn't been 117 * used before. 118 */ 119int drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item, 120 unsigned long seed, int bits, int shift, 121 unsigned long add) 122{ 123 int ret; 124 unsigned long mask = (1 << bits) - 1; 125 unsigned long first, unshifted_key = 0; 126 127 unshifted_key = hash32_buf(&seed, sizeof(seed), unshifted_key); 128 first = unshifted_key; 129 do { 130 item->key = (unshifted_key << shift) + add; 131 ret = drm_ht_insert_item(ht, item); 132 if (ret) 133 unshifted_key = (unshifted_key + 1) & mask; 134 } while(ret && (unshifted_key != first)); 135 136 if (ret) { 137 DRM_ERROR("Available key bit space exhausted\n"); 138 return -EINVAL; 139 } 140 return 0; 141} 142 143int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key, 144 struct drm_hash_item **item) 145{ 146 struct drm_hash_item *entry; 147 148 entry = drm_ht_find_key(ht, key); 149 if (!entry) 150 return -EINVAL; 151 152 *item = entry; 153 return 0; 154} 155 156int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key) 157{ 158 struct drm_hash_item *entry; 159 160 entry = drm_ht_find_key(ht, key); 161 if (entry) { 162 LIST_REMOVE(entry, head); 163 return 0; 164 } 165 return -EINVAL; 166} 167 168int drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item) 169{ 170 LIST_REMOVE(item, head); 171 return 0; 172} 173 174void drm_ht_remove(struct drm_open_hash *ht) 175{ 176 if (ht->table) { 177 hashdone(ht->table, HASH_LIST, ht->mask); 178 ht->table = NULL; 179 } 180} 181