00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #ifndef BPT_H
00012 #define BPT_H
00013
00014
00015
00016
00017
00018 #ifndef __LSEOS_COMPLIANT__
00019 # include <sys/types.h>
00020 # include <string.h>
00021 # include <stdio.h>
00022 #endif
00023
00024
00025
00026
00027
00028 #define BPT_VERSION "1.9"
00029
00030
00031
00032
00033
00034 #define BPT_INIT_HEIGHT 0x1
00035 #define BPT_INIT_NIKEYS 0x2
00036 #define BPT_INIT_NLKEYS 0x2
00037
00038
00039
00040
00041
00042 #define BPT_NDI_T signed int
00043 #define BPT_UNI_T signed int
00044 #define BPT_OPTS_T unsigned char
00045 #define BPT_CB_T unsigned char
00046 #define BPT_TYPE_T unsigned char
00047 #define BPT_FLAGS_T unsigned char
00048 #define BPT_BLKSZ_T unsigned int
00049 #define BPT_NODES_T unsigned int
00050 #define BPT_HEIGHT_T unsigned short
00051
00052
00053
00054
00055
00056 typedef BPT_CB_T t_bpt_cb;
00057 typedef BPT_OPTS_T t_bpt_opts;
00058 typedef BPT_TYPE_T t_bpt_type;
00059 typedef BPT_FLAGS_T t_bpt_flags;
00060
00061
00062
00063
00064
00065 #define BPT_OPT_ZERO 0x0
00066
00067 #define BPT_OPT_TREE 0x1
00068 #define BPT_OPT_NODE 0x2
00069
00070 #define BPT_OPT_HEAD 0x1
00071 #define BPT_OPT_TAIL 0x2
00072
00073 #define BPT_OPT_KEY 0x1
00074 #define BPT_OPT_PARENT 0x2
00075
00076 #define BPT_OPT_PERFECT 0x1
00077 #define BPT_OPT_PARTIAL 0x2
00078 #define BPT_OPT_COLLIDE 0x4
00079
00080 #define BPT_OPT_NONDI(T) (t_bpt_ndi_##T)0x0
00081 #define BPT_OPT_NOKEY(T) (t_bpt_key_##T)0x0
00082 #define BPT_OPT_NOVALUE(T) (t_bpt_addr_##T)0x0
00083
00084 #define BPT_OPT_INIT 0x1
00085 #define BPT_OPT_ADD 0x2
00086 #define BPT_OPT_MODIFY 0x3
00087 #define BPT_OPT_REMOVE 0x4
00088 #define BPT_OPT_CLEAN 0x5
00089
00090
00091
00092
00093
00094 #define BPT_CB_UNKNOWN 0x0
00095 #define BPT_CB_INSERT 0x1
00096 #define BPT_CB_SPLIT 0x2
00097 #define BPT_CB_MODIFY 0x3
00098 #define BPT_CB_DELETE 0x4
00099 #define BPT_CB_MIGRATE 0x5
00100 #define BPT_CB_BALANCE 0x6
00101
00102
00103
00104
00105
00106 #define BPT_FLAG_ZERO 0x0
00107 #define BPT_FLAG_CALLBACK 0x1
00108 #define BPT_FLAG_COLLIDE 0x2
00109
00110
00111
00112
00113
00114 #define BPT_TYPE_INTERNAL 0x1
00115 #define BPT_TYPE_LEAF 0x2
00116
00117
00118
00119
00120
00121 #ifdef BPT_DEBUG
00122 #define bpt_debug(fmt...) \
00123 { \
00124 fprintf(stderr, "[%s:%u] ", __FILE__, __LINE__); \
00125 fprintf(stderr, fmt); \
00126 }
00127
00128 #else
00129 #define bpt_debug(fmt...)
00130 #endif
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146 #define BPT_INIT_ALLOC() \
00147 (1)
00148
00149 #define BPT_ADD_ALLOC(_bpt_) \
00150 ((_bpt_)->height + 1)
00151
00152 #define BPT_REMOVE_ALLOC(_bpt_) \
00153 (0)
00154
00155 #define BPT_MODIFY_ALLOC(_bpt_) \
00156 (BPT_ADD_ALLOC(_bpt_) + BPT_REMOVE_ALLOC(_bpt_))
00157
00158 #define BPT_CLEAN_ALLOC(_bpt_) \
00159 (0)
00160
00161
00162
00163
00164
00165
00166 #define BPT_INIT_SIZE() \
00167 (1)
00168
00169 #define BPT_ADD_SIZE(_bpt_) \
00170 ((_bpt_)->height + 1)
00171
00172 #define BPT_REMOVE_SIZE(_bpt_) \
00173 ((_bpt_)->height * ((_bpt_)->height - 1) + 1)
00174
00175 #define BPT_MODIFY_SIZE(_bpt_) \
00176 (BPT_ADD_SIZE(_bpt_) + BPT_REMOVE_SIZE(_bpt_))
00177
00178 #define BPT_CLEAN_SIZE(_bpt_) \
00179 ((_bpt_)->nodes)
00180
00181
00182
00183
00184
00185 #define t_bpt_key(T) \
00186 t_bpt_key_##T
00187
00188 #define t_bpt_addr(T) \
00189 t_bpt_addr_##T
00190
00191 #define t_bpt_ndi(T) \
00192 t_bpt_ndi_##T
00193
00194 #define t_bpt_uni(T) \
00195 t_bpt_uni_##T
00196
00197 #define t_bpt_blksz(T) \
00198 t_bpt_blksz_##T
00199
00200 #define t_bpt_nodes(T) \
00201 t_bpt_nodes_##T
00202
00203 #define t_bpt_height(T) \
00204 t_bpt_height_##T
00205
00206 #define t_bpt_node(T) \
00207 t_bpt_node_##T
00208
00209 #define t_bpt_imm(T) \
00210 t_bpt_imm_##T
00211
00212 #define t_bpt(T) \
00213 t_bpt_##T
00214
00215 #define t_bpt_cbctx(T) \
00216 t_bpt_cbctx_##T
00217
00218 #define t_bpt_unused(T) \
00219 t_bpt_unused_##T
00220
00221 #define t_bpt_head(T) \
00222 t_bpt_head_##T
00223
00224 #define t_bpt_inentry(T) \
00225 t_bpt_inentry_##T
00226
00227 #define t_bpt_lfentry(T) \
00228 t_bpt_lfentry_##T
00229
00230 #define t_bpt_entry(T) \
00231 t_bpt_entry_##T
00232
00233 #define t_bpt_load_fn(T) \
00234 t_bpt_load_fn_##T
00235
00236 #define t_bpt_unload_fn(T) \
00237 t_bpt_unload_fn_##T
00238
00239 #define t_bpt_callback_fn(T) \
00240 t_bpt_callback_fn_##T
00241
00242
00243
00244
00245
00246 #define bpt_list(T, _bpt_, _node_, _entry_, _opts_) \
00247 bpt_list_##T(_bpt_, _node_, _entry_, _opts_)
00248
00249 #define bpt_check_unused(T, _bpt_, _unused_, _opts_) \
00250 bpt_check_unused_##T(_bpt_, _unused_, _opts_)
00251
00252 #define bpt_first_entry(T, _bpt_, _node_, _first_) \
00253 bpt_first_entry_##T(_bpt_, _node_, _first_)
00254
00255 #define bpt_prev_entry(T, _bpt_, _current_, _previous_, _opts_) \
00256 bpt_prev_entry_##T(_bpt_, _current_, _previous_, _opts_)
00257
00258 #define bpt_next_entry(T, _bpt_, _current_, _next_, _opts_) \
00259 bpt_next_entry_##T(_bpt_, _current_, _next_, _opts_)
00260
00261 #define bpt_last_entry(T, _bpt_, _node_, _last_) \
00262 bpt_last_entry_##T(_bpt_, _node_, _last_)
00263
00264 #define bpt_reinit_entries(T, _bpt_, _node_) \
00265 bpt_reinit_entries_##T(_bpt_, _node_)
00266
00267 #define bpt_make_node(T, _bpt_, _node_, _type_, _parent_) \
00268 bpt_make_node_##T(_bpt_, _node_, _type_, _parent_)
00269
00270 #define bpt_key(T, _bpt_, _node_, _key_) \
00271 bpt_key_##T(_bpt_, _node_, _key_)
00272
00273 #define bpt_ndi(T, _bpt_, _node_, _value_, _ndi_) \
00274 bpt_ndi_##T(_bpt_, _node_, _value_, _ndi_)
00275
00276 #define bpt_update_node(T, _bpt_, _node_, _addr_, _key_,_opts_) \
00277 bpt_update_node_##T(_bpt_, _node_, _addr_, _key_, _opts_)
00278
00279 #define bpt_update_parent(T, _bpt_, _node_) \
00280 bpt_update_parent_##T(_bpt_, _node_)
00281
00282 #define bpt_update(T, _bpt_, _node_, _opts_) \
00283 bpt_update_##T(_bpt_, _node_, _opts_)
00284
00285 #define bpt_linear_search(T, _bpt_, _node_, _key_, _ndi_, _opts_) \
00286 bpt_linear_search_##T(_bpt_, _node_, _key_, _ndi_, _opts_)
00287
00288 #define bpt_dichotomic_search(T, _bpt_, _node_, _key_, _ndi_, _opts_) \
00289 bpt_dichotomic_search_##T(_bpt_, _node_, _key_, _ndi_, _opts_)
00290
00291 #define bpt_search_entry(T, _bpt_, _node_, _key_, _ndi_, _opts_) \
00292 bpt_search_entry_##T(_bpt_, _node_, _key_, _ndi_, _opts_)
00293
00294 #define bpt_search_leaf(T, _bpt_, _node_, _leaf_, _key_) \
00295 bpt_search_leaf_##T(_bpt_, _node_, _leaf_, _key_)
00296
00297 #define bpt_search(T, _bpt_, _key_, _entry_) \
00298 bpt_search_##T(_bpt_, _key_, _entry_)
00299
00300 #define bpt_collide_next(T, _bpt_, _key_, _entry_) \
00301 bpt_collide_next_##T(_bpt_, _key_, _entry_)
00302
00303 #define bpt_collide_search(T, _bpt_, _key_, _value_, _entry_) \
00304 bpt_collide_search_##T(_bpt_, _key_, _value_, _entry_)
00305
00306 #define bpt_check_collide(T, _bpt_, _node1_, _key_, _value_) \
00307 bpt_check_collide_##T(_bpt_, _node1_, _key_, _value_)
00308
00309 #define bpt_node_size(T, _bpt_, _node_) \
00310 bpt_node_size_##T(_bpt_, _node_)
00311
00312 #define bpt_simplify(T, _bpt_, _node_, _unused_) \
00313 bpt_simplify_##T(_bpt_, _node_, _unused_)
00314
00315 #define bpt_balancein_1(T, _bpt_, _node1_, _node2_, \
00316 _cbctx_, _prev_, _unused_) \
00317 bpt_balancein_1_##T(_bpt_, _node1_, _node2_, _cbctx_, _prev_, _unused_)
00318
00319 #define bpt_balancein_2(T, _bpt_, _node1_, _node2_, \
00320 _cbctx_, _prev_, _unused_) \
00321 bpt_balancein_2_##T(_bpt_, _node1_, _node2_, _cbctx_, _prev_, _unused_)
00322
00323 #define bpt_balancein_3(T, _bpt_, _node1_, _node2_, \
00324 _cbctx_, _prev_, _unused_) \
00325 bpt_balancein_3_##T(_bpt_, _node1_, _node2_, _cbctx_, _prev_, _unused_)
00326
00327 #define bpt_balancein_4(T, _bpt_, _node1_, _node2_, \
00328 _cbctx_, _prev_, _unused_) \
00329 bpt_balancein_4_##T(_bpt_, _node1_, _node2_, _cbctx_, _prev_, _unused_)
00330
00331 #define bpt_delete(T, _bpt_, _entry_, _cbctx_, _unused_) \
00332 bpt_delete_##T(_bpt_, _entry_, _cbctx_, _unused_)
00333
00334 #define bpt_remove(T, _bpt_, _key_, _unused_) \
00335 bpt_remove_##T(_bpt_, _key_, _unused_)
00336
00337 #define bpt_collide_remove(T, _bpt_, _entry_, _unused_) \
00338 bpt_collide_remove_##T(_bpt_, _entry_, _unused_)
00339
00340 #define bpt_modify(T, _bpt_, _key_, _lfentry_, _unused_) \
00341 bpt_modify_##T(_bpt_, _key_, _lfentry_, _unused_)
00342
00343 #define bpt_collide_modify(T, _bpt_, _entry_, _lfentry_, _unused_) \
00344 bpt_collide_modify_##T(_bpt_, _entry_, _lfentry_, _unused_)
00345
00346 #define bpt_insert_head(T, _bpt_, _node1_, _node2_) \
00347 bpt_insert_head_##T(_bpt_, _node1_, _node2_)
00348
00349 #define bpt_insert_tail(T, _bpt_, _node1_, _node2_) \
00350 bpt_insert_tail_##T(_bpt_, _node1_, _node2_)
00351
00352 #define bpt_shift_sort(T, _bpt_, _node_) \
00353 bpt_shift_sort_##T(_bpt_, _node_)
00354
00355 #define bpt_insert_sort(T, _bpt_, _node_, _key_, _value_, \
00356 _ndi_, _opts_) \
00357 bpt_insert_sort_##T(_bpt_, _node_, _key_, _value_, _ndi_, _opts_)
00358
00359 #define bpt_new_root(T, _bpt_, _node1_, _node2_, _unused_) \
00360 bpt_new_root_##T(_bpt_, _node1_, _node2_, _unused_)
00361
00362 #define bpt_balanceout(T, _bpt_, _node1_, _node2_, _entry_, _cbctx_) \
00363 bpt_balanceout_##T(_bpt_, _node1_, _node2_, _entry_, _cbctx_)
00364
00365 #define bpt_split_node(T, _bpt_, _node1_, _entry_, \
00366 _current_, _unused_) \
00367 bpt_split_node_##T(_bpt_, _node1_, _entry_, _current_, _unused_)
00368
00369 #define bpt_insert(T, _bpt_, _node_, _entry_, _cbctx_, _unused_) \
00370 bpt_insert_##T(_bpt_, _node_, _entry_, _cbctx_, _unused_)
00371
00372 #define bpt_add(T, _bpt_, _lfentry_, _unused_) \
00373 bpt_add_##T(_bpt_, _lfentry_, _unused_)
00374
00375 #define bpt_init(T, _bpt_, _blksz_, _unusedval_, _flags_, \
00376 _load_, _unload_, _callback_, _unused_) \
00377 bpt_init_##T(_bpt_, _blksz_, _unusedval_, _flags_, _load_, \
00378 _unload_, _callback_, _unused_)
00379
00380 #define bpt_clean_node(T, _bpt_, _node_, _unused_) \
00381 bpt_clean_node_##T(_bpt_, _node_, _unused_)
00382
00383 #define bpt_clean(T, _bpt_, _unused_) \
00384 bpt_clean_##T(_bpt_, _unused_)
00385
00386
00387
00388
00389
00390 #define BPT_HEAD(T, _node_) \
00391 (t_bpt_head(T) *)((_node_)->buf)
00392
00393 #define BPT_INENTRY(T, _node_, _ndi_) \
00394 (t_bpt_inentry(T) *)((_node_)->buf + sizeof(t_bpt_head(T)) + \
00395 (_ndi_) * sizeof(t_bpt_inentry(T)))
00396
00397 #define BPT_LFENTRY(T, _node_, _ndi_) \
00398 (t_bpt_lfentry(T) *)((_node_)->buf + sizeof(t_bpt_head(T)) + \
00399 (_ndi_) * sizeof(t_bpt_lfentry(T)))
00400
00401 #define BPT_INIT_ENTRY(T, _node_, _ndi_) \
00402 memset((BPT_HEAD(T, (_node_)))->type == BPT_TYPE_INTERNAL ? \
00403 (_node_)->buf + sizeof(t_bpt_head(T)) + \
00404 (_ndi_) * sizeof(t_bpt_inentry(T)) : \
00405 (_node_)->buf + sizeof(t_bpt_head(T)) + \
00406 (_ndi_) * sizeof(t_bpt_lfentry(T)), 0x0, \
00407 (BPT_HEAD(T, (_node_)))->type == BPT_TYPE_INTERNAL ? \
00408 sizeof(t_bpt_inentry(T)) : sizeof(t_bpt_lfentry(T)))
00409
00410 #define BPT_IMPORT_ENTRY(T, _node_, _ndi_, _entry_) \
00411 memcpy((BPT_HEAD(T, (_node_)))->type == BPT_TYPE_INTERNAL ? \
00412 (_node_)->buf + sizeof(t_bpt_head(T)) + \
00413 (_ndi_) * sizeof(t_bpt_inentry(T)) : \
00414 (_node_)->buf + sizeof(t_bpt_head(T)) + \
00415 (_ndi_) * sizeof(t_bpt_lfentry(T)), \
00416 (_entry_), \
00417 (BPT_HEAD(T, (_node_)))->type == BPT_TYPE_INTERNAL ? \
00418 sizeof(t_bpt_inentry(T)) : sizeof(t_bpt_lfentry(T)));
00419
00420 #define BPT_EXPORT_ENTRY(T, _node_, _ndi_, _entry_) \
00421 memcpy((_entry_), \
00422 (BPT_HEAD(T, (_node_)))->type == BPT_TYPE_INTERNAL ? \
00423 (_node_)->buf + sizeof(t_bpt_head(T)) + \
00424 (_ndi_) * sizeof(t_bpt_inentry(T)) : \
00425 (_node_)->buf + sizeof(t_bpt_head(T)) + \
00426 (_ndi_) * sizeof(t_bpt_lfentry(T)), \
00427 (_BPT_HEAD(T, (_node_))->type == BPT_TYPE_INTERNAL ? \
00428 sizeof(t_bpt_inentry(T)) : sizeof(t_bpt_lfentry(T)));
00429
00430 #define BPT_COPY_ENTRY(T, _node1_, _node2_, _ndi1_, _ndi2_) \
00431 memcpy((BPT_HEAD(T, (_node1_)))->type == BPT_TYPE_INTERNAL ? \
00432 (_node2_)->buf + sizeof(t_bpt_head(T)) + \
00433 (_ndi2_) * sizeof(t_bpt_inentry(T)) : \
00434 (_node2_)->buf + sizeof(t_bpt_head(T)) + \
00435 (_ndi2_) * sizeof(t_bpt_lfentry(T)), \
00436 (BPT_HEAD(T, (_node1_)))->type == BPT_TYPE_INTERNAL ? \
00437 (_node1_)->buf + sizeof(t_bpt_head(T)) + \
00438 (_ndi1_) * sizeof(t_bpt_inentry(T)) : \
00439 (_node1_)->buf + sizeof(t_bpt_head(T)) + \
00440 (_ndi1_) * sizeof(t_bpt_lfentry(T)), \
00441 (BPT_HEAD(T, (_node1_)))->type == BPT_TYPE_INTERNAL ? \
00442 sizeof(t_bpt_inentry(T)) : sizeof(t_bpt_lfentry(T)));
00443
00444 #define BPT_SWAP_ENTRIES(T, _node_, _ndi1_, _ndi2_) \
00445 { \
00446 if ((BPT_HEAD(T, (_node_)))->type == BPT_TYPE_INTERNAL) \
00447 { \
00448 t_bpt_inentry(T) _swap_; \
00449 \
00450 memcpy(&_swap_, (_node_)->buf + sizeof(t_bpt_head(T)) + (_ndi1_) * \
00451 sizeof(t_bpt_inentry(T)), sizeof(t_bpt_inentry(T))); \
00452 memcpy((_node_)->buf + sizeof(t_bpt_head(T)) + (_ndi1_) * \
00453 sizeof(t_bpt_inentry(T)), (_node_)->buf + \
00454 sizeof(t_bpt_head(T)) + (_ndi2_) * \
00455 sizeof(t_bpt_inentry(T)), sizeof(t_bpt_inentry(T))); \
00456 memcpy((_node_)->buf + sizeof(t_bpt_head(T)) + (_ndi2_) * \
00457 sizeof(t_bpt_inentry(T)), &_swap_, \
00458 sizeof(t_bpt_inentry(T))); \
00459 } \
00460 else \
00461 { \
00462 t_bpt_lfentry(T) _swap_; \
00463 \
00464 memcpy(&_swap_, (_node_)->buf + sizeof(t_bpt_head(T)) + (_ndi1_) * \
00465 sizeof(t_bpt_lfentry(T)), sizeof(t_bpt_lfentry(T))); \
00466 memcpy((_node_)->buf + sizeof(t_bpt_head(T)) + (_ndi1_) * \
00467 sizeof(t_bpt_lfentry(T)), (_node_)->buf + \
00468 sizeof(t_bpt_head(T)) + (_ndi2_) * \
00469 sizeof(t_bpt_lfentry(T)), sizeof(t_bpt_lfentry(T))); \
00470 memcpy((_node_)->buf + sizeof(t_bpt_head(T)) + (_ndi2_) * \
00471 sizeof(t_bpt_lfentry(T)), &_swap_, \
00472 sizeof(t_bpt_lfentry(T))); \
00473 } \
00474 }
00475
00476 #define BPT_SET_ENTRY(T, _node_, _ndi_, _elem_, _value_) \
00477 { \
00478 if ((BPT_HEAD(T, (_node_)))->type == BPT_TYPE_INTERNAL) \
00479 { \
00480 t_bpt_inentry(T) *_entry_ = BPT_INENTRY(T, _node_, _ndi_); \
00481 \
00482 _entry_->_elem_ = (_value_); \
00483 } \
00484 else \
00485 { \
00486 t_bpt_lfentry(T) *_entry_ = BPT_LFENTRY(T, _node_, _ndi_); \
00487 \
00488 _entry_->_elem_ = (_value_); \
00489 } \
00490 }
00491
00492 #define BPT_GET_ENTRY(T, _node_, _ndi_, _elem_) \
00493 ((BPT_HEAD(T, (_node_)))->type == BPT_TYPE_INTERNAL ? \
00494 ((t_bpt_inentry(T) *)((_node_)->buf + sizeof(t_bpt_head(T)) + (_ndi_) * \
00495 sizeof(t_bpt_inentry(T))))->_elem_ : \
00496 ((t_bpt_lfentry(T) *)((_node_)->buf + sizeof(t_bpt_head(T)) + (_ndi_) * \
00497 sizeof(t_bpt_lfentry(T))))->_elem_)
00498
00499 #define BPT_GET_THIS_ENTRY(T, _head_, _ptr_, _elem_) \
00500 ((_head_)->type == BPT_TYPE_INTERNAL ? \
00501 ((t_bpt_inentry(T) *)(_ptr_))->_elem_ : \
00502 ((t_bpt_lfentry(T) *)(_ptr_))->_elem_)
00503
00504 #define BPT_QUOTA(T, _bpt_, _node_) \
00505 (t_bpt_ndi(T)) ((BPT_HEAD(T, (_node_)))->type == BPT_TYPE_INTERNAL ? \
00506 ((_bpt_)->nikeys * 50 / 100) : \
00507 ((_bpt_)->nlkeys * 50 / 100))
00508
00509
00510
00511
00512
00513 #define BPT_NODES(_bpt_) \
00514 (_bpt_)->nodes
00515
00516 #define BPT_NIKEYS(_bpt_) \
00517 (_bpt_)->nikeys
00518
00519 #define BPT_NLKEYS(_bpt_) \
00520 (_bpt_)->nlkeys
00521
00522 #define BPT_HEIGHT(_bpt_) \
00523 (_bpt_)->height
00524
00525 #define BPT_NKEYS(T, _bpt_, _node_) \
00526 ((BPT_HEAD(T, (_node_)))->type == BPT_TYPE_INTERNAL ? \
00527 (_bpt_)->nikeys : (_bpt_)->nlkeys)
00528
00529 #define BPT_COPY_NODE(_bpt_, _node1_, _node2_) \
00530 memcpy((_node2_), (_node1_), (_bpt_)->blksz)
00531
00532 #define BPT_LOAD(_bpt_, _node_, _addr_) \
00533 (_bpt_)->load((_bpt_), (_node_), (_addr_))
00534
00535 #define BPT_UNLOAD(_bpt_, _node_) \
00536 (_bpt_)->unload((_bpt_), (_node_));
00537
00538 #define BPT_CALLBACK(_bpt_, _cbctx_) \
00539 { \
00540 if ((_bpt_)->flags & BPT_FLAG_CALLBACK) \
00541 (_bpt_)->callback((_bpt_), (_cbctx_)); \
00542 }
00543
00544 #define BPT_GET_ROOT(_bpt_) \
00545 (_bpt_)->root
00546
00547 #define BPT_SET_ROOT(_bpt_, _root_) \
00548 (_bpt_)->root = (_root_)
00549
00550 #define BPT_INIT_CBCTX(_bpt_, _cbctx_) \
00551 { \
00552 if ((_bpt_)->flags & BPT_FLAG_CALLBACK) \
00553 { \
00554 (_cbctx_)->cb = BPT_CB_UNKNOWN; \
00555 \
00556 (_cbctx_)->previous.node = (_bpt_)->unused; \
00557 (_cbctx_)->previous.ndi = 0; \
00558 (_cbctx_)->current.node = (_bpt_)->unused; \
00559 (_cbctx_)->current.ndi = 0; \
00560 \
00561 (_cbctx_)->node = (_bpt_)->unused; \
00562 \
00563 (_cbctx_)->node1 = (_bpt_)->unused; \
00564 (_cbctx_)->node2 = (_bpt_)->unused; \
00565 } \
00566 }
00567
00568 #define BPT_SET_CBCTX(_bpt_, _head_, _cbctx_, _elem_, _value_) \
00569 { \
00570 if (((_bpt_)->flags & BPT_FLAG_CALLBACK) && \
00571 ((_head_)->type == BPT_TYPE_LEAF)) \
00572 (_cbctx_)->_elem_ = (_value_); \
00573 }
00574
00575 #define BPT_RESERVE(_bpt_, _unused_, _var_) \
00576 { \
00577 (_var_) = (_unused_)->array[(_unused_)->index]; \
00578 (_unused_)->array[(_unused_)->index] = (_bpt_)->unused; \
00579 (_unused_)->index--; \
00580 (_bpt_)->nodes++; \
00581 }
00582
00583 #define BPT_RELEASE(_bpt_, _unused_, _val_) \
00584 { \
00585 (_unused_)->index++; \
00586 (_unused_)->array[(_unused_)->index] = (_val_); \
00587 (_bpt_)->nodes--; \
00588 }
00589
00590
00591
00592
00593
00594 #define bpt_make_types(T, _t_bpt_blksz_, _t_bpt_ndi_, _t_bpt_uni_, \
00595 _t_bpt_nodes_, _t_bpt_height_, _t_bpt_key_, \
00596 _t_bpt_addr_, _t_bpt_inentry_, \
00597 _t_bpt_lfentry_) \
00598 \
00599 typedef struct s_bpt_##T t_bpt_##T; \
00600 \
00601 typedef _t_bpt_blksz_ t_bpt_blksz_##T; \
00602 typedef _t_bpt_ndi_ t_bpt_ndi_##T; \
00603 typedef _t_bpt_uni_ t_bpt_uni_##T; \
00604 typedef _t_bpt_nodes_ t_bpt_nodes_##T; \
00605 typedef _t_bpt_height_ t_bpt_height_##T; \
00606 typedef _t_bpt_key_ t_bpt_key_##T; \
00607 typedef _t_bpt_addr_ t_bpt_addr_##T; \
00608 typedef _t_bpt_inentry_ t_bpt_inentry_##T; \
00609 typedef _t_bpt_lfentry_ t_bpt_lfentry_##T; \
00610 \
00611 typedef _t_bpt_addr_ t_bpt_node_##T; \
00612 \
00613 typedef struct s_bpt_imm_##T \
00614 { \
00615 t_bpt_node(T) addr; \
00616 void *buf; \
00617 } t_bpt_imm_##T; \
00618 \
00619 typedef struct s_bpt_entry_##T \
00620 { \
00621 t_bpt_node(T) node; \
00622 t_bpt_ndi(T) ndi; \
00623 } t_bpt_entry_##T; \
00624 \
00625 typedef struct s_bpt_cbctx_##T \
00626 { \
00627 t_bpt_cb cb; \
00628 \
00629 t_bpt_entry(T) previous; \
00630 t_bpt_entry(T) current; \
00631 \
00632 t_bpt_node(T) node; \
00633 \
00634 t_bpt_node(T) node1; \
00635 t_bpt_node(T) node2; \
00636 } t_bpt_cbctx_##T; \
00637 \
00638 typedef void (*t_bpt_load_fn_##T)(t_bpt(T) *bpt, \
00639 t_bpt_imm(T) *node, \
00640 t_bpt_node(T) addr); \
00641 \
00642 typedef void (*t_bpt_unload_fn_##T)(t_bpt(T) *bpt, \
00643 t_bpt_imm(T) *node); \
00644 \
00645 typedef void (*t_bpt_callback_fn_##T)(t_bpt(T) *bpt, \
00646 t_bpt_cbctx(T) *cbctx); \
00647 \
00648 struct s_bpt_##T \
00649 { \
00650 t_bpt_blksz(T) blksz; \
00651 t_bpt_addr(T) unused; \
00652 t_bpt_nodes(T) nodes; \
00653 \
00654 t_bpt_flags flags; \
00655 t_bpt_ndi(T) nikeys; \
00656 t_bpt_ndi(T) nlkeys; \
00657 t_bpt_height(T) height; \
00658 t_bpt_node(T) root; \
00659 \
00660 t_bpt_load_fn(T) load; \
00661 t_bpt_unload_fn(T) unload; \
00662 t_bpt_callback_fn(T) callback; \
00663 }; \
00664 \
00665 typedef struct s_bpt_unused_##T \
00666 { \
00667 t_bpt_addr(T) *array; \
00668 t_bpt_uni(T) index; \
00669 } t_bpt_unused_##T; \
00670 \
00671 typedef struct s_bpt_head_##T \
00672 { \
00673 t_bpt_type type; \
00674 t_bpt_node(T) parent; \
00675 t_bpt_node(T) prv; \
00676 t_bpt_node(T) nxt; \
00677 } __attribute__((packed)) t_bpt_head_##T;
00678
00679 #define bpt_make_protos(T) \
00680 \
00681 int bpt_list_##T(t_bpt(T) *bpt, \
00682 t_bpt_imm(T) *node, \
00683 t_bpt_entry(T) *entry, \
00684 t_bpt_opts opts); \
00685 \
00686 int bpt_check_unused_##T(t_bpt(T) *bpt, \
00687 t_bpt_unused(T) *unused, \
00688 t_bpt_opts opts); \
00689 \
00690 int bpt_first_entry_##T(t_bpt(T) *bpt, \
00691 t_bpt_imm(T) *node, \
00692 t_bpt_ndi(T) *first); \
00693 \
00694 int bpt_prev_entry_##T(t_bpt(T) *bpt, \
00695 t_bpt_entry(T) current, \
00696 t_bpt_entry(T) *previous, \
00697 t_bpt_opts opts); \
00698 \
00699 int bpt_next_entry_##T(t_bpt(T) *bpt, \
00700 t_bpt_entry(T) current, \
00701 t_bpt_entry(T) *next, \
00702 t_bpt_opts opts); \
00703 \
00704 int bpt_last_entry_##T(t_bpt(T) *bpt, \
00705 t_bpt_imm(T) *node, \
00706 t_bpt_ndi(T) *last); \
00707 \
00708 void bpt_reinit_entries_##T(t_bpt(T) *bpt, \
00709 t_bpt_imm(T) *node); \
00710 \
00711 void bpt_make_node_##T(t_bpt(T) *bpt, \
00712 t_bpt_imm(T) *node, \
00713 t_bpt_type type, \
00714 t_bpt_node(T) parent); \
00715 \
00716 void bpt_key_##T(t_bpt(T) *bpt, \
00717 t_bpt_imm(T) *node, \
00718 t_bpt_key(T) *key); \
00719 \
00720 \
00721 int bpt_ndi_##T(t_bpt(T) *bpt, \
00722 t_bpt_imm(T) *node, \
00723 t_bpt_addr(T) value, \
00724 t_bpt_ndi(T) *ndi); \
00725 \
00726 int bpt_update_node_##T(t_bpt(T) *bpt, \
00727 t_bpt_imm(T) *node, \
00728 t_bpt_node(T) addr, \
00729 t_bpt_key(T) key, \
00730 t_bpt_opts opts); \
00731 \
00732 void bpt_update_parent_##T(t_bpt(T) *bpt, \
00733 t_bpt_imm(T) *node); \
00734 \
00735 int bpt_update_##T(t_bpt(T) *bpt, \
00736 t_bpt_imm(T) *node, \
00737 t_bpt_opts opts); \
00738 \
00739 int bpt_linear_search_##T(t_bpt(T) *bpt, \
00740 t_bpt_imm(T) *node, \
00741 t_bpt_key(T) key, \
00742 t_bpt_ndi(T) *ndi, \
00743 t_bpt_opts opts); \
00744 \
00745 int bpt_dichotomic_search_##T(t_bpt(T) *bpt, \
00746 t_bpt_imm(T) *node, \
00747 t_bpt_key(T) key, \
00748 t_bpt_ndi(T) *ndi, \
00749 t_bpt_opts opts); \
00750 \
00751 int bpt_search_entry_##T(t_bpt(T) *bpt, \
00752 t_bpt_imm(T) *node, \
00753 t_bpt_key(T) key, \
00754 t_bpt_ndi(T) *ndi, \
00755 t_bpt_opts opts); \
00756 \
00757 int bpt_search_leaf_##T(t_bpt(T) *bpt, \
00758 t_bpt_imm(T) *node, \
00759 t_bpt_node(T) *leaf, \
00760 t_bpt_key(T) key); \
00761 \
00762 int bpt_search_##T(t_bpt(T) *bpt, \
00763 t_bpt_key(T) key, \
00764 t_bpt_entry(T) *entry); \
00765 \
00766 int bpt_collide_next_##T(t_bpt(T) *bpt, \
00767 t_bpt_key(T) key, \
00768 t_bpt_entry(T) *entry); \
00769 \
00770 int bpt_collide_search_##T(t_bpt(T) *bpt, \
00771 t_bpt_key(T) key, \
00772 t_bpt_addr(T) value, \
00773 t_bpt_entry(T) *entry); \
00774 \
00775 int bpt_check_collide_##T(t_bpt(T) *bpt, \
00776 t_bpt_imm(T) *node1, \
00777 t_bpt_key(T) key, \
00778 t_bpt_addr(T) value); \
00779 \
00780 t_bpt_ndi(T) bpt_node_size_##T(t_bpt(T) *bpt, \
00781 t_bpt_imm(T) *node); \
00782 \
00783 void bpt_simplify_##T(t_bpt(T) *bpt, \
00784 t_bpt_imm(T) *node, \
00785 t_bpt_unused(T) *unused); \
00786 \
00787 int bpt_balancein_1_##T(t_bpt(T) *bpt, \
00788 t_bpt_imm(T) *node1, \
00789 t_bpt_imm(T) *node2, \
00790 t_bpt_cbctx(T) *cbctx, \
00791 t_bpt_entry(T) prev, \
00792 t_bpt_unused(T) *unused); \
00793 \
00794 int bpt_balancein_2_##T(t_bpt(T) *bpt, \
00795 t_bpt_imm(T) *node1, \
00796 t_bpt_imm(T) *node2, \
00797 t_bpt_cbctx(T) *cbctx, \
00798 t_bpt_entry(T) prev, \
00799 t_bpt_unused(T) *unused); \
00800 \
00801 int bpt_balancein_3_##T(t_bpt(T) *bpt, \
00802 t_bpt_imm(T) *node2, \
00803 t_bpt_imm(T) *node1, \
00804 t_bpt_cbctx(T) *cbctx, \
00805 t_bpt_entry(T) prev, \
00806 t_bpt_unused(T) *unused); \
00807 \
00808 int bpt_balancein_4_##T(t_bpt(T) *bpt, \
00809 t_bpt_imm(T) *node2, \
00810 t_bpt_imm(T) *node1, \
00811 t_bpt_cbctx(T) *cbctx, \
00812 t_bpt_entry(T) prev, \
00813 t_bpt_unused(T) *unused); \
00814 \
00815 int bpt_delete_##T(t_bpt(T) *bpt, \
00816 t_bpt_entry(T) entry, \
00817 t_bpt_cbctx(T) *cbctx, \
00818 t_bpt_unused(T) *unused); \
00819 \
00820 int bpt_remove_##T(t_bpt(T) *bpt, \
00821 t_bpt_key(T) key, \
00822 t_bpt_unused(T) *unused); \
00823 \
00824 int bpt_collide_remove_##T(t_bpt(T) *bpt, \
00825 t_bpt_entry(T) entry, \
00826 t_bpt_unused(T) *unused); \
00827 \
00828 int bpt_modify_##T(t_bpt(T) *bpt, \
00829 t_bpt_key(T) key, \
00830 t_bpt_lfentry(T) *lfentry, \
00831 t_bpt_unused(T) *unused); \
00832 \
00833 int bpt_collide_modify_##T(t_bpt(T) *bpt, \
00834 t_bpt_entry(T) entry, \
00835 t_bpt_lfentry(T) *lfentry, \
00836 t_bpt_unused(T) *unused); \
00837 \
00838 void bpt_insert_head_##T(t_bpt(T) *bpt, \
00839 t_bpt_imm(T) *node1, \
00840 t_bpt_imm(T) *node2); \
00841 \
00842 void bpt_insert_tail_##T(t_bpt(T) *bpt, \
00843 t_bpt_imm(T) *node1, \
00844 t_bpt_imm(T) *node2); \
00845 \
00846 void bpt_shift_sort_##T(t_bpt(T) *bpt, \
00847 t_bpt_imm(T) *node); \
00848 \
00849 void bpt_insert_sort_##T(t_bpt(T) *bpt, \
00850 t_bpt_imm(T) *node, \
00851 t_bpt_key(T) key, \
00852 t_bpt_addr(T) value, \
00853 t_bpt_ndi(T) *ndi, \
00854 t_bpt_opts opts); \
00855 \
00856 void bpt_new_root_##T(t_bpt(T) *bpt, \
00857 t_bpt_imm(T) *node1, \
00858 t_bpt_imm(T) *node2, \
00859 t_bpt_unused(T) *unused); \
00860 \
00861 int bpt_balanceout_##T(t_bpt(T) *bpt, \
00862 t_bpt_imm(T) *node1, \
00863 t_bpt_imm(T) *node2, \
00864 void *entry, \
00865 t_bpt_cbctx(T) *cbctx); \
00866 \
00867 int bpt_split_node_##T(t_bpt(T) *bpt, \
00868 t_bpt_imm(T) *node1, \
00869 void *entry, \
00870 t_bpt_cbctx(T) *cbctx, \
00871 t_bpt_unused(T) *unused); \
00872 \
00873 int bpt_insert_##T(t_bpt(T) *bpt, \
00874 t_bpt_imm(T) *node, \
00875 void *entry, \
00876 t_bpt_cbctx(T) *cbctx, \
00877 t_bpt_unused(T) *unused); \
00878 \
00879 int bpt_add_##T(t_bpt(T) *bpt, \
00880 t_bpt_lfentry(T) *lfentry, \
00881 t_bpt_unused(T) *unused); \
00882 \
00883 int bpt_init_##T(t_bpt(T) *bpt, \
00884 t_bpt_blksz(T) blksz, \
00885 t_bpt_addr(T) unusedvalue, \
00886 t_bpt_flags flags, \
00887 t_bpt_load_fn(T) load, \
00888 t_bpt_unload_fn(T) unload, \
00889 t_bpt_callback_fn(T) callback, \
00890 t_bpt_unused(T) *unused); \
00891 \
00892 int bpt_clean_node_##T(t_bpt(T) *bpt, \
00893 t_bpt_imm(T) *node, \
00894 t_bpt_unused(T) *unused); \
00895 \
00896 int bpt_clean_##T(t_bpt(T) *bpt, \
00897 t_bpt_unused(T) *unused);
00898
00899 #define bpt_make_functions(T, _key_, _value_) \
00900 \
00901
00902
00903 \
00904 \
00905 int bpt_list_##T(t_bpt(T) *bpt, \
00906 t_bpt_imm(T) *node, \
00907 t_bpt_entry(T) *entry, \
00908 t_bpt_opts opts) \
00909 { \
00910 t_bpt_head(T) *head = BPT_HEAD(T, node); \
00911 t_bpt_imm(T) child; \
00912 t_bpt_ndi(T) i; \
00913 \
00914 if (head->type == BPT_TYPE_LEAF) \
00915 { \
00916 entry->node = node->addr; \
00917 if (opts & BPT_OPT_HEAD) \
00918 { \
00919 if (bpt_first_entry(T, bpt, node, &entry->ndi) != 0) \
00920 return (-1); \
00921 } \
00922 else if (opts & BPT_OPT_TAIL) \
00923 { \
00924 if (bpt_last_entry(T, bpt, node, &entry->ndi) != 0) \
00925 return (-1); \
00926 } \
00927 else \
00928 return (-1); \
00929 \
00930 return (0); \
00931 } \
00932 \
00933 if (opts & BPT_OPT_HEAD) \
00934 { \
00935 if (bpt_first_entry(T, bpt, node, &i) != 0) \
00936 return (-1); \
00937 } \
00938 else if (opts & BPT_OPT_TAIL) \
00939 { \
00940 if (bpt_last_entry(T, bpt, node, &i) != 0) \
00941 return (-1); \
00942 } \
00943 else \
00944 return (-1); \
00945 \
00946 BPT_LOAD(bpt, &child, BPT_GET_ENTRY(T, node, i, _value_)); \
00947 \
00948 if (bpt_list(T, bpt, &child, entry, opts) != 0) \
00949 { \
00950 BPT_UNLOAD(bpt, &child); \
00951 return (-1); \
00952 } \
00953 \
00954 BPT_UNLOAD(bpt, &child); \
00955 \
00956 return (0); \
00957 } \
00958 \
00959
00960
00961 \
00962 \
00963 int bpt_check_unused_##T(t_bpt(T) *bpt, \
00964 t_bpt_unused(T) *unused, \
00965 t_bpt_opts opts) \
00966 { \
00967 if (opts == BPT_OPT_INIT) \
00968 { \
00969 if (unused->index >= (BPT_INIT_ALLOC() - 1)) \
00970 return (0); \
00971 } \
00972 else if (opts == BPT_OPT_ADD) \
00973 { \
00974 if (unused->index >= (BPT_ADD_ALLOC(bpt) - 1)) \
00975 return (0); \
00976 } \
00977 else if (opts == BPT_OPT_MODIFY) \
00978 { \
00979 if (unused->index >= (BPT_MODIFY_ALLOC(bpt) - 1)) \
00980 return (0); \
00981 } \
00982 else if (opts == BPT_OPT_REMOVE) \
00983 { \
00984 if (unused->index >= (BPT_REMOVE_ALLOC(bpt) - 1)) \
00985 return (0); \
00986 } \
00987 else if (opts == BPT_OPT_CLEAN) \
00988 { \
00989 if (unused->index >= (BPT_CLEAN_ALLOC(bpt) - 1)) \
00990 return (0); \
00991 } \
00992 \
00993 return (-1); \
00994 } \
00995 \
00996
00997
00998 \
00999 \
01000 int bpt_first_entry_##T(t_bpt(T) *bpt, \
01001 t_bpt_imm(T) *node, \
01002 t_bpt_ndi(T) *first) \
01003 { \
01004 t_bpt_ndi(T) nkeys = BPT_NKEYS(T, bpt, node); \
01005 t_bpt_ndi(T) i; \
01006 \
01007 for (i = 0; i < nkeys; i++) \
01008 if (BPT_GET_ENTRY(T, node, i, _value_) != bpt->unused) \
01009 { \
01010 *first = i; \
01011 return (0); \
01012 } \
01013 \
01014 return (-1); \
01015 } \
01016 \
01017
01018
01019 \
01020 \
01021 int bpt_prev_entry_##T(t_bpt(T) *bpt, \
01022 t_bpt_entry(T) current, \
01023 t_bpt_entry(T) *previous, \
01024 t_bpt_opts opts) \
01025 { \
01026 if (opts & BPT_OPT_NODE) \
01027 { \
01028 t_bpt_head(T) *head; \
01029 t_bpt_ndi(T) nkeys; \
01030 t_bpt_imm(T) node; \
01031 t_bpt_ndi(T) i; \
01032 \
01033 if ((current.ndi - 1) < 0) \
01034 return (-1); \
01035 \
01036 BPT_LOAD(bpt, &node, current.node); \
01037 head = BPT_HEAD(T, &node); \
01038 nkeys = BPT_NKEYS(T, bpt, &node); \
01039 \
01040 if (current.ndi >= nkeys) \
01041 { \
01042 BPT_UNLOAD(bpt, &node); \
01043 return (-1); \
01044 } \
01045 \
01046 for (i = current.ndi - 1; i >= 0; i--) \
01047 if (BPT_GET_ENTRY(T, &node, i, _value_) != bpt->unused) \
01048 { \
01049 previous->node = node.addr; \
01050 previous->ndi = i; \
01051 \
01052 BPT_UNLOAD(bpt, &node); \
01053 \
01054 return (0); \
01055 } \
01056 \
01057 BPT_UNLOAD(bpt, &node); \
01058 } \
01059 \
01060 if (opts & BPT_OPT_TREE) \
01061 { \
01062 t_bpt_head(T) *head; \
01063 t_bpt_imm(T) node; \
01064 t_bpt_imm(T) prev; \
01065 \
01066 if (bpt_prev_entry(T, bpt, current, previous, BPT_OPT_NODE) == 0) \
01067 return (0); \
01068 \
01069 do \
01070 { \
01071 BPT_LOAD(bpt, &node, current.node); \
01072 head = BPT_HEAD(T, &node); \
01073 \
01074 if (head->prv == bpt->unused) \
01075 { \
01076 BPT_UNLOAD(bpt, &node); \
01077 return (-1); \
01078 } \
01079 \
01080 BPT_LOAD(bpt, &prev, head->prv); \
01081 BPT_UNLOAD(bpt, &node); \
01082 \
01083 previous->node = prev.addr; \
01084 if (bpt_last_entry(T, bpt, &prev, &previous->ndi) == 0) \
01085 { \
01086 BPT_UNLOAD(bpt, &prev); \
01087 return (0); \
01088 } \
01089 \
01090 current.node = prev.addr; \
01091 \
01092 BPT_UNLOAD(bpt, &prev); \
01093 } while (1); \
01094 \
01095 return (0); \
01096 } \
01097 \
01098 return (-1); \
01099 } \
01100 \
01101
01102
01103 \
01104 \
01105 int bpt_next_entry_##T(t_bpt(T) *bpt, \
01106 t_bpt_entry(T) current, \
01107 t_bpt_entry(T) *next, \
01108 t_bpt_opts opts) \
01109 { \
01110 if (opts & BPT_OPT_NODE) \
01111 { \
01112 t_bpt_head(T) *head; \
01113 t_bpt_ndi(T) nkeys; \
01114 t_bpt_imm(T) node; \
01115 t_bpt_ndi(T) i; \
01116 \
01117 BPT_LOAD(bpt, &node, current.node); \
01118 head = BPT_HEAD(T, &node); \
01119 nkeys = BPT_NKEYS(T, bpt, &node); \
01120 \
01121 if ((current.ndi >= nkeys) || \
01122 ((current.ndi + 1) >= nkeys)) \
01123 { \
01124 BPT_UNLOAD(bpt, &node); \
01125 return (-1); \
01126 } \
01127 \
01128 for (i = current.ndi + 1; i < nkeys; i++) \
01129 if (BPT_GET_ENTRY(T, &node, i, _value_) != bpt->unused) \
01130 { \
01131 next->node = node.addr; \
01132 next->ndi = i; \
01133 \
01134 BPT_UNLOAD(bpt, &node); \
01135 \
01136 return (0); \
01137 } \
01138 \
01139 BPT_UNLOAD(bpt, &node); \
01140 } \
01141 \
01142 if (opts & BPT_OPT_TREE) \
01143 { \
01144 t_bpt_head(T) *head; \
01145 t_bpt_imm(T) node; \
01146 t_bpt_imm(T) nxt; \
01147 \
01148 if (bpt_next_entry(T, bpt, current, next, BPT_OPT_NODE) == 0) \
01149 return (0); \
01150 \
01151 do \
01152 { \
01153 BPT_LOAD(bpt, &node, current.node); \
01154 head = BPT_HEAD(T, &node); \
01155 \
01156 if (head->nxt == bpt->unused) \
01157 { \
01158 BPT_UNLOAD(bpt, &node); \
01159 return (-1); \
01160 } \
01161 \
01162 BPT_LOAD(bpt, &nxt, head->nxt); \
01163 BPT_UNLOAD(bpt, &node); \
01164 \
01165 next->node = nxt.addr; \
01166 if (bpt_first_entry(T, bpt, &nxt, &next->ndi) == 0) \
01167 { \
01168 BPT_UNLOAD(bpt, &nxt); \
01169 return (0); \
01170 } \
01171 \
01172 current.node = nxt.addr; \
01173 \
01174 BPT_UNLOAD(bpt, &nxt); \
01175 } while (1); \
01176 \
01177 return (0); \
01178 } \
01179 \
01180 return (-1); \
01181 } \
01182 \
01183
01184
01185 \
01186 \
01187 int bpt_last_entry_##T(t_bpt(T) *bpt, \
01188 t_bpt_imm(T) *node, \
01189 t_bpt_ndi(T) *last) \
01190 { \
01191 if ((*last = bpt_node_size(T, bpt, node) - 1) < 0) \
01192 return (-1); \
01193 \
01194 return (0); \
01195 } \
01196 \
01197
01198
01199 \
01200 \
01201 void bpt_reinit_entries_##T(t_bpt(T) *bpt, \
01202 t_bpt_imm(T) *node) \
01203 { \
01204 t_bpt_ndi(T) nkeys = BPT_NKEYS(T, bpt, node); \
01205 t_bpt_ndi(T) i; \
01206 \
01207 for (i = 0; i < nkeys; i++) \
01208 { \
01209 BPT_INIT_ENTRY(T, node, i); \
01210 BPT_SET_ENTRY(T, node, i, _value_, bpt->unused); \
01211 } \
01212 } \
01213 \
01214
01215
01216 \
01217 \
01218 void bpt_make_node_##T(t_bpt(T) *bpt, \
01219 t_bpt_imm(T) *node, \
01220 t_bpt_type type, \
01221 t_bpt_node(T) parent) \
01222 { \
01223 t_bpt_head(T) *head = BPT_HEAD(T, node); \
01224 t_bpt_ndi(T) nkeys; \
01225 t_bpt_ndi(T) i; \
01226 \
01227 nkeys = type == BPT_TYPE_INTERNAL ? bpt->nikeys : bpt->nlkeys; \
01228 \
01229 head->type = type; \
01230 head->parent = parent; \
01231 head->prv = bpt->unused; \
01232 head->nxt = bpt->unused; \
01233 \
01234 for (i = 0; i < nkeys; i++) \
01235 { \
01236 BPT_INIT_ENTRY(T, node, i); \
01237 BPT_SET_ENTRY(T, node, i, _value_, bpt->unused); \
01238 } \
01239 } \
01240 \
01241
01242
01243 \
01244 \
01245 void bpt_key_##T(t_bpt(T) *bpt, \
01246 t_bpt_imm(T) *node, \
01247 t_bpt_key(T) *key) \
01248 { \
01249 t_bpt_ndi(T) ndi; \
01250 \
01251 bpt_last_entry(T, bpt, node, &ndi); \
01252 \
01253 *key = BPT_GET_ENTRY(T, node, ndi, _key_); \
01254 } \
01255 \
01256
01257
01258
01259
01260
01261
01262
01263
01264
01265 \
01266 \
01267 int bpt_ndi_##T(t_bpt(T) *bpt, \
01268 t_bpt_imm(T) *node, \
01269 t_bpt_addr(T) value, \
01270 t_bpt_ndi(T) *ndi) \
01271 { \
01272 t_bpt_ndi(T) nkeys = BPT_NKEYS(T, bpt, node); \
01273 t_bpt_ndi(T) i; \
01274 \
01275 for (i = 0; (i < nkeys) && \
01276 (BPT_GET_ENTRY(T, node, i, _value_) != bpt->unused); \
01277 i++) \
01278 if (BPT_GET_ENTRY(T, node, i, _value_) == value) \
01279 { \
01280 *ndi = i; \
01281 return (0); \
01282 } \
01283 \
01284 return (-1); \
01285 } \
01286 \
01287
01288
01289 \
01290 \
01291 int bpt_update_node_##T(t_bpt(T) *bpt, \
01292 t_bpt_imm(T) *node, \
01293 t_bpt_node(T) addr, \
01294 t_bpt_key(T) key, \
01295 t_bpt_opts opts) \
01296 { \
01297 t_bpt_head(T) *head = BPT_HEAD(T, node); \
01298 t_bpt_key(T) oldk = 0; \
01299 t_bpt_key(T) newk = 0; \
01300 t_bpt_imm(T) parent; \
01301 t_bpt_ndi(T) ndi; \
01302 \
01303 if (bpt_ndi(T, bpt, node, addr, &ndi) != 0) \
01304 { \
01305 bpt_debug("[bptd] panic: this case should never happen\n"); \
01306 return (-1); \
01307 } \
01308 \
01309 if (opts & BPT_OPT_KEY) \
01310 { \
01311 bpt_key(T, bpt, node, &oldk); \
01312 BPT_SET_ENTRY(T, node, ndi, _key_, key); \
01313 } \
01314 \
01315 if (head->parent == bpt->unused) \
01316 return (0); \
01317 \
01318 bpt_key(T, bpt, node, &newk); \
01319 \
01320 if (!(opts & BPT_OPT_KEY)) \
01321 oldk = newk; \
01322 \
01323 if (newk == oldk) \
01324 return (0); \
01325 \
01326 BPT_LOAD(bpt, &parent, head->parent); \
01327 \
01328 if (bpt_update_node(T, bpt, &parent, node->addr, newk, opts) != 0) \
01329 { \
01330 BPT_UNLOAD(bpt, &parent); \
01331 return (-1); \
01332 } \
01333 \
01334 BPT_UNLOAD(bpt, &parent); \
01335 \
01336 return (0); \
01337 } \
01338 \
01339
01340
01341 \
01342 \
01343 void bpt_update_parent_##T(t_bpt(T) *bpt, \
01344 t_bpt_imm(T) *node) \
01345 { \
01346 t_bpt_ndi(T) nkeys = BPT_NKEYS(T, bpt, node); \
01347 t_bpt_ndi(T) i; \
01348 \
01349 for (i = 0; (i < nkeys) && \
01350 (BPT_GET_ENTRY(T, node, i, _value_) != bpt->unused); \
01351 i++) \
01352 { \
01353 t_bpt_head(T) *chead; \
01354 t_bpt_imm(T) child; \
01355 \
01356 BPT_LOAD(bpt, &child, BPT_GET_ENTRY(T, node, i, _value_)); \
01357 chead = BPT_HEAD(T, &child); \
01358 chead->parent = node->addr; \
01359 BPT_UNLOAD(bpt, &child); \
01360 } \
01361 } \
01362 \
01363
01364
01365 \
01366 \
01367 int bpt_update_##T(t_bpt(T) *bpt, \
01368 t_bpt_imm(T) *node, \
01369 t_bpt_opts opts) \
01370 { \
01371 t_bpt_head(T) *head = BPT_HEAD(T, node); \
01372 t_bpt_imm(T) parent; \
01373 t_bpt_key(T) key; \
01374 \
01375 if (opts & BPT_OPT_PARENT) \
01376 { \
01377 bpt_update_parent(T, bpt, node); \
01378 opts &= ~BPT_OPT_PARENT; \
01379 } \
01380 \
01381 if (head->parent == bpt->unused) \
01382 return (0); \
01383 \
01384 if (opts == BPT_OPT_ZERO) \
01385 return (0); \
01386 \
01387 bpt_key(T, bpt, node, &key); \
01388 \
01389 BPT_LOAD(bpt, &parent, head->parent); \
01390 \
01391 if (bpt_update_node(T, bpt, &parent, node->addr, key, opts) != 0) \
01392 { \
01393 BPT_UNLOAD(bpt, &parent); \
01394 return (-1); \
01395 } \
01396 \
01397 BPT_UNLOAD(bpt, &parent); \
01398 \
01399 return (0); \
01400 } \
01401 \
01402
01403
01404 \
01405 \
01406 int bpt_linear_search_##T(t_bpt(T) *bpt, \
01407 t_bpt_imm(T) *node, \
01408 t_bpt_key(T) key, \
01409 t_bpt_ndi(T) *ndi, \
01410 t_bpt_opts opts) \
01411 { \
01412 t_bpt_ndi(T) nkeys = BPT_NKEYS(T, bpt, node); \
01413 t_bpt_ndi(T) i; \
01414 \
01415 for (i = 0; (i < nkeys) && \
01416 (BPT_GET_ENTRY(T, node, i, _value_) != bpt->unused); \
01417 i++) \
01418 { \
01419 if (opts & BPT_OPT_PARTIAL) \
01420 if ((key <= BPT_GET_ENTRY(T, node, i, _key_)) || \
01421 ((i + 1) >= nkeys) || \
01422 (BPT_GET_ENTRY(T, node, i + 1, _value_) == bpt->unused)) \
01423 { \
01424 *ndi = i; \
01425 return (0); \
01426 } \
01427 \
01428 if (opts & BPT_OPT_PERFECT) \
01429 if (key == BPT_GET_ENTRY(T, node, i, _key_)) \
01430 { \
01431 *ndi = i; \
01432 return (0); \
01433 } \
01434 } \
01435 \
01436 return (-1); \
01437 } \
01438 \
01439
01440
01441 \
01442 \
01443 int bpt_dichotomic_search_##T(t_bpt(T) *bpt, \
01444 t_bpt_imm(T) *node, \
01445 t_bpt_key(T) key, \
01446 t_bpt_ndi(T) *ndi, \
01447 t_bpt_opts opts) \
01448 { \
01449 t_bpt_ndi(T) j = BPT_NKEYS(T, bpt, node) - 1; \
01450 t_bpt_ndi(T) i = 0; \
01451 \
01452 if (BPT_GET_ENTRY(T, node, 0, _value_) == bpt->unused) \
01453 { \
01454 *ndi = 0; \
01455 return (opts & BPT_OPT_PARTIAL ? 0 : -1); \
01456 } \
01457 \
01458 while (i <= j) \
01459 { \
01460 t_bpt_ndi(T) k = (i + j) / 2; \
01461 \
01462 if (BPT_GET_ENTRY(T, node, k, _value_) == bpt->unused) \
01463 { \
01464 j = k - 1; \
01465 continue; \
01466 } \
01467 \
01468 if (opts & BPT_OPT_PERFECT) \
01469 if (BPT_GET_ENTRY(T, node, k, _key_) == key) \
01470 { \
01471 *ndi = k; \
01472 return (0); \
01473 } \
01474 \
01475 if (opts & BPT_OPT_PARTIAL) \
01476 if ((key <= BPT_GET_ENTRY(T, node, k, _key_)) && \
01477 ((k == 0) || \
01478 (key > BPT_GET_ENTRY(T, node, k - 1, _key_)))) \
01479 { \
01480 *ndi = k; \
01481 return (0); \
01482 } \
01483 \
01484 if (key < BPT_GET_ENTRY(T, node, k, _key_)) \
01485 j = k - 1; \
01486 else \
01487 i = k + 1; \
01488 } \
01489 \
01490 if (opts & BPT_OPT_PARTIAL) \
01491 { \
01492 if (bpt_last_entry(T, bpt, node, ndi) != 0) \
01493 return (-1); \
01494 \
01495 return (0); \
01496 } \
01497 \
01498 return (-1); \
01499 } \
01500 \
01501
01502
01503
01504
01505 \
01506 \
01507 int bpt_search_entry_##T(t_bpt(T) *bpt, \
01508 t_bpt_imm(T) *node, \
01509 t_bpt_key(T) key, \
01510 t_bpt_ndi(T) *ndi, \
01511 t_bpt_opts opts) \
01512 { \
01513 if (bpt->flags & BPT_FLAG_COLLIDE) \
01514 return (bpt_linear_search(T, bpt, node, key, ndi, opts)); \
01515 else \
01516 return (bpt_dichotomic_search(T, bpt, node, key, ndi, opts)); \
01517 } \
01518 \
01519
01520
01521
01522 \
01523 \
01524 int bpt_search_leaf_##T(t_bpt(T) *bpt, \
01525 t_bpt_imm(T) *node, \
01526 t_bpt_node(T) *leaf, \
01527 t_bpt_key(T) key) \
01528 { \
01529 t_bpt_head(T) *head = BPT_HEAD(T, node); \
01530 t_bpt_imm(T) child; \
01531 t_bpt_ndi(T) ndi; \
01532 \
01533 if (head->type == BPT_TYPE_LEAF) \
01534 { \
01535 *leaf = node->addr; \
01536 return (0); \
01537 } \
01538 \
01539 if (bpt_search_entry(T, bpt, node, key, &ndi, BPT_OPT_PARTIAL) != 0) \
01540 return (-1); \
01541 \
01542 BPT_LOAD(bpt, &child, BPT_GET_ENTRY(T, node, ndi, _value_)); \
01543 \
01544 if (bpt_search_leaf(T, bpt, &child, leaf, key) != 0) \
01545 { \
01546 BPT_UNLOAD(bpt, &child); \
01547 return (-1); \
01548 } \
01549 \
01550 BPT_UNLOAD(bpt, &child); \
01551 \
01552 return (0); \
01553 } \
01554 \
01555
01556
01557
01558
01559
01560
01561 \
01562 \
01563 int bpt_search_##T(t_bpt(T) *bpt, \
01564 t_bpt_key(T) key, \
01565 t_bpt_entry(T) *entry) \
01566 { \
01567 t_bpt_head(T) *head; \
01568 t_bpt_imm(T) leaf; \
01569 t_bpt_imm(T) root; \
01570 \
01571 BPT_LOAD(bpt, &root, BPT_GET_ROOT(bpt)); \
01572 head = BPT_HEAD(T, &root); \
01573 \
01574 if (bpt_search_leaf(T, bpt, &root, &entry->node, key) != 0) \
01575 { \
01576 bpt_debug("[bptd] no leaf present in the tree\n"); \
01577 BPT_UNLOAD(bpt, &root); \
01578 return (-1); \
01579 } \
01580 \
01581 BPT_UNLOAD(bpt, &root); \
01582 BPT_LOAD(bpt, &leaf, entry->node); \
01583 head = BPT_HEAD(T, &leaf); \
01584 \
01585 if (bpt_search_entry(T, bpt, &leaf, key, &entry->ndi, \
01586 BPT_OPT_PERFECT) != 0) \
01587 { \
01588 bpt_debug("[bptd] cannot find the entry\n"); \
01589 BPT_UNLOAD(bpt, &leaf); \
01590 return (-1); \
01591 } \
01592 \
01593 BPT_UNLOAD(bpt, &leaf); \
01594 \
01595 return (0); \
01596 } \
01597 \
01598
01599
01600
01601
01602
01603
01604
01605
01606 \
01607 \
01608 int bpt_collide_next_##T(t_bpt(T) *bpt, \
01609 t_bpt_key(T) key, \
01610 t_bpt_entry(T) *entry) \
01611 { \
01612 t_bpt_head(T) *head; \
01613 t_bpt_imm(T) node; \
01614 \
01615 if (bpt_next_entry(T, bpt, *entry, entry, BPT_OPT_TREE) != 0) \
01616 return (-1); \
01617 \
01618 BPT_LOAD(bpt, &node, entry->node); \
01619 head = BPT_HEAD(T, &node); \
01620 \
01621 if (BPT_GET_ENTRY(T, &node, entry->ndi, _key_) != key) \
01622 { \
01623 BPT_UNLOAD(bpt, &node); \
01624 return (-1); \
01625 } \
01626 \
01627 BPT_UNLOAD(bpt, &node); \
01628 \
01629 return (0); \
01630 } \
01631 \
01632
01633
01634 \
01635 \
01636 int bpt_collide_search_##T(t_bpt(T) *bpt, \
01637 t_bpt_key(T) key, \
01638 t_bpt_addr(T) value, \
01639 t_bpt_entry(T) *entry) \
01640 { \
01641 t_bpt_head(T) *head; \
01642 t_bpt_imm(T) node; \
01643 \
01644 if (bpt_search(T, bpt, key, entry) != 0) \
01645 { \
01646 bpt_debug("[bptd] cannot find the entry in collision\n"); \
01647 return (-1); \
01648 } \
01649 \
01650 do \
01651 { \
01652 BPT_LOAD(bpt, &node, entry->node); \
01653 head = BPT_HEAD(T, &node); \
01654 \
01655 if ((BPT_GET_ENTRY(T, &node, entry->ndi, _key_) == key) && \
01656 (BPT_GET_ENTRY(T, &node, entry->ndi, _value_) == value)) \
01657 { \
01658 BPT_UNLOAD(bpt, &node); \
01659 return (0); \
01660 } \
01661 \
01662 BPT_UNLOAD(bpt, &node); \
01663 } while (bpt_collide_next(T, bpt, key, entry) == 0); \
01664 \
01665 return (-1); \
01666 } \
01667 \
01668
01669
01670 \
01671 \
01672 int bpt_check_collide_##T(t_bpt(T) *bpt, \
01673 t_bpt_imm(T) *node1, \
01674 t_bpt_key(T) key, \
01675 t_bpt_addr(T) value) \
01676 { \
01677 t_bpt_head(T) *head2; \
01678 t_bpt_imm(T) node2; \
01679 t_bpt_entry(T) entry; \
01680 \
01681 entry.node = node1->addr; \
01682 if (bpt_search_entry(T, bpt, node1, key, &entry.ndi, \
01683 BPT_OPT_PERFECT) != 0) \
01684 return (0); \
01685 \
01686 do \
01687 { \
01688 BPT_LOAD(bpt, &node2, entry.node); \
01689 head2 = BPT_HEAD(T, &node2); \
01690 \
01691 if ((BPT_GET_ENTRY(T, &node2, entry.ndi, _key_) == key) && \
01692 (BPT_GET_ENTRY(T, &node2, entry.ndi, _value_) == value)) \
01693 { \
01694 BPT_UNLOAD(bpt, &node2); \
01695 return (-1); \
01696 } \
01697 \
01698 BPT_UNLOAD(bpt, &node2); \
01699 } while (bpt_collide_next(T, bpt, key, &entry) == 0); \
01700 \
01701 return (0); \
01702 } \
01703 \
01704
01705
01706
01707
01708
01709 \
01710 \
01711 t_bpt_ndi(T) bpt_node_size_##T(t_bpt(T) *bpt, \
01712 t_bpt_imm(T) *node) \
01713 { \
01714 t_bpt_ndi(T) nkeys = BPT_NKEYS(T, bpt, node); \
01715 t_bpt_ndi(T) j = nkeys - 1; \
01716 t_bpt_ndi(T) i = 0; \
01717 \
01718 if (BPT_GET_ENTRY(T, node, 0, _value_) == bpt->unused) \
01719 return (0); \
01720 \
01721 while (i <= j) \
01722 { \
01723 t_bpt_ndi(T) k = (i + j) / 2; \
01724 \
01725 if ((BPT_GET_ENTRY(T, node, k, _value_) != bpt->unused) \
01726 && (((k + 1) > j) || \
01727 (BPT_GET_ENTRY(T, node, k + 1, _value_) == bpt->unused))) \
01728 return (k + 1); \
01729 \
01730 if (BPT_GET_ENTRY(T, node, k, _value_) == bpt->unused) \
01731 j = k - 1; \
01732 else \
01733 i = k + 1; \
01734 } \
01735 \
01736 return (0); \
01737 } \
01738 \
01739
01740
01741
01742
01743 \
01744 \
01745 void bpt_simplify_##T(t_bpt(T) *bpt, \
01746 t_bpt_imm(T) *node1, \
01747 t_bpt_unused(T) *unused) \
01748 { \
01749 t_bpt_head(T) *head1 = BPT_HEAD(T, node1); \
01750 t_bpt_head(T) *head2; \
01751 t_bpt_node(T) parent; \
01752 t_bpt_imm(T) node2; \
01753 \
01754 if (head1->parent == bpt->unused) \
01755 return ; \
01756 \
01757 if ((head1->prv != bpt->unused) || (head1->nxt != bpt->unused)) \
01758 return ; \
01759 \
01760 BPT_LOAD(bpt, &node2, node1->addr); \
01761 head2 = BPT_HEAD(T, &node2); \
01762 \
01763 while (head2->parent != bpt->unused) \
01764 { \
01765 parent = head2->parent; \
01766 \
01767 BPT_UNLOAD(bpt, &node2); \
01768 \
01769 BPT_LOAD(bpt, &node2, parent); \
01770 head2 = BPT_HEAD(T, &node2); \
01771 \
01772 BPT_RELEASE(bpt, unused, node2.addr); \
01773 } \
01774 \
01775 BPT_UNLOAD(bpt, &node2); \
01776 \
01777 head1->parent = bpt->unused; \
01778 BPT_SET_ROOT(bpt, node1->addr); \
01779 } \
01780 \
01781
01782
01783
01784 \
01785 \
01786 int bpt_balancein_1_##T(t_bpt(T) *bpt, \
01787 t_bpt_imm(T) *node1, \
01788 t_bpt_imm(T) *node2, \
01789 t_bpt_cbctx(T) *cbctx, \
01790 t_bpt_entry(T) prev, \
01791 t_bpt_unused(T) *unused) \
01792 { \
01793 t_bpt_head(T) *head1 = BPT_HEAD(T, node1); \
01794 t_bpt_head(T) *head2 = BPT_HEAD(T, node2); \
01795 t_bpt_imm(T) parent; \
01796 t_bpt_entry(T) entry; \
01797 \
01798 bpt_insert_head(T, bpt, node1, node2); \
01799 \
01800 head2->prv = head1->prv; \
01801 if (head2->prv != bpt->unused) \
01802 { \
01803 t_bpt_head(T) *head3; \
01804 t_bpt_imm(T) node3; \
01805 \
01806 BPT_LOAD(bpt, &node3, head2->prv); \
01807 head3 = BPT_HEAD(T, &node3); \
01808 head3->nxt = node2->addr; \
01809 BPT_UNLOAD(bpt, &node3); \
01810 } \
01811 \
01812 if (head2->type == BPT_TYPE_INTERNAL) \
01813 if (bpt_update(T, bpt, node2, BPT_OPT_PARENT) != 0) \
01814 return (-1); \
01815 \
01816 BPT_LOAD(bpt, &parent, head1->parent); \
01817 \
01818 entry.node = parent.addr; \
01819 if (bpt_ndi(T, bpt, &parent, node1->addr, &entry.ndi) != 0) \
01820 { \
01821 BPT_UNLOAD(bpt, &parent); \
01822 return (-1); \
01823 } \
01824 \
01825 BPT_UNLOAD(bpt, &parent); \
01826 \
01827 if (bpt_delete(T, bpt, entry, cbctx, unused) != 0) \
01828 return (-1); \
01829 \
01830 BPT_SET_CBCTX(bpt, head2, cbctx, cb, BPT_CB_MIGRATE); \
01831 if (prev.node == node1->addr) \
01832 { \
01833 BPT_SET_CBCTX(bpt, head2, cbctx, previous.node, node2->addr); \
01834 BPT_SET_CBCTX(bpt, head2, cbctx, previous.ndi, prev.ndi); \
01835 } \
01836 else \
01837 { \
01838 BPT_SET_CBCTX(bpt, head2, cbctx, previous.node, prev.node); \
01839 BPT_SET_CBCTX(bpt, head2, cbctx, previous.ndi, prev.ndi); \
01840 } \
01841 BPT_SET_CBCTX(bpt, head2, cbctx, node, node2->addr); \
01842 \
01843 BPT_RELEASE(bpt, unused, node1->addr); \
01844 \
01845 return (0); \
01846 } \
01847 \
01848
01849
01850
01851 \
01852 \
01853 int bpt_balancein_2_##T(t_bpt(T) *bpt, \
01854 t_bpt_imm(T) *node1, \
01855 t_bpt_imm(T) *node2, \
01856 t_bpt_cbctx(T) *cbctx, \
01857 t_bpt_entry(T) prev, \
01858 t_bpt_unused(T) *unused) \
01859 { \
01860 t_bpt_head(T) *head1 = BPT_HEAD(T, node1); \
01861 t_bpt_ndi(T) ndi1; \
01862 t_bpt_ndi(T) ndi2; \
01863 \
01864 bpt_insert_sort(T, bpt, node1, BPT_OPT_NOKEY(T), BPT_OPT_NOVALUE(T), \
01865 &ndi1, BPT_OPT_TAIL); \
01866 \
01867 if (bpt_first_entry(T, bpt, node2, &ndi2) != 0) \
01868 return (-1); \
01869 \
01870 BPT_COPY_ENTRY(T, node2, node1, ndi2, ndi1); \
01871 \
01872 BPT_INIT_ENTRY(T, node2, ndi2); \
01873 BPT_SET_ENTRY(T, node2, ndi2, _value_, bpt->unused); \
01874 \
01875 bpt_shift_sort(T, bpt, node2); \
01876 \
01877 if (head1->type == BPT_TYPE_INTERNAL) \
01878 if (bpt_update(T, bpt, node1, BPT_OPT_PARENT) != 0) \
01879 return (-1); \
01880 \
01881 if (bpt_update(T, bpt, node1, BPT_OPT_KEY) != 0) \
01882 return (-1); \
01883 \
01884 BPT_SET_CBCTX(bpt, head1, cbctx, cb, BPT_CB_BALANCE); \
01885 BPT_SET_CBCTX(bpt, head1, cbctx, previous.node, prev.node); \
01886 BPT_SET_CBCTX(bpt, head1, cbctx, previous.ndi, prev.ndi); \
01887 BPT_SET_CBCTX(bpt, head1, cbctx, node1, node1->addr); \
01888 BPT_SET_CBCTX(bpt, head1, cbctx, node2, node2->addr); \
01889 \
01890 return (0); \
01891 } \
01892 \
01893
01894
01895
01896 \
01897 \
01898 int bpt_balancein_3_##T(t_bpt(T) *bpt, \
01899 t_bpt_imm(T) *node2, \
01900 t_bpt_imm(T) *node1, \
01901 t_bpt_cbctx(T) *cbctx, \
01902 t_bpt_entry(T) prev, \
01903 t_bpt_unused(T) *unused) \
01904 { \
01905 t_bpt_head(T) *head1 = BPT_HEAD(T, node1); \
01906 t_bpt_head(T) *head2 = BPT_HEAD(T, node2); \
01907 t_bpt_ndi(T) node1sz = bpt_node_size(T, bpt, node1); \
01908 t_bpt_imm(T) parent; \
01909 t_bpt_entry(T) entry; \
01910 \
01911 bpt_insert_tail(T, bpt, node2, node1); \
01912 \
01913 head1->nxt = head2->nxt; \
01914 if (head1->nxt != bpt->unused) \
01915 { \
01916 t_bpt_head(T) *head3; \
01917 t_bpt_imm(T) node3; \
01918 \
01919 BPT_LOAD(bpt, &node3, head2->nxt); \
01920 head3 = BPT_HEAD(T, &node3); \
01921 head3->prv = node1->addr; \
01922 BPT_UNLOAD(bpt, &node3); \
01923 } \
01924 \
01925 if (head1->type == BPT_TYPE_INTERNAL) \
01926 if (bpt_update(T, bpt, node1, BPT_OPT_PARENT) != 0) \
01927 return (-1); \
01928 \
01929 if (bpt_update(T, bpt, node1, BPT_OPT_KEY) != 0) \
01930 return (-1); \
01931 \
01932 BPT_LOAD(bpt, &parent, head2->parent); \
01933 \
01934 entry.node = head2->parent; \
01935 if (bpt_ndi(T, bpt, &parent, node2->addr, &entry.ndi) != 0) \
01936 { \
01937 BPT_UNLOAD(bpt, &parent); \
01938 return (-1); \
01939 } \
01940 \
01941 BPT_UNLOAD(bpt, &parent); \
01942 \
01943 if (bpt_delete(T, bpt, entry, cbctx, unused) != 0) \
01944 return (-1); \
01945 \
01946 BPT_SET_CBCTX(bpt, head1, cbctx, cb, BPT_CB_MIGRATE); \
01947 if (prev.node == node2->addr) \
01948 { \
01949 BPT_SET_CBCTX(bpt, head1, cbctx, previous.node, node1->addr); \
01950 BPT_SET_CBCTX(bpt, head1, cbctx, previous.ndi, \
01951 node1sz + prev.ndi); \
01952 } \
01953 else \
01954 { \
01955 BPT_SET_CBCTX(bpt, head1, cbctx, previous.node, prev.node); \
01956 BPT_SET_CBCTX(bpt, head1, cbctx, previous.ndi, prev.ndi); \
01957 } \
01958 BPT_SET_CBCTX(bpt, head1, cbctx, node, node1->addr); \
01959 \
01960 BPT_RELEASE(bpt, unused, node2->addr); \
01961 \
01962 return (0); \
01963 } \
01964 \
01965
01966
01967 \
01968 \
01969 int bpt_balancein_4_##T(t_bpt(T) *bpt, \
01970 t_bpt_imm(T) *node2, \
01971 t_bpt_imm(T) *node1, \
01972 t_bpt_cbctx(T) *cbctx, \
01973 t_bpt_entry(T) prev, \
01974 t_bpt_unused(T) *unused) \
01975 { \
01976 t_bpt_head(T) *head2 = BPT_HEAD(T, node2); \
01977 t_bpt_ndi(T) ndi1; \
01978 t_bpt_ndi(T) ndi2; \
01979 \
01980 bpt_insert_sort(T, bpt, node2, BPT_OPT_NOKEY(T), BPT_OPT_NOVALUE(T), \
01981 &ndi2, BPT_OPT_HEAD); \
01982 \
01983 if (bpt_last_entry(T, bpt, node1, &ndi1) != 0) \
01984 return (-1); \
01985 \
01986 BPT_COPY_ENTRY(T, node1, node2, ndi1, ndi2); \
01987 \
01988 BPT_INIT_ENTRY(T, node1, ndi1); \
01989 BPT_SET_ENTRY(T, node1, ndi1, _value_, bpt->unused); \
01990 \
01991 if (head2->type == BPT_TYPE_INTERNAL) \
01992 if (bpt_update(T, bpt, node2, BPT_OPT_PARENT) != 0) \
01993 return (-1); \
01994 \
01995 if (bpt_update(T, bpt, node1, BPT_OPT_KEY) != 0) \
01996 return (-1); \
01997 \
01998 BPT_SET_CBCTX(bpt, head2, cbctx, cb, BPT_CB_BALANCE); \
01999 if ((prev.node == node1->addr) && (prev.ndi == ndi1)) \
02000 { \
02001 BPT_SET_CBCTX(bpt, head2, cbctx, previous.node, node2->addr); \
02002 BPT_SET_CBCTX(bpt, head2, cbctx, previous.ndi, ndi2); \
02003 } \
02004 else \
02005 { \
02006 BPT_SET_CBCTX(bpt, head2, cbctx, previous.node, prev.node); \
02007 BPT_SET_CBCTX(bpt, head2, cbctx, previous.ndi, prev.ndi + 1); \
02008 } \
02009 BPT_SET_CBCTX(bpt, head2, cbctx, node1, node1->addr); \
02010 BPT_SET_CBCTX(bpt, head2, cbctx, node2, node2->addr); \
02011 \
02012 return (0); \
02013 } \
02014 \
02015
02016
02017
02018
02019
02020
02021
02022
02023
02024
02025
02026
02027
02028 \
02029 \
02030 int bpt_delete_##T(t_bpt(T) *bpt, \
02031 t_bpt_entry(T) entry, \
02032 t_bpt_cbctx(T) *cbctx, \
02033 t_bpt_unused(T) *unused) \
02034 { \
02035 t_bpt_head(T) *head1; \
02036 t_bpt_head(T) *head2; \
02037 t_bpt_imm(T) node1; \
02038 t_bpt_imm(T) node2; \
02039 t_bpt_ndi(T) nkeys; \
02040 t_bpt_entry(T) prev; \
02041 \
02042 if (bpt_prev_entry(T, bpt, entry, &prev, BPT_OPT_TREE) != 0) \
02043 { \
02044 prev.node = bpt->unused; \
02045 prev.ndi = 0; \
02046 } \
02047 \
02048 BPT_LOAD(bpt, &node1, entry.node); \
02049 head1 = BPT_HEAD(T, &node1); \
02050 nkeys = BPT_NKEYS(T, bpt, &node1); \
02051 \
02052 BPT_INIT_ENTRY(T, &node1, entry.ndi); \
02053 BPT_SET_ENTRY(T, &node1, entry.ndi, _value_, bpt->unused); \
02054 \
02055 bpt_shift_sort(T, bpt, &node1); \
02056 \
02057 if ((head1->parent == bpt->unused) || \
02058 (bpt_node_size(T, bpt, &node1) >= BPT_QUOTA(T, bpt, &node1))) \
02059 { \
02060 if (bpt_update(T, bpt, &node1, BPT_OPT_KEY) != 0) \
02061 { \
02062 bpt_debug("[bptd] cannot update the node\n"); \
02063 BPT_UNLOAD(bpt, &node1); \
02064 return (-1); \
02065 } \
02066 \
02067 BPT_SET_CBCTX(bpt, head1, cbctx, cb, BPT_CB_DELETE); \
02068 BPT_SET_CBCTX(bpt, head1, cbctx, previous.node, prev.node); \
02069 BPT_SET_CBCTX(bpt, head1, cbctx, previous.ndi, prev.ndi); \
02070 BPT_SET_CBCTX(bpt, head1, cbctx, node, node1.addr); \
02071 \
02072 BPT_UNLOAD(bpt, &node1); \
02073 \
02074 return (0); \
02075 } \
02076 \
02077 if (head1->nxt != bpt->unused) \
02078 { \
02079 BPT_LOAD(bpt, &node2, head1->nxt); \
02080 head2 = BPT_HEAD(T, &node2); \
02081 \
02082 if ((bpt_node_size(T, bpt, &node2) + \
02083 bpt_node_size(T, bpt, &node1)) <= nkeys) \
02084 { \
02085 if (bpt_balancein_1(T, bpt, &node1, &node2, cbctx, \
02086 prev, unused) != 0) \
02087 { \
02088 bpt_debug("[bptd] cannot balance entries in the " \
02089 "second node\n"); \
02090 BPT_UNLOAD(bpt, &node2); \
02091 BPT_UNLOAD(bpt, &node1); \
02092 return (-1); \
02093 } \
02094 \
02095 bpt_simplify(T, bpt, &node2, unused); \
02096 \
02097 BPT_UNLOAD(bpt, &node2); \
02098 BPT_UNLOAD(bpt, &node1); \
02099 return (0); \
02100 } \
02101 else \
02102 { \
02103 if (bpt_balancein_2(T, bpt, &node1, &node2, cbctx, \
02104 prev, unused) != 0) \
02105 { \
02106 bpt_debug("[bptd] cannot balance one entry in the node\n"); \
02107 BPT_UNLOAD(bpt, &node2); \
02108 BPT_UNLOAD(bpt, &node1); \
02109 return (-1); \
02110 } \
02111 \
02112 BPT_UNLOAD(bpt, &node2); \
02113 BPT_UNLOAD(bpt, &node1); \
02114 return (0); \
02115 } \
02116 \
02117 BPT_UNLOAD(bpt, &node2); \
02118 } \
02119 \
02120 if (head1->prv != bpt->unused) \
02121 { \
02122 BPT_LOAD(bpt, &node2, head1->prv); \
02123 head2 = BPT_HEAD(T, &node2); \
02124 \
02125 if ((bpt_node_size(T, bpt, &node2) + \
02126 bpt_node_size(T, bpt, &node1)) <= nkeys) \
02127 { \
02128 if (bpt_balancein_3(T, bpt, &node1, &node2, cbctx, \
02129 prev, unused) != 0) \
02130 { \
02131 bpt_debug("[bptd] cannot balance entries in the second " \
02132 "node\n"); \
02133 BPT_UNLOAD(bpt, &node2); \
02134 BPT_UNLOAD(bpt, &node1); \
02135 return (-1); \
02136 } \
02137 \
02138 bpt_simplify(T, bpt, &node2, unused); \
02139 \
02140 BPT_UNLOAD(bpt, &node2); \
02141 BPT_UNLOAD(bpt, &node1); \
02142 return (0); \
02143 } \
02144 else \
02145 { \
02146 if (bpt_balancein_4(T, bpt, &node1, &node2, cbctx, \
02147 prev, unused) != 0) \
02148 { \
02149 bpt_debug("[bptd] cannot balance one entry in the node\n"); \
02150 BPT_UNLOAD(bpt, &node2); \
02151 BPT_UNLOAD(bpt, &node1); \
02152 return (-1); \
02153 } \
02154 \
02155 BPT_UNLOAD(bpt, &node2); \
02156 BPT_UNLOAD(bpt, &node1); \
02157 return (0); \
02158 } \
02159 \
02160 BPT_UNLOAD(bpt, &node2); \
02161 } \
02162 \
02163 if (bpt_update(T, bpt, &node1, BPT_OPT_KEY) != 0) \
02164 { \
02165 bpt_debug("[bptd] cannot update the node\n"); \
02166 BPT_UNLOAD(bpt, &node1); \
02167 return (-1); \
02168 } \
02169 \
02170 bpt_simplify(T, bpt, &node1, unused); \
02171 \
02172 BPT_SET_CBCTX(bpt, head1, cbctx, cb, BPT_CB_DELETE); \
02173 BPT_SET_CBCTX(bpt, head1, cbctx, previous.node, prev.node); \
02174 BPT_SET_CBCTX(bpt, head1, cbctx, previous.ndi, prev.ndi); \
02175 BPT_SET_CBCTX(bpt, head1, cbctx, node, node1.addr); \
02176 \
02177 BPT_UNLOAD(bpt, &node1); \
02178 \
02179 return (0); \
02180 } \
02181 \
02182
02183
02184
02185
02186
02187
02188
02189
02190
02191
02192 \
02193 \
02194 int bpt_remove_##T(t_bpt(T) *bpt, \
02195 t_bpt_key(T) key, \
02196 t_bpt_unused(T) *unused) \
02197 { \
02198 t_bpt_cbctx(T) cbctx; \
02199 t_bpt_entry(T) entry; \
02200 \
02201 if (bpt_check_unused(T, bpt, unused, BPT_OPT_REMOVE) != 0) \
02202 { \
02203 bpt_debug("[bptd] bad unused array\n"); \
02204 return (-1); \
02205 } \
02206 \
02207 if (bpt_search(T, bpt, key, &entry) != 0) \
02208 { \
02209 bpt_debug("[bptd] cannot find the entry looked for\n"); \
02210 return (-1); \
02211 } \
02212 \
02213 BPT_INIT_CBCTX(bpt, &cbctx); \
02214 \
02215 if (bpt_delete(T, bpt, entry, &cbctx, unused) != 0) \
02216 { \
02217 bpt_debug("[bptd] cannot delete the leaf entry\n"); \
02218 return (-1); \
02219 } \
02220 \
02221 BPT_CALLBACK(bpt, &cbctx); \
02222 \
02223 return (0); \
02224 } \
02225 \
02226
02227
02228
02229
02230
02231 \
02232 \
02233 int bpt_collide_remove_##T(t_bpt(T) *bpt, \
02234 t_bpt_entry(T) entry, \
02235 t_bpt_unused(T) *unused) \
02236 { \
02237 t_bpt_cbctx(T) cbctx; \
02238 \
02239 if (bpt_check_unused(T, bpt, unused, BPT_OPT_REMOVE) != 0) \
02240 { \
02241 bpt_debug("[bptd] bad unused array\n"); \
02242 return (-1); \
02243 } \
02244 \
02245 BPT_INIT_CBCTX(bpt, &cbctx); \
02246 \
02247 if (bpt_delete(T, bpt, entry, &cbctx, unused) != 0) \
02248 { \
02249 bpt_debug("[bptd] cannot delete the leaf entry\n"); \
02250 return (-1); \
02251 } \
02252 \
02253 BPT_CALLBACK(bpt, &cbctx); \
02254 \
02255 return (0); \
02256 } \
02257 \
02258
02259
02260
02261
02262
02263
02264
02265
02266
02267
02268
02269
02270
02271
02272
02273
02274 \
02275 \
02276 int bpt_modify_##T(t_bpt(T) *bpt, \
02277 t_bpt_key(T) key, \
02278 t_bpt_lfentry(T) *lfentry, \
02279 t_bpt_unused(T) *unused) \
02280 { \
02281 t_bpt_cbctx(T) cbctx; \
02282 t_bpt_head(T) *head; \
02283 t_bpt_entry(T) entry; \
02284 t_bpt_imm(T) node; \
02285 \
02286 if (bpt_check_unused(T, bpt, unused, BPT_OPT_MODIFY) != 0) \
02287 { \
02288 bpt_debug("[bptd] bad unused array\n"); \
02289 return (-1); \
02290 } \
02291 \
02292 if (lfentry->_value_ == bpt->unused) \
02293 { \
02294 bpt_debug("[bptd] the leaf entry to update has a non-valid key\n"); \
02295 return (-1); \
02296 } \
02297 \
02298 if (bpt_search(T, bpt, key, &entry) != 0) \
02299 { \
02300 bpt_debug("[bptd] cannot find the entry\n"); \
02301 return (-1); \
02302 } \
02303 \
02304 BPT_LOAD(bpt, &node, entry.node); \
02305 head = BPT_HEAD(T, &node); \
02306 \
02307 BPT_INIT_CBCTX(bpt, &cbctx); \
02308 \
02309 if (lfentry->_key_ == BPT_GET_ENTRY(T, &node, entry.ndi, _key_)) \
02310 { \
02311 BPT_IMPORT_ENTRY(T, &node, entry.ndi, lfentry); \
02312 \
02313 BPT_SET_CBCTX(bpt, head, &cbctx, cb, BPT_CB_MODIFY); \
02314 BPT_SET_CBCTX(bpt, head, &cbctx, current.node, node.addr); \
02315 BPT_SET_CBCTX(bpt, head, &cbctx, current.ndi, entry.ndi); \
02316 BPT_SET_CBCTX(bpt, head, &cbctx, node, node.addr); \
02317 \
02318 BPT_CALLBACK(bpt, &cbctx); \
02319 \
02320 BPT_UNLOAD(bpt, &node); \
02321 \
02322 return (0); \
02323 } \
02324 \
02325 BPT_UNLOAD(bpt, &node); \
02326 \
02327 if (bpt_remove(T, bpt, key, unused) != 0) \
02328 { \
02329 bpt_debug("[bptd] cannot remove the entry\n"); \
02330 return (-1); \
02331 } \
02332 \
02333 if (bpt_add(T, bpt, lfentry, unused) != 0) \
02334 { \
02335 bpt_debug("[bptd] cannot add the entry\n"); \
02336 return (-1); \
02337 } \
02338 \
02339 return (0); \
02340 } \
02341 \
02342
02343
02344
02345
02346
02347 \
02348 \
02349 int bpt_collide_modify_##T(t_bpt(T) *bpt, \
02350 t_bpt_entry(T) entry, \
02351 t_bpt_lfentry(T) *lfentry, \
02352 t_bpt_unused(T) *unused) \
02353 { \
02354 t_bpt_cbctx(T) cbctx; \
02355 t_bpt_head(T) *head; \
02356 t_bpt_imm(T) node; \
02357 \
02358 if (bpt_check_unused(T, bpt, unused, BPT_OPT_MODIFY) != 0) \
02359 { \
02360 bpt_debug("[bptd] bad unused array\n"); \
02361 return (-1); \
02362 } \
02363 \
02364 if (lfentry->_value_ == bpt->unused) \
02365 { \
02366 bpt_debug("[bptd] the leaf entry to update has a non-valid key\n"); \
02367 return (-1); \
02368 } \
02369 \
02370 BPT_LOAD(bpt, &node, entry.node); \
02371 head = BPT_HEAD(T, &node); \
02372 \
02373 BPT_INIT_CBCTX(bpt, &cbctx); \
02374 \
02375 if (lfentry->_key_ == BPT_GET_ENTRY(T, &node, entry.ndi, _key_)) \
02376 { \
02377 BPT_IMPORT_ENTRY(T, &node, entry.ndi, lfentry); \
02378 \
02379 BPT_SET_CBCTX(bpt, head, &cbctx, cb, BPT_CB_MODIFY); \
02380 BPT_SET_CBCTX(bpt, head, &cbctx, current.node, node.addr); \
02381 BPT_SET_CBCTX(bpt, head, &cbctx, current.ndi, entry.ndi); \
02382 BPT_SET_CBCTX(bpt, head, &cbctx, node, node.addr); \
02383 \
02384 BPT_CALLBACK(bpt, &cbctx); \
02385 \
02386 BPT_UNLOAD(bpt, &node); \
02387 \
02388 return (0); \
02389 } \
02390 \
02391 BPT_UNLOAD(bpt, &node); \
02392 \
02393 if (bpt_collide_remove(T, bpt, entry, unused) != 0) \
02394 { \
02395 bpt_debug("[bptd] cannot remove a collision\n"); \
02396 return (-1); \
02397 } \
02398 \
02399 if (bpt_add(T, bpt, lfentry, unused) != 0) \
02400 { \
02401 bpt_debug("[bptd] cannot add an entry\n"); \
02402 return (-1); \
02403 } \
02404 \
02405 return (0); \
02406 } \
02407 \
02408
02409
02410 \
02411 \
02412 void bpt_insert_head_##T(t_bpt(T) *bpt, \
02413 t_bpt_imm(T) *node1, \
02414 t_bpt_imm(T) *node2) \
02415 { \
02416 t_bpt_ndi(T) node1sz = bpt_node_size(T, bpt, node1); \
02417 t_bpt_ndi(T) node2sz = bpt_node_size(T, bpt, node2); \
02418 t_bpt_ndi(T) i; \
02419 \
02420 for (i = node2sz - 1; i >= 0; i--) \
02421 BPT_COPY_ENTRY(T, node2, node2, i, node1sz + i); \
02422 for (i = 0; i < node1sz; i++) \
02423 BPT_COPY_ENTRY(T, node1, node2, i, i); \
02424 } \
02425 \
02426
02427
02428 \
02429 \
02430 void bpt_insert_tail_##T(t_bpt(T) *bpt, \
02431 t_bpt_imm(T) *node1, \
02432 t_bpt_imm(T) *node2) \
02433 { \
02434 t_bpt_ndi(T) node2sz = bpt_node_size(T, bpt, node2); \
02435 t_bpt_ndi(T) nkeys = BPT_NKEYS(T, bpt, node1); \
02436 t_bpt_ndi(T) i; \
02437 \
02438 for (i = 0; (i < nkeys) && \
02439 (BPT_GET_ENTRY(T, node1, i, _value_) != bpt->unused); \
02440 i++) \
02441 BPT_COPY_ENTRY(T, node1, node2, i, node2sz + i); \
02442 } \
02443 \
02444
02445
02446
02447 \
02448 \
02449 void bpt_shift_sort_##T(t_bpt(T) *bpt, \
02450 t_bpt_imm(T) *node) \
02451 { \
02452 t_bpt_ndi(T) nkeys = BPT_NKEYS(T, bpt, node); \
02453 t_bpt_entry(T) current; \
02454 \
02455 for (current.node = node->addr, current.ndi = 0; \
02456 current.ndi < nkeys; current.ndi++) \
02457 if (BPT_GET_ENTRY(T, node, current.ndi, _value_) == bpt->unused) \
02458 { \
02459 t_bpt_entry(T) next; \
02460 \
02461 if (bpt_next_entry(T, bpt, current, &next, BPT_OPT_NODE) != 0) \
02462 break; \
02463 \
02464 BPT_SWAP_ENTRIES(T, node, current.ndi, next.ndi); \
02465 } \
02466 } \
02467 \
02468
02469
02470 \
02471 \
02472 void bpt_insert_sort_##T(t_bpt(T) *bpt, \
02473 t_bpt_imm(T) *node, \
02474 t_bpt_key(T) key, \
02475 t_bpt_addr(T) value, \
02476 t_bpt_ndi(T) *ndi, \
02477 t_bpt_opts opts) \
02478 { \
02479 t_bpt_ndi(T) nodesz = bpt_node_size(T, bpt, node); \
02480 t_bpt_ndi(T) nkeys = BPT_NKEYS(T, bpt, node); \
02481 t_bpt_ndi(T) i; \
02482 \
02483 if (opts & BPT_OPT_HEAD) \
02484 { \
02485 for (*ndi = 0, i = nodesz - 1; i >= 0; i--) \
02486 BPT_COPY_ENTRY(T, node, node, i, i + 1); \
02487 } \
02488 else if (opts & BPT_OPT_TAIL) \
02489 { \
02490 *ndi = nodesz; \
02491 } \
02492 else \
02493 { \
02494 for (*ndi = 0; (*ndi < nkeys) && \
02495 (BPT_GET_ENTRY(T, node, *ndi, _value_) != bpt->unused); \
02496 (*ndi)++) \
02497 if (BPT_GET_ENTRY(T, node, *ndi, _key_) >= key) \
02498 { \
02499 if (bpt->flags & BPT_FLAG_COLLIDE) \
02500 while ((BPT_GET_ENTRY(T, node, *ndi, _value_) != bpt->unused) &&\
02501 (BPT_GET_ENTRY(T, node, *ndi, _key_) == key) && \
02502 (BPT_GET_ENTRY(T, node, *ndi, _value_) < value)) \
02503 *ndi = *ndi + 1; \
02504 break; \
02505 } \
02506 \
02507 if (nodesz > *ndi) \
02508 for (i = nodesz - 1; i >= *ndi; i--) \
02509 BPT_COPY_ENTRY(T, node, node, i, i + 1); \
02510 } \
02511 \
02512 BPT_INIT_ENTRY(T, node, *ndi); \
02513 BPT_SET_ENTRY(T, node, *ndi, _value_, bpt->unused); \
02514 } \
02515 \
02516
02517
02518
02519 \
02520 \
02521 void bpt_new_root_##T(t_bpt(T) *bpt, \
02522 t_bpt_imm(T) *node1, \
02523 t_bpt_imm(T) *node2, \
02524 t_bpt_unused(T) *unused) \
02525 { \
02526 t_bpt_head(T) *head1 = BPT_HEAD(T, node1); \
02527 t_bpt_head(T) *head2 = BPT_HEAD(T, node2); \
02528 t_bpt_inentry(T) inentry; \
02529 t_bpt_head(T) *head0; \
02530 t_bpt_imm(T) root; \
02531 t_bpt_addr(T) blk; \
02532 t_bpt_ndi(T) ndi; \
02533 \
02534 BPT_RESERVE(bpt, unused, blk); \
02535 BPT_LOAD(bpt, &root, blk); \
02536 \
02537 bpt_make_node(T, bpt, &root, BPT_TYPE_INTERNAL, bpt->unused); \
02538 head0 = BPT_HEAD(T, &root); \
02539 \
02540 memset(&inentry, 0x0, sizeof(t_bpt_inentry(T))); \
02541 bpt_key(T, bpt, node1, &inentry._key_); \
02542 inentry._value_ = node1->addr; \
02543 \
02544 bpt_insert_sort(T, bpt, &root, inentry._key_, inentry._value_, \
02545 &ndi, BPT_OPT_ZERO); \
02546 \
02547 BPT_IMPORT_ENTRY(T, &root, ndi, &inentry); \
02548 \
02549 memset(&inentry, 0x0, sizeof(t_bpt_inentry(T))); \
02550 bpt_key(T, bpt, node2, &inentry._key_); \
02551 inentry._value_ = node2->addr; \
02552 \
02553 bpt_insert_sort(T, bpt, &root, inentry._key_, inentry._value_, \
02554 &ndi, BPT_OPT_ZERO); \
02555 \
02556 BPT_IMPORT_ENTRY(T, &root, ndi, &inentry); \
02557 \
02558 BPT_SET_ROOT(bpt, root.addr); \
02559 head1->parent = root.addr; \
02560 head2->parent = root.addr; \
02561 \
02562 bpt->height++; \
02563 \
02564 BPT_UNLOAD(bpt, &root); \
02565 } \
02566 \
02567
02568
02569
02570 \
02571 \
02572 int bpt_balanceout_##T(t_bpt(T) *bpt, \
02573 t_bpt_imm(T) *node1, \
02574 t_bpt_imm(T) *node2, \
02575 void *entry, \
02576 t_bpt_cbctx(T) *cbctx) \
02577 { \
02578 t_bpt_head(T) *head1 = BPT_HEAD(T, node1); \
02579 t_bpt_ndi(T) nkeys = BPT_NKEYS(T, bpt, node1); \
02580 t_bpt_head(T) *head2; \
02581 t_bpt_ndi(T) i; \
02582 t_bpt_ndi(T) j; \
02583 \
02584 BPT_COPY_NODE(bpt, node1->buf, node2->buf); \
02585 bpt_reinit_entries(T, bpt, node1); \
02586 head2 = BPT_HEAD(T, node2); \
02587 \
02588 for (i = 0, j = 0; i < ((nkeys + 1) / 2); i++) \
02589 { \
02590 if ((entry != NULL) && \
02591 (BPT_GET_THIS_ENTRY(T, head1, entry, _key_) < \
02592 BPT_GET_ENTRY(T, node2, j, _key_))) \
02593 { \
02594 BPT_IMPORT_ENTRY(T, node1, i, entry); \
02595 \
02596 BPT_SET_CBCTX(bpt, head1, cbctx, current.node, node1->addr); \
02597 BPT_SET_CBCTX(bpt, head1, cbctx, current.ndi, i); \
02598 \
02599 entry = NULL; \
02600 continue; \
02601 } \
02602 \
02603 BPT_COPY_ENTRY(T, node2, node1, j, i); \
02604 BPT_INIT_ENTRY(T, node2, j); \
02605 BPT_SET_ENTRY(T, node2, j, _value_, bpt->unused); \
02606 j++; \
02607 } \
02608 \
02609 bpt_shift_sort(T, bpt, node2); \
02610 \
02611 if (entry != NULL) \
02612 { \
02613 bpt_insert_sort(T, bpt, node2, \
02614 BPT_GET_THIS_ENTRY(T, head1, entry, _key_), \
02615 BPT_GET_THIS_ENTRY(T, head1, entry, _value_), \
02616 &i, BPT_OPT_ZERO); \
02617 BPT_IMPORT_ENTRY(T, node2, i, entry); \
02618 \
02619 BPT_SET_CBCTX(bpt, head2, cbctx, current.node, node2->addr); \
02620 BPT_SET_CBCTX(bpt, head2, cbctx, current.ndi, i); \
02621 } \
02622 \
02623 head2->prv = node1->addr; \
02624 head2->nxt = head1->nxt; \
02625 head1->nxt = node2->addr; \
02626 \
02627 if (head2->nxt != bpt->unused) \
02628 { \
02629 t_bpt_head(T) *head3; \
02630 t_bpt_imm(T) node3; \
02631 \
02632 BPT_LOAD(bpt, &node3, head2->nxt); \
02633 head3 = BPT_HEAD(T, &node3); \
02634 head3->prv = node2->addr; \
02635 BPT_UNLOAD(bpt, &node3); \
02636 } \
02637 \
02638 if (head1->type == BPT_TYPE_INTERNAL) \
02639 { \
02640 if (bpt_update(T, bpt, node1, BPT_OPT_PARENT) != 0) \
02641 return (-1); \
02642 \
02643 if (bpt_update(T, bpt, node2, BPT_OPT_PARENT) != 0) \
02644 return (-1); \
02645 } \
02646 \
02647 return (0); \
02648 } \
02649 \
02650
02651
02652
02653
02654
02655
02656
02657
02658 \
02659 \
02660 int bpt_split_node_##T(t_bpt(T) *bpt, \
02661 t_bpt_imm(T) *node1, \
02662 void *entry, \
02663 t_bpt_cbctx(T) *cbctx, \
02664 t_bpt_unused(T) *unused) \
02665 { \
02666 t_bpt_head(T) *head1 = BPT_HEAD(T, node1); \
02667 t_bpt_head(T) *head2; \
02668 t_bpt_imm(T) node2; \
02669 t_bpt_addr(T) blk; \
02670 \
02671 BPT_RESERVE(bpt, unused, blk); \
02672 BPT_LOAD(bpt, &node2, blk); \
02673 \
02674 bpt_make_node(T, bpt, &node2, head1->type, head1->parent); \
02675 head2 = BPT_HEAD(T, &node2); \
02676 \
02677 if (bpt_balanceout(T, bpt, node1, &node2, entry, cbctx) != 0) \
02678 { \
02679 bpt_debug("[bptd] cannot balance entries between two nodes\n"); \
02680 BPT_UNLOAD(bpt, &node2); \
02681 BPT_RELEASE(bpt, unused, blk); \
02682 return (-1); \
02683 } \
02684 \
02685 if (head1->parent == bpt->unused) \
02686 { \
02687 bpt_new_root(T, bpt, node1, &node2, unused); \
02688 } \
02689 else \
02690 { \
02691 t_bpt_inentry(T) inentry; \
02692 t_bpt_imm(T) parent; \
02693 \
02694 if (bpt_update(T, bpt, node1, BPT_OPT_KEY) != 0) \
02695 { \
02696 BPT_UNLOAD(bpt, &node2); \
02697 BPT_RELEASE(bpt, unused, blk); \
02698 return (-1); \
02699 } \
02700 \
02701 memset(&inentry, 0x0, sizeof(t_bpt_inentry(T))); \
02702 bpt_key(T, bpt, &node2, &inentry._key_); \
02703 inentry._value_ = node2.addr; \
02704 \
02705 BPT_LOAD(bpt, &parent, head2->parent); \
02706 \
02707 if (bpt_insert(T, bpt, &parent, &inentry, cbctx, unused) != 0) \
02708 { \
02709 bpt_debug("[bptd] cannot insert the entry in the parent node\n"); \
02710 BPT_UNLOAD(bpt, &parent); \
02711 BPT_UNLOAD(bpt, &node2); \
02712 BPT_RELEASE(bpt, unused, blk); \
02713 return (-1); \
02714 } \
02715 \
02716 BPT_UNLOAD(bpt, &parent); \
02717 } \
02718 \
02719 BPT_SET_CBCTX(bpt, head1, cbctx, cb, BPT_CB_SPLIT); \
02720 BPT_SET_CBCTX(bpt, head1, cbctx, node1, node1->addr); \
02721 BPT_SET_CBCTX(bpt, head1, cbctx, node2, node2.addr); \
02722 \
02723 BPT_UNLOAD(bpt, &node2); \
02724 \
02725 return (0); \
02726 } \
02727 \
02728
02729
02730
02731
02732
02733
02734
02735
02736 \
02737 \
02738 int bpt_insert_##T(t_bpt(T) *bpt, \
02739 t_bpt_imm(T) *node, \
02740 void *entry, \
02741 t_bpt_cbctx(T) *cbctx, \
02742 t_bpt_unused(T) *unused) \
02743 { \
02744 t_bpt_head(T) *head = BPT_HEAD(T, node); \
02745 \
02746 if (bpt_node_size(T, bpt, node) < BPT_NKEYS(T, bpt, node)) \
02747 { \
02748 t_bpt_ndi(T) ndi; \
02749 \
02750 bpt_insert_sort(T, bpt, node, \
02751 BPT_GET_THIS_ENTRY(T, head, entry, _key_), \
02752 BPT_GET_THIS_ENTRY(T, head, entry, _value_), \
02753 &ndi, BPT_OPT_ZERO); \
02754 \
02755 BPT_IMPORT_ENTRY(T, node, ndi, entry); \
02756 \
02757 if (bpt_update(T, bpt, node, BPT_OPT_KEY) != 0) \
02758 { \
02759 bpt_debug("[bptd] cannot update the tree\n"); \
02760 return (-1); \
02761 } \
02762 \
02763 BPT_SET_CBCTX(bpt, head, cbctx, cb, BPT_CB_INSERT); \
02764 BPT_SET_CBCTX(bpt, head, cbctx, current.node, node->addr); \
02765 BPT_SET_CBCTX(bpt, head, cbctx, current.ndi, ndi); \
02766 BPT_SET_CBCTX(bpt, head, cbctx, node, node->addr); \
02767 } \
02768 else \
02769 { \
02770 if (bpt_split_node(T, bpt, node, entry, cbctx, unused) != 0) \
02771 { \
02772 bpt_debug("[bptd] cannot split the node\n"); \
02773 return (-1); \
02774 } \
02775 } \
02776 \
02777 return (0); \
02778 } \
02779 \
02780
02781
02782
02783
02784
02785
02786
02787
02788
02789
02790
02791 \
02792 \
02793 int bpt_add_##T(t_bpt(T) *bpt, \
02794 t_bpt_lfentry(T) *lfentry, \
02795 t_bpt_unused(T) *unused) \
02796 { \
02797 t_bpt_cbctx(T) cbctx; \
02798 t_bpt_addr(T) addr; \
02799 t_bpt_imm(T) leaf; \
02800 t_bpt_imm(T) root; \
02801 \
02802 if (bpt_check_unused(T, bpt, unused, BPT_OPT_ADD) != 0) \
02803 { \
02804 bpt_debug("[bptd] bad unused array\n"); \
02805 return (-1); \
02806 } \
02807 \
02808 if (lfentry->_value_ == bpt->unused) \
02809 { \
02810 bpt_debug("[bptd] the leaf entry to insert has a non-valid key\n"); \
02811 return (-1); \
02812 } \
02813 \
02814 BPT_LOAD(bpt, &root, BPT_GET_ROOT(bpt)); \
02815 \
02816 if (bpt_search_leaf(T, bpt, &root, &addr, lfentry->_key_) != 0) \
02817 { \
02818 bpt_debug("[bptd] no leaf present in the tree\n"); \
02819 BPT_UNLOAD(bpt, &root); \
02820 return (-1); \
02821 } \
02822 \
02823 BPT_UNLOAD(bpt, &root); \
02824 BPT_LOAD(bpt, &leaf, addr); \
02825 \
02826 if (bpt_check_collide(T, bpt, &leaf, lfentry->_key_, lfentry->_value_) != 0)\
02827 { \
02828 bpt_debug("[bptd] this entry collide with an other\n"); \
02829 BPT_UNLOAD(bpt, &leaf); \
02830 return (-1); \
02831 } \
02832 \
02833 BPT_INIT_CBCTX(bpt, &cbctx); \
02834 \
02835 if (bpt_insert(T, bpt, &leaf, lfentry, &cbctx, unused) != 0) \
02836 { \
02837 bpt_debug("[bptd] cannot insert the leaf entry\n"); \
02838 BPT_UNLOAD(bpt, &leaf); \
02839 return (-1); \
02840 } \
02841 \
02842 BPT_CALLBACK(bpt, &cbctx); \
02843 \
02844 BPT_UNLOAD(bpt, &leaf); \
02845 \
02846 return (0); \
02847 } \
02848 \
02849
02850
02851
02852 \
02853 \
02854 int bpt_init_##T(t_bpt(T) *bpt, \
02855 t_bpt_blksz(T) blksz, \
02856 t_bpt_addr(T) unusedvalue, \
02857 t_bpt_flags flags, \
02858 t_bpt_load_fn(T) load, \
02859 t_bpt_unload_fn(T) unload, \
02860 t_bpt_callback_fn(T) callback, \
02861 t_bpt_unused(T) *unused) \
02862 { \
02863 t_bpt_imm(T) root; \
02864 \
02865 if (bpt_check_unused(T, bpt, unused, BPT_OPT_INIT) != 0) \
02866 { \
02867 bpt_debug("[bptd] bad unused array\n"); \
02868 return (-1); \
02869 } \
02870 \
02871 bpt->blksz = blksz; \
02872 bpt->unused = unusedvalue; \
02873 bpt->nodes = 0; \
02874 bpt->flags = flags; \
02875 bpt->nikeys = (bpt->blksz - sizeof(t_bpt_head(T))) / \
02876 sizeof(t_bpt_inentry(T)); \
02877 bpt->nlkeys = (bpt->blksz - sizeof(t_bpt_head(T))) / \
02878 sizeof(t_bpt_lfentry(T)); \
02879 bpt->height = BPT_INIT_HEIGHT; \
02880 \
02881 if (bpt->nikeys < BPT_INIT_NIKEYS) \
02882 { \
02883 bpt_debug("[bptd] number of keys per internal node too low\n"); \
02884 return (-1); \
02885 } \
02886 \
02887 if (bpt->nlkeys < BPT_INIT_NLKEYS) \
02888 { \
02889 bpt_debug("[bptd] number of keys per leaf node too low\n"); \
02890 return (-1); \
02891 } \
02892 \
02893 BPT_RESERVE(bpt, unused, bpt->root); \
02894 \
02895 bpt->load = load; \
02896 bpt->unload = unload; \
02897 bpt->callback = callback; \
02898 \
02899 BPT_LOAD(bpt, &root, BPT_GET_ROOT(bpt)); \
02900 \
02901 bpt_make_node(T, bpt, &root, BPT_TYPE_LEAF, bpt->unused); \
02902 \
02903 BPT_UNLOAD(bpt, &root); \
02904 \
02905 return (0); \
02906 } \
02907 \
02908
02909
02910 \
02911 \
02912 int bpt_clean_node_##T(t_bpt(T) *bpt, \
02913 t_bpt_imm(T) *node, \
02914 t_bpt_unused(T) *unused) \
02915 { \
02916 t_bpt_head(T) *head = BPT_HEAD(T, node); \
02917 t_bpt_ndi(T) nkeys = BPT_NKEYS(T, bpt, node); \
02918 t_bpt_imm(T) child; \
02919 t_bpt_ndi(T) i; \
02920 \
02921 BPT_RELEASE(bpt, unused, node->addr); \
02922 \
02923 if (head->type == BPT_TYPE_LEAF) \
02924 return (0); \
02925 \
02926 for (i = 0; (i < nkeys) && \
02927 (BPT_GET_ENTRY(T, node, i, _value_) != bpt->unused); \
02928 i++) \
02929 { \
02930 BPT_LOAD(bpt, &child, BPT_GET_ENTRY(T, node, i, _value_)); \
02931 \
02932 if (bpt_clean_node(T, bpt, &child, unused) != 0) \
02933 { \
02934 BPT_UNLOAD(bpt, &child); \
02935 return (-1); \
02936 } \
02937 \
02938 BPT_UNLOAD(bpt, &child); \
02939 } \
02940 \
02941 return (0); \
02942 } \
02943 \
02944
02945
02946
02947
02948
02949 \
02950 \
02951 int bpt_clean_##T(t_bpt(T) *bpt, \
02952 t_bpt_unused(T) *unused) \
02953 { \
02954 t_bpt_imm(T) root; \
02955 \
02956 if (bpt_check_unused(T, bpt, unused, BPT_OPT_CLEAN) != 0) \
02957 { \
02958 bpt_debug("[bptd] bad unused array\n"); \
02959 return (-1); \
02960 } \
02961 \
02962 BPT_LOAD(bpt, &root, BPT_GET_ROOT(bpt)); \
02963 \
02964 if (bpt_clean_node(T, bpt, &root, unused) != 0) \
02965 { \
02966 bpt_debug("[bptd] cannot clean the nodes\n"); \
02967 BPT_UNLOAD(bpt, &root); \
02968 return (-1); \
02969 } \
02970 \
02971 BPT_UNLOAD(bpt, &root); \
02972 \
02973 return (0); \
02974 }
02975
02976 #define bpt_make(T, _t_bpt_blksz_, _t_bpt_ndi_, _t_bpt_uni_, \
02977 _t_bpt_nodes_, _t_bpt_height_, _t_bpt_key_, \
02978 _t_bpt_addr_, _t_bpt_inentry_, _t_bpt_lfentry_, \
02979 _key_, _value_) \
02980 bpt_make_types(T, _t_bpt_blksz_, _t_bpt_ndi_, _t_bpt_uni_, _t_bpt_nodes_, \
02981 _t_bpt_height_, _t_bpt_key_, _t_bpt_addr_, _t_bpt_inentry_, \
02982 _t_bpt_lfentry_) \
02983 bpt_make_protos(T) \
02984 bpt_make_functions(T, _key_, _value_)
02985
02986 #endif
