Blame view
drivers/gpu/drm/drm_hashtab.c
5.18 KB
3a1bd924f
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
/************************************************************************** * * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA. * All Rights Reserved. * * Permission is hereby granted, free of charge, to any person obtaining a * copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sub license, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice (including the * next paragraph) shall be included in all copies or substantial portions * of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE * USE OR OTHER DEALINGS IN THE SOFTWARE. * * **************************************************************************/ /* * Simple open hash tab implementation. * * Authors: |
96de0e252
|
32 |
* Thomas Hellström <thomas-at-tungstengraphics-dot-com> |
3a1bd924f
|
33 34 35 36 37 |
*/ #include "drmP.h" #include "drm_hashtab.h" #include <linux/hash.h> |
5a0e3ad6a
|
38 |
#include <linux/slab.h> |
2d1a8a48a
|
39 |
#include <linux/export.h> |
3a1bd924f
|
40 |
|
e0be428e6
|
41 |
int drm_ht_create(struct drm_open_hash *ht, unsigned int order) |
3a1bd924f
|
42 |
{ |
7811bddb6
|
43 |
unsigned int size = 1 << order; |
3a1bd924f
|
44 |
|
3a1bd924f
|
45 |
ht->order = order; |
c1185ccdf
|
46 |
ht->table = NULL; |
7811bddb6
|
47 48 49 50 |
if (size <= PAGE_SIZE / sizeof(*ht->table)) ht->table = kcalloc(size, sizeof(*ht->table), GFP_KERNEL); else ht->table = vzalloc(size*sizeof(*ht->table)); |
3a1bd924f
|
51 52 53 54 55 |
if (!ht->table) { DRM_ERROR("Out of memory for hash table "); return -ENOMEM; } |
3a1bd924f
|
56 57 |
return 0; } |
f2cb5d86e
|
58 |
EXPORT_SYMBOL(drm_ht_create); |
3a1bd924f
|
59 |
|
e0be428e6
|
60 |
void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key) |
3a1bd924f
|
61 |
{ |
e0be428e6
|
62 |
struct drm_hash_item *entry; |
3a1bd924f
|
63 64 65 66 67 68 69 70 71 72 |
struct hlist_head *h_list; struct hlist_node *list; unsigned int hashed_key; int count = 0; hashed_key = hash_long(key, ht->order); DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x ", key, hashed_key); h_list = &ht->table[hashed_key]; hlist_for_each(list, h_list) { |
e0be428e6
|
73 |
entry = hlist_entry(list, struct drm_hash_item, head); |
3a1bd924f
|
74 75 76 77 |
DRM_DEBUG("count %d, key: 0x%08lx ", count++, entry->key); } } |
bc5f4523f
|
78 |
static struct hlist_node *drm_ht_find_key(struct drm_open_hash *ht, |
3a1bd924f
|
79 80 |
unsigned long key) { |
e0be428e6
|
81 |
struct drm_hash_item *entry; |
3a1bd924f
|
82 83 84 85 86 87 88 |
struct hlist_head *h_list; struct hlist_node *list; unsigned int hashed_key; hashed_key = hash_long(key, ht->order); h_list = &ht->table[hashed_key]; hlist_for_each(list, h_list) { |
e0be428e6
|
89 |
entry = hlist_entry(list, struct drm_hash_item, head); |
3a1bd924f
|
90 91 92 93 94 95 96 |
if (entry->key == key) return list; if (entry->key > key) break; } return NULL; } |
e0be428e6
|
97 |
int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item) |
3a1bd924f
|
98 |
{ |
e0be428e6
|
99 |
struct drm_hash_item *entry; |
3a1bd924f
|
100 101 102 103 104 105 106 107 108 |
struct hlist_head *h_list; struct hlist_node *list, *parent; unsigned int hashed_key; unsigned long key = item->key; hashed_key = hash_long(key, ht->order); h_list = &ht->table[hashed_key]; parent = NULL; hlist_for_each(list, h_list) { |
e0be428e6
|
109 |
entry = hlist_entry(list, struct drm_hash_item, head); |
3a1bd924f
|
110 |
if (entry->key == key) |
47cc14093
|
111 |
return -EINVAL; |
3a1bd924f
|
112 113 114 115 116 117 118 119 120 121 122 |
if (entry->key > key) break; parent = list; } if (parent) { hlist_add_after(parent, &item->head); } else { hlist_add_head(&item->head, h_list); } return 0; } |
a2c0a97b7
|
123 |
EXPORT_SYMBOL(drm_ht_insert_item); |
3a1bd924f
|
124 125 |
/* |
bc5f4523f
|
126 |
* Just insert an item and return any "bits" bit key that hasn't been |
3a1bd924f
|
127 128 |
* used before. */ |
e0be428e6
|
129 |
int drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item, |
3a1bd924f
|
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
unsigned long seed, int bits, int shift, unsigned long add) { int ret; unsigned long mask = (1 << bits) - 1; unsigned long first, unshifted_key; unshifted_key = hash_long(seed, bits); first = unshifted_key; do { item->key = (unshifted_key << shift) + add; ret = drm_ht_insert_item(ht, item); if (ret) unshifted_key = (unshifted_key + 1) & mask; } while(ret && (unshifted_key != first)); if (ret) { DRM_ERROR("Available key bit space exhausted "); return -EINVAL; } return 0; } |
f2cb5d86e
|
153 |
EXPORT_SYMBOL(drm_ht_just_insert_please); |
3a1bd924f
|
154 |
|
e0be428e6
|
155 156 |
int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key, struct drm_hash_item **item) |
3a1bd924f
|
157 158 159 160 161 |
{ struct hlist_node *list; list = drm_ht_find_key(ht, key); if (!list) |
47cc14093
|
162 |
return -EINVAL; |
3a1bd924f
|
163 |
|
e0be428e6
|
164 |
*item = hlist_entry(list, struct drm_hash_item, head); |
3a1bd924f
|
165 166 |
return 0; } |
f2cb5d86e
|
167 |
EXPORT_SYMBOL(drm_ht_find_item); |
3a1bd924f
|
168 |
|
e0be428e6
|
169 |
int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key) |
3a1bd924f
|
170 171 172 173 174 175 |
{ struct hlist_node *list; list = drm_ht_find_key(ht, key); if (list) { hlist_del_init(list); |
3a1bd924f
|
176 177 |
return 0; } |
47cc14093
|
178 |
return -EINVAL; |
3a1bd924f
|
179 |
} |
e0be428e6
|
180 |
int drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item) |
3a1bd924f
|
181 182 |
{ hlist_del_init(&item->head); |
3a1bd924f
|
183 184 |
return 0; } |
a2c0a97b7
|
185 |
EXPORT_SYMBOL(drm_ht_remove_item); |
3a1bd924f
|
186 |
|
e0be428e6
|
187 |
void drm_ht_remove(struct drm_open_hash *ht) |
3a1bd924f
|
188 189 |
{ if (ht->table) { |
7811bddb6
|
190 |
if ((PAGE_SIZE / sizeof(*ht->table)) >> ht->order) |
9a298b2ac
|
191 |
kfree(ht->table); |
7811bddb6
|
192 193 |
else vfree(ht->table); |
3a1bd924f
|
194 195 196 |
ht->table = NULL; } } |
f2cb5d86e
|
197 |
EXPORT_SYMBOL(drm_ht_remove); |