Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
drm_hashtab.c
Go to the documentation of this file.
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 int drm_ht_create(struct drm_open_hash *ht, unsigned int order)
42 {
43  unsigned int size = 1 << order;
44 
45  ht->order = order;
46  ht->table = NULL;
47  if (size <= PAGE_SIZE / sizeof(*ht->table))
48  ht->table = kcalloc(size, sizeof(*ht->table), GFP_KERNEL);
49  else
50  ht->table = vzalloc(size*sizeof(*ht->table));
51  if (!ht->table) {
52  DRM_ERROR("Out of memory for hash table\n");
53  return -ENOMEM;
54  }
55  return 0;
56 }
58 
59 void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key)
60 {
61  struct drm_hash_item *entry;
62  struct hlist_head *h_list;
63  struct hlist_node *list;
64  unsigned int hashed_key;
65  int count = 0;
66 
67  hashed_key = hash_long(key, ht->order);
68  DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key);
69  h_list = &ht->table[hashed_key];
70  hlist_for_each(list, h_list) {
71  entry = hlist_entry(list, struct drm_hash_item, head);
72  DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);
73  }
74 }
75 
76 static struct hlist_node *drm_ht_find_key(struct drm_open_hash *ht,
77  unsigned long key)
78 {
79  struct drm_hash_item *entry;
80  struct hlist_head *h_list;
81  struct hlist_node *list;
82  unsigned int hashed_key;
83 
84  hashed_key = hash_long(key, ht->order);
85  h_list = &ht->table[hashed_key];
86  hlist_for_each(list, h_list) {
87  entry = hlist_entry(list, struct drm_hash_item, head);
88  if (entry->key == key)
89  return list;
90  if (entry->key > key)
91  break;
92  }
93  return NULL;
94 }
95 
96 
98 {
99  struct drm_hash_item *entry;
100  struct hlist_head *h_list;
101  struct hlist_node *list, *parent;
102  unsigned int hashed_key;
103  unsigned long key = item->key;
104 
105  hashed_key = hash_long(key, ht->order);
106  h_list = &ht->table[hashed_key];
107  parent = NULL;
108  hlist_for_each(list, h_list) {
109  entry = hlist_entry(list, struct drm_hash_item, head);
110  if (entry->key == key)
111  return -EINVAL;
112  if (entry->key > key)
113  break;
114  parent = list;
115  }
116  if (parent) {
117  hlist_add_after(parent, &item->head);
118  } else {
119  hlist_add_head(&item->head, h_list);
120  }
121  return 0;
122 }
124 
125 /*
126  * Just insert an item and return any "bits" bit key that hasn't been
127  * used before.
128  */
130  unsigned long seed, int bits, int shift,
131  unsigned long add)
132 {
133  int ret;
134  unsigned long mask = (1 << bits) - 1;
135  unsigned long first, unshifted_key;
136 
137  unshifted_key = hash_long(seed, bits);
138  first = unshifted_key;
139  do {
140  item->key = (unshifted_key << shift) + add;
141  ret = drm_ht_insert_item(ht, item);
142  if (ret)
143  unshifted_key = (unshifted_key + 1) & mask;
144  } while(ret && (unshifted_key != first));
145 
146  if (ret) {
147  DRM_ERROR("Available key bit space exhausted\n");
148  return -EINVAL;
149  }
150  return 0;
151 }
153 
154 int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key,
155  struct drm_hash_item **item)
156 {
157  struct hlist_node *list;
158 
159  list = drm_ht_find_key(ht, key);
160  if (!list)
161  return -EINVAL;
162 
163  *item = hlist_entry(list, struct drm_hash_item, head);
164  return 0;
165 }
167 
168 int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key)
169 {
170  struct hlist_node *list;
171 
172  list = drm_ht_find_key(ht, key);
173  if (list) {
174  hlist_del_init(list);
175  return 0;
176  }
177  return -EINVAL;
178 }
179 
181 {
182  hlist_del_init(&item->head);
183  return 0;
184 }
186 
187 void drm_ht_remove(struct drm_open_hash *ht)
188 {
189  if (ht->table) {
190  if ((PAGE_SIZE / sizeof(*ht->table)) >> ht->order)
191  kfree(ht->table);
192  else
193  vfree(ht->table);
194  ht->table = NULL;
195  }
196 }