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 * Simple open hash tab implementation. 30 * 31 * Authors: 32 * Thomas Hellström <thomas-at-tungstengraphics-dot-com> 33 */ 34 35 #include <drm/drmP.h> 36 #include <drm/drm_hashtab.h> 37 #include <linux/hash.h> 38 #include <linux/slab.h> 39 #include <linux/export.h> 40 41 struct hlist_node * 42 drm_ht_find_key(struct drm_open_hash *, unsigned long); 43 struct hlist_node * 44 drm_ht_find_key_rcu(struct drm_open_hash *, unsigned long); 45 46 int drm_ht_create(struct drm_open_hash *ht, unsigned int order) 47 { 48 printf("%s stub\n", __func__); 49 return -ENOSYS; 50 #ifdef notyet 51 unsigned int size = 1 << order; 52 53 ht->order = order; 54 ht->table = NULL; 55 if (size <= PAGE_SIZE / sizeof(*ht->table)) 56 ht->table = kcalloc(size, sizeof(*ht->table), GFP_KERNEL); 57 else 58 ht->table = vzalloc(size*sizeof(*ht->table)); 59 if (!ht->table) { 60 DRM_ERROR("Out of memory for hash table\n"); 61 return -ENOMEM; 62 } 63 return 0; 64 #endif 65 } 66 EXPORT_SYMBOL(drm_ht_create); 67 68 void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key) 69 { 70 printf("%s stub\n", __func__); 71 #ifdef notyet 72 struct drm_hash_item *entry; 73 struct hlist_head *h_list; 74 unsigned int hashed_key; 75 int count = 0; 76 77 hashed_key = hash_long(key, ht->order); 78 DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key); 79 h_list = &ht->table[hashed_key]; 80 hlist_for_each_entry(entry, h_list, head) 81 DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key); 82 #endif 83 } 84 85 struct hlist_node * 86 drm_ht_find_key(struct drm_open_hash *ht, 87 unsigned long key) 88 { 89 printf("%s stub\n", __func__); 90 return NULL; 91 #ifdef notyet 92 struct drm_hash_item *entry; 93 struct hlist_head *h_list; 94 unsigned int hashed_key; 95 96 hashed_key = hash_long(key, ht->order); 97 h_list = &ht->table[hashed_key]; 98 hlist_for_each_entry(entry, h_list, head) { 99 if (entry->key == key) 100 return &entry->head; 101 if (entry->key > key) 102 break; 103 } 104 return NULL; 105 #endif 106 } 107 108 struct hlist_node * 109 drm_ht_find_key_rcu(struct drm_open_hash *ht, 110 unsigned long key) 111 { 112 printf("%s stub\n", __func__); 113 return NULL; 114 #ifdef notyet 115 struct drm_hash_item *entry; 116 struct hlist_head *h_list; 117 unsigned int hashed_key; 118 119 hashed_key = hash_long(key, ht->order); 120 h_list = &ht->table[hashed_key]; 121 hlist_for_each_entry_rcu(entry, h_list, head) { 122 if (entry->key == key) 123 return &entry->head; 124 if (entry->key > key) 125 break; 126 } 127 return NULL; 128 #endif 129 } 130 131 int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item) 132 { 133 printf("%s stub\n", __func__); 134 return -ENOSYS; 135 #ifdef notyet 136 struct drm_hash_item *entry; 137 struct hlist_head *h_list; 138 struct hlist_node *parent; 139 unsigned int hashed_key; 140 unsigned long key = item->key; 141 142 hashed_key = hash_long(key, ht->order); 143 h_list = &ht->table[hashed_key]; 144 parent = NULL; 145 hlist_for_each_entry(entry, h_list, head) { 146 if (entry->key == key) 147 return -EINVAL; 148 if (entry->key > key) 149 break; 150 parent = &entry->head; 151 } 152 if (parent) { 153 hlist_add_after_rcu(parent, &item->head); 154 } else { 155 hlist_add_head_rcu(&item->head, h_list); 156 } 157 return 0; 158 #endif 159 } 160 EXPORT_SYMBOL(drm_ht_insert_item); 161 162 /* 163 * Just insert an item and return any "bits" bit key that hasn't been 164 * used before. 165 */ 166 int drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item, 167 unsigned long seed, int bits, int shift, 168 unsigned long add) 169 { 170 printf("%s stub\n", __func__); 171 return -ENOSYS; 172 #ifdef notyet 173 int ret; 174 unsigned long mask = (1 << bits) - 1; 175 unsigned long first, unshifted_key; 176 177 unshifted_key = hash_long(seed, bits); 178 first = unshifted_key; 179 do { 180 item->key = (unshifted_key << shift) + add; 181 ret = drm_ht_insert_item(ht, item); 182 if (ret) 183 unshifted_key = (unshifted_key + 1) & mask; 184 } while(ret && (unshifted_key != first)); 185 186 if (ret) { 187 DRM_ERROR("Available key bit space exhausted\n"); 188 return -EINVAL; 189 } 190 return 0; 191 #endif 192 } 193 EXPORT_SYMBOL(drm_ht_just_insert_please); 194 195 int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key, 196 struct drm_hash_item **item) 197 { 198 printf("%s stub\n", __func__); 199 return -ENOSYS; 200 #ifdef notyet 201 struct hlist_node *list; 202 203 list = drm_ht_find_key_rcu(ht, key); 204 if (!list) 205 return -EINVAL; 206 207 *item = hlist_entry(list, struct drm_hash_item, head); 208 return 0; 209 #endif 210 } 211 EXPORT_SYMBOL(drm_ht_find_item); 212 213 int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key) 214 { 215 printf("%s stub\n", __func__); 216 return -ENOSYS; 217 #ifdef notyet 218 struct hlist_node *list; 219 220 list = drm_ht_find_key(ht, key); 221 if (list) { 222 hlist_del_init_rcu(list); 223 return 0; 224 } 225 return -EINVAL; 226 #endif 227 } 228 229 int drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item) 230 { 231 printf("%s stub\n", __func__); 232 return -ENOSYS; 233 #ifdef notyet 234 hlist_del_init_rcu(&item->head); 235 return 0; 236 #endif 237 } 238 EXPORT_SYMBOL(drm_ht_remove_item); 239 240 void drm_ht_remove(struct drm_open_hash *ht) 241 { 242 printf("%s stub\n", __func__); 243 #ifdef notyet 244 if (ht->table) { 245 if ((PAGE_SIZE / sizeof(*ht->table)) >> ht->order) 246 kfree(ht->table); 247 else 248 vfree(ht->table); 249 ht->table = NULL; 250 } 251 #endif 252 } 253 EXPORT_SYMBOL(drm_ht_remove); 254