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