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 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 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 } 82 83 struct hlist_node * 84 drm_ht_find_key(struct drm_open_hash *ht, 85 unsigned long key) 86 { 87 printf("%s stub\n", __func__); 88 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 drm_ht_find_key_rcu(struct drm_open_hash *ht, 108 unsigned long key) 109 { 110 printf("%s stub\n", __func__); 111 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 int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item) 130 { 131 printf("%s stub\n", __func__); 132 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 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 printf("%s stub\n", __func__); 169 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 int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key, 194 struct drm_hash_item **item) 195 { 196 printf("%s stub\n", __func__); 197 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 int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key) 212 { 213 printf("%s stub\n", __func__); 214 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 int drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item) 228 { 229 printf("%s stub\n", __func__); 230 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 void drm_ht_remove(struct drm_open_hash *ht) 239 { 240 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 } 251 EXPORT_SYMBOL(drm_ht_remove); 252