Part 6 - The Cursor Abstraction

    This should be a shorter part than the last one. We’re just going to refactor a bit to make it easier to start the B-Tree implementation.

    We’re going to add a object which represents a location in the table. Things you might want to do with cursors:

    • Create a cursor at the beginning of the table
    • Create a cursor at the end of the table
    • Access the row the cursor is pointing to

    • Advance the cursor to the next row
      Those are the behaviors we’re going to implement now. Later, we will also want to:

    • Delete the row pointed to by a cursor

    • Modify the row pointed to by a cursor
    • Search a table for a given ID, and create a cursor pointing to the row with that ID
      Without further ado, here’s the Cursor type:

    A cursor also has a reference to the table it’s part of (so our cursor functions can take just the cursor as a parameter).

    Finally, it has a boolean called end_of_table. This is so we can represent a position past the end of the table (which is somewhere we may want to insert a row).

    table_start() and table_end() create new cursors:

    1. +Cursor* table_start(Table* table) {
    2. +  Cursor* cursor = malloc(sizeof(Cursor));
    3. +  cursor->table = table;
    4. +  cursor->row_num = 0;
    5. +  cursor->end_of_table = (table->num_rows == 0);
    6. +
    7. +  return cursor;
    8. +
    9. +Cursor* table_end(Table* table) {
    10. +  Cursor* cursor = malloc(sizeof(Cursor));
    12. +  cursor->row_num = table->num_rows;
    13. +  cursor->end_of_table = true;
    14. +
    15. +  return cursor;
    16. +}

    Our row_slot() function will become cursor_value(), which returns a pointer to the position described by the cursor:

    Advancing the cursor in our current table structure is as simple as incrementing the row number. This will be a bit more complicated in a B-tree.

    1. +void cursor_advance(Cursor* cursor) {
    2. +  cursor->row_num += 1;
    3. +  if (cursor->row_num >= cursor->table->num_rows) {
    4. +    cursor->end_of_table = true;
    5. +  }

    When selecting all rows in the table, we open a cursor at the start of the table, print the row, then advance the cursor to the next row. Repeat until we’ve reached the end of the table.

    1.  ExecuteResult execute_select(Statement* statement, Table* table) {
    2. +  Cursor* cursor = table_start(table);
    4.    Row row;
    5. -  for (uint32_t i = 0; i < table->num_rows; i++) {
    6. -    deserialize_row(row_slot(table, i), &row);
    7. +  while (!(cursor->end_of_table)) {
    8. +    deserialize_row(cursor_value(cursor), &row);
    9.      print_row(&row);
    10. +    cursor_advance(cursor);
    11.    }
    12. +
    13. +  free(cursor);
    14. +
    15.  }

    Alright, that’s it! Like I said, this was a shorter refactor that should help us as we rewrite our table data structure into a B-Tree. execute_select() and execute_insert() can interact with the table entirely through the cursor without assuming anything about how the table is stored.

    Here’s the complete diff to this part:

    Part 5 - Persistence to Disk