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