1235783Skib/************************************************************************** 2235783Skib * 3235783Skib * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA. 4235783Skib * All Rights Reserved. 5235783Skib * 6235783Skib * Permission is hereby granted, free of charge, to any person obtaining a 7235783Skib * copy of this software and associated documentation files (the 8235783Skib * "Software"), to deal in the Software without restriction, including 9235783Skib * without limitation the rights to use, copy, modify, merge, publish, 10235783Skib * distribute, sub license, and/or sell copies of the Software, and to 11235783Skib * permit persons to whom the Software is furnished to do so, subject to 12235783Skib * the following conditions: 13235783Skib * 14235783Skib * The above copyright notice and this permission notice (including the 15235783Skib * next paragraph) shall be included in all copies or substantial portions 16235783Skib * of the Software. 17235783Skib * 18235783Skib * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19235783Skib * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 20235783Skib * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL 21235783Skib * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, 22235783Skib * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 23235783Skib * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE 24235783Skib * USE OR OTHER DEALINGS IN THE SOFTWARE. 25235783Skib * 26235783Skib * 27235783Skib **************************************************************************/ 28235783Skib 29235783Skib#include <sys/cdefs.h> 30235783Skib__FBSDID("$FreeBSD$"); 31235783Skib 32235783Skib/* 33235783Skib * Simple open hash tab implementation. 34235783Skib * 35235783Skib * Authors: 36235783Skib * Thomas Hellstr��m <thomas-at-tungstengraphics-dot-com> 37235783Skib */ 38235783Skib 39235783Skib#include <dev/drm2/drmP.h> 40235783Skib#include <dev/drm2/drm_hashtab.h> 41235783Skib 42235783Skib#include <sys/hash.h> 43235783Skib 44235783Skibint drm_ht_create(struct drm_open_hash *ht, unsigned int order) 45235783Skib{ 46235783Skib ht->size = 1 << order; 47235783Skib ht->order = order; 48235783Skib ht->table = NULL; 49235783Skib ht->table = hashinit_flags(ht->size, DRM_MEM_HASHTAB, &ht->mask, 50235783Skib HASH_NOWAIT); 51235783Skib if (!ht->table) { 52235783Skib DRM_ERROR("Out of memory for hash table\n"); 53235783Skib return -ENOMEM; 54235783Skib } 55235783Skib return 0; 56235783Skib} 57235783Skib 58235783Skibvoid drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key) 59235783Skib{ 60235783Skib struct drm_hash_item *entry; 61235783Skib struct drm_hash_item_list *h_list; 62235783Skib unsigned int hashed_key; 63235783Skib int count = 0; 64235783Skib 65235783Skib hashed_key = hash32_buf(&key, sizeof(key), ht->order); 66235783Skib DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key); 67235783Skib h_list = &ht->table[hashed_key & ht->mask]; 68235783Skib LIST_FOREACH(entry, h_list, head) 69235783Skib DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key); 70235783Skib} 71235783Skib 72235783Skibstatic struct drm_hash_item * 73235783Skibdrm_ht_find_key(struct drm_open_hash *ht, unsigned long key) 74235783Skib{ 75235783Skib struct drm_hash_item *entry; 76235783Skib struct drm_hash_item_list *h_list; 77235783Skib unsigned int hashed_key; 78235783Skib 79235783Skib hashed_key = hash32_buf(&key, sizeof(key), ht->order); 80235783Skib h_list = &ht->table[hashed_key & ht->mask]; 81235783Skib LIST_FOREACH(entry, h_list, head) { 82235783Skib if (entry->key == key) 83235783Skib return entry; 84235783Skib if (entry->key > key) 85235783Skib break; 86235783Skib } 87235783Skib return NULL; 88235783Skib} 89235783Skib 90235783Skib 91235783Skibint drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item) 92235783Skib{ 93235783Skib struct drm_hash_item *entry, *parent; 94235783Skib struct drm_hash_item_list *h_list; 95235783Skib unsigned int hashed_key; 96235783Skib unsigned long key = item->key; 97235783Skib 98235783Skib hashed_key = hash32_buf(&key, sizeof(key), ht->order); 99235783Skib h_list = &ht->table[hashed_key & ht->mask]; 100235783Skib parent = NULL; 101235783Skib LIST_FOREACH(entry, h_list, head) { 102235783Skib if (entry->key == key) 103235783Skib return -EINVAL; 104235783Skib if (entry->key > key) 105235783Skib break; 106235783Skib parent = entry; 107235783Skib } 108235783Skib if (parent) { 109235783Skib LIST_INSERT_AFTER(parent, item, head); 110235783Skib } else { 111235783Skib LIST_INSERT_HEAD(h_list, item, head); 112235783Skib } 113235783Skib return 0; 114235783Skib} 115235783Skib 116235783Skib/* 117235783Skib * Just insert an item and return any "bits" bit key that hasn't been 118235783Skib * used before. 119235783Skib */ 120235783Skibint drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item, 121235783Skib unsigned long seed, int bits, int shift, 122235783Skib unsigned long add) 123235783Skib{ 124235783Skib int ret; 125235783Skib unsigned long mask = (1 << bits) - 1; 126235783Skib unsigned long first, unshifted_key = 0; 127235783Skib 128235783Skib unshifted_key = hash32_buf(&seed, sizeof(seed), unshifted_key); 129235783Skib first = unshifted_key; 130235783Skib do { 131235783Skib item->key = (unshifted_key << shift) + add; 132235783Skib ret = drm_ht_insert_item(ht, item); 133235783Skib if (ret) 134235783Skib unshifted_key = (unshifted_key + 1) & mask; 135235783Skib } while(ret && (unshifted_key != first)); 136235783Skib 137235783Skib if (ret) { 138235783Skib DRM_ERROR("Available key bit space exhausted\n"); 139235783Skib return -EINVAL; 140235783Skib } 141235783Skib return 0; 142235783Skib} 143235783Skib 144235783Skibint drm_ht_find_item(struct drm_open_hash *ht, unsigned long key, 145235783Skib struct drm_hash_item **item) 146235783Skib{ 147235783Skib struct drm_hash_item *entry; 148235783Skib 149235783Skib entry = drm_ht_find_key(ht, key); 150235783Skib if (!entry) 151235783Skib return -EINVAL; 152235783Skib 153235783Skib *item = entry; 154235783Skib return 0; 155235783Skib} 156235783Skib 157235783Skibint drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key) 158235783Skib{ 159235783Skib struct drm_hash_item *entry; 160235783Skib 161235783Skib entry = drm_ht_find_key(ht, key); 162235783Skib if (entry) { 163235783Skib LIST_REMOVE(entry, head); 164235783Skib return 0; 165235783Skib } 166235783Skib return -EINVAL; 167235783Skib} 168235783Skib 169235783Skibint drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item) 170235783Skib{ 171235783Skib LIST_REMOVE(item, head); 172235783Skib return 0; 173235783Skib} 174235783Skib 175235783Skibvoid drm_ht_remove(struct drm_open_hash *ht) 176235783Skib{ 177235783Skib if (ht->table) { 178235783Skib hashdestroy(ht->table, DRM_MEM_HASHTAB, ht->mask); 179235783Skib ht->table = NULL; 180235783Skib } 181235783Skib} 182