drm_hashtab.c 5.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209
  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. #include <linux/export.h>
  35. #include <linux/hash.h>
  36. #include <linux/mm.h>
  37. #include <linux/rculist.h>
  38. #include <linux/slab.h>
  39. #include <linux/vmalloc.h>
  40. #include <drm/drm_hashtab.h>
  41. #include <drm/drm_print.h>
  42. int drm_ht_create(struct drm_open_hash *ht, unsigned int order)
  43. {
  44. unsigned int size = 1 << order;
  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(array_size(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. }
  57. EXPORT_SYMBOL(drm_ht_create);
  58. void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key)
  59. {
  60. struct drm_hash_item *entry;
  61. struct hlist_head *h_list;
  62. unsigned int hashed_key;
  63. int count = 0;
  64. hashed_key = hash_long(key, ht->order);
  65. DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key);
  66. h_list = &ht->table[hashed_key];
  67. hlist_for_each_entry(entry, h_list, head)
  68. DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);
  69. }
  70. static struct hlist_node *drm_ht_find_key(struct drm_open_hash *ht,
  71. unsigned long key)
  72. {
  73. struct drm_hash_item *entry;
  74. struct hlist_head *h_list;
  75. unsigned int hashed_key;
  76. hashed_key = hash_long(key, ht->order);
  77. h_list = &ht->table[hashed_key];
  78. hlist_for_each_entry(entry, h_list, head) {
  79. if (entry->key == key)
  80. return &entry->head;
  81. if (entry->key > key)
  82. break;
  83. }
  84. return NULL;
  85. }
  86. static struct hlist_node *drm_ht_find_key_rcu(struct drm_open_hash *ht,
  87. unsigned long key)
  88. {
  89. struct drm_hash_item *entry;
  90. struct hlist_head *h_list;
  91. unsigned int hashed_key;
  92. hashed_key = hash_long(key, ht->order);
  93. h_list = &ht->table[hashed_key];
  94. hlist_for_each_entry_rcu(entry, h_list, head) {
  95. if (entry->key == key)
  96. return &entry->head;
  97. if (entry->key > key)
  98. break;
  99. }
  100. return NULL;
  101. }
  102. int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item)
  103. {
  104. struct drm_hash_item *entry;
  105. struct hlist_head *h_list;
  106. struct hlist_node *parent;
  107. unsigned int hashed_key;
  108. unsigned long key = item->key;
  109. hashed_key = hash_long(key, ht->order);
  110. h_list = &ht->table[hashed_key];
  111. parent = NULL;
  112. hlist_for_each_entry(entry, h_list, head) {
  113. if (entry->key == key)
  114. return -EINVAL;
  115. if (entry->key > key)
  116. break;
  117. parent = &entry->head;
  118. }
  119. if (parent) {
  120. hlist_add_behind_rcu(&item->head, parent);
  121. } else {
  122. hlist_add_head_rcu(&item->head, h_list);
  123. }
  124. return 0;
  125. }
  126. EXPORT_SYMBOL(drm_ht_insert_item);
  127. /*
  128. * Just insert an item and return any "bits" bit key that hasn't been
  129. * used before.
  130. */
  131. int drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item,
  132. unsigned long seed, int bits, int shift,
  133. unsigned long add)
  134. {
  135. int ret;
  136. unsigned long mask = (1UL << bits) - 1;
  137. unsigned long first, unshifted_key;
  138. unshifted_key = hash_long(seed, bits);
  139. first = unshifted_key;
  140. do {
  141. item->key = (unshifted_key << shift) + add;
  142. ret = drm_ht_insert_item(ht, item);
  143. if (ret)
  144. unshifted_key = (unshifted_key + 1) & mask;
  145. } while(ret && (unshifted_key != first));
  146. if (ret) {
  147. DRM_ERROR("Available key bit space exhausted\n");
  148. return -EINVAL;
  149. }
  150. return 0;
  151. }
  152. EXPORT_SYMBOL(drm_ht_just_insert_please);
  153. int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key,
  154. struct drm_hash_item **item)
  155. {
  156. struct hlist_node *list;
  157. list = drm_ht_find_key_rcu(ht, key);
  158. if (!list)
  159. return -EINVAL;
  160. *item = hlist_entry(list, struct drm_hash_item, head);
  161. return 0;
  162. }
  163. EXPORT_SYMBOL(drm_ht_find_item);
  164. int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key)
  165. {
  166. struct hlist_node *list;
  167. list = drm_ht_find_key(ht, key);
  168. if (list) {
  169. hlist_del_init_rcu(list);
  170. return 0;
  171. }
  172. return -EINVAL;
  173. }
  174. int drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item)
  175. {
  176. hlist_del_init_rcu(&item->head);
  177. return 0;
  178. }
  179. EXPORT_SYMBOL(drm_ht_remove_item);
  180. void drm_ht_remove(struct drm_open_hash *ht)
  181. {
  182. if (ht->table) {
  183. kvfree(ht->table);
  184. ht->table = NULL;
  185. }
  186. }
  187. EXPORT_SYMBOL(drm_ht_remove);