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-1301 USA */
15
16#ifndef INCLUDE_LF_INCLUDED
17#define INCLUDE_LF_INCLUDED
18
19#include <my_atomic.h>
20#include <my_cpu.h>
21
22C_MODE_START
23
24/*
25 wait-free dynamic array, see lf_dynarray.c
26
27 4 levels of 256 elements each mean 4311810304 elements in an array - it
28 should be enough for a while
29*/
30#define LF_DYNARRAY_LEVEL_LENGTH 256
31#define LF_DYNARRAY_LEVELS 4
32
33typedef struct {
34 void * volatile level[LF_DYNARRAY_LEVELS];
35 uint size_of_element;
36} LF_DYNARRAY;
37
38typedef int (*lf_dynarray_func)(void *, void *);
39
40void lf_dynarray_init(LF_DYNARRAY *array, uint element_size);
41void lf_dynarray_destroy(LF_DYNARRAY *array);
42
43void *lf_dynarray_value(LF_DYNARRAY *array, uint idx);
44void *lf_dynarray_lvalue(LF_DYNARRAY *array, uint idx);
45int lf_dynarray_iterate(LF_DYNARRAY *array, lf_dynarray_func func, void *arg);
46
47/*
48 pin manager for memory allocator, lf_alloc-pin.c
49*/
50
51#define LF_PINBOX_PINS 4
52#define LF_PURGATORY_SIZE 100
53
54typedef void lf_pinbox_free_func(void *, void *, void*);
55
56typedef struct {
57 LF_DYNARRAY pinarray;
58 lf_pinbox_free_func *free_func;
59 void *free_func_arg;
60 uint free_ptr_offset;
61 uint32 volatile pinstack_top_ver; /* this is a versioned pointer */
62 uint32 volatile pins_in_array; /* number of elements in array */
63} LF_PINBOX;
64
65typedef struct {
66 void * volatile pin[LF_PINBOX_PINS];
67 LF_PINBOX *pinbox;
68 void **stack_ends_here;
69 void *purgatory;
70 uint32 purgatory_count;
71 uint32 volatile link;
72 /* avoid false sharing */
73 char pad[CPU_LEVEL1_DCACHE_LINESIZE];
74} LF_PINS;
75
76/* compile-time assert to make sure we have enough pins. */
77#define lf_pin(PINS, PIN, ADDR) \
78 do { \
79 compile_time_assert(PIN < LF_PINBOX_PINS); \
80 my_atomic_storeptr(&(PINS)->pin[PIN], (ADDR)); \
81 } while(0)
82
83#define lf_unpin(PINS, PIN) lf_pin(PINS, PIN, NULL)
84#define lf_assert_pin(PINS, PIN) assert((PINS)->pin[PIN] != 0)
85#define lf_assert_unpin(PINS, PIN) assert((PINS)->pin[PIN] == 0)
86
87void lf_pinbox_init(LF_PINBOX *pinbox, uint free_ptr_offset,
88 lf_pinbox_free_func *free_func, void * free_func_arg);
89void lf_pinbox_destroy(LF_PINBOX *pinbox);
90
91LF_PINS *lf_pinbox_get_pins(LF_PINBOX *pinbox);
92void lf_pinbox_put_pins(LF_PINS *pins);
93void lf_pinbox_free(LF_PINS *pins, void *addr);
94
95/*
96 memory allocator, lf_alloc-pin.c
97*/
98
99typedef struct st_lf_allocator {
100 LF_PINBOX pinbox;
101 uchar * volatile top;
102 uint element_size;
103 uint32 volatile mallocs;
104 void (*constructor)(uchar *); /* called, when an object is malloc()'ed */
105 void (*destructor)(uchar *); /* called, when an object is free()'d */
106} LF_ALLOCATOR;
107
108void lf_alloc_init(LF_ALLOCATOR *allocator, uint size, uint free_ptr_offset);
109void lf_alloc_destroy(LF_ALLOCATOR *allocator);
110uint lf_alloc_pool_count(LF_ALLOCATOR *allocator);
111/*
112 shortcut macros to access underlying pinbox functions from an LF_ALLOCATOR
113 see lf_pinbox_get_pins() and lf_pinbox_put_pins()
114*/
115#define lf_alloc_free(PINS, PTR) lf_pinbox_free((PINS), (PTR))
116#define lf_alloc_get_pins(A) lf_pinbox_get_pins(&(A)->pinbox)
117#define lf_alloc_put_pins(PINS) lf_pinbox_put_pins(PINS)
118#define lf_alloc_direct_free(ALLOC, ADDR) \
119 do { \
120 if ((ALLOC)->destructor) \
121 (ALLOC)->destructor((uchar*) ADDR); \
122 my_free(ADDR); \
123 } while(0)
124
125void *lf_alloc_new(LF_PINS *pins);
126
127C_MODE_END
128
129/*
130 extendible hash, lf_hash.c
131*/
132#include <hash.h>
133
134C_MODE_START
135
136typedef struct st_lf_hash LF_HASH;
137typedef void (*lf_hash_initializer)(LF_HASH *hash, void *dst, const void *src);
138
139#define LF_HASH_UNIQUE 1
140
141/* lf_hash overhead per element (that is, sizeof(LF_SLIST) */
142extern const int LF_HASH_OVERHEAD;
143
144struct st_lf_hash {
145 LF_DYNARRAY array; /* hash itself */
146 LF_ALLOCATOR alloc; /* allocator for elements */
147 my_hash_get_key get_key; /* see HASH */
148 lf_hash_initializer initializer; /* called when an element is inserted */
149 my_hash_function hash_function; /* see HASH */
150 CHARSET_INFO *charset; /* see HASH */
151 uint key_offset, key_length; /* see HASH */
152 uint element_size; /* size of memcpy'ed area on insert */
153 uint flags; /* LF_HASH_UNIQUE, etc */
154 int32 volatile size; /* size of array */
155 int32 volatile count; /* number of elements in the hash */
156};
157
158void lf_hash_init(LF_HASH *hash, uint element_size, uint flags,
159 uint key_offset, uint key_length, my_hash_get_key get_key,
160 CHARSET_INFO *charset);
161void lf_hash_destroy(LF_HASH *hash);
162int lf_hash_insert(LF_HASH *hash, LF_PINS *pins, const void *data);
163void *lf_hash_search(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen);
164void *lf_hash_search_using_hash_value(LF_HASH *hash, LF_PINS *pins,
165 my_hash_value_type hash_value,
166 const void *key, uint keylen);
167int lf_hash_delete(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen);
168int lf_hash_iterate(LF_HASH *hash, LF_PINS *pins,
169 my_hash_walk_action action, void *argument);
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
181C_MODE_END
182
183#endif
184
185