« back to all changes in this revision
Viewing changes to drizzled/tree.cc
- browse files at revision 2479
- compare with another revision
- download diff
- download tarball
- view history from revision 2479
- Committer: Mark Atwood
- Date: 2011-12-27 16:09:18 UTC
- mfrom: (2461.2.1 trunk)
- Revision ID: me@mark.atwood.name-20111227160918-ai7t6ka9s9xlmlbv
resolve and merge lp:~ivolucien/drizzle/trunk-bug-621861
- files added:
- .bzrignore
- files renamed:
- .bzrignore => .bzrignore.THIS
- files modified:
- drizzled/item/sum.cc
added
removed
drizzled/tree.cc
15
15
16
16
/*
17
17
Code for handling red-black (balanced) binary trees.
18
key in tree is allocated accrding to following:
18
key in tree is allocated according to following:
19
19
20
20
1) If size < 0 then tree will not allocate keys and only a pointer to
21
21
each key is saved in tree.
29
29
3) if key_size is given to init_tree then each node will continue the
30
30
key and calls to insert_key may increase length of key.
31
31
if key_size > sizeof(pointer) and key_size is a multiple of 8 (double
32
allign) then key will be put on a 8 alligned adress. Else
33
the key will be on adress (element+1). This is transparent for user
32
align) then key will be put on a 8 aligned address. Else
33
the key will be on address (element+1). This is transparent for user
34
34
compare and search functions uses a pointer to given key-argument.
35
35
36
36
- If you use a free function for tree-elements and you are freeing
48
48
/*
49
49
NOTE:
50
50
tree->compare function should be ALWAYS called as
51
(*tree->compare)(custom_arg, ELEMENT_KEY(tree,element), key)
52
and not other way around, as
53
(*tree->compare)(custom_arg, key, ELEMENT_KEY(tree,element))
51
(*compare)(custom_arg, element_key(element), key)
52
and NOT the other way around, as
53
(*compare)(custom_arg, key, element_key(element))
54
54
*/
55
55
56
56
#include <config.h>
58
58
#include <drizzled/tree.h>
59
59
#include <drizzled/internal/my_sys.h>
60
60
#include <drizzled/internal/m_string.h>
61
#include <drizzled/memory/root.h>
62
61
63
62
#define BLACK 1
64
63
#define RED 0
65
64
#define DEFAULT_ALLOC_SIZE 8192
66
65
#define DEFAULT_ALIGN_SIZE 8192
67
66
68
#define ELEMENT_KEY(tree,element)\
69
(tree->offset_to_key ? (void*)((unsigned char*) element+tree->offset_to_key) :\
70
*((void**) (element+1)))
71
#define ELEMENT_CHILD(element, offs) (*(TREE_ELEMENT**)((char*)element + offs))
72
67
73
68
namespace drizzled
74
69
{
75
70
76
77
static void delete_tree_element(TREE *,TREE_ELEMENT *);
78
static int tree_walk_left_root_right(TREE *,TREE_ELEMENT *,
79
tree_walk_action,void *);
80
static int tree_walk_right_root_left(TREE *,TREE_ELEMENT *,
81
tree_walk_action,void *);
82
static void left_rotate(TREE_ELEMENT **parent,TREE_ELEMENT *leaf);
83
static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf);
84
static void rb_insert(TREE *tree,TREE_ELEMENT ***parent,
85
TREE_ELEMENT *leaf);
86
87
88
void init_tree(TREE *tree, size_t default_alloc_size, uint32_t memory_limit,
89
uint32_t size, qsort_cmp2 compare, bool with_delete,
90
tree_element_free free_element, void *custom_arg)
71
/**
72
* Tree class public methods
73
*/
74
75
void Tree::init_tree(size_t default_alloc_size, uint32_t mem_limit,
76
uint32_t size, qsort_cmp2 compare_callback, bool free_with_tree,
77
tree_element_free free_callback, void *caller_arg)
91
78
{
92
79
if (default_alloc_size < DEFAULT_ALLOC_SIZE)
93
80
default_alloc_size= DEFAULT_ALLOC_SIZE;
94
81
default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
95
memset(&tree->null_element, 0, sizeof(tree->null_element));
96
tree->root= &tree->null_element;
97
tree->compare= compare;
98
tree->size_of_element= size > 0 ? (uint32_t) size : 0;
99
tree->memory_limit= memory_limit;
100
tree->free= free_element;
101
tree->allocated= 0;
102
tree->elements_in_tree= 0;
103
tree->custom_arg = custom_arg;
104
tree->null_element.colour= BLACK;
105
tree->null_element.left=tree->null_element.right= 0;
106
tree->flag= 0;
107
if (!free_element &&
82
memset(&this->null_element, 0, sizeof(this->null_element));
83
root= &this->null_element;
84
compare= compare_callback;
85
size_of_element= size > 0 ? (uint32_t) size : 0;
86
memory_limit= mem_limit;
87
free= free_callback;
88
allocated= 0;
89
elements_in_tree= 0;
90
custom_arg = caller_arg;
91
null_element.colour= BLACK;
92
null_element.left=this->null_element.right= 0;
93
flag= 0;
94
if (!free_callback &&
108
95
(size <= sizeof(void*) || ((uint32_t) size & (sizeof(void*)-1))))
109
96
{
110
97
/*
111
98
We know that the data doesn't have to be aligned (like if the key
112
99
contains a double), so we can store the data combined with the
113
TREE_ELEMENT.
100
Tree_Element.
114
101
*/
115
tree->offset_to_key= sizeof(TREE_ELEMENT); /* Put key after element */
102
offset_to_key= sizeof(Tree_Element); /* Put key after element */
116
103
/* Fix allocation size so that we don't lose any memory */
117
default_alloc_size/= (sizeof(TREE_ELEMENT)+size);
104
default_alloc_size/= (sizeof(Tree_Element)+size);
118
105
if (!default_alloc_size)
119
106
default_alloc_size= 1;
120
default_alloc_size*= (sizeof(TREE_ELEMENT)+size);
107
default_alloc_size*= (sizeof(Tree_Element)+size);
121
108
}
122
109
else
123
110
{
124
tree->offset_to_key= 0; /* use key through pointer */
125
tree->size_of_element+= sizeof(void*);
126
}
127
if (! (tree->with_delete= with_delete))
128
{
129
tree->mem_root.init(default_alloc_size);
130
tree->mem_root.min_malloc= (sizeof(TREE_ELEMENT)+tree->size_of_element);
131
}
132
}
133
134
static void free_tree(TREE *tree, myf free_flags)
135
{
136
if (tree->root) /* If initialized */
137
{
138
if (tree->with_delete)
139
delete_tree_element(tree,tree->root);
140
else
141
{
142
if (tree->free)
143
{
144
if (tree->memory_limit)
145
(*tree->free)(NULL, free_init, tree->custom_arg);
146
delete_tree_element(tree,tree->root);
147
if (tree->memory_limit)
148
(*tree->free)(NULL, free_end, tree->custom_arg);
149
}
150
tree->mem_root.free_root(free_flags);
151
}
152
}
153
tree->root= &tree->null_element;
154
tree->elements_in_tree= 0;
155
tree->allocated= 0;
156
}
157
158
void delete_tree(TREE* tree)
159
{
160
free_tree(tree, MYF(0)); /* free() mem_root if applicable */
161
}
162
163
void reset_tree(TREE* tree)
111
offset_to_key= 0; /* use key through pointer */
112
size_of_element+= sizeof(void*);
113
}
114
if (! (with_delete= free_with_tree))
115
{
116
mem_root.init(default_alloc_size);
117
mem_root.min_malloc= (sizeof(Tree_Element)+size_of_element);
118
}
119
}
120
121
void Tree::delete_tree()
122
{
123
free_tree(MYF(0)); /* free() mem_root if applicable */
124
}
125
126
void Tree::reset_tree()
164
127
{
165
128
/* do not free mem_root, just mark blocks as free */
166
free_tree(tree, MYF(memory::MARK_BLOCKS_FREE));
167
}
168
169
170
static void delete_tree_element(TREE *tree, TREE_ELEMENT *element)
171
{
172
if (element != &tree->null_element)
173
{
174
delete_tree_element(tree,element->left);
175
if (tree->free)
176
(*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
177
delete_tree_element(tree,element->right);
178
if (tree->with_delete)
179
free((char*) element);
180
}
181
}
182
183
184
/*
185
insert, search and delete of elements
186
187
The following should be true:
188
parent[0] = & parent[-1][0]->left ||
189
parent[0] = & parent[-1][0]->right
190
*/
191
192
TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint32_t key_size,
193
void* custom_arg)
129
free_tree(MYF(memory::MARK_BLOCKS_FREE));
130
}
131
132
Tree_Element* Tree::tree_insert(void* key, uint32_t key_size, void* caller_arg)
194
133
{
195
134
int cmp;
196
TREE_ELEMENT *element,***parent;
135
Tree_Element *element,***parent;
197
136
198
parent= tree->parents;
199
*parent = &tree->root; element= tree->root;
137
parent= this->parents;
138
*parent = &this->root; element= this->root;
200
139
for (;;)
201
140
{
202
if (element == &tree->null_element ||
203
(cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
204
key)) == 0)
141
if (element == &this->null_element ||
142
(cmp = (*compare)(caller_arg, element_key(element), key)) == 0)
205
143
break;
206
144
if (cmp < 0)
207
145
{
212
150
*++parent = &element->left; element= element->left;
213
151
}
214
152
}
215
if (element == &tree->null_element)
153
if (element == &this->null_element)
216
154
{
217
size_t alloc_size= sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
218
tree->allocated+= alloc_size;
155
size_t alloc_size= sizeof(Tree_Element)+key_size+this->size_of_element;
156
this->allocated+= alloc_size;
219
157
220
if (tree->memory_limit && tree->elements_in_tree
221
&& tree->allocated > tree->memory_limit)
158
if (this->memory_limit && this->elements_in_tree
159
&& this->allocated > this->memory_limit)
222
160
{
223
reset_tree(tree);
224
return tree_insert(tree, key, key_size, custom_arg);
161
reset_tree();
162
return tree_insert(key, key_size, caller_arg);
225
163
}
226
164
227
key_size+= tree->size_of_element;
228
if (tree->with_delete)
229
element= (TREE_ELEMENT *) malloc(alloc_size);
165
key_size+= this->size_of_element;
166
if (this->with_delete)
167
element= (Tree_Element *) malloc(alloc_size);
230
168
else
231
element= (TREE_ELEMENT *) tree->mem_root.alloc(alloc_size);
169
element= (Tree_Element *) this->mem_root.alloc(alloc_size);
232
170
**parent= element;
233
element->left= element->right= &tree->null_element;
234
if (!tree->offset_to_key)
171
element->left= element->right= &this->null_element;
172
if (!this->offset_to_key)
235
173
{
236
174
if (key_size == sizeof(void*)) /* no length, save pointer */
237
175
*((void**) (element+1))= key;
242
180
}
243
181
}
244
182
else
245
memcpy((unsigned char*) element + tree->offset_to_key, key, key_size);
183
memcpy((unsigned char*) element + this->offset_to_key, key, key_size);
246
184
element->count= 1; /* May give warning in purify */
247
tree->elements_in_tree++;
248
rb_insert(tree,parent,element); /* rebalance tree */
185
this->elements_in_tree++;
186
rb_insert(parent,element); /* rebalance tree */
249
187
}
250
188
else
251
189
{
252
if (tree->flag & TREE_NO_DUPS)
190
if (this->flag & TREE_NO_DUPS)
253
191
return(NULL);
254
192
element->count++;
255
193
/* Avoid a wrap over of the count. */
260
198
return element;
261
199
}
262
200
263
void *tree_search_key(TREE *tree, const void *key,
264
TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
265
enum ha_rkey_function flag, void *custom_arg)
266
{
267
TREE_ELEMENT *element= tree->root;
268
TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
269
TREE_ELEMENT **last_equal_element= NULL;
270
271
/*
272
TODO: support for HA_READ_KEY_OR_PREV, HA_READ_PREFIX flags if needed.
273
*/
274
275
*parents = &tree->null_element;
276
while (element != &tree->null_element)
277
{
278
int cmp;
279
280
*++parents= element;
281
282
if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
283
key)) == 0)
284
{
285
switch (flag) {
286
case HA_READ_KEY_EXACT:
287
case HA_READ_KEY_OR_NEXT:
288
case HA_READ_BEFORE_KEY:
289
last_equal_element= parents;
290
cmp= 1;
291
break;
292
case HA_READ_AFTER_KEY:
293
cmp= -1;
294
break;
295
case HA_READ_PREFIX_LAST:
296
case HA_READ_PREFIX_LAST_OR_PREV:
297
last_equal_element= parents;
298
cmp= -1;
299
break;
300
default:
301
return NULL;
302
}
303
}
304
if (cmp < 0) /* element < key */
305
{
306
last_right_step_parent= parents;
307
element= element->right;
308
}
309
else
310
{
311
last_left_step_parent= parents;
312
element= element->left;
313
}
314
}
315
switch (flag) {
316
case HA_READ_KEY_EXACT:
317
case HA_READ_PREFIX_LAST:
318
*last_pos= last_equal_element;
319
break;
320
case HA_READ_KEY_OR_NEXT:
321
*last_pos= last_equal_element ? last_equal_element : last_left_step_parent;
322
break;
323
case HA_READ_AFTER_KEY:
324
*last_pos= last_left_step_parent;
325
break;
326
case HA_READ_PREFIX_LAST_OR_PREV:
327
*last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
328
break;
329
case HA_READ_BEFORE_KEY:
330
*last_pos= last_right_step_parent;
331
break;
332
default:
333
return NULL;
334
}
335
336
return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
337
}
338
339
void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
340
int r_offs)
341
{
342
TREE_ELEMENT *x= **last_pos;
343
344
if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
345
{
346
x= ELEMENT_CHILD(x, r_offs);
347
*++*last_pos= x;
348
while (ELEMENT_CHILD(x, l_offs) != &tree->null_element)
349
{
350
x= ELEMENT_CHILD(x, l_offs);
351
*++*last_pos= x;
352
}
353
return ELEMENT_KEY(tree, x);
354
}
355
else
356
{
357
TREE_ELEMENT *y= *--*last_pos;
358
while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs))
359
{
360
x= y;
361
y= *--*last_pos;
362
}
363
return y == &tree->null_element ? NULL : ELEMENT_KEY(tree, y);
364
}
365
}
366
367
/*
368
Expected that tree is fully balanced
369
(each path from root to leaf has the same length)
370
*/
371
ha_rows tree_record_pos(TREE *tree, const void *key,
372
enum ha_rkey_function flag, void *custom_arg)
373
{
374
TREE_ELEMENT *element= tree->root;
375
double left= 1;
376
double right= tree->elements_in_tree;
377
378
while (element != &tree->null_element)
379
{
380
int cmp;
381
382
if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
383
key)) == 0)
384
{
385
switch (flag) {
386
case HA_READ_KEY_EXACT:
387
case HA_READ_BEFORE_KEY:
388
cmp= 1;
389
break;
390
case HA_READ_AFTER_KEY:
391
cmp= -1;
392
break;
393
default:
394
return HA_POS_ERROR;
395
}
396
}
397
if (cmp < 0) /* element < key */
398
{
399
element= element->right;
400
left= (left + right) / 2;
401
}
402
else
403
{
404
element= element->left;
405
right= (left + right) / 2;
406
}
407
}
408
409
switch (flag) {
410
case HA_READ_KEY_EXACT:
411
case HA_READ_BEFORE_KEY:
412
return (ha_rows) right;
413
case HA_READ_AFTER_KEY:
414
return (ha_rows) left;
415
default:
416
return HA_POS_ERROR;
417
}
418
}
419
420
int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
421
{
422
switch (visit) {
423
case left_root_right:
424
return tree_walk_left_root_right(tree,tree->root,action,argument);
425
case right_root_left:
426
return tree_walk_right_root_left(tree,tree->root,action,argument);
201
int Tree::tree_walk(tree_walk_action action, void *argument, TREE_WALK visit)
202
{
203
switch (visit) {
204
case left_root_right:
205
return tree_walk_left_root_right(root,action,argument);
206
case right_root_left:
207
return tree_walk_right_root_left(root,action,argument);
427
208
}
428
209
429
210
return 0; /* Keep gcc happy */
430
211
}
431
212
432
static int tree_walk_left_root_right(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
213
/**
214
* Tree class private methods
215
*/
216
217
void Tree::free_tree(myf free_flags)
218
{
219
if (root) /* If initialized */
220
{
221
if (with_delete)
222
delete_tree_element(root);
223
else
224
{
225
if (free)
226
{
227
if (memory_limit)
228
(*free)(NULL, free_init, custom_arg);
229
delete_tree_element(root);
230
if (memory_limit)
231
(*free)(NULL, free_end, custom_arg);
232
}
233
mem_root.free_root(free_flags);
234
}
235
}
236
root= &null_element;
237
elements_in_tree= 0;
238
allocated= 0;
239
}
240
241
void* Tree::element_key(Tree_Element* element)
242
{
243
return offset_to_key ? (void*)((unsigned char*) element + offset_to_key)
244
: *((void**)(element + 1));
245
}
246
247
void Tree::delete_tree_element(Tree_Element *element)
248
{
249
if (element != &null_element)
250
{
251
delete_tree_element(element->left);
252
if (free)
253
(*free)(element_key(element), free_free, custom_arg);
254
delete_tree_element(element->right);
255
if (with_delete)
256
delete element;
257
}
258
}
259
260
int Tree::tree_walk_left_root_right(Tree_Element *element, tree_walk_action action, void *argument)
433
261
{
434
262
int error;
435
263
if (element->left) /* Not null_element */
436
264
{
437
if ((error=tree_walk_left_root_right(tree,element->left,action,
265
if ((error=tree_walk_left_root_right(element->left,action,
438
266
argument)) == 0 &&
439
(error=(*action)(ELEMENT_KEY(tree,element),
440
element->count,
441
argument)) == 0)
442
error=tree_walk_left_root_right(tree,element->right,action,argument);
267
(error=(*action)(element_key(element), element->count, argument)) == 0)
268
error=tree_walk_left_root_right(element->right,action,argument);
443
269
return error;
444
270
}
445
271
446
272
return 0;
447
273
}
448
274
449
static int tree_walk_right_root_left(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
275
int Tree::tree_walk_right_root_left(Tree_Element *element, tree_walk_action action, void *argument)
450
276
{
451
277
int error;
452
278
if (element->right) /* Not null_element */
453
279
{
454
if ((error=tree_walk_right_root_left(tree,element->right,action,
280
if ((error=tree_walk_right_root_left(element->right,action,
455
281
argument)) == 0 &&
456
(error=(*action)(ELEMENT_KEY(tree,element),
282
(error=(*action)(element_key(element),
457
283
element->count,
458
284
argument)) == 0)
459
error=tree_walk_right_root_left(tree,element->left,action,argument);
285
error=tree_walk_right_root_left(element->left,action,argument);
460
286
return error;
461
287
}
462
288
463
289
return 0;
464
290
}
465
291
466
467
/* Functions to fix up the tree after insert and delete */
468
469
static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
292
void Tree::left_rotate(Tree_Element **parent, Tree_Element *element)
470
293
{
471
TREE_ELEMENT *y;
294
Tree_Element *y;
472
295
473
y= leaf->right;
474
leaf->right= y->left;
296
y= element->right;
297
element->right= y->left;
475
298
parent[0]= y;
476
y->left= leaf;
299
y->left= element;
477
300
}
478
301
479
static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
302
void Tree::right_rotate(Tree_Element **parent, Tree_Element *element)
480
303
{
481
TREE_ELEMENT *x;
304
Tree_Element *x;
482
305
483
x= leaf->left;
484
leaf->left= x->right;
306
x= element->left;
307
element->left= x->right;
485
308
parent[0]= x;
486
x->right= leaf;
309
x->right= element;
487
310
}
488
311
489
static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
312
void Tree::rb_insert(Tree_Element ***parent, Tree_Element *element)
490
313
{
491
TREE_ELEMENT *y,*par,*par2;
314
Tree_Element *y,*par,*par2;
492
315
493
leaf->colour=RED;
494
while (leaf != tree->root && (par=parent[-1][0])->colour == RED)
316
element->colour=RED;
317
while (element != root && (par=parent[-1][0])->colour == RED)
495
318
{
496
319
if (par == (par2=parent[-2][0])->left)
497
320
{
500
323
{
501
324
par->colour= BLACK;
502
325
y->colour= BLACK;
503
leaf= par2;
326
element= par2;
504
327
parent-= 2;
505
leaf->colour= RED; /* And the loop continues */
328
element->colour= RED; /* And the loop continues */
506
329
}
507
330
else
508
331
{
509
if (leaf == par->right)
332
if (element == par->right)
510
333
{
511
334
left_rotate(parent[-1],par);
512
par= leaf; /* leaf is now parent to old leaf */
335
par= element; /* element is now parent to old element */
513
336
}
514
337
par->colour= BLACK;
515
338
par2->colour= RED;
524
347
{
525
348
par->colour= BLACK;
526
349
y->colour= BLACK;
527
leaf= par2;
350
element= par2;
528
351
parent-= 2;
529
leaf->colour= RED; /* And the loop continues */
352
element->colour= RED; /* And the loop continues */
530
353
}
531
354
else
532
355
{
533
if (leaf == par->left)
356
if (element == par->left)
534
357
{
535
358
right_rotate(parent[-1],par);
536
par= leaf;
359
par= element;
537
360
}
538
361
par->colour= BLACK;
539
362
par2->colour= RED;
542
365
}
543
366
}
544
367
}
545
tree->root->colour=BLACK;
368
root->colour=BLACK;
546
369
}
547
370
548
371
} /* namespace drizzled */
Loggerhead is a web-based interface for Breezy
Version: 2.0.1