Changeset b7f364e in mainline

Timestamp:

2006-04-12T12:36:58Z (19 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

9a8d91b

Parents:

ec55358

Message:

Modify B+tree node key width to be 64-bit wide on all platforms.

Location:

generic

Files:

• include/adt/btree.h (modified) (3 diffs)
• src/adt/btree.c (modified) (16 diffs)
• src/proc/task.c (modified) (1 diff)
• src/proc/thread.c (modified) (3 diffs)

generic/include/adt/btree.h

@@ -37 +37 @@
 #define BTREE_MAX_KEYS  (BTREE_M - 1)
 
+typedef __u64 btree_key_t;
+
 /** B-tree node structure. */
 struct btree_node {
@@ -43 +45 @@
 
         /** Keys. We currently support only single keys. Additional room for one extra key is provided. */
-        __native key[BTREE_MAX_KEYS + 1];
+        btree_key_t key[BTREE_MAX_KEYS + 1];
 
         /** 
@@ -82 +84 @@
 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, btree_node_t *leaf_node);
-extern void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node);
+extern void btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node);
+extern void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node);
+extern void *btree_search(btree_t *t, btree_key_t key, btree_node_t **leaf_node);
 
 extern btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node);

generic/src/adt/btree.c

@@ -47 +47 @@
 #include <print.h>
 
-static void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node);
-static void _btree_remove(btree_t *t, __native key, btree_node_t *node);
+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, __native key, void *value, btree_node_t *lsubtree);
-static void node_insert_key_and_rsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
-static void node_remove_key_and_lsubtree(btree_node_t *node, __native key);
-static void node_remove_key_and_rsubtree(btree_node_t *node, __native key);
-static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
+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, __native key, void *value, btree_node_t *rsubtree);
-static bool try_insert_by_rotation_to_right(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
+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);
@@ -109 +109 @@
  * @param leaf_node Leaf node where the insertion should begin.
  */ 
-void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node)
+void btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node)
 {
         btree_node_t *lnode;
@@ -133 +133 @@
  * @param node Start inserting into this node.
  */
-void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node)
+void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node)
 {
         if (node->keys < BTREE_MAX_KEYS) {
@@ -152 +152 @@
         } else {
                 btree_node_t *rnode;
-                __native median;
+                btree_key_t median;
                 
                 /*
@@ -194 +194 @@
  * @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)
+void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node)
 {
         btree_node_t *lnode;
@@ -214 +214 @@
  * @param node Node where the key being removed resides.
  */
-void _btree_remove(btree_t *t, __native key, btree_node_t *node)
+void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node)
 {
         if (ROOT_NODE(node)) {
@@ -291 +291 @@
  * @return Pointer to value or NULL if there is no such key.
  */
-void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node)
+void *btree_search(btree_t *t, btree_key_t key, btree_node_t **leaf_node)
 {
         btree_node_t *cur, *next;
@@ -417 +417 @@
  * @param lsubtree Pointer to the left subtree.
  */ 
-void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree)
+void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree)
 {
         int i;
@@ -453 +453 @@
  * @param rsubtree Pointer to the right subtree.
  */ 
-void node_insert_key_and_rsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree)
+void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
 {
         int i;
@@ -485 +485 @@
  * @param key Key to be removed.
  */
-void node_remove_key_and_lsubtree(btree_node_t *node, __native key)
+void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
 {
         int i, j;
@@ -513 +513 @@
  * @param key Key to be removed.
  */
-void node_remove_key_and_rsubtree(btree_node_t *node, __native key)
+void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
 {
         int i, j;
@@ -550 +550 @@
  * @return Newly created right sibling of node.
  */ 
-btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median)
+btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median)
 {
         btree_node_t *rnode;
@@ -685 +685 @@
 void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
 {
-        __native key;
+        btree_key_t key;
 
         key = lnode->key[lnode->keys - 1];
@@ -722 +722 @@
 void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
 {
-        __native key;
+        btree_key_t key;
 
         key = rnode->key[0];
@@ -761 +761 @@
  * @return True if the rotation was performed, false otherwise.
  */
-bool try_insert_by_rotation_to_left(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
+bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
 {
         index_t idx;
@@ -808 +808 @@
  * @return True if the rotation was performed, false otherwise.
  */
-bool try_insert_by_rotation_to_right(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
+bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
 {
         index_t idx;

generic/src/proc/task.c

@@ -101 +101 @@
 
         ta->taskid = ++task_counter;
-        btree_insert(&tasks_btree, (__native) ta, (void *) ta, NULL);
+        btree_insert(&tasks_btree, (btree_key_t) ta->taskid, (void *) ta, NULL);
 
         spinlock_unlock(&tasks_lock);

generic/src/proc/thread.c

@@ -237 +237 @@
         
         spinlock_lock(&threads_lock);
-        btree_remove(&threads_btree, (__native) t, NULL);
+        btree_remove(&threads_btree, (btree_key_t) ((__address ) t), NULL);
         spinlock_unlock(&threads_lock);
         
@@ -313 +313 @@
         ipl = interrupts_disable();
         spinlock_lock(&threads_lock);
-        btree_insert(&threads_btree, (__native) t, (void *) t, NULL);
+        btree_insert(&threads_btree, (btree_key_t) ((__address) t), (void *) t, NULL);
         spinlock_unlock(&threads_lock);
         
@@ -447 +447 @@
         btree_node_t *leaf;
         
-        return btree_search(&threads_btree, (__native) t, &leaf) != NULL;
+        return btree_search(&threads_btree, (btree_key_t) ((__address) t), &leaf) != NULL;
 }