Home | History | Annotate | Line # | Download | only in bsd-core 
      1 /**************************************************************************
      2  *
      3  * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA.
      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 OR
     19  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
     20  * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
     21  * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
     22  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
     23  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
     24  * USE OR OTHER DEALINGS IN THE SOFTWARE.
     25  *
     26  *
     27  **************************************************************************/
     28 
     29 #include <sys/cdefs.h>
     30 __KERNEL_RCSID(0, "$NetBSD: drm_hashtab.c,v 1.1 2011/02/18 14:26:09 jmcneill Exp $");
     31 
     32 /*
     33  * Simple open hash tab implementation.
     34  *
     35  * Authors:
     36  * Thomas Hellstrm <thomas-at-tungstengraphics-dot-com>
     37  */
     38 
     39 #include "drmP.h"
     40 #include "drm_hashtab.h"
     41 
     42 #include <sys/hash.h>
     43 
     44 int 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 
     57 void 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 
     71 static struct drm_hash_item *
     72 drm_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 
     90 int 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  */
    119 int 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 
    143 int 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 
    156 int 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 
    168 int 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 
    174 void 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