Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Is there possibility of having overflow ? #77

Open
caleberi opened this issue Sep 9, 2021 · 0 comments
Open

Is there possibility of having overflow ? #77

caleberi opened this issue Sep 9, 2021 · 0 comments

Comments

@caleberi
Copy link

caleberi commented Sep 9, 2021

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 ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant