HelenOS-historicHelenOSHelenOS-doc

Català-Valencià – Catalan中文 – Chinese (Simplified)中文 – Chinese (Traditional)Česky – CzechDansk – DanishNederlands – DutchEnglish – EnglishSuomi – FinnishFrançais – FrenchDeutsch – Germanעברית – Hebrewहिंदी – HindiMagyar – HungarianBahasa Indonesia – IndonesianItaliano – Italian日本語 – Japanese한국어 – KoreanМакедонски – Macedonianमराठी – MarathiNorsk – NorwegianPolski – PolishPortuguês – PortuguesePortuguês – Portuguese (Brazil)Русский – RussianSlovenčina – SlovakSlovenščina – SlovenianEspañol – SpanishSvenska – SwedishTürkçe – TurkishУкраїнська – UkrainianOëzbekcha – Uzbek

Compare Revisions

• This comparison shows the changes necessary to convert path

  → /kernel/trunk/ @ 1164

  → /kernel/trunk @ 1163

  ↔ Reverse comparison

• Compare Path:	Rev

  With Path:	Rev

Regard whitespace Rev 1164 → Rev 1163

/kernel/trunk/generic/include/adt/btree.h
76,8 → 76,6
link_t leaf_head; /**< Leaf-level list head. */
};
extern void btree_init(void);
extern void btree_create(btree_t *t);
extern void btree_destroy(btree_t *t);

/kernel/trunk/generic/src/adt/btree.c
28,7 → 28,7
/*
* This B-tree has the following properties:
* - it is a ballanced 3-4-5 tree (i.e. BTREE_M = 5)
* - it is a ballanced 2-3-4-5 tree (i.e. BTREE_M = 5)
* - values (i.e. pointers to values) are stored only in leaves
* - leaves are linked in a list
* - technically, it is a B+tree (because of the previous properties)
74,14 → 74,6
#define MEDIAN_LOW(n) ((n)->key[MEDIAN_LOW_INDEX((n))]);
#define MEDIAN_HIGH(n) ((n)->key[MEDIAN_HIGH_INDEX((n))]);
static slab_cache_t *btree_node_slab;
/** Initialize B-trees. */
void btree_init(void)
{
btree_node_slab = slab_cache_create("btree_node_slab", sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
}
/** Create empty B-tree.
*
* @param t B-tree.
89,7 → 81,7
void btree_create(btree_t *t)
{
list_initialize(&t->leaf_head);
t->root = (btree_node_t *) slab_alloc(btree_node_slab, 0);
t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
node_initialize(t->root);
list_append(&t->root->leaf_link, &t->leaf_head);
}
98,7 → 90,7
void btree_destroy(btree_t *t)
{
ASSERT(!t->root->keys);
slab_free(btree_node_slab, t->root);
free(t->root);
}
/** Insert key-value pair into B-tree.
169,7 → 161,7
/*
* We split the root node. Create new root.
*/
t->root = (btree_node_t *) slab_alloc(btree_node_slab, 0);
t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
node->parent = t->root;
rnode->parent = t->root;
node_initialize(t->root);
222,7 → 214,7
*/
t->root = node->subtree[0];
t->root->parent = NULL;
slab_free(btree_node_slab, node);
free(node);
} else {
/*
* Remove the key from the root node.
277,7 → 269,7
list_remove(&rnode->leaf_link);
idx = find_key_by_subtree(parent, rnode, true);
ASSERT((int) idx != -1);
slab_free(btree_node_slab, rnode);
free(rnode);
_btree_remove(t, parent->key[idx], parent);
}
}
570,7 → 562,7
/*
* Allocate and initialize new right sibling.
*/
rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0);
rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
node_initialize(rnode);
rnode->parent = node->parent;
rnode->depth = node->depth;

/kernel/trunk/generic/src/main/main.c
57,7 → 57,6
#include <typedefs.h>
#include <ipc/ipc.h>
#include <macros.h>
#include <adt/btree.h>
#ifdef CONFIG_SMP
#include <arch/smp/apic.h>
169,7 → 168,6
arch_pre_mm_init();
frame_init(); /* Initialize at least 1 memory segment big enough for slab to work */
slab_cache_init();
btree_init();
as_init();
page_init();
tlb_init();