1203287Srnoland/************************************************************************** 2203287Srnoland * 3203287Srnoland * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA. 4203287Srnoland * All Rights Reserved. 5203287Srnoland * 6203287Srnoland * Permission is hereby granted, free of charge, to any person obtaining a 7203287Srnoland * copy of this software and associated documentation files (the 8203287Srnoland * "Software"), to deal in the Software without restriction, including 9203287Srnoland * without limitation the rights to use, copy, modify, merge, publish, 10203287Srnoland * distribute, sub license, and/or sell copies of the Software, and to 11203287Srnoland * permit persons to whom the Software is furnished to do so, subject to 12203287Srnoland * the following conditions: 13203287Srnoland * 14203287Srnoland * The above copyright notice and this permission notice (including the 15203287Srnoland * next paragraph) shall be included in all copies or substantial portions 16203287Srnoland * of the Software. 17203287Srnoland * 18203287Srnoland * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19203287Srnoland * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 20203287Srnoland * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL 21203287Srnoland * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, 22203287Srnoland * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 23203287Srnoland * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE 24203287Srnoland * USE OR OTHER DEALINGS IN THE SOFTWARE. 25203287Srnoland * 26203287Srnoland * 27203287Srnoland **************************************************************************/ 28203287Srnoland 29203287Srnoland#include <sys/cdefs.h> 30203287Srnoland__FBSDID("$FreeBSD: releng/10.3/sys/dev/drm/drm_hashtab.c 207118 2010-04-23 14:48:30Z rnoland $"); 31203287Srnoland 32203287Srnoland/* 33203287Srnoland * Simple open hash tab implementation. 34203287Srnoland * 35203287Srnoland * Authors: 36203287Srnoland * Thomas Hellstr��m <thomas-at-tungstengraphics-dot-com> 37203287Srnoland */ 38203287Srnoland 39203287Srnoland#include "dev/drm/drmP.h" 40203287Srnoland#include "dev/drm/drm_hashtab.h" 41203287Srnoland 42203287Srnoland#include <sys/hash.h> 43203287Srnoland 44203287Srnolandint drm_ht_create(struct drm_open_hash *ht, unsigned int order) 45203287Srnoland{ 46203287Srnoland ht->size = 1 << order; 47203287Srnoland ht->order = order; 48203287Srnoland ht->table = NULL; 49207118Srnoland ht->table = hashinit_flags(ht->size, DRM_MEM_HASHTAB, &ht->mask, 50207118Srnoland HASH_NOWAIT); 51203287Srnoland if (!ht->table) { 52203287Srnoland DRM_ERROR("Out of memory for hash table\n"); 53203287Srnoland return -ENOMEM; 54203287Srnoland } 55203287Srnoland return 0; 56203287Srnoland} 57203287Srnoland 58203287Srnolandvoid drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key) 59203287Srnoland{ 60203287Srnoland struct drm_hash_item *entry; 61203287Srnoland struct drm_hash_item_list *h_list; 62203287Srnoland unsigned int hashed_key; 63203287Srnoland int count = 0; 64203287Srnoland 65203287Srnoland hashed_key = hash32_buf(&key, sizeof(key), ht->order); 66203287Srnoland DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key); 67203287Srnoland h_list = &ht->table[hashed_key & ht->mask]; 68203287Srnoland LIST_FOREACH(entry, h_list, head) 69203287Srnoland DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key); 70203287Srnoland} 71203287Srnoland 72203287Srnolandstatic struct drm_hash_item * 73203287Srnolanddrm_ht_find_key(struct drm_open_hash *ht, unsigned long key) 74203287Srnoland{ 75203287Srnoland struct drm_hash_item *entry; 76203287Srnoland struct drm_hash_item_list *h_list; 77203287Srnoland unsigned int hashed_key; 78203287Srnoland 79203287Srnoland hashed_key = hash32_buf(&key, sizeof(key), ht->order); 80203287Srnoland h_list = &ht->table[hashed_key & ht->mask]; 81203287Srnoland LIST_FOREACH(entry, h_list, head) { 82203287Srnoland if (entry->key == key) 83203287Srnoland return entry; 84203287Srnoland if (entry->key > key) 85203287Srnoland break; 86203287Srnoland } 87203287Srnoland return NULL; 88203287Srnoland} 89203287Srnoland 90203287Srnoland 91203287Srnolandint drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item) 92203287Srnoland{ 93203287Srnoland struct drm_hash_item *entry, *parent; 94203287Srnoland struct drm_hash_item_list *h_list; 95203287Srnoland unsigned int hashed_key; 96203287Srnoland unsigned long key = item->key; 97203287Srnoland 98203287Srnoland hashed_key = hash32_buf(&key, sizeof(key), ht->order); 99203287Srnoland h_list = &ht->table[hashed_key & ht->mask]; 100203287Srnoland parent = NULL; 101203287Srnoland LIST_FOREACH(entry, h_list, head) { 102203287Srnoland if (entry->key == key) 103203287Srnoland return -EINVAL; 104203287Srnoland if (entry->key > key) 105203287Srnoland break; 106203287Srnoland parent = entry; 107203287Srnoland } 108203287Srnoland if (parent) { 109203287Srnoland LIST_INSERT_AFTER(parent, item, head); 110203287Srnoland } else { 111203287Srnoland LIST_INSERT_HEAD(h_list, item, head); 112203287Srnoland } 113203287Srnoland return 0; 114203287Srnoland} 115203287Srnoland 116203287Srnoland/* 117203287Srnoland * Just insert an item and return any "bits" bit key that hasn't been 118203287Srnoland * used before. 119203287Srnoland */ 120203287Srnolandint drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item, 121203287Srnoland unsigned long seed, int bits, int shift, 122203287Srnoland unsigned long add) 123203287Srnoland{ 124203287Srnoland int ret; 125203287Srnoland unsigned long mask = (1 << bits) - 1; 126203287Srnoland unsigned long first, unshifted_key = 0; 127203287Srnoland 128203287Srnoland unshifted_key = hash32_buf(&seed, sizeof(seed), unshifted_key); 129203287Srnoland first = unshifted_key; 130203287Srnoland do { 131203287Srnoland item->key = (unshifted_key << shift) + add; 132203287Srnoland ret = drm_ht_insert_item(ht, item); 133203287Srnoland if (ret) 134203287Srnoland unshifted_key = (unshifted_key + 1) & mask; 135203287Srnoland } while(ret && (unshifted_key != first)); 136203287Srnoland 137203287Srnoland if (ret) { 138203287Srnoland DRM_ERROR("Available key bit space exhausted\n"); 139203287Srnoland return -EINVAL; 140203287Srnoland } 141203287Srnoland return 0; 142203287Srnoland} 143203287Srnoland 144203287Srnolandint drm_ht_find_item(struct drm_open_hash *ht, unsigned long key, 145203287Srnoland struct drm_hash_item **item) 146203287Srnoland{ 147203287Srnoland struct drm_hash_item *entry; 148203287Srnoland 149203287Srnoland entry = drm_ht_find_key(ht, key); 150203287Srnoland if (!entry) 151203287Srnoland return -EINVAL; 152203287Srnoland 153203287Srnoland *item = entry; 154203287Srnoland return 0; 155203287Srnoland} 156203287Srnoland 157203287Srnolandint drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key) 158203287Srnoland{ 159203287Srnoland struct drm_hash_item *entry; 160203287Srnoland 161203287Srnoland entry = drm_ht_find_key(ht, key); 162203287Srnoland if (entry) { 163203287Srnoland LIST_REMOVE(entry, head); 164203287Srnoland return 0; 165203287Srnoland } 166203287Srnoland return -EINVAL; 167203287Srnoland} 168203287Srnoland 169203287Srnolandint drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item) 170203287Srnoland{ 171203287Srnoland LIST_REMOVE(item, head); 172203287Srnoland return 0; 173203287Srnoland} 174203287Srnoland 175203287Srnolandvoid drm_ht_remove(struct drm_open_hash *ht) 176203287Srnoland{ 177203287Srnoland if (ht->table) { 178203287Srnoland hashdestroy(ht->table, DRM_MEM_HASHTAB, ht->mask); 179203287Srnoland ht->table = NULL; 180203287Srnoland } 181203287Srnoland} 182