1 /* $OpenBSD: drm_hashtab.c,v 1.2 2014/03/09 11:07:18 jsg 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 int drm_ht_create(struct drm_open_hash *ht, unsigned int order) 45 { 46 printf("%s stub\n", __func__); 47 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 void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key) 67 { 68 printf("%s stub\n", __func__); 69 #ifdef notyet 70 struct drm_hash_item *entry; 71 struct hlist_head *h_list; 72 struct hlist_node *list; 73 unsigned int hashed_key; 74 int count = 0; 75 76 hashed_key = hash_long(key, ht->order); 77 DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key); 78 h_list = &ht->table[hashed_key]; 79 hlist_for_each_entry(entry, list, h_list, head) 80 DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key); 81 #endif 82 } 83 84 struct hlist_node * 85 drm_ht_find_key(struct drm_open_hash *ht, 86 unsigned long key) 87 { 88 printf("%s stub\n", __func__); 89 return NULL; 90 #ifdef notyet 91 struct drm_hash_item *entry; 92 struct hlist_head *h_list; 93 struct hlist_node *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, list, h_list, head) { 99 if (entry->key == key) 100 return list; 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 struct hlist_node *list; 118 unsigned int hashed_key; 119 120 hashed_key = hash_long(key, ht->order); 121 h_list = &ht->table[hashed_key]; 122 hlist_for_each_entry_rcu(entry, list, h_list, head) { 123 if (entry->key == key) 124 return list; 125 if (entry->key > key) 126 break; 127 } 128 return NULL; 129 #endif 130 } 131 132 int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item) 133 { 134 printf("%s stub\n", __func__); 135 return -ENOSYS; 136 #ifdef notyet 137 struct drm_hash_item *entry; 138 struct hlist_head *h_list; 139 struct hlist_node *list, *parent; 140 unsigned int hashed_key; 141 unsigned long key = item->key; 142 143 hashed_key = hash_long(key, ht->order); 144 h_list = &ht->table[hashed_key]; 145 parent = NULL; 146 hlist_for_each_entry(entry, list, h_list, head) { 147 if (entry->key == key) 148 return -EINVAL; 149 if (entry->key > key) 150 break; 151 parent = list; 152 } 153 if (parent) { 154 hlist_add_after_rcu(parent, &item->head); 155 } else { 156 hlist_add_head_rcu(&item->head, h_list); 157 } 158 return 0; 159 #endif 160 } 161 EXPORT_SYMBOL(drm_ht_insert_item); 162 163 /* 164 * Just insert an item and return any "bits" bit key that hasn't been 165 * used before. 166 */ 167 int drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item, 168 unsigned long seed, int bits, int shift, 169 unsigned long add) 170 { 171 printf("%s stub\n", __func__); 172 return -ENOSYS; 173 #ifdef notyet 174 int ret; 175 unsigned long mask = (1 << bits) - 1; 176 unsigned long first, unshifted_key; 177 178 unshifted_key = hash_long(seed, bits); 179 first = unshifted_key; 180 do { 181 item->key = (unshifted_key << shift) + add; 182 ret = drm_ht_insert_item(ht, item); 183 if (ret) 184 unshifted_key = (unshifted_key + 1) & mask; 185 } while(ret && (unshifted_key != first)); 186 187 if (ret) { 188 DRM_ERROR("Available key bit space exhausted\n"); 189 return -EINVAL; 190 } 191 return 0; 192 #endif 193 } 194 EXPORT_SYMBOL(drm_ht_just_insert_please); 195 196 int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key, 197 struct drm_hash_item **item) 198 { 199 printf("%s stub\n", __func__); 200 return -ENOSYS; 201 #ifdef notyet 202 struct hlist_node *list; 203 204 list = drm_ht_find_key_rcu(ht, key); 205 if (!list) 206 return -EINVAL; 207 208 *item = hlist_entry(list, struct drm_hash_item, head); 209 return 0; 210 #endif 211 } 212 EXPORT_SYMBOL(drm_ht_find_item); 213 214 int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key) 215 { 216 printf("%s stub\n", __func__); 217 return -ENOSYS; 218 #ifdef notyet 219 struct hlist_node *list; 220 221 list = drm_ht_find_key(ht, key); 222 if (list) { 223 hlist_del_init_rcu(list); 224 return 0; 225 } 226 return -EINVAL; 227 #endif 228 } 229 230 int drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item) 231 { 232 printf("%s stub\n", __func__); 233 return -ENOSYS; 234 #ifdef notyet 235 hlist_del_init_rcu(&item->head); 236 return 0; 237 #endif 238 } 239 EXPORT_SYMBOL(drm_ht_remove_item); 240 241 void drm_ht_remove(struct drm_open_hash *ht) 242 { 243 printf("%s stub\n", __func__); 244 #ifdef notyet 245 if (ht->table) { 246 if ((PAGE_SIZE / sizeof(*ht->table)) >> ht->order) 247 kfree(ht->table); 248 else 249 vfree(ht->table); 250 ht->table = NULL; 251 } 252 #endif 253 } 254 EXPORT_SYMBOL(drm_ht_remove); 255