Jan Kończak

Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
Your assignment is to implement a thread-safe key-value table (akin to a
[[https://en.wikipedia.org/wiki/Hash_table|hash table]]), with the keys and
values being integers, that works as follows:
  * the table consists of variable number of buckets, labeled with consecutive natural numbers (0, 1, 2, …),
  * each bucket has a fixed capacity of key-value pairs (a maximum number of elements it can store),
  * when adding a new key-value pair:
    * first the number of the bucket is told by calculating ''key [[https://en.wikipedia.org/wiki/Modulo|%]] bucket count'', and then the key-value pair is added to an empty place in the bucket
    * if the bucket is full, a //rehashing// is preformed as follows: the number of buckets is doubled, and all items are relocated to corresponding buckets; once this is completed, the attempt to add the item is repeated,
  * when looking for the value associated with a given key, the bucket number is calculated, and that bucket is searched for the corresponding key-value pair,
  * any operation (apart form creating and destroying) on the table must work fine when run concurrently with any other other operations (apart form creating and destroying) on the table.

Below, you are provided a header file with declarations of functions and the
description of how they have to work. You must not modify the header file.
For synchronization you must use the POSIX API. 

The solutions will be graded basing on the correctness of the code, use of
fine-grained locking and correctness of memory management. Moreover, severe
code illegibility, spaghetti code, code bloat and redundancy will lower the
grade. Implementing the table in a different manner than the one described
on this page will be counted as a fail.

**The deadline for the assignment is 05.06.2025 (AoE).**
\\
You must send me your solution as a single uncompressed attachment
to an e-mail message with the subject beginning with [OSCP].

Please reach me by e-mail if anything there is not clear for you.

<code c table.h>
#pragma once
#include <limits.h>
#include <stdlib.h>

struct table_t;

/** "INVALID_KEY" may be used internally to mark non-existing items */
#define INVALID_KEY INT_MIN

/** "INVALID_VAL" shall be returned if no value was associated with the key */
#define INVALID_VAL INT_MIN

/** "INVALID_ARGUMENTS" shall be returned if provided arguments are invalid */
#define INVALID_ARGUMENTS (INVALID_VAL + 1)

/** "OUT_OF_MEMORY" shall be returned if the system ran out of memory */
#define OUT_OF_MEMORY (INVALID_VAL + 2)

/** Creates a new hash table.
 * Bucket size (number of items in bucket) stays fixed.
 * The map shall initially have the number of buckets as provided.
 * @returns
 *   INVALID_ARGUMENTS if table is NULL or numberOfBuckets is 0 or bucketSize is 0, or
 *   OUT_OF_MEMORY if dynamic memory allocation failed, or
 *   EXIT_SUCCESS.
 */
int table_init(struct table_t **table, size_t numberOfBuckets, size_t bucketSize);

/** Adds or replaces "value" under the "key" to the "table", and if the pointer
 * "oldValue" is not null, the old value is written to "*oldValue" (if there
 * was no value associated with the key, INVALID_VAL must be written instead).
 * If needed, doubles the bucket count to make space for the new element.
 * @returns
 *   INVALID_ARGUMENTS if table is NULL or key is "INVALID_KEY" or value is "INVALID_VAL", or
 *   OUT_OF_MEMORY if dynamic memory allocation failed, or
 *   EXIT_SUCCESS.
 */
int table_insert(struct table_t *table, int key, int value, int *oldValue);

/** @returns
 *   INVALID_ARGUMENTS if table is NULL or key is "INVALID_KEY", or
 *   INVALID_VAL if the provided key does not exist in the table, or
 *   the value associated with "key" in the "table"
 */
int table_lookup(struct table_t *table, int key);

/** Acts identical to "table_lookup", but additionally erases the key from the
 * table */
int table_deleteKey(struct table_t *table, int key);

/** If the table contains given key, "table_awaitAndDelete" acts identical to
 * "table_delete", else "table_awaitAndDelete" waits until the given key is
 * added (by a concurrent thread) to the table and then acts identical to
 * "table_delete". */
int table_awaitAndDelete(struct table_t *table, int key);

/** Deallocates all memory associated with the table.
 * @returns
 *   INVALID_ARGUMENTS if table is NULL, or
 *   EXIT_SUCCESS.
 */
int table_destroy(struct table_t *table);

struct table_iterator_t;

/** Creates a new "table_iterator_t" object and returns it to caller.
 * The caller must then execute "table_next" until it returns "TABLE_END".
 * Please read the description of "table_next" for more information.
 * @returns
 *   NULL if table is NULL, or
 *   address of the new iterator object.
 */
struct table_iterator_t *table_begin(struct table_t *table);

/** "TABLE_END" is returned by "table_next" if all items were iterated over */
#define TABLE_END -1

/** Checks if there is an item that was not yet visited.
 * 
 * If there is such item, this function sets "*key" to the key and "*value"
 * to the pointer to the item and returns EXIT_SUCCESS. Note that the value
 * can be changed via the pointer until subsequent call to "table_next".
 * 
 * If there is no such item, this function returns "TABLE_END" and destroys
 * the iterator, freeing all resources associated with it.
 * 
 * 
 * If a "table_deleteKey" or "table_awaitAndDelete" is called concurrently
 * (i.e., between the "table_begin" and the last "table_next"), the deleted
 * key may or may not be iterated over.
 * 
 * If a "table_insert" is called concurrently (i.e., between the "table_begin"
 * and the last "table_next"), the added key may or may not be iterated over,
 * but no item can be iterated over multiple times.
 * 
 * @returns
 *   INVALID_ARGUMENTS if table_next is NULL, or
 *   TABLE_END if all elements were returned by previous calls to table_next, or
 *   EXIT_SUCCESS if key and *value point to the next item. 
 */
int table_next(struct table_iterator_t *iterator, int *key, int **value);
</code>

++++ An example code that uses the table is provided here:|
<code c example.c>
#include "table.h"

#include <assert.h>
#include <pthread.h>
#include <stdint.h>
#include <unistd.h>

// helper functions and variables declaration
void advanceStep(int n);
void waitStep(int n);
void restartMeasuringTime();
double measuredTime();
_Thread_local int k, v, *p;

struct table_t *myTable;

void thread0(void) {
    table_init(&myTable, 4, 2);

    v = table_lookup(myTable, 0);          assert(v == INVALID_VAL);

    table_insert(myTable, 1, 2, &v);       assert(v == INVALID_VAL);

    v = table_lookup(myTable, 1);          assert(v == 2);

    table_insert(myTable, 5, 3, NULL);
    table_insert(myTable, 9, 4, NULL);

    v = table_deleteKey(myTable, 1);       assert(v == 2);
    v = table_lookup(myTable, 5);          assert(v == 3);
    v = table_lookup(myTable, 9);          assert(v == 4);
    v = table_lookup(myTable, 1);          assert(v == INVALID_VAL);

    restartMeasuringTime();
    advanceStep(1);

    v = table_awaitAndDelete(myTable, 1);
    assert(v == 5 && measuredTime() > 0.1);

    table_insert(myTable, 3, 6, NULL);
    table_insert(myTable, 4, 7, NULL);
    table_insert(myTable, 6, 8, NULL);
    table_insert(myTable, 12, 9, NULL);

    int s = 2;
    uint_fast16_t seenKeys = 0;
    #define expectedKeys (((1<<3)|(1<<4)|(1<<12)|(1<<5)|(1<<6)|(1<<9)))

    struct table_iterator_t *it = table_begin(myTable);
    while (table_next(it, &k, &p) == EXIT_SUCCESS) {
        advanceStep(s++);
        seenKeys |= 1 << k;
        if (k == 6)
            *p = 10;
        usleep(100000);
    }
                                           assert((seenKeys & expectedKeys) == expectedKeys);
                                           assert(s == 8);

    v = table_lookup(myTable, 6);          assert(v == 10);

    table_destroy(myTable);
}

void *thread1(void *_) {
    waitStep(1);
    usleep(100000);
    table_insert(myTable, 1, 5, NULL);

    waitStep(2);
    v = table_lookup(myTable, 6);          assert(v == 8);
    return NULL;
}

void *thread2(void *_) {
    waitStep(3);
    table_insert(myTable, 19, 10, &v);     assert(v == INVALID_VAL);
    return NULL;
}

void *thread3(void *_) {
    waitStep(4);
    v = table_deleteKey(myTable, 3);       assert(v == 6);
    return NULL;
}

int main() {
    void *(*funcs[])(void *) = {thread1, thread2, thread3};
    #define count ((sizeof(funcs) / sizeof(*funcs)))
    pthread_t ids[count];
    for (int i = 0; i < count; ++i)
        pthread_create(&ids[i], NULL, funcs[i], NULL);
    thread0();
    for (int i = 0; i < count; ++i)
        pthread_join(ids[i], NULL);
    return 0;
}

int step;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;
void advanceStep(int n) {
    pthread_mutex_lock(&m);
    assert(n == step + 1);
    step = n;
    pthread_cond_broadcast(&c);
    pthread_mutex_unlock(&m);
}
void waitStep(int n) {
    pthread_mutex_lock(&m);
    while (step < n)
        pthread_cond_wait(&c, &m);
    pthread_mutex_unlock(&m);
}

_Thread_local struct timespec t;
void restartMeasuringTime() {
    clock_gettime(CLOCK_MONOTONIC, &t);
}
double measuredTime() {
    struct timespec now;
    clock_gettime(CLOCK_MONOTONIC, &now);
    double elapsed = now.tv_sec - t.tv_sec;
    elapsed += (now.tv_nsec - t.tv_nsec) / 1e9;
    return elapsed;
}
</code>
++++
Jan Kończak

Narzędzia użytkownika

Narzędzia witryny

Narzędzia strony
