rhashtable-types.h 3.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135
  1. /* SPDX-License-Identifier: GPL-2.0 */
  2. /*
  3. * Resizable, Scalable, Concurrent Hash Table
  4. *
  5. * Simple structures that might be needed in include
  6. * files.
  7. */
  8. #ifndef _LINUX_RHASHTABLE_TYPES_H
  9. #define _LINUX_RHASHTABLE_TYPES_H
  10. #include <linux/atomic.h>
  11. #include <linux/compiler.h>
  12. #include <linux/mutex.h>
  13. #include <linux/workqueue.h>
  14. struct rhash_head {
  15. struct rhash_head __rcu *next;
  16. };
  17. struct rhlist_head {
  18. struct rhash_head rhead;
  19. struct rhlist_head __rcu *next;
  20. };
  21. struct bucket_table;
  22. /**
  23. * struct rhashtable_compare_arg - Key for the function rhashtable_compare
  24. * @ht: Hash table
  25. * @key: Key to compare against
  26. */
  27. struct rhashtable_compare_arg {
  28. struct rhashtable *ht;
  29. const void *key;
  30. };
  31. typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
  32. typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
  33. typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
  34. const void *obj);
  35. /**
  36. * struct rhashtable_params - Hash table construction parameters
  37. * @nelem_hint: Hint on number of elements, should be 75% of desired size
  38. * @key_len: Length of key
  39. * @key_offset: Offset of key in struct to be hashed
  40. * @head_offset: Offset of rhash_head in struct to be hashed
  41. * @max_size: Maximum size while expanding
  42. * @min_size: Minimum size while shrinking
  43. * @automatic_shrinking: Enable automatic shrinking of tables
  44. * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash)
  45. * @obj_hashfn: Function to hash object
  46. * @obj_cmpfn: Function to compare key with object
  47. */
  48. struct rhashtable_params {
  49. u16 nelem_hint;
  50. u16 key_len;
  51. u16 key_offset;
  52. u16 head_offset;
  53. unsigned int max_size;
  54. u16 min_size;
  55. bool automatic_shrinking;
  56. rht_hashfn_t hashfn;
  57. rht_obj_hashfn_t obj_hashfn;
  58. rht_obj_cmpfn_t obj_cmpfn;
  59. };
  60. /**
  61. * struct rhashtable - Hash table handle
  62. * @tbl: Bucket table
  63. * @key_len: Key length for hashfn
  64. * @max_elems: Maximum number of elements in table
  65. * @p: Configuration parameters
  66. * @rhlist: True if this is an rhltable
  67. * @run_work: Deferred worker to expand/shrink asynchronously
  68. * @mutex: Mutex to protect current/future table swapping
  69. * @lock: Spin lock to protect walker list
  70. * @nelems: Number of elements in table
  71. */
  72. struct rhashtable {
  73. struct bucket_table __rcu *tbl;
  74. unsigned int key_len;
  75. unsigned int max_elems;
  76. struct rhashtable_params p;
  77. bool rhlist;
  78. struct work_struct run_work;
  79. struct mutex mutex;
  80. spinlock_t lock;
  81. atomic_t nelems;
  82. };
  83. /**
  84. * struct rhltable - Hash table with duplicate objects in a list
  85. * @ht: Underlying rhtable
  86. */
  87. struct rhltable {
  88. struct rhashtable ht;
  89. };
  90. /**
  91. * struct rhashtable_walker - Hash table walker
  92. * @list: List entry on list of walkers
  93. * @tbl: The table that we were walking over
  94. */
  95. struct rhashtable_walker {
  96. struct list_head list;
  97. struct bucket_table *tbl;
  98. };
  99. /**
  100. * struct rhashtable_iter - Hash table iterator
  101. * @ht: Table to iterate through
  102. * @p: Current pointer
  103. * @list: Current hash list pointer
  104. * @walker: Associated rhashtable walker
  105. * @slot: Current slot
  106. * @skip: Number of entries to skip in slot
  107. */
  108. struct rhashtable_iter {
  109. struct rhashtable *ht;
  110. struct rhash_head *p;
  111. struct rhlist_head *list;
  112. struct rhashtable_walker walker;
  113. unsigned int slot;
  114. unsigned int skip;
  115. bool end_of_table;
  116. };
  117. int rhashtable_init(struct rhashtable *ht,
  118. const struct rhashtable_params *params);
  119. int rhltable_init(struct rhltable *hlt,
  120. const struct rhashtable_params *params);
  121. #endif /* _LINUX_RHASHTABLE_TYPES_H */