9
3

lf.h 6.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186
  1. /* Copyright (c) 2007, 2010, Oracle and/or its affiliates. All rights reserved.
  2. This program is free software; you can redistribute it and/or modify
  3. it under the terms of the GNU General Public License as published by
  4. the Free Software Foundation; version 2 of the License.
  5. This program is distributed in the hope that it will be useful,
  6. but WITHOUT ANY WARRANTY; without even the implied warranty of
  7. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  8. GNU General Public License for more details.
  9. You should have received a copy of the GNU General Public License
  10. along with this program; if not, write to the Free Software
  11. Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
  12. #ifndef INCLUDE_LF_INCLUDED
  13. #define INCLUDE_LF_INCLUDED
  14. #include <my_atomic.h>
  15. C_MODE_START
  16. /*
  17. wait-free dynamic array, see lf_dynarray.c
  18. 4 levels of 256 elements each mean 4311810304 elements in an array - it
  19. should be enough for a while
  20. */
  21. #define LF_DYNARRAY_LEVEL_LENGTH 256
  22. #define LF_DYNARRAY_LEVELS 4
  23. typedef struct {
  24. void * volatile level[LF_DYNARRAY_LEVELS];
  25. uint size_of_element;
  26. } LF_DYNARRAY;
  27. typedef int (*lf_dynarray_func)(void *, void *);
  28. void lf_dynarray_init(LF_DYNARRAY *array, uint element_size);
  29. void lf_dynarray_destroy(LF_DYNARRAY *array);
  30. void *lf_dynarray_value(LF_DYNARRAY *array, uint idx);
  31. void *lf_dynarray_lvalue(LF_DYNARRAY *array, uint idx);
  32. int lf_dynarray_iterate(LF_DYNARRAY *array, lf_dynarray_func func, void *arg);
  33. /*
  34. pin manager for memory allocator, lf_alloc-pin.c
  35. */
  36. #define LF_PINBOX_PINS 4
  37. #define LF_PURGATORY_SIZE 100
  38. typedef void lf_pinbox_free_func(void *, void *, void*);
  39. typedef struct {
  40. LF_DYNARRAY pinarray;
  41. lf_pinbox_free_func *free_func;
  42. void *free_func_arg;
  43. uint free_ptr_offset;
  44. uint32 volatile pinstack_top_ver; /* this is a versioned pointer */
  45. uint32 volatile pins_in_array; /* number of elements in array */
  46. } LF_PINBOX;
  47. typedef struct {
  48. void * volatile pin[LF_PINBOX_PINS];
  49. LF_PINBOX *pinbox;
  50. void **stack_ends_here;
  51. void *purgatory;
  52. uint32 purgatory_count;
  53. uint32 volatile link;
  54. /* we want sizeof(LF_PINS) to be 128 to avoid false sharing */
  55. char pad[128-sizeof(uint32)*2
  56. -sizeof(LF_PINBOX *)
  57. -sizeof(void*)
  58. -sizeof(void *)*(LF_PINBOX_PINS+1)];
  59. } LF_PINS;
  60. /* compile-time assert to make sure we have enough pins. */
  61. #define lf_pin(PINS, PIN, ADDR) \
  62. do { \
  63. compile_time_assert(PIN < LF_PINBOX_PINS); \
  64. my_atomic_storeptr(&(PINS)->pin[PIN], (ADDR)); \
  65. } while(0)
  66. #define lf_unpin(PINS, PIN) lf_pin(PINS, PIN, NULL)
  67. #define lf_assert_pin(PINS, PIN) assert((PINS)->pin[PIN] != 0)
  68. #define lf_assert_unpin(PINS, PIN) assert((PINS)->pin[PIN] == 0)
  69. void lf_pinbox_init(LF_PINBOX *pinbox, uint free_ptr_offset,
  70. lf_pinbox_free_func *free_func, void * free_func_arg);
  71. void lf_pinbox_destroy(LF_PINBOX *pinbox);
  72. LF_PINS *lf_pinbox_get_pins(LF_PINBOX *pinbox);
  73. void lf_pinbox_put_pins(LF_PINS *pins);
  74. void lf_pinbox_free(LF_PINS *pins, void *addr);
  75. /*
  76. memory allocator, lf_alloc-pin.c
  77. */
  78. typedef struct st_lf_allocator {
  79. LF_PINBOX pinbox;
  80. uchar * volatile top;
  81. uint element_size;
  82. uint32 volatile mallocs;
  83. void (*constructor)(uchar *); /* called, when an object is malloc()'ed */
  84. void (*destructor)(uchar *); /* called, when an object is free()'d */
  85. } LF_ALLOCATOR;
  86. void lf_alloc_init(LF_ALLOCATOR *allocator, uint size, uint free_ptr_offset);
  87. void lf_alloc_destroy(LF_ALLOCATOR *allocator);
  88. uint lf_alloc_pool_count(LF_ALLOCATOR *allocator);
  89. /*
  90. shortcut macros to access underlying pinbox functions from an LF_ALLOCATOR
  91. see lf_pinbox_get_pins() and lf_pinbox_put_pins()
  92. */
  93. #define lf_alloc_free(PINS, PTR) lf_pinbox_free((PINS), (PTR))
  94. #define lf_alloc_get_pins(A) lf_pinbox_get_pins(&(A)->pinbox)
  95. #define lf_alloc_put_pins(PINS) lf_pinbox_put_pins(PINS)
  96. #define lf_alloc_direct_free(ALLOC, ADDR) \
  97. do { \
  98. if ((ALLOC)->destructor) \
  99. (ALLOC)->destructor((uchar*) ADDR); \
  100. my_free(ADDR); \
  101. } while(0)
  102. void *lf_alloc_new(LF_PINS *pins);
  103. C_MODE_END
  104. /*
  105. extendible hash, lf_hash.c
  106. */
  107. #include <hash.h>
  108. C_MODE_START
  109. typedef struct st_lf_hash LF_HASH;
  110. typedef void (*lf_hash_initializer)(LF_HASH *hash, void *dst, const void *src);
  111. #define LF_HASH_UNIQUE 1
  112. /* lf_hash overhead per element (that is, sizeof(LF_SLIST) */
  113. extern const int LF_HASH_OVERHEAD;
  114. struct st_lf_hash {
  115. LF_DYNARRAY array; /* hash itself */
  116. LF_ALLOCATOR alloc; /* allocator for elements */
  117. my_hash_get_key get_key; /* see HASH */
  118. lf_hash_initializer initializer; /* called when an element is inserted */
  119. my_hash_function hash_function; /* see HASH */
  120. CHARSET_INFO *charset; /* see HASH */
  121. uint key_offset, key_length; /* see HASH */
  122. uint element_size; /* size of memcpy'ed area on insert */
  123. uint flags; /* LF_HASH_UNIQUE, etc */
  124. int32 volatile size; /* size of array */
  125. int32 volatile count; /* number of elements in the hash */
  126. };
  127. void lf_hash_init(LF_HASH *hash, uint element_size, uint flags,
  128. uint key_offset, uint key_length, my_hash_get_key get_key,
  129. CHARSET_INFO *charset);
  130. void lf_hash_destroy(LF_HASH *hash);
  131. int lf_hash_insert(LF_HASH *hash, LF_PINS *pins, const void *data);
  132. void *lf_hash_search(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen);
  133. void *lf_hash_search_using_hash_value(LF_HASH *hash, LF_PINS *pins,
  134. my_hash_value_type hash_value,
  135. const void *key, uint keylen);
  136. int lf_hash_delete(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen);
  137. int lf_hash_iterate(LF_HASH *hash, LF_PINS *pins,
  138. my_hash_walk_action action, void *argument);
  139. /*
  140. shortcut macros to access underlying pinbox functions from an LF_HASH
  141. see lf_pinbox_get_pins() and lf_pinbox_put_pins()
  142. */
  143. #define lf_hash_get_pins(HASH) lf_alloc_get_pins(&(HASH)->alloc)
  144. #define lf_hash_put_pins(PINS) lf_pinbox_put_pins(PINS)
  145. #define lf_hash_search_unpin(PINS) lf_unpin((PINS), 2)
  146. /*
  147. cleanup
  148. */
  149. C_MODE_END
  150. #endif