diff options
author | Stefan Zabka <zabkaste@hu-berlin.de> | 2020-06-18 15:04:54 +0200 |
---|---|---|
committer | Stefan Zabka <zabkaste@hu-berlin.de> | 2020-06-18 15:05:14 +0200 |
commit | 021afcb8e4aa4fbc7905f527089c415108c86c75 (patch) | |
tree | 3fd53ab9a1ccdb8b807bb973a4e19da077b871ea /04_exercise/slotmap | |
parent | 190c347866ebd0c703407285646c6ce3e94f19a4 (diff) | |
download | betriebssysteme-021afcb8e4aa4fbc7905f527089c415108c86c75.tar.gz betriebssysteme-021afcb8e4aa4fbc7905f527089c415108c86c75.zip |
Switched to slotmap
Diffstat (limited to '04_exercise/slotmap')
-rw-r--r-- | 04_exercise/slotmap/slomap_test.c | 19 | ||||
-rw-r--r-- | 04_exercise/slotmap/slotmap.c | 48 | ||||
-rw-r--r-- | 04_exercise/slotmap/slotmap.h | 36 |
3 files changed, 103 insertions, 0 deletions
diff --git a/04_exercise/slotmap/slomap_test.c b/04_exercise/slotmap/slomap_test.c new file mode 100644 index 0000000..930bfa8 --- /dev/null +++ b/04_exercise/slotmap/slomap_test.c @@ -0,0 +1,19 @@ +// +// Created by stefan on 18.06.20. +// +#include <assert.h> +#include <slotmap.h> +#include <stdbool.h> + +bool find1(void const * ptr) { + return * (int const *) ptr == 1; +} +int main() { + smEntry slab [10]; + int data [6] = {0, 1, 2,3,4,5}; + smHeader header = smInit((smEntry *)&slab, 10); + smInsert(&header, &data[1]); + smEntry * entry = smFindEntry(&header, &find1); + assert(*(int *)entry->value == 1); + return 0; +} diff --git a/04_exercise/slotmap/slotmap.c b/04_exercise/slotmap/slotmap.c new file mode 100644 index 0000000..57c4ef5 --- /dev/null +++ b/04_exercise/slotmap/slotmap.c @@ -0,0 +1,48 @@ +// +// Created by stefan on 18.06.20. +// + +#include "slotmap.h" +#include <stdio.h> +smHeader smInit(smEntry * slab, size_t size) { + for (int i = 0; i < size; ++i) { + slab[i].value = (intptr_t)NULL; + } + return (smHeader){.slab = slab, .size=size}; +} +int smInsert(smHeader const * header, void * value) { + for (size_t i = 0; i< header->size; ++i ) { + intptr_t ptr = atomic_load(&header->slab[i].value); + if((void *)ptr == NULL) { + intptr_t expected = (intptr_t) NULL; + if(atomic_compare_exchange_strong(&header->slab[i].value, &expected, (intptr_t) value)){ + return 0; + } + } + } + return -1; +} +void smDelete(smEntry * node) { + intptr_t oldval = atomic_exchange(&node->value, (intptr_t)(NULL)); + if((void *) oldval == NULL) { + fprintf(stderr, "A Node has been double deleted"); + } +} +void smDeleteValue(smHeader const * header, void * value){ + for (size_t i = 0; i< header->size; ++i ) { + intptr_t ptr = atomic_load(&header->slab[i].value); + if((void *)ptr == value) { + smDelete(&header->slab[i]); + } + } +} +smEntry *smFindEntry(smHeader const * header, SearchFunction func){ + for (size_t i = 0; i< header->size; ++i ) { + void * value = (void *) atomic_load(&header->slab[i].value); + + if(value != NULL && func(value)) { + return &header->slab[i]; + } + } + return NULL; +} diff --git a/04_exercise/slotmap/slotmap.h b/04_exercise/slotmap/slotmap.h new file mode 100644 index 0000000..1d687fc --- /dev/null +++ b/04_exercise/slotmap/slotmap.h @@ -0,0 +1,36 @@ +// +// Created by stefan on 18.06.20. +// + +#ifndef BETRIEBSYSTEME_SLOTMAP_H +#define BETRIEBSYSTEME_SLOTMAP_H +#include <stdatomic.h> +#include <stdlib.h> +#include <stdbool.h> + +typedef struct smNode { + atomic_intptr_t value; +} smEntry; + +typedef struct smHeader { + smEntry *slab; + size_t size; +} smHeader; + +typedef bool (*SearchFunction)(void const *); + +smHeader smInit(smEntry * slab, size_t size); +int smInsert(smHeader const * header, void * value); +void smDelete(smEntry * node); +void smDeleteValue(smHeader const * header, void * value); +/** + * Returns a node whose value is accepted by the SearchFunction + * @param header The header of the slotmap to be searched + * @param func The search function, that will be applied to each element until one is found + * @return the Entry that was found + */ +smEntry *smFindEntry(smHeader const * header, SearchFunction func); + + + +#endif // BETRIEBSYSTEME_SLOTMAP_H |