bptarea.h

Go to the documentation of this file.

/*
** bptarea.h for lseos in lseos-lib/libarea
** 
** Copyright (c)2004 Vianney Rancurel, Julien Quintard
** Login   <vianney@epita.fr>
** 
** Started on  Fri Oct 29 17:27:17 2004 Vianney Rancurel
** Last update Mon Dec  6 12:31:29 2004 Vianney Rancurel
*/
#ifndef __LIBAREA_BPTAREA_H__
#define __LIBAREA_BPTAREA_H__   1

typedef struct          s_inentry
{
  t_area_uint           key;
  t_area_uint           value;
  t_area_uint           interval;
}                       t_inentry;

typedef struct          s_lfentry
{
  t_area_uint           key;
  t_area_uint           value;
  t_area_uint           interval;
}                       t_lfentry;

bpt_make_types(area_tree,
               t_area_uint,
               t_area_int,              /* ndi          */
               t_area_int,              /* uni          */
               t_area_uint,
               t_area_uint,
               t_area_uint,
               t_area_uint,
               t_inentry,
               t_lfentry)

bpt_make_protos(area_tree)

/* PROTO bptarea.c */
/* bptarea.c */
int bpt_list_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_entry_area_tree *entry, t_bpt_opts opts);
int bpt_check_unused_area_tree(t_bpt_area_tree *bpt, t_bpt_unused_area_tree *unused, t_bpt_opts opts);
int bpt_first_entry_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_ndi_area_tree *first);
int bpt_prev_entry_area_tree(t_bpt_area_tree *bpt, t_bpt_entry_area_tree current, t_bpt_entry_area_tree *previous, t_bpt_opts opts);
int bpt_next_entry_area_tree(t_bpt_area_tree *bpt, t_bpt_entry_area_tree current, t_bpt_entry_area_tree *next, t_bpt_opts opts);
int bpt_last_entry_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_ndi_area_tree *last);
void bpt_reinit_entries_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node);
void bpt_make_node_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_type type, t_bpt_node_area_tree parent);
void bpt_key_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_key_area_tree *key);
int bpt_ndi_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_addr_area_tree value, t_bpt_ndi_area_tree *ndi);
int bpt_update_node_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_node_area_tree addr, t_bpt_key_area_tree key, t_bpt_opts opts);
void bpt_update_parent_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node);
int bpt_update_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_opts opts);
int bpt_linear_search_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_key_area_tree key, t_bpt_ndi_area_tree *ndi, t_bpt_opts opts);
int bpt_dichotomic_search_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_key_area_tree key, t_bpt_ndi_area_tree *ndi, t_bpt_opts opts);
int bpt_search_entry_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_key_area_tree key, t_bpt_ndi_area_tree *ndi, t_bpt_opts opts);
int bpt_search_leaf_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_node_area_tree *leaf, t_bpt_key_area_tree key);
int bpt_search_area_tree(t_bpt_area_tree *bpt, t_bpt_key_area_tree key, t_bpt_entry_area_tree *entry);
int bpt_collide_next_area_tree(t_bpt_area_tree *bpt, t_bpt_key_area_tree key, t_bpt_entry_area_tree *entry);
int bpt_collide_search_area_tree(t_bpt_area_tree *bpt, t_bpt_key_area_tree key, t_bpt_addr_area_tree value, t_bpt_entry_area_tree *entry);
int bpt_check_collide_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node1, t_bpt_key_area_tree key, t_bpt_addr_area_tree value);
t_bpt_ndi_area_tree bpt_node_size_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node);
void bpt_simplify_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node1, t_bpt_unused_area_tree *unused);
int bpt_balancein_1_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node1, t_bpt_imm_area_tree *node2, t_bpt_cbctx_area_tree *cbctx, t_bpt_entry_area_tree prev, t_bpt_unused_area_tree *unused);
int bpt_balancein_2_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node1, t_bpt_imm_area_tree *node2, t_bpt_cbctx_area_tree *cbctx, t_bpt_entry_area_tree prev, t_bpt_unused_area_tree *unused);
int bpt_balancein_3_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node2, t_bpt_imm_area_tree *node1, t_bpt_cbctx_area_tree *cbctx, t_bpt_entry_area_tree prev, t_bpt_unused_area_tree *unused);
int bpt_balancein_4_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node2, t_bpt_imm_area_tree *node1, t_bpt_cbctx_area_tree *cbctx, t_bpt_entry_area_tree prev, t_bpt_unused_area_tree *unused);
int bpt_delete_area_tree(t_bpt_area_tree *bpt, t_bpt_entry_area_tree entry, t_bpt_cbctx_area_tree *cbctx, t_bpt_unused_area_tree *unused);
int bpt_remove_area_tree(t_bpt_area_tree *bpt, t_bpt_key_area_tree key, t_bpt_unused_area_tree *unused);
int bpt_collide_remove_area_tree(t_bpt_area_tree *bpt, t_bpt_entry_area_tree entry, t_bpt_unused_area_tree *unused);
int bpt_modify_area_tree(t_bpt_area_tree *bpt, t_bpt_key_area_tree key, t_bpt_lfentry_area_tree *lfentry, t_bpt_unused_area_tree *unused);
int bpt_collide_modify_area_tree(t_bpt_area_tree *bpt, t_bpt_entry_area_tree entry, t_bpt_lfentry_area_tree *lfentry, t_bpt_unused_area_tree *unused);
void bpt_insert_head_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node1, t_bpt_imm_area_tree *node2);
void bpt_insert_tail_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node1, t_bpt_imm_area_tree *node2);
void bpt_shift_sort_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node);
void bpt_insert_sort_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_key_area_tree key, t_bpt_addr_area_tree value, t_bpt_ndi_area_tree *ndi, t_bpt_opts opts);
void bpt_new_root_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node1, t_bpt_imm_area_tree *node2, t_bpt_unused_area_tree *unused);
int bpt_balanceout_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node1, t_bpt_imm_area_tree *node2, void *entry, t_bpt_cbctx_area_tree *cbctx);
int bpt_split_node_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node1, void *entry, t_bpt_cbctx_area_tree *cbctx, t_bpt_unused_area_tree *unused);
int bpt_insert_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, void *entry, t_bpt_cbctx_area_tree *cbctx, t_bpt_unused_area_tree *unused);
int bpt_add_area_tree(t_bpt_area_tree *bpt, t_bpt_lfentry_area_tree *lfentry, t_bpt_unused_area_tree *unused);
int bpt_init_area_tree(t_bpt_area_tree *bpt, t_bpt_blksz_area_tree blksz, t_bpt_addr_area_tree unusedvalue, t_bpt_flags flags, t_bpt_load_fn_area_tree load, t_bpt_unload_fn_area_tree unload, t_bpt_callback_fn_area_tree callback, t_bpt_unused_area_tree *unused);
int bpt_clean_node_area_tree(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_unused_area_tree *unused);
int bpt_clean_area_tree(t_bpt_area_tree *bpt, t_bpt_unused_area_tree *unused);
void bptarea_dump_node(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_area_uint level);
void bptarea_dump(t_bpt_area_tree *bpt);
void bptarea_load(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_node_area_tree addr);
void bptarea_unload(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node);
t_area_uint bptarea_get_interval(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, int how);
void bptarea_cb_update_node(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node, t_bpt_node_area_tree addr, t_area_uint interval);
void bptarea_cb_update(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node);
void bptarea_cb_interval(t_bpt_area_tree *bpt, t_bpt_imm_area_tree *node1, t_bpt_ndi_area_tree ndi);
void bptarea_cb_insert(t_bpt_area_tree *bpt, t_bpt_cbctx_area_tree *cbctx);
void bptarea_cb_split(t_bpt_area_tree *bpt, t_bpt_cbctx_area_tree *cbctx);
void bptarea_cb_modify(t_bpt_area_tree *bpt, t_bpt_cbctx_area_tree *cbctx);
void bptarea_cb_delete(t_bpt_area_tree *bpt, t_bpt_cbctx_area_tree *cbctx);
void bptarea_cb_migrate(t_bpt_area_tree *bpt, t_bpt_cbctx_area_tree *cbctx);
void bptarea_cb_balance(t_bpt_area_tree *bpt, t_bpt_cbctx_area_tree *cbctx);
void bptarea_callback(t_bpt_area_tree *bpt, t_bpt_cbctx_area_tree *cbctx);
void bptarea_set_subinit(struct s_area_set *area_set);
t_area_status bptarea_set_add(struct s_area_set *set, t_area **io);
int bptarea_find_colliding_area(t_bpt_area_tree *bpt, t_bpt_entry_area_tree *entry, t_bpt_imm_area_tree *node, t_area_uint blk, int nb_blks);
t_area_status bptarea_set_collide(struct s_area_set *set, t_area_uint blk, int nb_blks);
int bptarea_find_enclosing_area(t_bpt_area_tree *bpt, t_bpt_entry_area_tree *entry, t_bpt_imm_area_tree *node, t_area_uint blk, int nb_blks);
t_area_status bptarea_set_get_area(struct s_area_set *set, t_area_uint blk, int nb_blks, t_area **bptarea);
t_area_status bptarea_set_remove(struct s_area_set *set, t_area **io, int no_alloc);
t_area_status bptarea_set_modify(struct s_area_set *set, t_area **io, int no_alloc);
int bptarea_find_best_interval(t_bpt_area_tree *bpt, t_bpt_entry_area_tree *entry, t_bpt_imm_area_tree *node, t_area_uint interval);
t_area_status bptarea_set_find_space(struct s_area_set *set, int nb_blks, t_area_fit_method fit, u_int32_t fitopts, t_area_uint *blk_returned);
void bptarea_set_dump(t_area_printf_fn printf_fn, struct s_area_set *set, t_area_match_fn match, void *val);
int bptarea_set_foreach(struct s_area_set *set, t_area_foreach_fn foreach, void *val);
t_area_uint bptarea_set_used(struct s_area_set *set, t_area_match_fn match, void *val, int *nb_areas);
int bptarea_set_empty(struct s_area_set *set);
int bptarea_set_add_alloc(struct s_area_set *area_set);
int bptarea_set_add_size(struct s_area_set *area_set);
int bptarea_set_modify_alloc(struct s_area_set *area_set);
int bptarea_set_modify_size(struct s_area_set *area_set);
int bptarea_set_remove_alloc(struct s_area_set *area_set);
int bptarea_set_remove_size(struct s_area_set *area_set);
t_area_status bptarea_set_old_add(struct s_area_set *set, t_area **new, t_area **unused1);
t_area_status bptarea_set_old_remove(struct s_area_set *set, t_area **todel, t_area **unused1, int no_alloc);
t_area_status bptarea_set_old_modify(struct s_area_set *set, t_area **new, t_area **new2, t_area **unused1, t_area **unused2, int no_alloc);
t_area_status bptarea_set_find_coalescible_space(struct s_area_set *set, t_area *ref_bptarea, t_area_fit_method fit, u_int32_t fitopts, t_area_uint *blk_returned);
#endif

---