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/ @ 1139

  → /kernel/ @ 1140

  ↔ Reverse comparison

• Compare Path:	Rev

  With Path:	Rev

Ignore whitespace Rev 1139 → Rev 1140

/kernel/trunk/generic/include/adt/btree.h
33,7 → 33,7
#include <typedefs.h>
#include <adt/list.h>
#define BTREE_M 4
#define BTREE_M 5
#define BTREE_MAX_KEYS (BTREE_M - 1)
/** B-tree node structure. */
52,8 → 52,8
/**
* Pointers to descendants of this node sorted according to the key array.
* subtree[0] points to subtree with keys lesser than or equal to key[0].
* subtree[1] points to subtree with keys greater than key[0] and lesser than or equal to key[1].
* subtree[0] points to subtree with keys lesser than to key[0].
* subtree[1] points to subtree with keys greater than or equal to key[0] and lesser than key[1].
* ...
* There is room for storing a subtree pointer for the extra key.
*/
80,7 → 80,7
extern void btree_destroy(btree_t *t);
extern void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node);
extern void btree_remove(btree_t *t, __native key);
extern void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node);
extern void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node);
extern void *btree_node_min(btree_node_t *node);

/kernel/trunk/generic/src/adt/btree.c
28,7 → 28,7
/*
* This B-tree has the following properties:
* - it is a ballanced 2-3-4 tree (i.e. BTREE_M = 4)
* - 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)
61,6 → 61,8
#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))]);
171,9 → 173,25
}
/* TODO */
void btree_remove(btree_t *t, __native key)
/** Remove B-tree node.
*
* @param B-tree.
* @param key Key to be removed from the B-tree along with its associated value.
* @param leaf_node If not NULL, pointer to the leaf node where the key is found.
*/
void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node)
{
btree_node_t *lnode;
lnode = leaf_node;
if (!lnode) {
if (!btree_search(t, key, &lnode)) {
panic("B-tree %P does not contain key %d\n", t, key);
}
}
/* TODO */
}
/** Search key in a B-tree.