Subversion Repositories HelenOS-historic

Rev

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

Rev 1196 Rev 1221
Line 115... Line 115...
115
    ASSERT(value);
115
    ASSERT(value);
116
   
116
   
117
    lnode = leaf_node;
117
    lnode = leaf_node;
118
    if (!lnode) {
118
    if (!lnode) {
119
        if (btree_search(t, key, &lnode)) {
119
        if (btree_search(t, key, &lnode)) {
120
            panic("B-tree %P already contains key %d\n", t, key);
120
            panic("B-tree %p already contains key %d\n", t, key);
121
        }
121
        }
122
    }
122
    }
123
   
123
   
124
    _btree_insert(t, key, value, NULL, lnode);
124
    _btree_insert(t, key, value, NULL, lnode);
125
}
125
}
Line 198... Line 198...
198
    btree_node_t *lnode;
198
    btree_node_t *lnode;
199
   
199
   
200
    lnode = leaf_node;
200
    lnode = leaf_node;
201
    if (!lnode) {
201
    if (!lnode) {
202
        if (!btree_search(t, key, &lnode)) {
202
        if (!btree_search(t, key, &lnode)) {
203
            panic("B-tree %P does not contain key %d\n", t, key);
203
            panic("B-tree %p does not contain key %d\n", t, key);
204
        }
204
        }
205
    }
205
    }
206
   
206
   
207
    _btree_remove(t, key, lnode);
207
    _btree_remove(t, key, lnode);
208
}
208
}
Line 498... Line 498...
498
            node->subtree[j - 1] = node->subtree[j];
498
            node->subtree[j - 1] = node->subtree[j];
499
            node->keys--;
499
            node->keys--;
500
            return;
500
            return;
501
        }
501
        }
502
    }
502
    }
503
    panic("node %P does not contain key %d\n", node, key);
503
    panic("node %p does not contain key %d\n", node, key);
504
}
504
}
505
 
505
 
506
/** Remove key and its right subtree pointer from B-tree node.
506
/** Remove key and its right subtree pointer from B-tree node.
507
 *
507
 *
508
 * Remove the key and eliminate gaps in node->key array.
508
 * Remove the key and eliminate gaps in node->key array.
Line 525... Line 525...
525
            }
525
            }
526
            node->keys--;
526
            node->keys--;
527
            return;
527
            return;
528
        }
528
        }
529
    }
529
    }
530
    panic("node %P does not contain key %d\n", node, key);
530
    panic("node %p does not contain key %d\n", node, key);
531
}
531
}
532
 
532
 
533
/** Split full B-tree node and insert new key-value-right-subtree triplet.
533
/** Split full B-tree node and insert new key-value-right-subtree triplet.
534
 *
534
 *
535
 * This function will split a node and return pointer to a newly created
535
 * This function will split a node and return pointer to a newly created
Line 667... Line 667...
667
   
667
   
668
    for (i = 0; i < node->keys + 1; i++) {
668
    for (i = 0; i < node->keys + 1; i++) {
669
        if (subtree == node->subtree[i])
669
        if (subtree == node->subtree[i])
670
            return i - (int) (right != false);
670
            return i - (int) (right != false);
671
    }
671
    }
672
    panic("node %P does not contain subtree %P\n", node, subtree);
672
    panic("node %p does not contain subtree %p\n", node, subtree);
673
}
673
}
674
 
674
 
675
/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
675
/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
676
 *
676
 *
677
 * The biggest key and its value and right subtree is rotated from the left node
677
 * The biggest key and its value and right subtree is rotated from the left node