Data types


Files

file  bitmap.h
file  btree.h
file  fifo.h
file  hash_table.h
file  list.h
file  bitmap.c
 Implementation of bitmap ADT.
file  btree.c
 B+tree implementation.
file  hash_table.c
 Implementation of generic chained hash table.
file  list.c
 Functions completing doubly linked circular list implementaion.

Data Structures

struct  bitmap_t
struct  btree_node
struct  btree
struct  hash_table
struct  hash_table_operations
struct  link

Defines

#define BITS2BYTES(bits)   (bits ? ((((bits)-1)>>3)+1) : 0)
#define BTREE_M   5
#define BTREE_MAX_KEYS   (BTREE_M - 1)
#define FIFO_INITIALIZE_STATIC(name, t, itms)
#define FIFO_INITIALIZE_DYNAMIC(name, t, itms)
#define fifo_pop(name)   name.fifo[name.head = (name.head + 1) < name.items ? (name.head + 1) : 0]
#define fifo_push(name, value)   name.fifo[name.tail = (name.tail + 1) < name.items ? (name.tail + 1) : 0] = (value)
#define fifo_create(name)   name.fifo = malloc(sizeof(*name.fifo) * name.items, 0)
#define hash_table_get_instance(item, type, member)   list_get_instance((item), type, member)
#define LIST_INITIALIZE(name)   link_t name = { .prev = &name, .next = &name }
#define list_get_instance(link, type, member)   (type *)(((__u8*)(link))-((__u8*)&(((type *)NULL)->member)))
#define ALL_ONES   0xff
#define ALL_ZEROES   0x00
#define ROOT_NODE(n)   (!(n)->parent)
#define INDEX_NODE(n)   ((n)->subtree[0] != NULL)
#define LEAF_NODE(n)   ((n)->subtree[0] == NULL)
#define FILL_FACTOR   ((BTREE_M-1)/2)
#define MEDIAN_LOW_INDEX(n)   (((n)->keys-1)/2)
#define MEDIAN_HIGH_INDEX(n)   ((n)->keys/2)
#define MEDIAN_LOW(n)   ((n)->key[MEDIAN_LOW_INDEX((n))]);
#define MEDIAN_HIGH(n)   ((n)->key[MEDIAN_HIGH_INDEX((n))]);

Typedefs

typedef __u64 btree_key_t

Functions

void bitmap_initialize (bitmap_t *bitmap, __u8 *map, count_t bits)
void bitmap_set_range (bitmap_t *bitmap, index_t start, count_t bits)
void bitmap_clear_range (bitmap_t *bitmap, index_t start, count_t bits)
void bitmap_copy (bitmap_t *dst, bitmap_t *src, count_t bits)
void btree_init (void)
void btree_create (btree_t *t)
void btree_destroy (btree_t *t)
void btree_insert (btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node)
void btree_remove (btree_t *t, btree_key_t key, btree_node_t *leaf_node)
void * btree_search (btree_t *t, btree_key_t key, btree_node_t **leaf_node)
btree_node_t * btree_leaf_node_left_neighbour (btree_t *t, btree_node_t *node)
btree_node_t * btree_leaf_node_right_neighbour (btree_t *t, btree_node_t *node)
void btree_print (btree_t *t)
void hash_table_create (hash_table_t *h, count_t m, count_t max_keys, hash_table_operations_t *op)
void hash_table_insert (hash_table_t *h, __native key[], link_t *item)
link_t * hash_table_find (hash_table_t *h, __native key[])
void hash_table_remove (hash_table_t *h, __native key[], count_t keys)
static void link_initialize (link_t *link)
static void list_initialize (link_t *head)
static void list_prepend (link_t *link, link_t *head)
static void list_append (link_t *link, link_t *head)
static void list_remove (link_t *link)
static bool list_empty (link_t *head)
static void headless_list_split_or_concat (link_t *part1, link_t *part2)
static void headless_list_split (link_t *part1, link_t *part2)
static void headless_list_concat (link_t *part1, link_t *part2)
bool list_member (const link_t *link, const link_t *head)
void list_concat (link_t *head1, link_t *head2)
static void btree_destroy_subtree (btree_node_t *root)
static void _btree_insert (btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node)
static void _btree_remove (btree_t *t, btree_key_t key, btree_node_t *node)
static void node_initialize (btree_node_t *node)
static void node_insert_key_and_lsubtree (btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree)
static void node_insert_key_and_rsubtree (btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
static void node_remove_key_and_lsubtree (btree_node_t *node, btree_key_t key)
static void node_remove_key_and_rsubtree (btree_node_t *node, btree_key_t key)
static btree_node_t * node_split (btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median)
static btree_node_t * node_combine (btree_node_t *node)
static index_t find_key_by_subtree (btree_node_t *node, btree_node_t *subtree, bool right)
static void rotate_from_right (btree_node_t *lnode, btree_node_t *rnode, index_t idx)
static void rotate_from_left (btree_node_t *lnode, btree_node_t *rnode, index_t idx)
static bool try_insert_by_rotation_to_left (btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
static bool try_insert_by_rotation_to_right (btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
static bool try_rotation_from_left (btree_node_t *rnode)
static bool try_rotation_from_right (btree_node_t *lnode)

Variables

static slab_cache_t * btree_node_slab

Define Documentation

#define ALL_ONES   0xff
 

Definition at line 47 of file bitmap.c.

Referenced by bitmap_set_range().

#define ALL_ZEROES   0x00
 

Definition at line 48 of file bitmap.c.

Referenced by bitmap_clear_range().

#define BITS2BYTES (  bits   )     (bits ? ((((bits)-1)>>3)+1) : 0)
 

Definition at line 41 of file bitmap.h.

Referenced by ddi_iospace_enable_arch(), and io_perm_bitmap_install().

#define BTREE_M   5
 

Definition at line 42 of file btree.h.

#define BTREE_MAX_KEYS   (BTREE_M - 1)
 

Definition at line 43 of file btree.h.

Referenced by _btree_insert(), node_initialize(), node_split(), try_insert_by_rotation_to_left(), and try_insert_by_rotation_to_right().

#define fifo_create (  name   )     name.fifo = malloc(sizeof(*name.fifo) * name.items, 0)
 

Allocate memory for dynamic FIFO.

Parameters:
name FIFO name.

Definition at line 116 of file fifo.h.

#define FIFO_INITIALIZE_DYNAMIC (  name,
t,
itms   ) 
 

Value:

struct {                                        \
                t *fifo;                                \
                count_t items;                          \
                index_t head;                           \
                index_t tail;                           \
        } name = {                                      \
                .fifo = NULL,                           \
                .items = (itms),                        \
                .head = 0,                              \
                .tail = 0                               \
        }
Create and prepare dynamic FIFO.

FIFO is allocated dynamically. This macro is suitable for creating larger FIFOs.

Parameters:
name Name of FIFO.
t Type of values stored in FIFO.
itms Number of items that can be stored in FIFO.

Definition at line 81 of file fifo.h.

#define FIFO_INITIALIZE_STATIC (  name,
t,
itms   ) 
 

Value:

struct {                                        \
                t fifo[(itms)];                         \
                count_t items;                          \
                index_t head;                           \
                index_t tail;                           \
        } name = {                                      \
                .items = (itms),                        \
                .head = 0,                              \
                .tail = 0                               \
        }
Create and initialize static FIFO.

FIFO is allocated statically. This macro is suitable for creating smaller FIFOs.

Parameters:
name Name of FIFO.
t Type of values stored in FIFO.
itms Number of items that can be stored in FIFO.

Definition at line 60 of file fifo.h.

#define fifo_pop (  name   )     name.fifo[name.head = (name.head + 1) < name.items ? (name.head + 1) : 0]
 

Pop value from head of FIFO.

Parameters:
name FIFO name.
Returns:
Leading value in FIFO.

Definition at line 100 of file fifo.h.

#define fifo_push (  name,
value   )     name.fifo[name.tail = (name.tail + 1) < name.items ? (name.tail + 1) : 0] = (value)
 

Push value to tail of FIFO.

Parameters:
name FIFO name.
value Value to be appended to FIFO.

Definition at line 109 of file fifo.h.

#define FILL_FACTOR   ((BTREE_M-1)/2)
 

Definition at line 79 of file btree.c.

Referenced by _btree_remove(), try_rotation_from_left(), and try_rotation_from_right().

#define hash_table_get_instance (  item,
type,
member   )     list_get_instance((item), type, member)
 

Definition at line 75 of file hash_table.h.

Referenced by futex_find(), futex_ht_compare(), and futex_ht_remove_callback().

#define INDEX_NODE (  n   )     ((n)->subtree[0] != NULL)
 

Definition at line 76 of file btree.c.

Referenced by node_combine(), and node_split().

#define LEAF_NODE (  n   )     ((n)->subtree[0] == NULL)
 

Definition at line 77 of file btree.c.

Referenced by _btree_insert(), btree_leaf_node_left_neighbour(), btree_leaf_node_right_neighbour(), btree_search(), rotate_from_left(), and rotate_from_right().

#define list_get_instance (  link,
type,
member   )     (type *)(((__u8*)(link))-((__u8*)&(((type *)NULL)->member)))
 

Definition at line 178 of file list.h.

Referenced by _waitq_wakeup_unsafe(), anon_share(), as_area_destroy(), as_area_resize(), as_destroy(), btree_leaf_node_left_neighbour(), btree_leaf_node_right_neighbour(), btree_print(), clock(), cmd_desc(), cmd_help(), cmd_register(), cmdtab_compl(), cmdtab_search_one(), elf_share(), futex_cleanup(), get_call(), get_mag_from_cache(), ipc_cleanup(), ipc_cleanup_call_list(), ipc_wait_for_call(), kcpulb(), ktaskclnp(), ktaskgc(), let_others_in(), parse_cmdline(), sched_print_list(), sh_info_remove_reference(), slab_enable_cpucache(), slab_obj_create(), slab_print_list(), slab_reclaim(), task_kill(), task_print_list(), thread_print_list(), timeout_register(), timeout_unregister(), zone_buddy_bisect(), zone_buddy_coalesce(), zone_buddy_find_block(), zone_buddy_find_buddy(), zone_buddy_get_order(), zone_buddy_mark_available(), zone_buddy_mark_busy(), zone_buddy_print_id(), zone_buddy_set_order(), and zone_frame_alloc().

#define LIST_INITIALIZE (  name   )     link_t name = { .prev = &name, .next = &name }
 

Declare and initialize statically allocated list.

Parameters:
name Name of the new statically allocated list.

Definition at line 51 of file list.h.

#define MEDIAN_HIGH (  n   )     ((n)->key[MEDIAN_HIGH_INDEX((n))]);
 

Definition at line 84 of file btree.c.

Referenced by node_split().

#define MEDIAN_HIGH_INDEX (  n   )     ((n)->keys/2)
 

Definition at line 82 of file btree.c.

Referenced by node_split().

#define MEDIAN_LOW (  n   )     ((n)->key[MEDIAN_LOW_INDEX((n))]);
 

Definition at line 83 of file btree.c.

#define MEDIAN_LOW_INDEX (  n   )     (((n)->keys-1)/2)
 

Definition at line 81 of file btree.c.

#define ROOT_NODE (  n   )     (!(n)->parent)
 

Definition at line 75 of file btree.c.

Referenced by _btree_insert(), _btree_remove(), node_combine(), try_insert_by_rotation_to_left(), try_insert_by_rotation_to_right(), try_rotation_from_left(), and try_rotation_from_right().

Typedef Documentation

typedef __u64 btree_key_t
 

Definition at line 45 of file btree.h.

Function Documentation

void _btree_insert (  btree_t *  t,
btree_key_t  key,
void *  value,
btree_node_t *  rsubtree,
btree_node_t *  node
)  [static]
 

Recursively insert into B-tree.

Parameters:
t B-tree.
key Key to be inserted.
value Value to be inserted.
rsubtree Right subtree of the inserted key.
node Start inserting into this node.

Definition at line 160 of file btree.c.

References BTREE_MAX_KEYS, btree_node_slab, btree_node::depth, btree_node::keys, btree_node::leaf_link, LEAF_NODE, list_prepend(), node_initialize(), node_insert_key_and_rsubtree(), node_split(), NULL, btree_node::parent, btree::root, ROOT_NODE, slab_alloc(), btree_node::subtree, try_insert_by_rotation_to_left(), and try_insert_by_rotation_to_right().

Referenced by btree_insert().

Here is the call graph for this function:

void _btree_remove (  btree_t *  t,
btree_key_t  key,
btree_node_t *  node
)  [static]
 

Recursively remove B-tree node.

Parameters:
t B-tree.
key Key to be removed from the B-tree along with its associated value.
node Node where the key being removed resides.

Definition at line 241 of file btree.c.

References btree_node_slab, FILL_FACTOR, btree_node::key, btree_node::keys, node_remove_key_and_rsubtree(), NULL, btree_node::parent, btree::root, ROOT_NODE, slab_free(), btree_node::subtree, try_rotation_from_left(), and try_rotation_from_right().

Referenced by btree_remove().

Here is the call graph for this function:

void bitmap_clear_range (  bitmap_t *  bitmap,
index_t  start,
count_t  bits
) 
 

Clear range of bits.

Parameters:
bitmap Bitmap structure.
start Starting bit.
bits Number of bits to clear.

Definition at line 120 of file bitmap.c.

References ALIGN_UP, ALL_ZEROES, ASSERT, bitmap_t::map, and min.

Referenced by bitmap_copy(), and ddi_iospace_enable_arch().

void bitmap_copy (  bitmap_t *  dst,
bitmap_t *  src,
count_t  bits
) 
 

Copy portion of one bitmap into another bitmap.

Parameters:
dst Destination bitmap.
src Source bitmap.
bits Number of bits to copy.

Definition at line 172 of file bitmap.c.

References ASSERT, bitmap_clear_range(), and bitmap_t::map.

Referenced by ddi_iospace_enable_arch(), and io_perm_bitmap_install().

Here is the call graph for this function:

void bitmap_initialize (  bitmap_t *  bitmap,
__u8 *  map,
count_t  bits
) 
 

Initialize bitmap.

No portion of the bitmap is set or cleared by this function.

Parameters:
bitmap Bitmap structure.
map Address of the memory used to hold the map.
bits Number of bits stored in bitmap.

Definition at line 58 of file bitmap.c.

References bitmap_t::bits, and bitmap_t::map.

Referenced by ddi_iospace_enable_arch(), io_perm_bitmap_install(), and task_create_arch().

void bitmap_set_range (  bitmap_t *  bitmap,
index_t  start,
count_t  bits
) 
 

Set range of bits.

Parameters:
bitmap Bitmap structure.
start Starting bit.
bits Number of bits to set.

Definition at line 70 of file bitmap.c.

References ALIGN_UP, ALL_ONES, ASSERT, bitmap_t::map, and min.

Referenced by ddi_iospace_enable_arch(), and io_perm_bitmap_install().

void btree_create (  btree_t *  t  ) 
 

Create empty B-tree.

Parameters:
t B-tree.

Definition at line 98 of file btree.c.

References btree_node_slab, btree::leaf_head, btree_node::leaf_link, list_append(), list_initialize(), node_initialize(), btree::root, and slab_alloc().

Referenced by as_area_create(), as_area_share(), as_create(), task_create(), task_init(), and thread_init().

Here is the call graph for this function:

void btree_destroy (  btree_t *  t  ) 
 

Destroy empty B-tree.

Definition at line 107 of file btree.c.

References btree_destroy_subtree(), and btree::root.

Referenced by sh_info_remove_reference(), and task_destroy().

Here is the call graph for this function:

void btree_destroy_subtree (  btree_node_t *  root  )  [static]
 

Destroy subtree rooted in a node.

Parameters:
root Root of the subtree.

Definition at line 139 of file btree.c.

References btree_node::keys, btree::root, and btree_node::subtree.

Referenced by btree_destroy().

void btree_init (  void   ) 
 

Initialize B-trees.

Definition at line 89 of file btree.c.

References btree_node_slab, NULL, slab_cache_create(), and SLAB_CACHE_MAGDEFERRED.

Referenced by main_bsp_separated_stack().

Here is the call graph for this function:

void btree_insert (  btree_t *  t,
btree_key_t  key,
void *  value,
btree_node_t *  leaf_node
) 
 

Insert key-value pair into B-tree.

Parameters:
t B-tree.
key Key to be inserted.
value Value to be inserted.
leaf_node Leaf node where the insertion should begin.

Definition at line 119 of file btree.c.

References _btree_insert(), ASSERT, btree_search(), NULL, and panic.

Referenced by anon_page_fault(), anon_share(), as_area_create(), elf_share(), futex_find(), task_create(), thread_create(), and used_space_insert().

Here is the call graph for this function:

btree_node_t * btree_leaf_node_left_neighbour (  btree_t *  t,
btree_node_t *  node
) 
 

Return pointer to B-tree leaf node's left neighbour.

Parameters:
t B-tree.
node Node whose left neighbour will be returned.
Returns:
Left neighbour of the node or NULL if the node does not have the left neighbour.

Definition at line 383 of file btree.c.

References ASSERT, btree::leaf_head, btree_node::leaf_link, LEAF_NODE, list_get_instance, NULL, and link::prev.

Referenced by check_area_conflicts(), elf_share(), and used_space_insert().

btree_node_t * btree_leaf_node_right_neighbour (  btree_t *  t,
btree_node_t *  node
) 
 

Return pointer to B-tree leaf node's right neighbour.

Parameters:
t B-tree.
node Node whose right neighbour will be returned.
Returns:
Right neighbour of the node or NULL if the node does not have the right neighbour.

Definition at line 399 of file btree.c.

References ASSERT, btree::leaf_head, btree_node::leaf_link, LEAF_NODE, list_get_instance, link::next, and NULL.

Referenced by check_area_conflicts(), and used_space_insert().

void btree_print (  btree_t *  t  ) 
 

Print B-tree.

Parameters:
t Print out B-tree.

Definition at line 942 of file btree.c.

References ASSERT, btree_node::bfs_link, btree_node::depth, btree_node::key, btree_node::keys, list_append(), list_empty(), list_get_instance, list_initialize(), list_remove(), link::next, printf(), btree::root, and btree_node::subtree.

Here is the call graph for this function:

void btree_remove (  btree_t *  t,
btree_key_t  key,
btree_node_t *  leaf_node
) 
 

Remove B-tree node.

Parameters:
t B-tree.
key Key to be removed from the B-tree along with its associated value.
leaf_node If not NULL, pointer to the leaf node where the key is found.

Definition at line 221 of file btree.c.

References _btree_remove(), btree_search(), and panic.

Referenced by task_kill(), thread_destroy(), used_space_insert(), and used_space_remove().

Here is the call graph for this function:

void * btree_search (  btree_t *  t,
btree_key_t  key,
btree_node_t **  leaf_node
) 
 

Search key in a B-tree.

Parameters:
t B-tree.
key Key to be searched.
leaf_node Address where to put pointer to visited leaf node.
Returns:
Pointer to value or NULL if there is no such key.

Definition at line 318 of file btree.c.

References btree_node::key, btree_node::keys, LEAF_NODE, NULL, btree::root, btree_node::subtree, and btree_node::value.

Referenced by anon_page_fault(), btree_insert(), btree_remove(), check_area_conflicts(), elf_page_fault(), elf_share(), find_area_and_lock(), futex_find(), task_find_by_id(), thread_exists(), used_space_insert(), and used_space_remove().

index_t find_key_by_subtree (  btree_node_t *  node,
btree_node_t *  subtree,
bool  right
)  [static]
 

Find key by its left or right subtree.

Parameters:
node B-tree node.
subtree Left or right subtree of a key found in node.
right If true, subtree is a right subtree. If false, subtree is a left subtree.
Returns:
Index of the key associated with the subtree.

Definition at line 689 of file btree.c.

References btree_node::keys, and btree_node::subtree.

Referenced by node_combine(), try_insert_by_rotation_to_left(), try_insert_by_rotation_to_right(), try_rotation_from_left(), and try_rotation_from_right().

void hash_table_create (  hash_table_t *  h,
count_t  m,
count_t  max_keys,
hash_table_operations_t *  op
) 
 

Create chained hash table.

Parameters:
h Hash table structure. Will be initialized by this call.
m Number of slots in the hash table.
max_keys Maximal number of keys needed to identify an item.
op Hash table operations structure.

Definition at line 55 of file hash_table.c.

References ASSERT, hash_table_operations::compare, hash_table::entries, hash_table::entry, hash_table_operations::hash, list_initialize(), malloc(), hash_table::max_keys, memsetb(), hash_table::op, and panic.

Referenced by futex_init().

Here is the call graph for this function:

link_t * hash_table_find (  hash_table_t *  h,
__native  key[]
) 
 

Search hash table for an item matching keys.

Parameters:
h Hash table.
key Array of all keys needed to compute hash index.
Returns:
Matching item on success, NULL if there is no such item.

Definition at line 103 of file hash_table.c.

References ASSERT, hash_table_operations::compare, hash_table::entry, hash_table_operations::hash, hash_table::max_keys, link::next, and hash_table::op.

Referenced by futex_find(), and hash_table_remove().

void hash_table_insert (  hash_table_t *  h,
__native  key[],
link_t *  item
) 
 

Insert item into hash table.

Parameters:
h Hash table.
key Array of all keys necessary to compute hash index.
item Item to be inserted into the hash table.

Definition at line 83 of file hash_table.c.

References ASSERT, hash_table_operations::compare, hash_table::entry, hash_table_operations::hash, list_append(), and hash_table::op.

Referenced by futex_find().

Here is the call graph for this function:

void hash_table_remove (  hash_table_t *  h,
__native  key[],
count_t  keys
) 
 

Remove all matching items from hash table.

For each removed item, h->remove_callback() is called.

Parameters:
h Hash table.
key Array of keys that will be compared against items of the hash table.
keys Number of keys in the key array.

Definition at line 133 of file hash_table.c.

References ASSERT, hash_table_operations::compare, hash_table::entries, hash_table::entry, hash_table_operations::hash, hash_table_find(), list_remove(), hash_table::max_keys, link::next, hash_table::op, link::prev, and hash_table_operations::remove_callback.

Referenced by futex_cleanup().

Here is the call graph for this function:

static void headless_list_concat (  link_t *  part1,
link_t *  part2
)  [static]
 

Concatenate two headless doubly-linked circular lists

Concatenate two headless doubly-linked circular lists.

Parameters:
part1 Pointer to link_t structure leading the first headless list.
part2 Pointer to link_t structure leading the second headless list.

Definition at line 173 of file list.h.

References headless_list_split_or_concat().

Here is the call graph for this function:

static void headless_list_split (  link_t *  part1,
link_t *  part2
)  [static]
 

Split headless doubly-linked circular list

Split headless doubly-linked circular list.

Parameters:
part1 Pointer to link_t structure leading the first half of the headless list.
part2 Pointer to link_t structure leading the second half of the headless list.

Definition at line 161 of file list.h.

References headless_list_split_or_concat().

Here is the call graph for this function:

static void headless_list_split_or_concat (  link_t *  part1,
link_t *  part2
)  [static]
 

Split or concatenate headless doubly-linked circular list

Split or concatenate headless doubly-linked circular list.

Note that the algorithm works both directions: concatenates splitted lists and splits concatenated lists.

Parameters:
part1 Pointer to link_t structure leading the first (half of the headless) list.
part2 Pointer to link_t structure leading the second (half of the headless) list.

Definition at line 142 of file list.h.

References link::next, and link::prev.

Referenced by headless_list_concat(), and headless_list_split().

static void link_initialize (  link_t *  link  )  [static]
 

Initialize doubly-linked circular list link

Initialize doubly-linked list link.

Parameters:
link Pointer to link_t structure to be initialized.

Definition at line 59 of file list.h.

References link::next, NULL, and link::prev.

Referenced by as_create(), cmd_initialize(), futex_initialize(), list_remove(), thr_constructor(), and timeout_reinitialize().

static void list_append (  link_t *  link,
link_t *  head
)  [static]
 

Add item to the end of doubly-linked circular list

Add item to the end of doubly-linked circular list.

Parameters:
link Pointer to link_t structure to be added.
head Pointer to link_t structure representing head of the list.

Definition at line 99 of file list.h.

References link::next, and link::prev.

Referenced by _ipc_answer_free_call(), _ipc_call(), _slab_cache_create(), as_switch(), btree_create(), btree_print(), buddy_system_free(), cmd_register(), hash_table_insert(), ipc_phone_connect(), ipc_wait_for_call(), send_call(), thread_create(), thread_ready(), and waitq_sleep_timeout_unsafe().

void list_concat (  link_t *  head1,
link_t *  head2
) 
 

Concatenate two lists

Concatenate lists head1 and head2, producing a single list head1 containing items from both (in head1, head2 order) and empty list head2.

Parameters:
head1 First list and concatenated output
head2 Second list and empty output.

Definition at line 81 of file list.c.

References list_empty(), list_initialize(), link::next, and link::prev.

Referenced by relink_rq().

Here is the call graph for this function:

static bool list_empty (  link_t *  head  )  [static]
 

Query emptiness of doubly-linked circular list

Query emptiness of doubly-linked circular list.

Parameters:
head Pointer to link_t structure representing head of the list.

Definition at line 126 of file list.h.

References link::next.

Referenced by _rwlock_read_lock_timeout(), _waitq_wakeup_unsafe(), as_area_resize(), as_destroy(), btree_print(), buddy_system_alloc(), buddy_system_can_alloc(), buddy_system_structure_print(), get_mag_from_cache(), ipc_cleanup(), ipc_cleanup_call_list(), ipc_wait_for_call(), let_others_in(), list_concat(), slab_cache_destroy(), and slab_obj_create().

static void list_initialize (  link_t *  head  )  [static]
 

Initialize doubly-linked circular list

Initialize doubly-linked circular list.

Parameters:
head Pointer to link_t structure representing head of the list.

Definition at line 71 of file list.h.

References link::next, and link::prev.

Referenced by _slab_cache_create(), btree_create(), btree_print(), buddy_system_create(), cpu_init(), hash_table_create(), ipc_answerbox_init(), list_concat(), relink_rq(), task_create(), timeout_init(), and waitq_initialize().

bool list_member (  const link_t *  link,
const link_t *  head
) 
 

Check for membership

Check whether link is contained in the list head. The membership is defined as pointer equivalence.

Parameters:
link Item to look for.
head List to look in.
Returns:
true if link is contained in head, false otherwise.

Definition at line 54 of file list.c.

References link::next.

static void list_prepend (  link_t *  link,
link_t *  head
)  [static]
 

Add item to the beginning of doubly-linked circular list

Add item to the beginning of doubly-linked circular list.

Parameters:
link Pointer to link_t structure to be added.
head Pointer to link_t structure representing head of the list.

Definition at line 84 of file list.h.

References link::next, and link::prev.

Referenced by _btree_insert(), put_mag_to_cache(), slab_obj_create(), slab_obj_destroy(), and timeout_register().

static void list_remove (  link_t *  link  )  [static]
 

Remove item from doubly-linked circular list

Remove item from doubly-linked circular list.

Parameters:
link Pointer to link_t structure to be removed from the list it is contained in.

Definition at line 113 of file list.h.

References link_initialize(), link::next, and link::prev.

Referenced by _waitq_wakeup_unsafe(), answer_preprocess(), as_destroy(), as_switch(), btree_print(), buddy_system_alloc(), buddy_system_alloc_block(), buddy_system_free(), clock(), get_mag_from_cache(), hash_table_remove(), ipc_answer(), ipc_cleanup_call_list(), ipc_forward(), ipc_phone_hangup(), ipc_wait_for_call(), kcpulb(), slab_cache_destroy(), slab_obj_create(), slab_obj_destroy(), thread_destroy(), timeout_unregister(), waitq_interrupt_sleep(), and waitq_timeouted_sleep().

Here is the call graph for this function:

btree_node_t * node_combine (  btree_node_t *  node  )  [static]
 

Combine node with any of its siblings.

The siblings are required to be below the fill factor.

Parameters:
node Node to combine with one of its siblings.
Returns:
Pointer to the rightmost of the two nodes.

Definition at line 638 of file btree.c.

References ASSERT, find_key_by_subtree(), INDEX_NODE, btree_node::key, btree_node::keys, btree_node::parent, ROOT_NODE, btree_node::subtree, and btree_node::value.

Here is the call graph for this function:

void node_initialize (  btree_node_t *  node  )  [static]
 

Initialize B-tree node.

Parameters:
node B-tree node.

Definition at line 412 of file btree.c.

References BTREE_MAX_KEYS, btree_node::key, btree_node::keys, NULL, btree_node::subtree, and btree_node::value.

Referenced by _btree_insert(), btree_create(), and node_split().

void node_insert_key_and_lsubtree (  btree_node_t *  node,
btree_key_t  key,
void *  value,
btree_node_t *  lsubtree
)  [static]
 

Insert key-value-lsubtree triplet into B-tree node.

It is actually possible to have more keys than BTREE_MAX_KEYS. This feature is used during insert by right rotation.

Parameters:
node B-tree node into wich the new key is to be inserted.
key The key to be inserted.
value Pointer to value to be inserted.
lsubtree Pointer to the left subtree.

Definition at line 444 of file btree.c.

References btree_node::key, btree_node::keys, btree_node::subtree, and btree_node::value.

Referenced by rotate_from_left().

void node_insert_key_and_rsubtree (  btree_node_t *  node,
btree_key_t  key,
void *  value,
btree_node_t *  rsubtree
)  [static]
 

Insert key-value-rsubtree triplet into B-tree node.

It is actually possible to have more keys than BTREE_MAX_KEYS. This feature is used during splitting the node when the number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation also makes use of this feature.

Parameters:
node B-tree node into wich the new key is to be inserted.
key The key to be inserted.
value Pointer to value to be inserted.
rsubtree Pointer to the right subtree.

Definition at line 480 of file btree.c.

References btree_node::key, btree_node::keys, btree_node::subtree, and btree_node::value.

Referenced by _btree_insert(), node_split(), rotate_from_right(), try_insert_by_rotation_to_left(), and try_insert_by_rotation_to_right().

void node_remove_key_and_lsubtree (  btree_node_t *  node,
btree_key_t  key
)  [static]
 

Remove key and its left subtree pointer from B-tree node.

Remove the key and eliminate gaps in node->key array. Note that the value pointer and the left subtree pointer is removed from the node as well.

Parameters:
node B-tree node.
key Key to be removed.

Definition at line 512 of file btree.c.

References btree_node::key, btree_node::keys, btree_node::subtree, and btree_node::value.

Referenced by rotate_from_right().

void node_remove_key_and_rsubtree (  btree_node_t *  node,
btree_key_t  key
)  [static]
 

Remove key and its right subtree pointer from B-tree node.

Remove the key and eliminate gaps in node->key array. Note that the value pointer and the right subtree pointer is removed from the node as well.

Parameters:
node B-tree node.
key Key to be removed.

Definition at line 540 of file btree.c.

References btree_node::key, btree_node::keys, btree_node::subtree, and btree_node::value.

Referenced by _btree_remove(), and rotate_from_left().

btree_node_t * node_split (  btree_node_t *  node,
btree_key_t  key,
void *  value,
btree_node_t *  rsubtree,
btree_key_t *  median
)  [static]
 

Split full B-tree node and insert new key-value-right-subtree triplet.

This function will split a node and return pointer to a newly created node containing keys greater than or equal to the greater of medians (or median) of the old keys and the newly added key. It will also write the median key to a memory address supplied by the caller.

If the node being split is an index node, the median will not be included in the new node. If the node is a leaf node, the median will be copied there.

Parameters:
node B-tree node wich is going to be split.
key The key to be inserted.
value Pointer to the value to be inserted.
rsubtree Pointer to the right subtree of the key being added.
median Address in memory, where the median key will be stored.
Returns:
Newly created right sibling of node.

Definition at line 577 of file btree.c.

References ASSERT, BTREE_MAX_KEYS, btree_node_slab, btree_node::depth, INDEX_NODE, btree_node::key, btree_node::keys, MEDIAN_HIGH, MEDIAN_HIGH_INDEX, node_initialize(), node_insert_key_and_rsubtree(), btree_node::parent, slab_alloc(), btree_node::subtree, and btree_node::value.

Referenced by _btree_insert().

Here is the call graph for this function:

void rotate_from_left (  btree_node_t *  lnode,
btree_node_t *  rnode,
index_t  idx
)  [static]
 

Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.

The biggest key and its value and right subtree is rotated from the left node to the right. If the node is an index node, than the parent node key belonging to the left node takes part in the rotation.

Parameters:
lnode Left sibling.
rnode Right sibling.
idx Index of the parent node key that is taking part in the rotation.

Definition at line 710 of file btree.c.

References btree_node::key, btree_node::keys, LEAF_NODE, node_insert_key_and_lsubtree(), node_remove_key_and_rsubtree(), NULL, btree_node::parent, btree_node::subtree, and btree_node::value.

Referenced by try_insert_by_rotation_to_right(), and try_rotation_from_left().

Here is the call graph for this function:

void rotate_from_right (  btree_node_t *  lnode,
btree_node_t *  rnode,
index_t  idx
)  [static]
 

Rotate one key-value-lsubtree triplet from the right sibling to the left sibling.

The smallest key and its value and left subtree is rotated from the right node to the left. If the node is an index node, than the parent node key belonging to the right node takes part in the rotation.

Parameters:
lnode Left sibling.
rnode Right sibling.
idx Index of the parent node key that is taking part in the rotation.

Definition at line 747 of file btree.c.

References btree_node::key, LEAF_NODE, node_insert_key_and_rsubtree(), node_remove_key_and_lsubtree(), NULL, btree_node::parent, btree_node::subtree, and btree_node::value.

Referenced by try_insert_by_rotation_to_left(), and try_rotation_from_right().

Here is the call graph for this function:

bool try_insert_by_rotation_to_left (  btree_node_t *  node,
btree_key_t  inskey,
void *  insvalue,
btree_node_t *  rsubtree
)  [static]
 

Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.

Left sibling of the node (if it exists) is checked for free space. If there is free space, the key is inserted and the smallest key of the node is moved there. The index node which is the parent of both nodes is fixed.

Parameters:
node B-tree node.
inskey Key to be inserted.
insvalue Value to be inserted.
rsubtree Right subtree of inskey.
Returns:
True if the rotation was performed, false otherwise.

Definition at line 788 of file btree.c.

References BTREE_MAX_KEYS, find_key_by_subtree(), btree_node::keys, node_insert_key_and_rsubtree(), btree_node::parent, ROOT_NODE, rotate_from_right(), and btree_node::subtree.

Referenced by _btree_insert().

Here is the call graph for this function:

bool try_insert_by_rotation_to_right (  btree_node_t *  node,
btree_key_t  inskey,
void *  insvalue,
btree_node_t *  rsubtree
)  [static]
 

Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.

Right sibling of the node (if it exists) is checked for free space. If there is free space, the key is inserted and the biggest key of the node is moved there. The index node which is the parent of both nodes is fixed.

Parameters:
node B-tree node.
inskey Key to be inserted.
insvalue Value to be inserted.
rsubtree Right subtree of inskey.
Returns:
True if the rotation was performed, false otherwise.

Definition at line 835 of file btree.c.

References BTREE_MAX_KEYS, find_key_by_subtree(), btree_node::keys, node_insert_key_and_rsubtree(), btree_node::parent, ROOT_NODE, rotate_from_left(), and btree_node::subtree.

Referenced by _btree_insert().

Here is the call graph for this function:

bool try_rotation_from_left (  btree_node_t *  rnode  )  [static]
 

Rotate in a key from the left sibling or from the index node, if this operation can be done.

Parameters:
rnode Node into which to add key from its left sibling or from the index node.
Returns:
True if the rotation was performed, false otherwise.

Definition at line 874 of file btree.c.

References FILL_FACTOR, find_key_by_subtree(), btree_node::keys, btree_node::parent, ROOT_NODE, rotate_from_left(), and btree_node::subtree.

Referenced by _btree_remove().

Here is the call graph for this function:

bool try_rotation_from_right (  btree_node_t *  lnode  )  [static]
 

Rotate in a key from the right sibling or from the index node, if this operation can be done.

Parameters:
lnode Node into which to add key from its right sibling or from the index node.
Returns:
True if the rotation was performed, false otherwise.

Definition at line 909 of file btree.c.

References FILL_FACTOR, find_key_by_subtree(), btree_node::keys, btree_node::parent, ROOT_NODE, rotate_from_right(), and btree_node::subtree.

Referenced by _btree_remove().

Here is the call graph for this function:

Variable Documentation

slab_cache_t* btree_node_slab [static]
 

Definition at line 86 of file btree.c.

Referenced by _btree_insert(), _btree_remove(), btree_create(), btree_init(), and node_split().

Generated on Sun Jun 18 16:42:23 2006 for HelenOS Kernel (ia32) by  doxygen 1.4.6