SIGMOD Contest 2011
Loading...
Searching...
No Matches
Data Structures | Functions
refimplementation.c File Reference

A skeleton implementation of the SIGMOD 2011 programming contest API. More...

Data Structures

struct  scdb_index
 
struct  scdb_iterator
 

Functions

DBT * initialize_dbt ()
 
scdb_indexscdb_open (size_t max_disk_bytes, const char *disk_path)
 Opens an existing index, or creates one if it does not exist.
 
void scdb_close (scdb_index *index)
 Closes an open index.
 
scdb_status scdb_read (scdb_index *index, const char *key, size_t key_length, char *value_buffer, size_t *value_buffer_length)
 Reads the value corresponding to the specified key (exact match).
 
scdb_status scdb_write (scdb_index *index, const char *key, size_t key_length, const char *value, size_t value_length)
 Sets the specified key to map to the specified value.
 
scdb_status scdb_delete (scdb_index *index, const char *key, size_t key_length)
 Removes the specified key and associated value from the index.
 
scdb_status scdb_cas (scdb_index *index, const char *key, size_t key_length, const char *current_value, size_t current_value_length, const char *new_value, size_t new_value_length)
 Performs an atomic compare and swap.
 
scdb_iteratorscdb_iterate (scdb_index *index, const char *key, size_t key_length)
 Create an iterator over the index, starting at the smallest key that is greater than or equal to the provided key.
 
void scdb_iterator_close (scdb_iterator *iterator)
 Closes an open iterator.
 
scdb_status scdb_next (scdb_iterator *iterator, char *key_buffer, size_t *key_buffer_length, char *value_buffer, size_t *value_buffer_length)
 Reads the current key/value pair from the iterator, then advances the iterator.
 

Detailed Description

A skeleton implementation of the SIGMOD 2011 programming contest API.

Function Documentation

◆ scdb_cas()

scdb_status scdb_cas ( scdb_index * index,
const char * key,
size_t key_length,
const char * current_value,
size_t current_value_length,
const char * new_value,
size_t new_value_length )

Performs an atomic compare and swap.

If the current value for key matches the provided value, then update the key's value to new_value. The compare and swap occur atomically, each thread can assume that no other thread's updates are applied between the compare and swap operation. This primitive can be used to implement higher-level concurrency control, e.g. locks or validation for optimistic concurrency control.

Parameters
indexthe index to modify.
keypointer to the key bytes.
key_lengthlength of the key in bytes. Must be <= SCDB_MAX_KEY_LENGTH.
current_valuepointer to the bytes to be compared with the value stored in the index, cannot be NULL.
current_value_lengthlength of current_value in bytes. Must be <= SCDB_MAX_VALUE_LENGTH.
new_valuepointer to the value to be written if the comparison is successful, cannot be NULL.
new_value_lengthlength of the new value in bytes, must be >= 0.
Returns
SCDB_OK if the operation is successful, SCDB_NOT_FOUND if the key does not exist, SCDB_COMPARE_FAILED if the stored value does not match current_value, SCDB_ERROR if some other error occurs.

◆ scdb_close()

void scdb_close ( scdb_index * index)

Closes an open index.

This should free all resources associated with index. After this is called, the pointer cannot be used by any thread.

Parameters
indexthe index to be closed.

◆ scdb_delete()

scdb_status scdb_delete ( scdb_index * index,
const char * key,
size_t key_length )

Removes the specified key and associated value from the index.

After this returns, the delete must be committed and durable.

Parameters
indexthe index to modify.
keypointer to the key bytes.
key_lengthlength of the key in bytes. Must be <= SCDB_MAX_KEY_LENGTH.
Returns
SCDB_OK if the operation is successful, SCDB_NOT_FOUND if the key does not exist, SCDB_ERROR if some other error occurs.

◆ scdb_iterate()

scdb_iterator * scdb_iterate ( scdb_index * index,
const char * key,
size_t key_length )

Create an iterator over the index, starting at the smallest key that is greater than or equal to the provided key.

The keys are sorted in lexicographical byte order, with bytes treated as 8-bit unsigned integers. For example, the following order is correct: { 0x7f }, { 0x7f, 0x00 }, { 0x80 }. To start at the beginning of the index, pass in a NULL or zero-length key.

Parameters
indexthe index to iterate over.
keypointer to the key bytes.
key_lengthlength of the key in bytes. Must be <= SCDB_MAX_KEY_LENGTH.
Returns
pointer to an iterator to be used to read values from the index, or NULL if some error occurred.

◆ scdb_iterator_close()

void scdb_iterator_close ( scdb_iterator * iterator)

Closes an open iterator.

The provided iterator pointer cannot be used after calling this.

Parameters
iteratorpointer to the iterator to close.

◆ scdb_next()

scdb_status scdb_next ( scdb_iterator * iterator,
char * key_buffer,
size_t * key_buffer_length,
char * value_buffer,
size_t * value_buffer_length )

Reads the current key/value pair from the iterator, then advances the iterator.

The iterator does not need to be repeatable or isolated with respect to other transactions. The only restriction is that keys must be returned in strictly increasing order, and it must only return committed values.

If there is an error, the iterator is not advanced. If the buffers are too small, the length fields will indicate the length of the data to be returned.

Parameters
iteratorthe iterator to read from.
key_bufferpointer to memory where the key will be copied.
[in,out]key_buffer_lengthpointer to the length of value buffer. This will be set to the length of the key in the index.
value_bufferpointer to memory where the value will be copied.
[in,out]value_buffer_lengthpointer to the length of value buffer. This will be set to the length of the value in the index.
Returns
SCDB_OK if the operation is successful, SCDB_NOT_FOUND if there are no more keys in the iteration, SCDB_KEY_BUFFER_TOO_SMALL if the key is longer than the provided buffer, SCDB_VALUE_BUFFER_TOO_SMALL if the value is longer than the provided buffer, SCDB_ERROR if some other error occurs.

◆ scdb_open()

scdb_index * scdb_open ( size_t max_disk_bytes,
const char * disk_path )

Opens an existing index, or creates one if it does not exist.

Any number of files can be used to persist the index, provided that the total amount of space used does not exceed max_disk_bytes. This index must be thread-safe, meaning that it can be passed between multiple threads.

Parameters
max_disk_bytesthe maximum amount of disk space available for durability.
disk_paththe prefix that must be used for storing the non-volatile data.
Returns
pointer to the index that will be passed into all future API calls.

◆ scdb_read()

scdb_status scdb_read ( scdb_index * index,
const char * key,
size_t key_length,
char * value_buffer,
size_t * value_buffer_length )

Reads the value corresponding to the specified key (exact match).

If the provided buffer is too small, this will return SCDB_VALUE_BUFFER_TOO_SMALL and not copy any bytes into value_buffer. However, value_buffer_length is always set to the full length of the value stored in the index. The value returned must reflect the most recent successfully completed (committed) value, even if that update was performed by another thread.

Parameters
indexthe index to modify.
keypointer to the key bytes.
key_lengthlength of the key in bytes. Must be <= SCDB_MAX_KEY_LENGTH.
value_bufferpointer to memory where the value will be copied, cannot be NULL.
[in,out]value_buffer_lengthpointer to the length of value buffer. This will be set to the length of the value in the index.
Returns
SCDB_OK if the operation is successful, SCDB_NOT_FOUND if the key does not exist, SCDB_VALUE_BUFFER_TOO_SMALL if the value is longer than value_buffer, SCDB_ERROR if some other error occurs.

◆ scdb_write()

scdb_status scdb_write ( scdb_index * index,
const char * key,
size_t key_length,
const char * value_buffer,
size_t value_length )

Sets the specified key to map to the specified value.

This inserts a new key-value pair or updates the existing key. After this returns, the update must be committed and durable.

Parameters
indexthe index to modify.
keypointer to the key bytes.
key_lengthlength of the key in bytes. Must be <= SCDB_MAX_KEY_LENGTH.
value_bufferpointer to the value bytes, cannot be NULL.
value_lengthlength of the value in bytes. Must be <= SCDB_MAX_VALUE_LENGTH.
Returns
SCDB_OK if the operation is successful, SCDB_ERROR if some other error occurs.