Subversion Repositories HelenOS

Rev

Rev 3149 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 3149 Rev 4339
Line 122... Line 122...
122
    ASSERT(value);
122
    ASSERT(value);
123
   
123
   
124
    lnode = leaf_node;
124
    lnode = leaf_node;
125
    if (!lnode) {
125
    if (!lnode) {
126
        if (btree_search(t, key, &lnode)) {
126
        if (btree_search(t, key, &lnode)) {
127
            panic("B-tree %p already contains key %" PRIu64 "\n", t, key);
127
            panic("B-tree %p already contains key %" PRIu64 ".", t, key);
128
        }
128
        }
129
    }
129
    }
130
   
130
   
131
    _btree_insert(t, key, value, NULL, lnode);
131
    _btree_insert(t, key, value, NULL, lnode);
132
}
132
}
Line 222... Line 222...
222
    btree_node_t *lnode;
222
    btree_node_t *lnode;
223
   
223
   
224
    lnode = leaf_node;
224
    lnode = leaf_node;
225
    if (!lnode) {
225
    if (!lnode) {
226
        if (!btree_search(t, key, &lnode)) {
226
        if (!btree_search(t, key, &lnode)) {
227
            panic("B-tree %p does not contain key %" PRIu64 "\n", t, key);
227
            panic("B-tree %p does not contain key %" PRIu64 ".", t, key);
228
        }
228
        }
229
    }
229
    }
230
   
230
   
231
    _btree_remove(t, key, lnode);
231
    _btree_remove(t, key, lnode);
232
}
232
}
Line 522... Line 522...
522
            node->subtree[j - 1] = node->subtree[j];
522
            node->subtree[j - 1] = node->subtree[j];
523
            node->keys--;
523
            node->keys--;
524
            return;
524
            return;
525
        }
525
        }
526
    }
526
    }
527
    panic("node %p does not contain key %" PRIu64 "\n", node, key);
527
    panic("Node %p does not contain key %" PRIu64 ".", node, key);
528
}
528
}
529
 
529
 
530
/** Remove key and its right subtree pointer from B-tree node.
530
/** Remove key and its right subtree pointer from B-tree node.
531
 *
531
 *
532
 * Remove the key and eliminate gaps in node->key array.
532
 * Remove the key and eliminate gaps in node->key array.
Line 549... Line 549...
549
            }
549
            }
550
            node->keys--;
550
            node->keys--;
551
            return;
551
            return;
552
        }
552
        }
553
    }
553
    }
554
    panic("node %p does not contain key %" PRIu64 "\n", node, key);
554
    panic("Node %p does not contain key %" PRIu64 ".", node, key);
555
}
555
}
556
 
556
 
557
/** Split full B-tree node and insert new key-value-right-subtree triplet.
557
/** Split full B-tree node and insert new key-value-right-subtree triplet.
558
 *
558
 *
559
 * This function will split a node and return a pointer to a newly created
559
 * This function will split a node and return a pointer to a newly created
Line 691... Line 691...
691
   
691
   
692
    for (i = 0; i < node->keys + 1; i++) {
692
    for (i = 0; i < node->keys + 1; i++) {
693
        if (subtree == node->subtree[i])
693
        if (subtree == node->subtree[i])
694
            return i - (int) (right != false);
694
            return i - (int) (right != false);
695
    }
695
    }
696
    panic("node %p does not contain subtree %p\n", node, subtree);
696
    panic("Node %p does not contain subtree %p.", node, subtree);
697
}
697
}
698
 
698
 
699
/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
699
/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
700
 *
700
 *
701
 * The biggest key and its value and right subtree is rotated from the left node
701
 * The biggest key and its value and right subtree is rotated from the left node