cstack / db_tutorial

Writing a sqlite clone from scratch in C
https://cstack.github.io/db_tutorial
MIT License
9.56k stars 968 forks source link

Is there possibility of having overflow ? #77

Open caleberi opened 3 years ago

caleberi commented 3 years ago

According to the code in line uint32_t index = ( one_past_max_index+min_index ) / 2; // ?? overflow it seems possible to have an overflow because according to binary search algorithm there is possibility of having an overflow when using the formular m=(l+r)/2 instead of this formula m=l+(r-l)/2 source : https://medium.com/swlh/overflow-bug-in-binary-search-c4d4a824807a

Cursor* leaf_node_find(Table* table, uint32_t page_num, uint32_t key)
{
            // code  ....
    while (one_past_max_index != min_index) {
    uint32_t index = ( one_past_max_index+min_index ) / 2; // ??  overflow
    uint32_t key_at_index = *leaf_node_key(node, index);
    if (key == key_at_index) {
        // set the cursor to the current position before returning it 
        cursor->cell_num = index;
        return cursor;
    }
    // follow the normal binary search algorithm based
    // on where the condition fall to whether mid-1 of mid + 1
    if (key < key_at_index) { 
        one_past_max_index = index;
    } else {
        min_index = index + 1;
    }
  }
}

or what do you think ?