1
/**************************************************************************
3
* Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA.
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:
14
* The above copyright notice and this permission notice (including the
15
* next paragraph) shall be included in all copies or substantial portions
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.
27
**************************************************************************/
29
* Simple open hash tab implementation.
32
* Thomas Hellström <thomas-at-tungstengraphics-dot-com>
36
#include "drm_hashtab.h"
37
#include <linux/hash.h>
39
int drm_ht_create(struct drm_open_hash *ht, unsigned int order)
43
ht->size = 1 << order;
47
ht->use_vmalloc = ((ht->size * sizeof(*ht->table)) > PAGE_SIZE);
48
if (!ht->use_vmalloc) {
49
ht->table = kcalloc(ht->size, sizeof(*ht->table), GFP_KERNEL);
53
ht->table = vmalloc(ht->size*sizeof(*ht->table));
56
DRM_ERROR("Out of memory for hash table\n");
59
for (i=0; i< ht->size; ++i) {
60
INIT_HLIST_HEAD(&ht->table[i]);
64
EXPORT_SYMBOL(drm_ht_create);
66
void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key)
68
struct drm_hash_item *entry;
69
struct hlist_head *h_list;
70
struct hlist_node *list;
71
unsigned int hashed_key;
74
hashed_key = hash_long(key, ht->order);
75
DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key);
76
h_list = &ht->table[hashed_key];
77
hlist_for_each(list, h_list) {
78
entry = hlist_entry(list, struct drm_hash_item, head);
79
DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);
83
static struct hlist_node *drm_ht_find_key(struct drm_open_hash *ht,
86
struct drm_hash_item *entry;
87
struct hlist_head *h_list;
88
struct hlist_node *list;
89
unsigned int hashed_key;
91
hashed_key = hash_long(key, ht->order);
92
h_list = &ht->table[hashed_key];
93
hlist_for_each(list, h_list) {
94
entry = hlist_entry(list, struct drm_hash_item, head);
95
if (entry->key == key)
104
int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item)
106
struct drm_hash_item *entry;
107
struct hlist_head *h_list;
108
struct hlist_node *list, *parent;
109
unsigned int hashed_key;
110
unsigned long key = item->key;
112
hashed_key = hash_long(key, ht->order);
113
h_list = &ht->table[hashed_key];
115
hlist_for_each(list, h_list) {
116
entry = hlist_entry(list, struct drm_hash_item, head);
117
if (entry->key == key)
119
if (entry->key > key)
124
hlist_add_after(parent, &item->head);
126
hlist_add_head(&item->head, h_list);
130
EXPORT_SYMBOL(drm_ht_insert_item);
133
* Just insert an item and return any "bits" bit key that hasn't been
136
int drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item,
137
unsigned long seed, int bits, int shift,
141
unsigned long mask = (1 << bits) - 1;
142
unsigned long first, unshifted_key;
144
unshifted_key = hash_long(seed, bits);
145
first = unshifted_key;
147
item->key = (unshifted_key << shift) + add;
148
ret = drm_ht_insert_item(ht, item);
150
unshifted_key = (unshifted_key + 1) & mask;
151
} while(ret && (unshifted_key != first));
154
DRM_ERROR("Available key bit space exhausted\n");
159
EXPORT_SYMBOL(drm_ht_just_insert_please);
161
int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key,
162
struct drm_hash_item **item)
164
struct hlist_node *list;
166
list = drm_ht_find_key(ht, key);
170
*item = hlist_entry(list, struct drm_hash_item, head);
173
EXPORT_SYMBOL(drm_ht_find_item);
175
int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key)
177
struct hlist_node *list;
179
list = drm_ht_find_key(ht, key);
181
hlist_del_init(list);
188
int drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item)
190
hlist_del_init(&item->head);
194
EXPORT_SYMBOL(drm_ht_remove_item);
196
void drm_ht_remove(struct drm_open_hash *ht)
206
EXPORT_SYMBOL(drm_ht_remove);
added
removed
updates/nouveau/drm_hashtab.c
