Visitar URL original
Is there possibility of having overflow ? · Issue #77 · cstack/db_tutorial · GitHub
Skip to content

Is there possibility of having overflow ? #77

Description

@caleberi

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 ?

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions