netlify[bot]
commented
1 year ago Deploy Preview for splinterdb canceled.
| Name | Link |
|---|---|
| Latest commit | ebe49500b22c84910ad3ce029039ce237196f75a |
| Latest deploy log | https://app.netlify.com/sites/splinterdb/deploys/64c1ac8d7fea850008c63149 |
etwest
This PR allows splinter iterators to be bidirectional. To do this
It renames some of the iterator functions to make them more direction-neutral. For example, "advance" is renamed "next", so that we can add a "prev". "at_end" becomes 3 functions "can_prev", "can_next", and "can_curr" which allow for more granular bounds checking and inform us of what state the iterator is in.
It changes the possible states of an iterator to:
before start: Allowed to call "next", not allowed to call "get_current" or "prev"in range: Allowed to call all operationsafter end: Allowed to call "prev", not allowed to call "get_current" or "next"empty: Not allowed to perform any operations.It changes which iterator operations can fail: Now, only the "next" or "prev" method can fail. Getting the current key/value pair or checking bounds cannot fail. The rationale for this decision is: the fewer operations that can fail, the easier it is to use the iterator; in practice, all of the bounds implementations never fail; "next" and "prev" can fail; if there is an implementation that can fail on bounds checks, it is easy to move that failure to "next"/"prev" by performing the bounds check at the end of the "next"/"prev"; same for getting the current key/value pair.
It adds prev pointers in the btree which must be maintained during operations such as splitting leaves.
It adds "start_key" and "start_type" parameters to most iterator init functions. These determine the value of the key we are positioning the iterator relative to and where to actually begin relative to the start key, respectively. "start_type" may be one of the following: less_than, less_than_or_equal, greater_than, or greater_than_or_equal.