From 01d5015ba093f8c5fdb18b669943c7da6450e72f Mon Sep 17 00:00:00 2001 From: Olaf Wintermann Date: Sat, 8 Jul 2023 15:51:26 +0200 Subject: [PATCH] add single instance mode --- application/Fsb.c | 2 +- application/main.c | 25 +- application/playlist.c | 5 + application/playlist.h | 2 + application/properties.c | 2 +- application/settings.c | 187 +++++++ application/settings.h | 12 + application/window.c | 38 +- application/window.h | 2 + ucx/Makefile | 3 +- ucx/allocator.c | 14 + ucx/array_list.c | 103 ++-- ucx/buffer.c | 23 + ucx/compare.c | 52 +- ucx/cx/allocator.h | 46 +- ucx/cx/array_list.h | 2 +- ucx/cx/buffer.h | 36 ++ ucx/cx/collection.h | 147 ++++++ ucx/cx/common.h | 25 +- ucx/cx/hash_key.h | 11 +- ucx/cx/hash_map.h | 22 +- ucx/cx/iterator.h | 12 +- ucx/cx/linked_list.h | 12 +- ucx/cx/list.h | 149 ++---- ucx/cx/map.h | 1012 ++++++++++++++++++++++++++++++++------ ucx/cx/mempool.h | 102 ++-- ucx/cx/printf.h | 4 +- ucx/cx/string.h | 127 ++++- ucx/cx/utils.h | 1 - ucx/hash_key.c | 10 +- ucx/hash_map.c | 150 +++--- ucx/linked_list.c | 119 ++--- ucx/list.c | 151 +++--- ucx/map.c | 112 +++++ ucx/mempool.c | 232 +++++++++ ucx/printf.c | 4 +- ucx/string.c | 41 +- ucx/tree.c | 52 -- ucx/utils.c | 5 + 39 files changed, 2298 insertions(+), 756 deletions(-) create mode 100644 ucx/cx/collection.h create mode 100644 ucx/map.c create mode 100644 ucx/mempool.c delete mode 100644 ucx/tree.c diff --git a/application/Fsb.c b/application/Fsb.c index 42cd412..09c8eb6 100644 --- a/application/Fsb.c +++ b/application/Fsb.c @@ -2715,7 +2715,7 @@ static void pathbar_popup(Widget w, PathBar *p, XtPointer d) { Widget parent = XtParent(w); Display *dp = XtDisplay(parent); Window root = XDefaultRootWindow(dp); - + int x, y; Window child; XTranslateCoordinates(dp, XtWindow(parent), root, 0, 0, &x, &y, &child); diff --git a/application/main.c b/application/main.c index d8a3b31..422b6ee 100644 --- a/application/main.c +++ b/application/main.c @@ -114,6 +114,26 @@ int main(int argc, char** argv) { open_file_arg = argv[1]; } + // load settings + if(load_config()) { + return 1; + } + + // try single instance open + if(open_file_arg) { + char *instance_path = InstanceFilePath(display); + int instance_fd = ConnectToInstance(instance_path); + free(instance_path); + + if(instance_fd >= 0) { + write(instance_fd, "open ", 5); + write(instance_fd, open_file_arg, strlen(open_file_arg)); + write(instance_fd, "\n", 1); + close(instance_fd); + return 0; + } + } + XtAppAddInput( app, event_pipe[0], @@ -121,11 +141,6 @@ int main(int argc, char** argv) { input_proc, NULL); - // load settings - if(load_config()) { - return 1; - } - MainWindow *window = WindowCreate(display); toplevel_window = window->window; diff --git a/application/playlist.c b/application/playlist.c index e32110d..89c276b 100644 --- a/application/playlist.c +++ b/application/playlist.c @@ -32,6 +32,7 @@ void PlayListInit(MainWindow *win) { win->playlist.tracks = cxArrayListCreate(cxDefaultAllocator, NULL, CX_STORE_POINTERS, 64); + win->playlist.tracks->simple_destructor = free; win->playlist.current_track = -1; } @@ -77,3 +78,7 @@ void PlayListPlayTrack(MainWindow *win, int i) { } } } + +void PlayListClear(MainWindow *win) { + cxListClear(win->playlist.tracks); +} diff --git a/application/playlist.h b/application/playlist.h index 5e1a0b8..26df47b 100644 --- a/application/playlist.h +++ b/application/playlist.h @@ -37,6 +37,8 @@ void PlayListPlayNext(MainWindow *win, bool force); void PlayListPlayTrack(MainWindow *win, int i); +void PlayListClear(MainWindow *win); + #ifdef __cplusplus } #endif diff --git a/application/properties.c b/application/properties.c index ef2e1b5..52885f0 100644 --- a/application/properties.c +++ b/application/properties.c @@ -248,7 +248,7 @@ int ucx_properties_store(CxMap *map, FILE *file) { value = cx_str(v->value); written = 0; - written += fwrite(v->key->data.bytes, 1, v->key->len, file); + written += fwrite(v->key->data, 1, v->key->len, file); written += fwrite(" = ", 1, 3, file); written += fwrite(value.ptr, 1, value.length, file); written += fwrite("\n", 1, 1, file); diff --git a/application/settings.c b/application/settings.c index d3a670b..ac45d5d 100644 --- a/application/settings.c +++ b/application/settings.c @@ -31,15 +31,22 @@ #include #include +#include +#include + + #include "main.h" #include "utils.h" #include "json.h" +#include "window.h" +#include "playlist.h" #include #include //include #include #include +#include #define CONFIG_BASE_DIR ".config" #define UWP_CONFIG_DIR "uwplayer" @@ -52,6 +59,8 @@ static void conf_load_global_settings(void); static char *uwp_config_dir; +static int instance_socket = -1; + /* * root json config object */ @@ -249,3 +258,181 @@ static void* player_bin_search_thread(void *data) { char* SettingsGetPlayerBin(void) { return cxMapGet(uwp_settings, cx_hash_key_str(UWP_PLAYER_BIN)); } + + +char *InstanceFilePath(Display *dp) { + cxmutstr instance_file = cx_asprintf("instance%s", DisplayString(dp)); + char *path = util_concat_path(uwp_config_dir, instance_file.ptr); + free(instance_file.ptr); + return path; +} + +int ConnectToInstance(const char *path) { + int fd = socket(AF_UNIX, SOCK_STREAM, 0); + if(!fd) { + return -1; + } + + size_t path_len = strlen(path); + + struct sockaddr_un addr; + if(path_len > sizeof(addr.sun_path)-1) { + return -1; + } + + memset(&addr, 0, sizeof(addr)); + addr.sun_family = AF_UNIX; + memcpy(addr.sun_path, path, strlen(path) + 1); + + if(connect(fd, (struct sockaddr*)&addr, sizeof(addr))) { + close(fd); + return -1; + } + + return fd; +} + +int CreateSingleInstanceSocket(Display *dp, Bool *already_running) { + char *instance_path = InstanceFilePath(dp); + size_t instance_path_len = strlen(instance_path); + *already_running = 0; + + // check path + struct sockaddr_un addr; + if(instance_path_len > sizeof(addr.sun_path)-1) { + fprintf(stderr, "instance path '%s' too long for unix domain socket", instance_path); + free(instance_path); + return 1; + } + + // check if the socket already exists and is open + struct stat s; + if(!stat(instance_path, &s)) { + int fd = ConnectToInstance(instance_path); + close(fd); + if(fd >= 0) { + *already_running = 1; + return 0; // instance already running + } + + // instance not running but socket file exists + // remove socket before creating a new socket + unlink(instance_path); + } + + memset(&addr, 0, sizeof(addr)); + addr.sun_family = AF_UNIX; + memcpy(addr.sun_path, instance_path, instance_path_len+1); + + free(instance_path); + instance_socket = socket(AF_UNIX, SOCK_STREAM, 0); + if(instance_socket < 0) { + fprintf(stderr, "cannot create instance socket: %s", strerror(errno)); + return 1; + } + + if(bind(instance_socket, (struct sockaddr*)&addr, sizeof(addr))) { + fprintf(stderr, "cannot bind instance socket: %s", strerror(errno)); + return 1; + } + + pthread_t tid; + if(pthread_create(&tid, NULL, instance_socket_thread, NULL)) { + close(instance_socket); + instance_socket = -1; + return -1; + } + pthread_detach(tid); + + return 0; +} + +static Boolean cmd_open(XtPointer data) { + MainWindow *win = GetMainWindow(); + char *file = data; + printf("open %s\n", file); + + PlayListClear(win); + PlayListAddFile(win, file); + PlayListPlayTrack(win, win->playlist.tracks->size-1); + + free(data); + return 0; +} + +static void process_msg(CxBuffer *msgbuf, size_t *rpos) { + cxstring msg = cx_strn(NULL, 0); + for(size_t i=*rpos;isize;i++) { + if(msgbuf->space[i] == '\n') { + msg.ptr = msgbuf->space + *rpos; + msg.length = i - *rpos; + *rpos = i+1; + break; + } + } + + if(msg.length > 0) { + if(cx_strprefix(msg, CX_STR("open "))) { + cxstring file = cx_strsubs(msg, 5); + cxmutstr mfile = cx_strdup(file); + AppExecProc(cmd_open, mfile.ptr); + } else { + fprintf(stderr, "unknown instance command: {%.*s}\n", (int)msg.length, msg.ptr); + } + + if(*rpos < msgbuf->size) { + process_msg(msgbuf, rpos); + } + } +} + +void* instance_socket_thread(void *data) { + listen(instance_socket, 8); + + CxBuffer msgbuf; + cxBufferInit(&msgbuf, NULL, 1024, cxDefaultAllocator, CX_BUFFER_AUTO_EXTEND|CX_BUFFER_FREE_CONTENTS); + + char buf[1024]; + + while(TRUE) { + printf("accept instance socket\n"); + int fd = accept(instance_socket, NULL, 0); + if(fd < 0) { + break; + } + printf("accept instance connection\n"); + + msgbuf.pos = 0; + msgbuf.size = 0; + size_t rpos = 0; + + ssize_t r; + while((r = read(fd, buf, 1024)) > 0) { + cxBufferWrite(buf, 1, r, &msgbuf); + process_msg(&msgbuf, &rpos); + } + + printf("close instance connection\n"); + close(fd); + } + + cxBufferDestroy(&msgbuf); + + printf("instance socket shutdown\n"); + + return NULL; +} + +void ShutdownInstanceSocket(Display *dp) { + if(instance_socket < 0) { + return; + } + + shutdown(instance_socket, SHUT_RDWR); + close(instance_socket); + instance_socket = -1; + + char *instance_path = InstanceFilePath(dp); + unlink(instance_path); + free(instance_path); +} diff --git a/application/settings.h b/application/settings.h index e97b080..8cce5f2 100644 --- a/application/settings.h +++ b/application/settings.h @@ -23,6 +23,8 @@ #ifndef UWP_SETTINGS_H #define UWP_SETTINGS_H +#include + #ifdef __cplusplus extern "C" { #endif @@ -39,6 +41,16 @@ int load_config(void); char* SettingsGetPlayerBin(void); +char *InstanceFilePath(Display *dp); + +int ConnectToInstance(const char *path); + +int CreateSingleInstanceSocket(Display *dp, Bool *already_running); + +void* instance_socket_thread(void *data); + +void ShutdownInstanceSocket(Display *dp); + #ifdef __cplusplus } diff --git a/application/window.c b/application/window.c index 621ada7..96a4510 100644 --- a/application/window.c +++ b/application/window.c @@ -29,6 +29,7 @@ #include "player.h" #include "playlist.h" #include "xdnd.h" +#include "settings.h" #include "Fsb.h" #include "Sidebar.h" @@ -46,6 +47,7 @@ static void PlayRandomCB(Widget w, void *udata, void *cdata); static void ViewFullscreenCB(Widget w, void *udata, void *cdata); static void ViewSidebarCB(Widget w, void *udata, void *cdata); static void ViewAdjustWindowSizeCB(Widget w, void *udata, void *cdata); +static void PrefSingleInstanceCB(Widget w, void *udata, void *cdata); static void WindowRealized(MainWindow *win); @@ -479,6 +481,16 @@ static void WindowCreateMenu(MainWindow *win, Widget parent, Arg *mbargs, int nm XmStringFree(s); Widget viewMenu = XmVaCreateSimplePulldownMenu(menubar, "menu", 2, NULL, NULL); + s = XmStringCreateSimple("Preferences"); + Widget prefMenuItem = XtVaCreateManagedWidget( + "menuitem", + xmCascadeButtonWidgetClass, + menubar, + XmNlabelString, s, + NULL); + XmStringFree(s); + Widget prefMenu = XmVaCreateSimplePulldownMenu(menubar, "menu", 3, NULL, NULL); + // file menu createMenuItem(fileMenu, "fileOpen", "Open...", 'O', "CtrlO", "Ctrl+O", FileOpenCB, NULL); createMenuItem(fileMenu, "fileQuit", "Exit", 'E', "CtrlQ", "Ctrl+Q", FileQuitCB, NULL); @@ -493,7 +505,6 @@ static void WindowCreateMenu(MainWindow *win, Widget parent, Arg *mbargs, int nm XtVaSetValues(win->playAutoPlayButton, XmNindicatorType, XmONE_OF_MANY, NULL); XtVaSetValues(win->playRandom, XmNindicatorType, XmONE_OF_MANY, NULL); - // view menu createMenuItem(viewMenu, "viewFullscreen", "Fullscreen", 'F', "F", "F", ViewFullscreenCB, NULL); win->viewSidebarButton = createToggleMenuItem(viewMenu, "viewSidebar", "View Sidebar", 'S', False, NULL, NULL, ViewSidebarCB, win); @@ -501,6 +512,9 @@ static void WindowCreateMenu(MainWindow *win, Widget parent, Arg *mbargs, int nm createMenuSeparator(viewMenu); win->viewAdjustWindowSize = createToggleMenuItem(viewMenu, "viewAdjustWindowSize", "Adjust Window Size", 'W', TRUE, NULL, NULL, ViewAdjustWindowSizeCB, win); + + // preferences menu + win->prefSingleInstanceButton = createToggleMenuItem(prefMenu, "prefSingleInstance", "Single Instance", 'S', FALSE, NULL, NULL, PrefSingleInstanceCB, win); } void go_fullscreen(Display *dsp, Window win) @@ -682,6 +696,28 @@ static void ViewAdjustWindowSizeCB(Widget w, void *udata, void *cdata) { win->adjustWindowSize = XmToggleButtonGadgetGetState(w); } +static void PrefSingleInstanceCB(Widget w, void *udata, void *cdata) { + MainWindow *win = udata; + win->singleInstance = XmToggleButtonGadgetGetState(w); + + Display *dp = XtDisplay(w); + + if(!win->singleInstance) { + ShutdownInstanceSocket(dp); + return; + } + + Bool disable_item = False; + if(CreateSingleInstanceSocket(dp, &disable_item)) { + // TODO: err + disable_item = True; + } + if(disable_item) { + win->singleInstance = 0; + XmToggleButtonGadgetSetState(w, False, False); + } +} + void WindowAdjustAspectRatio(MainWindow *win) { if(!win->player) return; if(!win->player->isactive || win->player->width <= 0 || win->player->height <= 0) return; diff --git a/application/window.h b/application/window.h index deb8fe8..a7a9c1c 100644 --- a/application/window.h +++ b/application/window.h @@ -80,10 +80,12 @@ typedef struct MainWindow { Widget playRandom; Widget viewSidebarButton; Widget viewAdjustWindowSize; + Widget prefSingleInstanceButton; PlayList playlist; bool adjustWindowSize; + bool singleInstance; Time player_event_time; Time button_press_time; diff --git a/ucx/Makefile b/ucx/Makefile index 0825197..0bb8b51 100644 --- a/ucx/Makefile +++ b/ucx/Makefile @@ -32,13 +32,14 @@ include ../config.mk # list of source files SRC = allocator.c SRC += array_list.c -SRC += basic_mempool.c +SRC += mempool.c SRC += buffer.c SRC += compare.c SRC += hash_key.c SRC += hash_map.c SRC += linked_list.c SRC += list.c +SRC += map.c SRC += printf.c SRC += string.c SRC += utils.c diff --git a/ucx/allocator.c b/ucx/allocator.c index 7ccc6ff..e12255e 100644 --- a/ucx/allocator.c +++ b/ucx/allocator.c @@ -75,6 +75,20 @@ struct cx_allocator_s cx_default_allocator = { }; CxAllocator *cxDefaultAllocator = &cx_default_allocator; + +int cx_reallocate( + void **mem, + size_t n +) { + void *nmem = realloc(*mem, n); + if (nmem == NULL) { + return 1; + } else { + *mem = nmem; + return 0; + } +} + // IMPLEMENTATION OF HIGH LEVEL API void *cxMalloc( diff --git a/ucx/array_list.c b/ucx/array_list.c index 5c66d53..e59e648 100644 --- a/ucx/array_list.c +++ b/ucx/array_list.c @@ -103,7 +103,7 @@ enum cx_array_copy_result cx_array_copy( } #ifndef CX_ARRAY_SWAP_SBO_SIZE -#define CX_ARRAY_SWAP_SBO_SIZE 512 +#define CX_ARRAY_SWAP_SBO_SIZE 128 #endif void cx_array_swap( @@ -150,6 +150,7 @@ void cx_array_swap( typedef struct { struct cx_list_s base; void *data; + size_t capacity; struct cx_array_reallocator_s reallocator; } cx_array_list; @@ -168,7 +169,24 @@ static void *cx_arl_realloc( static void cx_arl_destructor(struct cx_list_s *list) { cx_array_list *arl = (cx_array_list *) list; + + char *ptr = arl->data; + + if (list->simple_destructor) { + for (size_t i = 0; i < list->size; i++) { + cx_invoke_simple_destructor(list, ptr); + ptr += list->item_size; + } + } + if (list->advanced_destructor) { + for (size_t i = 0; i < list->size; i++) { + cx_invoke_advanced_destructor(list, ptr); + ptr += list->item_size; + } + } + cxFree(list->allocator, arl->data); + cxFree(list->allocator, list); } static size_t cx_arl_insert_array( @@ -186,17 +204,17 @@ static size_t cx_arl_insert_array( // do we need to move some elements? if (index < list->size) { char const *first_to_move = (char const *) arl->data; - first_to_move += index * list->itemsize; + first_to_move += index * list->item_size; size_t elems_to_move = list->size - index; size_t start_of_moved = index + n; if (CX_ARRAY_COPY_SUCCESS != cx_array_copy( &arl->data, &list->size, - &list->capacity, + &arl->capacity, start_of_moved, first_to_move, - list->itemsize, + list->item_size, elems_to_move, &arl->reallocator )) { @@ -213,10 +231,10 @@ static size_t cx_arl_insert_array( if (CX_ARRAY_COPY_SUCCESS == cx_array_copy( &arl->data, &list->size, - &list->capacity, + &arl->capacity, index, array, - list->itemsize, + list->item_size, n, &arl->reallocator )) { @@ -249,7 +267,7 @@ static int cx_arl_insert_iter( ); if (result == 0 && prepend != 0) { iter->index++; - iter->elem_handle = ((char *) iter->elem_handle) + list->itemsize; + iter->elem_handle = ((char *) iter->elem_handle) + list->item_size; } return result; } else { @@ -271,11 +289,7 @@ static int cx_arl_remove( } // content destruction - if (list->content_destructor_type != CX_DESTRUCTOR_NONE) { - char *ptr = arl->data; - ptr += index * list->itemsize; - cx_list_invoke_destructor(list, ptr); - } + cx_invoke_destructor(list, ((char *) arl->data) + index * list->item_size); // short-circuit removal of last element if (index == list->size - 1) { @@ -287,10 +301,10 @@ static int cx_arl_remove( int result = cx_array_copy( &arl->data, &list->size, - &list->capacity, + &arl->capacity, index, - ((char *) arl->data) + (index + 1) * list->itemsize, - list->itemsize, + ((char *) arl->data) + (index + 1) * list->item_size, + list->item_size, list->size - index - 1, &arl->reallocator ); @@ -307,26 +321,20 @@ static void cx_arl_clear(struct cx_list_s *list) { cx_array_list *arl = (cx_array_list *) list; char *ptr = arl->data; - switch (list->content_destructor_type) { - case CX_DESTRUCTOR_SIMPLE: { - for (size_t i = 0; i < list->size; i++) { - cx_list_invoke_simple_destructor(list, ptr); - ptr += list->itemsize; - } - break; + if (list->simple_destructor) { + for (size_t i = 0; i < list->size; i++) { + cx_invoke_simple_destructor(list, ptr); + ptr += list->item_size; } - case CX_DESTRUCTOR_ADVANCED: { - for (size_t i = 0; i < list->size; i++) { - cx_list_invoke_advanced_destructor(list, ptr); - ptr += list->itemsize; - } - break; + } + if (list->advanced_destructor) { + for (size_t i = 0; i < list->size; i++) { + cx_invoke_advanced_destructor(list, ptr); + ptr += list->item_size; } - case CX_DESTRUCTOR_NONE: - break; // nothing } - memset(arl->data, 0, list->size * list->itemsize); + memset(arl->data, 0, list->size * list->item_size); list->size = 0; } @@ -337,7 +345,7 @@ static int cx_arl_swap( ) { if (i >= list->size || j >= list->size) return 1; cx_array_list *arl = (cx_array_list *) list; - cx_array_swap(arl->data, list->itemsize, i, j); + cx_array_swap(arl->data, list->item_size, i, j); return 0; } @@ -348,34 +356,35 @@ static void *cx_arl_at( if (index < list->size) { cx_array_list const *arl = (cx_array_list const *) list; char *space = arl->data; - return space + index * list->itemsize; + return space + index * list->item_size; } else { return NULL; } } -static size_t cx_arl_find( +static ssize_t cx_arl_find( struct cx_list_s const *list, void const *elem ) { assert(list->cmpfunc != NULL); + assert(list->size < SIZE_MAX / 2); char *cur = ((cx_array_list const *) list)->data; - for (size_t i = 0; i < list->size; i++) { + for (ssize_t i = 0; i < (ssize_t) list->size; i++) { if (0 == list->cmpfunc(elem, cur)) { return i; } - cur += list->itemsize; + cur += list->item_size; } - return list->size; + return -1; } static void cx_arl_sort(struct cx_list_s *list) { assert(list->cmpfunc != NULL); qsort(((cx_array_list *) list)->data, list->size, - list->itemsize, + list->item_size, list->cmpfunc ); } @@ -393,8 +402,8 @@ static int cx_arl_compare( if (d != 0) { return d; } - left += list->itemsize; - right += other->itemsize; + left += list->item_size; + right += other->item_size; } return 0; } else { @@ -407,7 +416,7 @@ static void cx_arl_reverse(struct cx_list_s *list) { void *data = ((cx_array_list const *) list)->data; size_t half = list->size / 2; for (size_t i = 0; i < half; i++) { - cx_array_swap(data, list->itemsize, i, list->size - 1 - i); + cx_array_swap(data, list->item_size, i, list->size - 1 - i); } } @@ -433,7 +442,7 @@ static void cx_arl_iter_next(void *it) { iter->index++; iter->elem_handle = ((char *) iter->elem_handle) - + ((struct cx_list_s const *) iter->src_handle)->itemsize; + + ((struct cx_list_s const *) iter->src_handle)->item_size; } } @@ -448,7 +457,7 @@ static void cx_arl_iter_prev(void *it) { iter->index--; if (iter->index < list->base.size) { iter->elem_handle = ((char *) list->data) - + iter->index * list->base.itemsize; + + iter->index * list->base.item_size; } } @@ -500,7 +509,7 @@ static cx_list_class cx_array_list_class = { CxList *cxArrayListCreate( CxAllocator const *allocator, - CxListComparator comparator, + cx_compare_func comparator, size_t item_size, size_t initial_capacity ) { @@ -514,12 +523,12 @@ CxList *cxArrayListCreate( list->base.cl = &cx_array_list_class; list->base.allocator = allocator; list->base.cmpfunc = comparator; - list->base.capacity = initial_capacity; + list->capacity = initial_capacity; if (item_size > 0) { - list->base.itemsize = item_size; + list->base.item_size = item_size; } else { - item_size = sizeof(void*); + item_size = sizeof(void *); cxListStorePointers((CxList *) list); } diff --git a/ucx/buffer.c b/ucx/buffer.c index a6ef0fb..d160504 100644 --- a/ucx/buffer.c +++ b/ucx/buffer.c @@ -70,6 +70,29 @@ void cxBufferDestroy(CxBuffer *buffer) { } } +CxBuffer *cxBufferCreate( + void *space, + size_t capacity, + CxAllocator const *allocator, + int flags +) { + CxBuffer *buf = cxMalloc(allocator, sizeof(CxBuffer)); + if (buf == NULL) return NULL; + if (0 == cxBufferInit(buf, space, capacity, allocator, flags)) { + return buf; + } else { + cxFree(allocator, buf); + return NULL; + } +} + +void cxBufferFree(CxBuffer *buffer) { + if ((buffer->flags & CX_BUFFER_FREE_CONTENTS) == CX_BUFFER_FREE_CONTENTS) { + cxFree(buffer->allocator, buffer->bytes); + } + cxFree(buffer->allocator, buffer); +} + int cxBufferSeek( CxBuffer *buffer, off_t offset, diff --git a/ucx/compare.c b/ucx/compare.c index 3922a8d..ee3fb74 100644 --- a/ucx/compare.c +++ b/ucx/compare.c @@ -31,8 +31,8 @@ #include int cx_cmp_int(void const *i1, void const *i2) { - int a = *((const int*) i1); - int b = *((const int*) i2); + int a = *((const int *) i1); + int b = *((const int *) i2); if (a == b) { return 0; } else { @@ -41,8 +41,8 @@ int cx_cmp_int(void const *i1, void const *i2) { } int cx_cmp_longint(void const *i1, void const *i2) { - long int a = *((const long int*) i1); - long int b = *((const long int*) i2); + long int a = *((const long int *) i1); + long int b = *((const long int *) i2); if (a == b) { return 0; } else { @@ -51,8 +51,8 @@ int cx_cmp_longint(void const *i1, void const *i2) { } int cx_cmp_longlong(void const *i1, void const *i2) { - long long a = *((const long long*) i1); - long long b = *((const long long*) i2); + long long a = *((const long long *) i1); + long long b = *((const long long *) i2); if (a == b) { return 0; } else { @@ -61,8 +61,8 @@ int cx_cmp_longlong(void const *i1, void const *i2) { } int cx_cmp_int16(void const *i1, void const *i2) { - int16_t a = *((const int16_t*) i1); - int16_t b = *((const int16_t*) i2); + int16_t a = *((const int16_t *) i1); + int16_t b = *((const int16_t *) i2); if (a == b) { return 0; } else { @@ -71,8 +71,8 @@ int cx_cmp_int16(void const *i1, void const *i2) { } int cx_cmp_int32(void const *i1, void const *i2) { - int32_t a = *((const int32_t*) i1); - int32_t b = *((const int32_t*) i2); + int32_t a = *((const int32_t *) i1); + int32_t b = *((const int32_t *) i2); if (a == b) { return 0; } else { @@ -81,8 +81,8 @@ int cx_cmp_int32(void const *i1, void const *i2) { } int cx_cmp_int64(void const *i1, void const *i2) { - int64_t a = *((const int64_t*) i1); - int64_t b = *((const int64_t*) i2); + int64_t a = *((const int64_t *) i1); + int64_t b = *((const int64_t *) i2); if (a == b) { return 0; } else { @@ -91,8 +91,8 @@ int cx_cmp_int64(void const *i1, void const *i2) { } int cx_cmp_uint(void const *i1, void const *i2) { - unsigned int a = *((const unsigned int*) i1); - unsigned int b = *((const unsigned int*) i2); + unsigned int a = *((const unsigned int *) i1); + unsigned int b = *((const unsigned int *) i2); if (a == b) { return 0; } else { @@ -101,8 +101,8 @@ int cx_cmp_uint(void const *i1, void const *i2) { } int cx_cmp_ulongint(void const *i1, void const *i2) { - unsigned long int a = *((const unsigned long int*) i1); - unsigned long int b = *((const unsigned long int*) i2); + unsigned long int a = *((const unsigned long int *) i1); + unsigned long int b = *((const unsigned long int *) i2); if (a == b) { return 0; } else { @@ -111,8 +111,8 @@ int cx_cmp_ulongint(void const *i1, void const *i2) { } int cx_cmp_ulonglong(void const *i1, void const *i2) { - unsigned long long a = *((const unsigned long long*) i1); - unsigned long long b = *((const unsigned long long*) i2); + unsigned long long a = *((const unsigned long long *) i1); + unsigned long long b = *((const unsigned long long *) i2); if (a == b) { return 0; } else { @@ -121,8 +121,8 @@ int cx_cmp_ulonglong(void const *i1, void const *i2) { } int cx_cmp_uint16(void const *i1, void const *i2) { - uint16_t a = *((const uint16_t*) i1); - uint16_t b = *((const uint16_t*) i2); + uint16_t a = *((const uint16_t *) i1); + uint16_t b = *((const uint16_t *) i2); if (a == b) { return 0; } else { @@ -131,8 +131,8 @@ int cx_cmp_uint16(void const *i1, void const *i2) { } int cx_cmp_uint32(void const *i1, void const *i2) { - uint32_t a = *((const uint32_t*) i1); - uint32_t b = *((const uint32_t*) i2); + uint32_t a = *((const uint32_t *) i1); + uint32_t b = *((const uint32_t *) i2); if (a == b) { return 0; } else { @@ -141,8 +141,8 @@ int cx_cmp_uint32(void const *i1, void const *i2) { } int cx_cmp_uint64(void const *i1, void const *i2) { - uint64_t a = *((const uint64_t*) i1); - uint64_t b = *((const uint64_t*) i2); + uint64_t a = *((const uint64_t *) i1); + uint64_t b = *((const uint64_t *) i2); if (a == b) { return 0; } else { @@ -151,8 +151,8 @@ int cx_cmp_uint64(void const *i1, void const *i2) { } int cx_cmp_float(void const *f1, void const *f2) { - float a = *((const float*) f1); - float b = *((const float*) f2); + float a = *((const float *) f1); + float b = *((const float *) f2); if (fabsf(a - b) < 1e-6f) { return 0; } else { diff --git a/ucx/cx/allocator.h b/ucx/cx/allocator.h index cd28934..45f47a9 100644 --- a/ucx/cx/allocator.h +++ b/ucx/cx/allocator.h @@ -133,39 +133,20 @@ typedef void (*cx_destructor_func2)( ) __attribute__((__nonnull__(2))); /** - * Structure holding an advanced destructor function and the desired payload. - * Invocations of func should use data as first argument. - */ -typedef struct { - /** - * A pointer to the data that SHALL be used to invoke func. - */ - void *data; - /** - * A pointer to the function to invoke. - */ - cx_destructor_func2 func; -} cx_advanced_destructor; - -/** - * Specifies the type of destructor to use. + * Re-allocate a previously allocated block and changes the pointer in-place, if necessary. + * + * \par Error handling + * \c errno will be set by realloc() on failure. + * + * @param mem pointer to the pointer to allocated block + * @param n the new size in bytes + * @return zero on success, non-zero on failure */ -enum cx_destructor_type { - /** - * Do not use a destructor function. - */ - CX_DESTRUCTOR_NONE, - /** - * Use a simple destructor. - * @see cx_destructor_func - */ - CX_DESTRUCTOR_SIMPLE, - /** - * Use an advanced destructor. - * @see cx_advanced_destructor - */ - CX_DESTRUCTOR_ADVANCED -}; +int cx_reallocate( + void **mem, + size_t n +) +__attribute__((__nonnull__)); /** * Allocate \p n bytes of memory. @@ -204,7 +185,6 @@ __attribute__((__alloc_size__(3))); /** * Re-allocate a previously allocated block and changes the pointer in-place, if necessary. * This function acts like cxRealloc() using the pointer pointed to by \p mem. - * On success, the pointer is changed to the new location (in case the * * \note Re-allocating a block allocated by a different allocator is undefined. * diff --git a/ucx/cx/array_list.h b/ucx/cx/array_list.h index 65ccc1e..62e564f 100644 --- a/ucx/cx/array_list.h +++ b/ucx/cx/array_list.h @@ -165,7 +165,7 @@ void cx_array_swap( */ CxList *cxArrayListCreate( CxAllocator const *allocator, - CxListComparator comparator, + cx_compare_func comparator, size_t item_size, size_t initial_capacity ); diff --git a/ucx/cx/buffer.h b/ucx/cx/buffer.h index d4be652..a000b2f 100644 --- a/ucx/cx/buffer.h +++ b/ucx/cx/buffer.h @@ -163,16 +163,52 @@ int cxBufferInit( int flags ); +/** + * Allocates and initializes a fresh buffer. + * + * \note You may provide \c NULL as argument for \p space. + * Then this function will allocate the space and enforce + * the #CX_BUFFER_FREE_CONTENTS flag. + * + * @param space pointer to the memory area, or \c NULL to allocate + * new memory + * @param capacity the capacity of the buffer + * @param allocator the allocator to use for allocating the structure and the automatic + * memory management within the buffer. If \c NULL, the default heap allocator will be used. + * @param flags buffer features (see cx_buffer_s.flags) + * @return a pointer to the buffer on success, \c NULL if a required allocation failed + */ +CxBuffer *cxBufferCreate( + void *space, + size_t capacity, + CxAllocator const *allocator, + int flags +); + /** * Destroys the buffer contents. * * Has no effect if the #CX_BUFFER_FREE_CONTENTS feature is not enabled. + * If you want to free the memory of the entire buffer, use cxBufferFree(). * * @param buffer the buffer which contents shall be destroyed + * @see cxBufferInit() */ __attribute__((__nonnull__)) void cxBufferDestroy(CxBuffer *buffer); +/** + * Deallocates the buffer. + * + * If the #CX_BUFFER_FREE_CONTENTS feature is enabled, this function also destroys + * the contents. If you \em only want to destroy the contents, use cxBufferDestroy(). + * + * @param buffer the buffer to deallocate + * @see cxBufferCreate() + */ +__attribute__((__nonnull__)) +void cxBufferFree(CxBuffer *buffer); + /** * Shifts the contents of the buffer by the given offset. * diff --git a/ucx/cx/collection.h b/ucx/cx/collection.h new file mode 100644 index 0000000..9dd08f0 --- /dev/null +++ b/ucx/cx/collection.h @@ -0,0 +1,147 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +/** + * \file collection.h + * \brief Common definitions for various collection implementations. + * \author Mike Becker + * \author Olaf Wintermann + * \version 3.0 + * \copyright 2-Clause BSD License + */ + +#ifndef UCX_COLLECTION_H +#define UCX_COLLECTION_H + +#include "allocator.h" +#include "iterator.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * Special constant used for creating collections that are storing pointers. + */ +#define CX_STORE_POINTERS 0 + +/** + * A comparator function comparing two collection elements. + */ +typedef int(*cx_compare_func)( + void const *left, + void const *right +); + +/** + * Use this macro to declare common members for a collection structure. + */ +#define CX_COLLECTION_MEMBERS \ + /** \ + * The allocator to use. \ + */ \ + CxAllocator const *allocator; \ + /** \ + * The comparator function for the elements. \ + */ \ + cx_compare_func cmpfunc; \ + /** \ + * The size of each element. \ + */ \ + size_t item_size; \ + /** \ + * The number of currently stored elements. \ + */ \ + size_t size; \ + /** \ + * An optional simple destructor for the collection's elements. \ + * \ + * @attention Read the documentation of the particular collection implementation \ + * whether this destructor shall only destroy the contents or also free the memory. \ + */ \ + cx_destructor_func simple_destructor; \ + /** \ + * An optional advanced destructor for the collection's elements. \ + * \ + * @attention Read the documentation of the particular collection implementation \ + * whether this destructor shall only destroy the contents or also free the memory. \ + */ \ + cx_destructor_func2 advanced_destructor; \ + /** \ + * The pointer to additional data that is passed to the advanced destructor. \ + */ \ + void *destructor_data; \ + /** \ + * Indicates if this instance of a collection is supposed to store pointers \ + * instead of copies of the actual objects. \ + */ \ + bool store_pointer; + +/** + * Invokes the simple destructor function for a specific element. + * + * Usually only used by collection implementations. There should be no need + * to invoke this macro manually. + * + * @param c the collection + * @param e the element + */ +#define cx_invoke_simple_destructor(c, e) \ + (c)->simple_destructor((c)->store_pointer ? (*((void **) (e))) : (e)) + +/** + * Invokes the advanced destructor function for a specific element. + * + * Usually only used by collection implementations. There should be no need + * to invoke this macro manually. + * + * @param c the collection + * @param e the element + */ +#define cx_invoke_advanced_destructor(c, e) \ + (c)->advanced_destructor((c)->destructor_data, \ + (c)->store_pointer ? (*((void **) (e))) : (e)) + + +/** + * Invokes all available destructor functions for a specific element. + * + * Usually only used by collection implementations. There should be no need + * to invoke this macro manually. + * + * @param c the collection + * @param e the element + */ +#define cx_invoke_destructor(c, e) \ + if ((c)->simple_destructor) cx_invoke_simple_destructor(c,e); \ + if ((c)->advanced_destructor) cx_invoke_advanced_destructor(c,e) + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif // UCX_COLLECTION_H diff --git a/ucx/cx/common.h b/ucx/cx/common.h index 38962c8..794c41d 100644 --- a/ucx/cx/common.h +++ b/ucx/cx/common.h @@ -89,10 +89,13 @@ /** Version constant which ensures to increase monotonically. */ #define UCX_VERSION (((UCX_VERSION_MAJOR)<<16)|UCX_VERSION_MINOR) +// Common Includes + #include #include #include #include +#include /** * Function pointer compatible with fwrite-like functions. @@ -114,17 +117,8 @@ typedef size_t (*cx_read_func)( void * ); -#ifdef _WIN32 - -#ifdef __MINGW32__ -#include -#endif // __MINGW32__ - -#else // !_WIN32 - -#include -#endif // _WIN32 +// Compiler specific stuff #ifndef __GNUC__ /** @@ -133,4 +127,15 @@ typedef size_t (*cx_read_func)( #define __attribute__(x) #endif +#ifdef _MSC_VER + +// fix missing ssize_t definition +#include +typedef SSIZE_T ssize_t; + +// fix missing _Thread_local support +#define _Thread_local __declspec(thread) + +#endif + #endif // UCX_COMMON_H diff --git a/ucx/cx/hash_key.h b/ucx/cx/hash_key.h index a921519..b7d1d1c 100644 --- a/ucx/cx/hash_key.h +++ b/ucx/cx/hash_key.h @@ -38,7 +38,7 @@ #ifndef UCX_HASH_KEY_H #define UCX_HASH_KEY_H -#include "stddef.h" +#include "common.h" #ifdef __cplusplus extern "C" { @@ -47,14 +47,7 @@ extern "C" { /** Internal structure for a key within a hash map. */ struct cx_hash_key_s { /** The key data. */ - union { - unsigned char *bytes; - unsigned char const *cbytes; - char *str; - char const *cstr; - void *obj; - void const *cobj; - } data; + void const *data; /** * The key data length. */ diff --git a/ucx/cx/hash_map.h b/ucx/cx/hash_map.h index cfa5f96..a7a94ce 100644 --- a/ucx/cx/hash_map.h +++ b/ucx/cx/hash_map.h @@ -70,11 +70,11 @@ struct cx_hash_map_s { * * If \p buckets is zero, an implementation defined default will be used. * - * If \p itemsize is CX_STORE_POINTERS, the created map will be created as if + * If \p item_size is CX_STORE_POINTERS, the created map will be created as if * cxMapStorePointers() was called immediately after creation. * * @note Iterators provided by this hash map implementation provide the remove operation. - * The index value of an iterator is the incremented when the iterator advanced without removal. + * The index value of an iterator is incremented when the iterator advanced without removal. * In other words, when the iterator is finished, \c index==size . * * @param allocator the allocator to use @@ -84,11 +84,27 @@ struct cx_hash_map_s { */ __attribute__((__nonnull__, __warn_unused_result__)) CxMap *cxHashMapCreate( - CxAllocator *allocator, + CxAllocator const *allocator, size_t itemsize, size_t buckets ); +/** + * Creates a new hash map with a default number of buckets. + * + * If \p item_size is CX_STORE_POINTERS, the created map will be created as if + * cxMapStorePointers() was called immediately after creation. + * + * @note Iterators provided by this hash map implementation provide the remove operation. + * The index value of an iterator is incremented when the iterator advanced without removal. + * In other words, when the iterator is finished, \c index==size . + * + * @param itemsize the size of one element + * @return a pointer to the new hash map + */ +#define cxHashMapCreateSimple(itemsize) \ + cxHashMapCreate(cxDefaultAllocator, itemsize, 0) + /** * Increases the number of buckets, if necessary. * diff --git a/ucx/cx/iterator.h b/ucx/cx/iterator.h index f2e2d71..26232aa 100644 --- a/ucx/cx/iterator.h +++ b/ucx/cx/iterator.h @@ -51,6 +51,8 @@ struct cx_iterator_base_s { /** * Returns a pointer to the current element. + * + * When valid returns false, the behavior of this function is undefined. */ __attribute__ ((__nonnull__)) void *(*current)(void const *); @@ -63,18 +65,22 @@ struct cx_iterator_base_s { /** * Advances the iterator. + * + * When valid returns false, the behavior of this function is undefined. */ __attribute__ ((__nonnull__)) void (*next)(void *); /** * Flag current element for removal, if possible. + * + * When valid returns false, the behavior of this function is undefined. */ __attribute__ ((__nonnull__)) bool (*flag_removal)(void *); /** - * Indicates whether this iterator is muting. + * Indicates whether this iterator may remove elements. */ bool mutating; @@ -198,13 +204,13 @@ struct cx_iterator_s { /** * Iterator value type. - * An iterator points to a certain element in an (possibly unbounded) chain of elements. + * An iterator points to a certain element in a (possibly unbounded) chain of elements. * Iterators that are based on collections (which have a defined "first" element), are supposed * to be "position-aware", which means that they keep track of the current index within the collection. * * @note Objects that are pointed to by an iterator are always mutable through that iterator. However, * this iterator cannot mutate the collection itself (add or remove elements) and any mutation of the - * collection by other means make this iterator invalid (regardless of what cxIteratorValid() returns). + * collection by other means makes this iterator invalid (regardless of what cxIteratorValid() returns). * * @see CxMutIterator */ diff --git a/ucx/cx/linked_list.h b/ucx/cx/linked_list.h index c0fc44e..1c942e3 100644 --- a/ucx/cx/linked_list.h +++ b/ucx/cx/linked_list.h @@ -66,7 +66,7 @@ extern bool CX_DISABLE_LINKED_LIST_SWAP_SBO; */ CxList *cxLinkedListCreate( CxAllocator const *allocator, - CxListComparator comparator, + cx_compare_func comparator, size_t item_size ); @@ -118,13 +118,13 @@ void *cx_linked_list_at( * @param loc_data the location of the \c data pointer within your node struct * @param cmp_func a compare function to compare \p elem against the node data * @param elem a pointer to the element to find - * @return the index of the element or a past-one index if the element could not be found + * @return the index of the element or a negative value if it could not be found */ -size_t cx_linked_list_find( +ssize_t cx_linked_list_find( void const *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, - CxListComparator cmp_func, + cx_compare_func cmp_func, void const *elem ) __attribute__((__nonnull__)); @@ -368,7 +368,7 @@ void cx_linked_list_sort( ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, - CxListComparator cmp_func + cx_compare_func cmp_func ) __attribute__((__nonnull__(1, 6))); @@ -390,7 +390,7 @@ int cx_linked_list_compare( void const *begin_right, ptrdiff_t loc_advance, ptrdiff_t loc_data, - CxListComparator cmp_func + cx_compare_func cmp_func ) __attribute__((__nonnull__(5))); /** diff --git a/ucx/cx/list.h b/ucx/cx/list.h index 95dec26..25e2ad5 100644 --- a/ucx/cx/list.h +++ b/ucx/cx/list.h @@ -38,28 +38,12 @@ #define UCX_LIST_H #include "common.h" -#include "allocator.h" -#include "iterator.h" +#include "collection.h" #ifdef __cplusplus extern "C" { #endif -#ifndef CX_STORE_POINTERS -/** - * Special constant used for creating collections that are storing pointers. - */ -#define CX_STORE_POINTERS 0 -#endif - -/** - * A comparator function comparing two list elements. - */ -typedef int(*CxListComparator)( - void const *left, - void const *right -); - /** * List class type. */ @@ -69,6 +53,7 @@ typedef struct cx_list_class_s cx_list_class; * Structure for holding the base data of a list. */ struct cx_list_s { + CX_COLLECTION_MEMBERS /** * The list class definition. */ @@ -77,50 +62,6 @@ struct cx_list_s { * The actual implementation in case the list class is delegating. */ cx_list_class const *climpl; - /** - * The allocator to use. - */ - CxAllocator const *allocator; - /** - * The comparator function for the elements. - */ - CxListComparator cmpfunc; - /** - * The size of each element (payload only). - */ - size_t itemsize; - /** - * The size of the list (number of currently stored elements). - */ - size_t size; - /** - * The capacity of the list (maximum number of elements). - */ - size_t capacity; - union { - /** - * An optional simple destructor for the list contents that admits the free() interface. - * - * @remark Set content_destructor_type to #CX_DESTRUCTOR_SIMPLE. - * - * @attention Read the documentation of the particular list implementation - * whether this destructor shall only destroy the contents or also free the memory. - */ - cx_destructor_func simple_destructor; - /** - * An optional advanced destructor for the list contents providing additional data. - * - * @remark Set content_destructor_type to #CX_DESTRUCTOR_ADVANCED. - * - * @attention Read the documentation of the particular list implementation - * whether this destructor shall only destroy the contents or also free the memory. - */ - cx_advanced_destructor advanced_destructor; - }; - /** - * The type of destructor to use. - */ - enum cx_destructor_type content_destructor_type; }; /** @@ -129,11 +70,14 @@ struct cx_list_s { struct cx_list_class_s { /** * Destructor function. + * + * Implementations SHALL invoke the content destructor functions if provided + * and SHALL deallocate the list memory, if an allocator is provided. */ void (*destructor)(struct cx_list_s *list); /** - * Member function for inserting a single elements. + * Member function for inserting a single element. * Implementors SHOULD see to performant implementations for corner cases. */ int (*insert_element)( @@ -195,13 +139,13 @@ struct cx_list_class_s { /** * Member function for finding an element. */ - size_t (*find)( + ssize_t (*find)( struct cx_list_s const *list, void const *elem ); /** - * Member function for sorting the list in place. + * Member function for sorting the list in-place. */ void (*sort)(struct cx_list_s *list); @@ -233,51 +177,6 @@ struct cx_list_class_s { */ typedef struct cx_list_s CxList; -/** - * Invokes the configured destructor function for a specific element. - * - * Usually only used by list implementations. There should be no need - * to invoke this function manually. - * - * @param list the list - * @param elem the element - */ -__attribute__((__nonnull__)) -void cx_list_invoke_destructor( - struct cx_list_s const *list, - void *elem -); - -/** - * Invokes the simple destructor function for a specific element. - * - * Usually only used by list implementations. There should be no need - * to invoke this function manually. - * - * @param list the list - * @param elem the element - */ -__attribute__((__nonnull__)) -void cx_list_invoke_simple_destructor( - struct cx_list_s const *list, - void *elem -); - -/** - * Invokes the advanced destructor function for a specific element. - * - * Usually only used by list implementations. There should be no need - * to invoke this function manually. - * - * @param list the list - * @param elem the element - */ -__attribute__((__nonnull__)) -void cx_list_invoke_advanced_destructor( - struct cx_list_s const *list, - void *elem -); - /** * Advises the list to store copies of the objects (default mode of operation). * @@ -309,11 +208,24 @@ void cxListStorePointers(CxList *list); * Returns true, if this list is storing pointers instead of the actual data. * * @param list - * @return + * @return true, if this list is storing pointers * @see cxListStorePointers() */ __attribute__((__nonnull__)) -bool cxListIsStoringPointers(CxList const *list); +static inline bool cxListIsStoringPointers(CxList const *list) { + return list->store_pointer; +} + +/** + * Returns the number of elements currently stored in the list. + * + * @param list the list + * @return the number of currently stored elements + */ +__attribute__((__nonnull__)) +static inline size_t cxListSize(CxList const *list) { + return list->size; +} /** * Adds an item to the end of the list. @@ -660,10 +572,11 @@ static inline CxMutIterator cxListMutBackwardsIterator(CxList *list) { * * @param list the list * @param elem the element to find - * @return the index of the element or \c (size+1) if the element is not found + * @return the index of the element or a negative + * value when the element is not found */ __attribute__((__nonnull__)) -static inline size_t cxListFind( +static inline ssize_t cxListFind( CxList const *list, void const *elem ) { @@ -671,7 +584,7 @@ static inline size_t cxListFind( } /** - * Sorts the list in place. + * Sorts the list in-place. * * \remark The underlying sort algorithm is implementation defined. * @@ -722,6 +635,14 @@ int cxListCompare( __attribute__((__nonnull__)) void cxListDestroy(CxList *list); +/** + * A shared instance of an empty list. + * + * Writing to that list is undefined. + */ +extern CxList * const cxEmptyList; + + #ifdef __cplusplus } // extern "C" #endif diff --git a/ucx/cx/map.h b/ucx/cx/map.h index c75cfa3..fcc621a 100644 --- a/ucx/cx/map.h +++ b/ucx/cx/map.h @@ -38,21 +38,14 @@ #define UCX_MAP_H #include "common.h" -#include "allocator.h" -#include "iterator.h" +#include "collection.h" +#include "string.h" #include "hash_key.h" #ifdef __cplusplus extern "C" { #endif -#ifndef CX_STORE_POINTERS -/** - * Special constant used for creating collections that are storing pointers. - */ -#define CX_STORE_POINTERS 0 -#endif - /** Type for the UCX map. */ typedef struct cx_map_s CxMap; @@ -64,21 +57,27 @@ typedef struct cx_map_class_s cx_map_class; /** Structure for the UCX map. */ struct cx_map_s { + CX_COLLECTION_MEMBERS /** The map class definition. */ cx_map_class *cl; - /** An allocator that is used for the map elements. */ - CxAllocator *allocator; - /** The number of elements currently stored. */ - size_t size; +}; + +/** + * The type of iterator for a map. + */ +enum cx_map_iterator_type { /** - * The size of an element. + * Iterates over key/value pairs. */ - size_t itemsize; + CX_MAP_ITERATOR_PAIRS, /** - * True, if this map shall store pointers instead - * of copies of objects. + * Iterates over keys only. */ - bool store_pointers; + CX_MAP_ITERATOR_KEYS, + /** + * Iterates over values only. + */ + CX_MAP_ITERATOR_VALUES }; /** @@ -122,44 +121,15 @@ struct cx_map_class_s { __attribute__((__nonnull__)) void *(*remove)( CxMap *map, - CxHashKey key + CxHashKey key, + bool destroy ); /** - * Iterator over the key/value pairs. - */ - __attribute__((__nonnull__, __warn_unused_result__)) - CxIterator (*iterator)(CxMap const *map); - - /** - * Iterator over the keys. - */ - __attribute__((__nonnull__, __warn_unused_result__)) - CxIterator (*iterator_keys)(CxMap const *map); - - /** - * Iterator over the values. - */ - __attribute__((__nonnull__, __warn_unused_result__)) - CxIterator (*iterator_values)(CxMap const *map); - - /** - * Mutating iterator over the key/value pairs. - */ - __attribute__((__nonnull__, __warn_unused_result__)) - CxMutIterator (*mut_iterator)(CxMap *map); - - /** - * Mutating iterator over the keys. - */ - __attribute__((__nonnull__, __warn_unused_result__)) - CxMutIterator (*mut_iterator_keys)(CxMap *map); - - /** - * Mutating iterator over the values. + * Creates an iterator for this map. */ __attribute__((__nonnull__, __warn_unused_result__)) - CxMutIterator (*mut_iterator_values)(CxMap *map); + CxIterator (*iterator)(CxMap const *map, enum cx_map_iterator_type type); }; /** @@ -176,6 +146,13 @@ struct cx_map_entry_s { void *value; }; +/** + * A shared instance of an empty map. + * + * Writing to that map is undefined. + */ +extern CxMap *const cxEmptyMap; + /** * Advises the map to store copies of the objects (default mode of operation). * @@ -187,7 +164,7 @@ struct cx_map_entry_s { */ __attribute__((__nonnull__)) static inline void cxMapStoreObjects(CxMap *map) { - map->store_pointers = false; + map->store_pointer = false; } /** @@ -204,8 +181,8 @@ static inline void cxMapStoreObjects(CxMap *map) { */ __attribute__((__nonnull__)) static inline void cxMapStorePointers(CxMap *map) { - map->store_pointers = true; - map->itemsize = sizeof(void *); + map->store_pointer = true; + map->item_size = sizeof(void *); } @@ -216,7 +193,6 @@ static inline void cxMapStorePointers(CxMap *map) { */ __attribute__((__nonnull__)) static inline void cxMapDestroy(CxMap *map) { - // TODO: likely to add auto-free feature for contents in the future map->cl->destructor(map); } @@ -231,78 +207,6 @@ static inline void cxMapClear(CxMap *map) { map->cl->clear(map); } -/** - * Puts a key/value-pair into the map. - * - * @param map the map - * @param key the key - * @param value the value - * @return 0 on success, non-zero value on failure - */ -__attribute__((__nonnull__)) -static inline int cxMapPut( - CxMap *map, - CxHashKey key, - void *value -) { - return map->cl->put(map, key, value); -} - -/** - * Retrieves a value by using a key. - * - * @param map the map - * @param key the key - * @return the value - */ -__attribute__((__nonnull__, __warn_unused_result__)) -static inline void *cxMapGet( - CxMap const *map, - CxHashKey key -) { - return map->cl->get(map, key); -} - -/** - * Removes a key/value-pair from the map by using the key. - * - * If this map is storing pointers, you should make sure that the map - * is not the last location where this pointer is stored. - * Otherwise, use cxMapRemoveAndGet() to retrieve the pointer while - * removing it from the map. - * - * @param map the map - * @param key the key - * @see cxMapRemoveAndGet() - */ -__attribute__((__nonnull__)) -static inline void cxMapRemove( - CxMap *map, - CxHashKey key -) { - (void) map->cl->remove(map, key); -} - -/** - * Removes a key/value-pair from the map by using the key. - * - * This function should only be used when the map is storing pointers, - * in order to retrieve the pointer you are about to remove. - * In any other case, cxMapRemove() is sufficient. - * - * @param map the map - * @param key the key - * @return the stored pointer or \c NULL if either the key is not present - * in the map or the map is not storing pointers - * @see cxMapStorePointers() - */ -__attribute__((__nonnull__, __warn_unused_result__)) -static inline void *cxMapRemoveAndGet( - CxMap *map, - CxHashKey key -) { - return map->cl->remove(map, key); -} // TODO: set-like map operations (union, intersect, difference) @@ -316,8 +220,8 @@ static inline void *cxMapRemoveAndGet( * @return an iterator for the currently stored values */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxMapIteratorValues(CxMap *map) { - return map->cl->iterator_values(map); +static inline CxIterator cxMapIteratorValues(CxMap const *map) { + return map->cl->iterator(map, CX_MAP_ITERATOR_VALUES); } /** @@ -332,8 +236,8 @@ static inline CxIterator cxMapIteratorValues(CxMap *map) { * @return an iterator for the currently stored keys */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxMapIteratorKeys(CxMap *map) { - return map->cl->iterator_keys(map); +static inline CxIterator cxMapIteratorKeys(CxMap const *map) { + return map->cl->iterator(map, CX_MAP_ITERATOR_KEYS); } /** @@ -350,8 +254,8 @@ static inline CxIterator cxMapIteratorKeys(CxMap *map) { * @see cxMapIteratorValues() */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxMapIterator(CxMap *map) { - return map->cl->iterator(map); +static inline CxIterator cxMapIterator(CxMap const *map) { + return map->cl->iterator(map, CX_MAP_ITERATOR_PAIRS); } @@ -365,9 +269,7 @@ static inline CxIterator cxMapIterator(CxMap *map) { * @return an iterator for the currently stored values */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) { - return map->cl->mut_iterator_values(map); -} +CxMutIterator cxMapMutIteratorValues(CxMap *map); /** * Creates a mutating iterator over the keys of a map. @@ -381,9 +283,7 @@ static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) { * @return an iterator for the currently stored keys */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) { - return map->cl->mut_iterator_keys(map); -} +CxMutIterator cxMapMutIteratorKeys(CxMap *map); /** * Creates a mutating iterator for a map. @@ -399,12 +299,836 @@ static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) { * @see cxMapMutIteratorValues() */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxMutIterator cxMapMutIterator(CxMap *map) { - return map->cl->mut_iterator(map); +CxMutIterator cxMapMutIterator(CxMap *map); + +#ifdef __cplusplus +} // end the extern "C" block here, because we want to start overloading + +/** + * Puts a key/value-pair into the map. + * + * @param map the map + * @param key the key + * @param value the value + * @return 0 on success, non-zero value on failure + */ +__attribute__((__nonnull__)) +static inline int cxMapPut( + CxMap *map, + CxHashKey const &key, + void *value +) { + return map->cl->put(map, key, value); } -#ifdef __cplusplus + +/** + * Puts a key/value-pair into the map. + * + * @param map the map + * @param key the key + * @param value the value + * @return 0 on success, non-zero value on failure + */ +__attribute__((__nonnull__)) +static inline int cxMapPut( + CxMap *map, + cxstring const &key, + void *value +) { + return map->cl->put(map, cx_hash_key_cxstr(key), value); } -#endif -#endif // UCX_MAP_H \ No newline at end of file +/** + * Puts a key/value-pair into the map. + * + * @param map the map + * @param key the key + * @param value the value + * @return 0 on success, non-zero value on failure + */ +__attribute__((__nonnull__)) +static inline int cxMapPut( + CxMap *map, + cxmutstr const &key, + void *value +) { + return map->cl->put(map, cx_hash_key_cxstr(key), value); +} + +/** + * Puts a key/value-pair into the map. + * + * @param map the map + * @param key the key + * @param value the value + * @return 0 on success, non-zero value on failure + */ +__attribute__((__nonnull__)) +static inline int cxMapPut( + CxMap *map, + char const *key, + void *value +) { + return map->cl->put(map, cx_hash_key_str(key), value); +} + +/** + * Retrieves a value by using a key. + * + * @param map the map + * @param key the key + * @return the value + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cxMapGet( + CxMap const *map, + CxHashKey const &key +) { + return map->cl->get(map, key); +} + +/** + * Retrieves a value by using a key. + * + * @param map the map + * @param key the key + * @return the value + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cxMapGet( + CxMap const *map, + cxstring const &key +) { + return map->cl->get(map, cx_hash_key_cxstr(key)); +} + +/** + * Retrieves a value by using a key. + * + * @param map the map + * @param key the key + * @return the value + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cxMapGet( + CxMap const *map, + cxmutstr const &key +) { + return map->cl->get(map, cx_hash_key_cxstr(key)); +} + +/** + * Retrieves a value by using a key. + * + * @param map the map + * @param key the key + * @return the value + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cxMapGet( + CxMap const *map, + char const *key +) { + return map->cl->get(map, cx_hash_key_str(key)); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * Always invokes the destructor function, if any, on the removed element. + * If this map is storing pointers and you just want to retrieve the pointer + * without invoking the destructor, use cxMapRemoveAndGet(). + * If you just want to detach the element from the map without invoking the + * destructor or returning the element, use cxMapDetach(). + * + * @param map the map + * @param key the key + * @see cxMapRemoveAndGet() + * @see cxMapDetach() + */ +__attribute__((__nonnull__)) +static inline void cxMapRemove( + CxMap *map, + CxHashKey const &key +) { + (void) map->cl->remove(map, key, true); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * Always invokes the destructor function, if any, on the removed element. + * If this map is storing pointers and you just want to retrieve the pointer + * without invoking the destructor, use cxMapRemoveAndGet(). + * If you just want to detach the element from the map without invoking the + * destructor or returning the element, use cxMapDetach(). + * + * @param map the map + * @param key the key + * @see cxMapRemoveAndGet() + * @see cxMapDetach() + */ +__attribute__((__nonnull__)) +static inline void cxMapRemove( + CxMap *map, + cxstring const &key +) { + (void) map->cl->remove(map, cx_hash_key_cxstr(key), true); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * Always invokes the destructor function, if any, on the removed element. + * If this map is storing pointers and you just want to retrieve the pointer + * without invoking the destructor, use cxMapRemoveAndGet(). + * If you just want to detach the element from the map without invoking the + * destructor or returning the element, use cxMapDetach(). + * + * @param map the map + * @param key the key + * @see cxMapRemoveAndGet() + * @see cxMapDetach() + */ +__attribute__((__nonnull__)) +static inline void cxMapRemove( + CxMap *map, + cxmutstr const &key +) { + (void) map->cl->remove(map, cx_hash_key_cxstr(key), true); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * Always invokes the destructor function, if any, on the removed element. + * If this map is storing pointers and you just want to retrieve the pointer + * without invoking the destructor, use cxMapRemoveAndGet(). + * If you just want to detach the element from the map without invoking the + * destructor or returning the element, use cxMapDetach(). + * + * @param map the map + * @param key the key + * @see cxMapRemoveAndGet() + * @see cxMapDetach() + */ +__attribute__((__nonnull__)) +static inline void cxMapRemove( + CxMap *map, + char const *key +) { + (void) map->cl->remove(map, cx_hash_key_str(key), true); +} + +/** + * Detaches a key/value-pair from the map by using the key + * without invoking the destructor. + * + * In general, you should only use this function if the map does not own + * the data and there is a valid reference to the data somewhere else + * in the program. In all other cases it is preferable to use + * cxMapRemove() or cxMapRemoveAndGet(). + * + * @param map the map + * @param key the key + * @see cxMapRemove() + * @see cxMapRemoveAndGet() + */ +__attribute__((__nonnull__)) +static inline void cxMapDetach( + CxMap *map, + CxHashKey const &key +) { + (void) map->cl->remove(map, key, false); +} + +/** + * Detaches a key/value-pair from the map by using the key + * without invoking the destructor. + * + * In general, you should only use this function if the map does not own + * the data and there is a valid reference to the data somewhere else + * in the program. In all other cases it is preferable to use + * cxMapRemove() or cxMapRemoveAndGet(). + * + * @param map the map + * @param key the key + * @see cxMapRemove() + * @see cxMapRemoveAndGet() + */ +__attribute__((__nonnull__)) +static inline void cxMapDetach( + CxMap *map, + cxstring const &key +) { + (void) map->cl->remove(map, cx_hash_key_cxstr(key), false); +} + +/** + * Detaches a key/value-pair from the map by using the key + * without invoking the destructor. + * + * In general, you should only use this function if the map does not own + * the data and there is a valid reference to the data somewhere else + * in the program. In all other cases it is preferable to use + * cxMapRemove() or cxMapRemoveAndGet(). + * + * @param map the map + * @param key the key + * @see cxMapRemove() + * @see cxMapRemoveAndGet() + */ +__attribute__((__nonnull__)) +static inline void cxMapDetach( + CxMap *map, + cxmutstr const &key +) { + (void) map->cl->remove(map, cx_hash_key_cxstr(key), false); +} + +/** + * Detaches a key/value-pair from the map by using the key + * without invoking the destructor. + * + * In general, you should only use this function if the map does not own + * the data and there is a valid reference to the data somewhere else + * in the program. In all other cases it is preferable to use + * cxMapRemove() or cxMapRemoveAndGet(). + * + * @param map the map + * @param key the key + * @see cxMapRemove() + * @see cxMapRemoveAndGet() + */ +__attribute__((__nonnull__)) +static inline void cxMapDetach( + CxMap *map, + char const *key +) { + (void) map->cl->remove(map, cx_hash_key_str(key), false); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * This function can be used when the map is storing pointers, + * in order to retrieve the pointer from the map without invoking + * any destructor function. Sometimes you do not want the pointer + * to be returned - in that case (instead of suppressing the "unused + * result" warning) you can use cxMapDetach(). + * + * If this map is not storing pointers, this function behaves like + * cxMapRemove() and returns \c NULL. + * + * @param map the map + * @param key the key + * @return the stored pointer or \c NULL if either the key is not present + * in the map or the map is not storing pointers + * @see cxMapStorePointers() + * @see cxMapDetach() + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cxMapRemoveAndGet( + CxMap *map, + CxHashKey key +) { + return map->cl->remove(map, key, !map->store_pointer); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * This function can be used when the map is storing pointers, + * in order to retrieve the pointer from the map without invoking + * any destructor function. Sometimes you do not want the pointer + * to be returned - in that case (instead of suppressing the "unused + * result" warning) you can use cxMapDetach(). + * + * If this map is not storing pointers, this function behaves like + * cxMapRemove() and returns \c NULL. + * + * @param map the map + * @param key the key + * @return the stored pointer or \c NULL if either the key is not present + * in the map or the map is not storing pointers + * @see cxMapStorePointers() + * @see cxMapDetach() + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cxMapRemoveAndGet( + CxMap *map, + cxstring key +) { + return map->cl->remove(map, cx_hash_key_cxstr(key), !map->store_pointer); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * This function can be used when the map is storing pointers, + * in order to retrieve the pointer from the map without invoking + * any destructor function. Sometimes you do not want the pointer + * to be returned - in that case (instead of suppressing the "unused + * result" warning) you can use cxMapDetach(). + * + * If this map is not storing pointers, this function behaves like + * cxMapRemove() and returns \c NULL. + * + * @param map the map + * @param key the key + * @return the stored pointer or \c NULL if either the key is not present + * in the map or the map is not storing pointers + * @see cxMapStorePointers() + * @see cxMapDetach() + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cxMapRemoveAndGet( + CxMap *map, + cxmutstr key +) { + return map->cl->remove(map, cx_hash_key_cxstr(key), !map->store_pointer); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * This function can be used when the map is storing pointers, + * in order to retrieve the pointer from the map without invoking + * any destructor function. Sometimes you do not want the pointer + * to be returned - in that case (instead of suppressing the "unused + * result" warning) you can use cxMapDetach(). + * + * If this map is not storing pointers, this function behaves like + * cxMapRemove() and returns \c NULL. + * + * @param map the map + * @param key the key + * @return the stored pointer or \c NULL if either the key is not present + * in the map or the map is not storing pointers + * @see cxMapStorePointers() + * @see cxMapDetach() + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cxMapRemoveAndGet( + CxMap *map, + char const *key +) { + return map->cl->remove(map, cx_hash_key_str(key), !map->store_pointer); +} + +#else // __cplusplus + +/** + * Puts a key/value-pair into the map. + * + * @param map the map + * @param key the key + * @param value the value + * @return 0 on success, non-zero value on failure + */ +__attribute__((__nonnull__)) +static inline int cx_map_put( + CxMap *map, + CxHashKey key, + void *value +) { + return map->cl->put(map, key, value); +} + +/** + * Puts a key/value-pair into the map. + * + * @param map the map + * @param key the key + * @param value the value + * @return 0 on success, non-zero value on failure + */ +__attribute__((__nonnull__)) +static inline int cx_map_put_cxstr( + CxMap *map, + cxstring key, + void *value +) { + return map->cl->put(map, cx_hash_key_cxstr(key), value); +} + +/** + * Puts a key/value-pair into the map. + * + * @param map the map + * @param key the key + * @param value the value + * @return 0 on success, non-zero value on failure + */ +__attribute__((__nonnull__)) +static inline int cx_map_put_mustr( + CxMap *map, + cxmutstr key, + void *value +) { + return map->cl->put(map, cx_hash_key_cxstr(key), value); +} + +/** + * Puts a key/value-pair into the map. + * + * @param map the map + * @param key the key + * @param value the value + * @return 0 on success, non-zero value on failure + */ +__attribute__((__nonnull__)) +static inline int cx_map_put_str( + CxMap *map, + char const *key, + void *value +) { + return map->cl->put(map, cx_hash_key_str(key), value); +} + +/** + * Puts a key/value-pair into the map. + * + * @param map the map + * @param key the key + * @param value the value + * @return 0 on success, non-zero value on failure + */ +#define cxMapPut(map, key, value) _Generic((key), \ + CxHashKey: cx_map_put, \ + cxstring: cx_map_put_cxstr, \ + cxmutstr: cx_map_put_mustr, \ + char*: cx_map_put_str, \ + char const*: cx_map_put_str) \ + (map, key, value) + +/** + * Retrieves a value by using a key. + * + * @param map the map + * @param key the key + * @return the value + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cx_map_get( + CxMap const *map, + CxHashKey key +) { + return map->cl->get(map, key); +} + +/** + * Retrieves a value by using a key. + * + * @param map the map + * @param key the key + * @return the value + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cx_map_get_cxstr( + CxMap const *map, + cxstring key +) { + return map->cl->get(map, cx_hash_key_cxstr(key)); +} + +/** + * Retrieves a value by using a key. + * + * @param map the map + * @param key the key + * @return the value + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cx_map_get_mustr( + CxMap const *map, + cxmutstr key +) { + return map->cl->get(map, cx_hash_key_cxstr(key)); +} + +/** + * Retrieves a value by using a key. + * + * @param map the map + * @param key the key + * @return the value + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cx_map_get_str( + CxMap const *map, + char const *key +) { + return map->cl->get(map, cx_hash_key_str(key)); +} + +/** + * Retrieves a value by using a key. + * + * @param map the map + * @param key the key + * @return the value + */ +#define cxMapGet(map, key) _Generic((key), \ + CxHashKey: cx_map_get, \ + cxstring: cx_map_get_cxstr, \ + cxmutstr: cx_map_get_mustr, \ + char*: cx_map_get_str, \ + char const*: cx_map_get_str) \ + (map, key) + +/** + * Removes a key/value-pair from the map by using the key. + * + * @param map the map + * @param key the key + */ +__attribute__((__nonnull__)) +static inline void cx_map_remove( + CxMap *map, + CxHashKey key +) { + (void) map->cl->remove(map, key, true); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * @param map the map + * @param key the key + */ +__attribute__((__nonnull__)) +static inline void cx_map_remove_cxstr( + CxMap *map, + cxstring key +) { + (void) map->cl->remove(map, cx_hash_key_cxstr(key), true); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * @param map the map + * @param key the key + */ +__attribute__((__nonnull__)) +static inline void cx_map_remove_mustr( + CxMap *map, + cxmutstr key +) { + (void) map->cl->remove(map, cx_hash_key_cxstr(key), true); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * @param map the map + * @param key the key + */ +__attribute__((__nonnull__)) +static inline void cx_map_remove_str( + CxMap *map, + char const *key +) { + (void) map->cl->remove(map, cx_hash_key_str(key), true); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * Always invokes the destructor function, if any, on the removed element. + * If this map is storing pointers and you just want to retrieve the pointer + * without invoking the destructor, use cxMapRemoveAndGet(). + * If you just want to detach the element from the map without invoking the + * destructor or returning the element, use cxMapDetach(). + * + * @param map the map + * @param key the key + * @see cxMapRemoveAndGet() + * @see cxMapDetach() + */ +#define cxMapRemove(map, key) _Generic((key), \ + CxHashKey: cx_map_remove, \ + cxstring: cx_map_remove_cxstr, \ + cxmutstr: cx_map_remove_mustr, \ + char*: cx_map_remove_str, \ + char const*: cx_map_remove_str) \ + (map, key) + +/** + * Detaches a key/value-pair from the map by using the key + * without invoking the destructor. + * + * @param map the map + * @param key the key + */ +__attribute__((__nonnull__)) +static inline void cx_map_detach( + CxMap *map, + CxHashKey key +) { + (void) map->cl->remove(map, key, false); +} + +/** + * Detaches a key/value-pair from the map by using the key + * without invoking the destructor. + * + * @param map the map + * @param key the key + */ +__attribute__((__nonnull__)) +static inline void cx_map_detach_cxstr( + CxMap *map, + cxstring key +) { + (void) map->cl->remove(map, cx_hash_key_cxstr(key), false); +} + +/** + * Detaches a key/value-pair from the map by using the key + * without invoking the destructor. + * + * @param map the map + * @param key the key + */ +__attribute__((__nonnull__)) +static inline void cx_map_detach_mustr( + CxMap *map, + cxmutstr key +) { + (void) map->cl->remove(map, cx_hash_key_cxstr(key), false); +} + +/** + * Detaches a key/value-pair from the map by using the key + * without invoking the destructor. + * + * @param map the map + * @param key the key + */ +__attribute__((__nonnull__)) +static inline void cx_map_detach_str( + CxMap *map, + char const *key +) { + (void) map->cl->remove(map, cx_hash_key_str(key), false); +} + +/** + * Detaches a key/value-pair from the map by using the key + * without invoking the destructor. + * + * In general, you should only use this function if the map does not own + * the data and there is a valid reference to the data somewhere else + * in the program. In all other cases it is preferable to use + * cxMapRemove() or cxMapRemoveAndGet(). + * + * @param map the map + * @param key the key + * @see cxMapRemove() + * @see cxMapRemoveAndGet() + */ +#define cxMapDetach(map, key) _Generic((key), \ + CxHashKey: cx_map_detach, \ + cxstring: cx_map_detach_cxstr, \ + cxmutstr: cx_map_detach_mustr, \ + char*: cx_map_detach_str, \ + char const*: cx_map_detach_str) \ + (map, key) + +/** + * Removes a key/value-pair from the map by using the key. + * + * @param map the map + * @param key the key + * @return the stored pointer or \c NULL if either the key is not present + * in the map or the map is not storing pointers + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cx_map_remove_and_get( + CxMap *map, + CxHashKey key +) { + return map->cl->remove(map, key, !map->store_pointer); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * @param map the map + * @param key the key + * @return the stored pointer or \c NULL if either the key is not present + * in the map or the map is not storing pointers + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cx_map_remove_and_get_cxstr( + CxMap *map, + cxstring key +) { + return map->cl->remove(map, cx_hash_key_cxstr(key), !map->store_pointer); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * @param map the map + * @param key the key + * @return the stored pointer or \c NULL if either the key is not present + * in the map or the map is not storing pointers + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cx_map_remove_and_get_mustr( + CxMap *map, + cxmutstr key +) { + return map->cl->remove(map, cx_hash_key_cxstr(key), !map->store_pointer); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * @param map the map + * @param key the key + * @return the stored pointer or \c NULL if either the key is not present + * in the map or the map is not storing pointers + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline void *cx_map_remove_and_get_str( + CxMap *map, + char const *key +) { + return map->cl->remove(map, cx_hash_key_str(key), !map->store_pointer); +} + +/** + * Removes a key/value-pair from the map by using the key. + * + * This function can be used when the map is storing pointers, + * in order to retrieve the pointer from the map without invoking + * any destructor function. Sometimes you do not want the pointer + * to be returned - in that case (instead of suppressing the "unused + * result" warning) you can use cxMapDetach(). + * + * If this map is not storing pointers, this function behaves like + * cxMapRemove() and returns \c NULL. + * + * @param map the map + * @param key the key + * @return the stored pointer or \c NULL if either the key is not present + * in the map or the map is not storing pointers + * @see cxMapStorePointers() + * @see cxMapDetach() + */ +#define cxMapRemoveAndGet(map, key) _Generic((key), \ + CxHashKey: cx_map_remove_and_get, \ + cxstring: cx_map_remove_and_get_cxstr, \ + cxmutstr: cx_map_remove_and_get_mustr, \ + char*: cx_map_remove_and_get_str, \ + char const*: cx_map_remove_and_get_str) \ + (map, key) + +#endif // __cplusplus + +#endif // UCX_MAP_H diff --git a/ucx/cx/mempool.h b/ucx/cx/mempool.h index a5b20c4..69c5bbf 100644 --- a/ucx/cx/mempool.h +++ b/ucx/cx/mempool.h @@ -37,30 +37,38 @@ #ifndef UCX_MEMPOOL_H #define UCX_MEMPOOL_H +#include "common.h" #include "allocator.h" #ifdef __cplusplus extern "C" { #endif -/** - * Memory pool class type. - */ -typedef struct cx_mempool_class_s cx_mempool_class; +/** Internal structure for pooled memory. */ +struct cx_mempool_memory_s; /** * The basic structure of a memory pool. * Should be the first member of an actual memory pool implementation. */ struct cx_mempool_s { + /** The provided allocator. */ + CxAllocator const *allocator; + /** - * The pool class definition. - */ - cx_mempool_class *cl; - /** - * The provided allocator. + * A destructor that shall be automatically registered for newly allocated memory. + * This destructor MUST NOT free the memory. */ - CxAllocator const *allocator; + cx_destructor_func auto_destr; + + /** Array of pooled memory. */ + struct cx_mempool_memory_s **data; + + /** Number of pooled memory items. */ + size_t size; + + /** Memory pool capacity. */ + size_t capacity; }; /** @@ -69,50 +77,70 @@ struct cx_mempool_s { typedef struct cx_mempool_s CxMempool; /** - * The class definition for a memory pool. + * Creates an array-based memory pool with a shared destructor function. + * + * This destructor MUST NOT free the memory. + * + * @param capacity the initial capacity of the pool + * @param destr the destructor function to use for allocated memory + * @return the created memory pool or \c NULL if allocation failed */ -struct cx_mempool_class_s { - /** Member function for destroying the pool. */ - __attribute__((__nonnull__)) - void (*destroy)(CxMempool *pool); - - /** Member function for setting a destructor. */ - __attribute__((__nonnull__)) - void (*set_destructor)( - CxMempool *pool, - void *memory, - cx_destructor_func fnc - ); -}; +__attribute__((__warn_unused_result__)) +CxMempool *cxMempoolCreate(size_t capacity, cx_destructor_func destr); +/** + * Creates a basic array-based memory pool. + * + * @param capacity the initial capacity of the pool + * @return the created memory pool or \c NULL if allocation failed + */ +__attribute__((__warn_unused_result__)) +static inline CxMempool *cxBasicMempoolCreate(size_t capacity) { + return cxMempoolCreate(capacity, NULL); +} /** - * Destroys a memory pool including their contents. + * Destroys a memory pool and frees the managed memory. * * @param pool the memory pool to destroy */ __attribute__((__nonnull__)) -static inline void cxMempoolDestroy(CxMempool *pool) { - pool->cl->destroy(pool); -} +void cxMempoolDestroy(CxMempool *pool); /** - * Sets a destructor function for an allocated memory object. + * Sets the destructor function for a specific allocated memory object. * - * If the memory is not managed by the pool, the behavior is undefined. + * If the memory is not managed by a UCX memory pool, the behavior is undefined. + * The destructor MUST NOT free the memory. * - * @param pool the pool - * @param memory the objected allocated in the pool + * @param memory the object allocated in the pool * @param fnc the destructor function */ __attribute__((__nonnull__)) -static inline void cxMempoolSetDestructor( - CxMempool *pool, +void cxMempoolSetDestructor( void *memory, cx_destructor_func fnc -) { - pool->cl->set_destructor(pool, memory, fnc); -} +); + +/** + * Registers foreign memory with this pool. + * + * The destructor, in contrast to memory allocated by the pool, MUST free the memory. + * + * A small portion of memory will be allocated to register the information in the pool. + * If that allocation fails, this function will return non-zero. + * + * @param pool the pool + * @param memory the object allocated in the pool + * @param destr the destructor function + * @return zero on success, non-zero on failure + */ +__attribute__((__nonnull__)) +int cxMempoolRegister( + CxMempool *pool, + void *memory, + cx_destructor_func destr +); #ifdef __cplusplus } // extern "C" diff --git a/ucx/cx/printf.h b/ucx/cx/printf.h index f4fc8ce..c2dc42f 100644 --- a/ucx/cx/printf.h +++ b/ucx/cx/printf.h @@ -96,7 +96,7 @@ int cx_vfprintf( */ __attribute__((__nonnull__(1, 2), __format__(printf, 2, 3))) cxmutstr cx_asprintf_a( - CxAllocator *allocator, + CxAllocator const *allocator, char const *fmt, ... ); @@ -129,7 +129,7 @@ cxmutstr cx_asprintf_a( */ __attribute__((__nonnull__)) cxmutstr cx_vasprintf_a( - CxAllocator *allocator, + CxAllocator const *allocator, char const *fmt, va_list ap ); diff --git a/ucx/cx/string.h b/ucx/cx/string.h index c2ccf7f..58eaec3 100644 --- a/ucx/cx/string.h +++ b/ucx/cx/string.h @@ -129,6 +129,18 @@ struct cx_strtok_ctx_s { */ typedef struct cx_strtok_ctx_s CxStrtokCtx; +#ifdef __cplusplus +extern "C" { + +/** + * A literal initializer for an UCX string structure. + * + * @param literal the string literal + */ +#define CX_STR(literal) cxstring{literal, sizeof(literal) - 1} + +#else // __cplusplus + /** * A literal initializer for an UCX string structure. * @@ -136,10 +148,8 @@ typedef struct cx_strtok_ctx_s CxStrtokCtx; * * @param literal the string literal */ -#define CX_STR(literal) {literal, sizeof(literal) - 1} +#define CX_STR(literal) (cxstring){literal, sizeof(literal) - 1} -#ifdef __cplusplus -extern "C" { #endif @@ -265,7 +275,7 @@ void cx_strfree(cxmutstr *str); */ __attribute__((__nonnull__)) void cx_strfree_a( - CxAllocator *alloc, + CxAllocator const *alloc, cxmutstr *str ); @@ -286,28 +296,50 @@ size_t cx_strlen( ); /** - * Concatenates two or more strings. + * Concatenates strings. * * The resulting string will be allocated by the specified allocator. - * So developers \em must pass the return value to cx_strfree() eventually. - * - * \note It is guaranteed that there is only one allocation. - * It is also guaranteed that the returned string is zero-terminated. + * So developers \em must pass the return value to cx_strfree_a() eventually. + * + * If \p str already contains a string, the memory will be reallocated and + * the other strings are appended. Otherwise, new memory is allocated. + * + * \note It is guaranteed that there is only one allocation. + * It is also guaranteed that the returned string is zero-terminated. * * @param alloc the allocator to use - * @param count the total number of strings to concatenate - * @param ... all strings + * @param str the string the other strings shall be concatenated to + * @param count the number of the other following strings to concatenate + * @param ... all other strings * @return the concatenated string */ __attribute__((__warn_unused_result__, __nonnull__)) -cxmutstr cx_strcat_a( - CxAllocator *alloc, +cxmutstr cx_strcat_ma( + CxAllocator const *alloc, + cxmutstr str, size_t count, ... ); /** - * Concatenates two or more strings. + * Concatenates strings and returns a new string. + * + * The resulting string will be allocated by the specified allocator. + * So developers \em must pass the return value to cx_strfree_a() eventually. + * + * \note It is guaranteed that there is only one allocation. + * It is also guaranteed that the returned string is zero-terminated. + * + * @param alloc the allocator to use + * @param count the number of the other following strings to concatenate + * @param ... all other strings + * @return the concatenated string + */ +#define cx_strcat_a(alloc, count, ...) \ +cx_strcat_ma(alloc, cx_mutstrn(NULL, 0), count, __VA_ARGS__) + +/** + * Concatenates strings and returns a new string. * * The resulting string will be allocated by standard \c malloc(). * So developers \em must pass the return value to cx_strfree() eventually. @@ -315,12 +347,32 @@ cxmutstr cx_strcat_a( * \note It is guaranteed that there is only one allocation. * It is also guaranteed that the returned string is zero-terminated. * - * @param count the total number of strings to concatenate - * @param ... all strings + * @param count the number of the other following strings to concatenate + * @param ... all other strings * @return the concatenated string */ #define cx_strcat(count, ...) \ -cx_strcat_a(cxDefaultAllocator, count, __VA_ARGS__) +cx_strcat_ma(cxDefaultAllocator, cx_mutstrn(NULL, 0), count, __VA_ARGS__) + +/** + * Concatenates strings. + * + * The resulting string will be allocated by standard \c malloc(). + * So developers \em must pass the return value to cx_strfree() eventually. + * + * If \p str already contains a string, the memory will be reallocated and + * the other strings are appended. Otherwise, new memory is allocated. + * + * \note It is guaranteed that there is only one allocation. + * It is also guaranteed that the returned string is zero-terminated. + * + * @param str the string the other strings shall be concatenated to + * @param count the number of the other following strings to concatenate + * @param ... all other strings + * @return the concatenated string + */ +#define cx_strcat_m(str, count, ...) \ +cx_strcat_ma(cxDefaultAllocator, str, count, __VA_ARGS__) /** * Returns a substring starting at the specified location. @@ -573,7 +625,7 @@ size_t cx_strsplit( */ __attribute__((__warn_unused_result__, __nonnull__)) size_t cx_strsplit_a( - CxAllocator *allocator, + CxAllocator const *allocator, cxstring string, cxstring delim, size_t limit, @@ -622,7 +674,7 @@ size_t cx_strsplit_m( */ __attribute__((__warn_unused_result__, __nonnull__)) size_t cx_strsplit_ma( - CxAllocator *allocator, + CxAllocator const *allocator, cxmutstr string, cxstring delim, size_t limit, @@ -660,7 +712,7 @@ int cx_strcasecmp( /** * Compares two strings. * - * This function has a compatible signature for the use as a CxListComparator. + * This function has a compatible signature for the use as a cx_compare_func. * * @param s1 the first string * @param s2 the second string @@ -676,7 +728,7 @@ int cx_strcmp_p( /** * Compares two strings ignoring case. * - * This function has a compatible signature for the use as a CxListComparator. + * This function has a compatible signature for the use as a cx_compare_func. * * @param s1 the first string * @param s2 the second string @@ -704,7 +756,7 @@ int cx_strcasecmp_p( */ __attribute__((__warn_unused_result__, __nonnull__)) cxmutstr cx_strdup_a( - CxAllocator *allocator, + CxAllocator const *allocator, cxstring string ); @@ -722,6 +774,35 @@ cxmutstr cx_strdup_a( */ #define cx_strdup(string) cx_strdup_a(cxDefaultAllocator, string) + +/** + * Creates a duplicate of the specified string. + * + * The new string will contain a copy allocated by \p allocator. + * + * \note The returned string is guaranteed to be zero-terminated. + * + * @param allocator the allocator to use + * @param string the string to duplicate + * @return a duplicate of the string + * @see cx_strdup_m() + */ +#define cx_strdup_ma(allocator, string) cx_strdup_a(allocator, cx_strcast(string)) + +/** + * Creates a duplicate of the specified string. + * + * The new string will contain a copy allocated by standard + * \c malloc(). So developers \em must pass the return value to cx_strfree(). + * + * \note The returned string is guaranteed to be zero-terminated. + * + * @param string the string to duplicate + * @return a duplicate of the string + * @see cx_strdup_ma() + */ +#define cx_strdup_m(string) cx_strdup_a(cxDefaultAllocator, cx_strcast(string)) + /** * Omits leading and trailing spaces. * @@ -843,7 +924,7 @@ void cx_strupper(cxmutstr string); */ __attribute__((__warn_unused_result__, __nonnull__)) cxmutstr cx_strreplacen_a( - CxAllocator *allocator, + CxAllocator const *allocator, cxstring str, cxstring pattern, cxstring replacement, diff --git a/ucx/cx/utils.h b/ucx/cx/utils.h index bcdd9c7..2c35a92 100644 --- a/ucx/cx/utils.h +++ b/ucx/cx/utils.h @@ -183,7 +183,6 @@ size_t cx_stream_ncopy( * @param dest the destination stream * @param rfnc the read function * @param wfnc the write function - * @param n the maximum number of bytes that shall be copied. * @return total number of bytes copied */ #define cx_stream_copy(src, dest, rfnc, wfnc) \ diff --git a/ucx/hash_key.c b/ucx/hash_key.c index c1bd430..a219dca 100644 --- a/ucx/hash_key.c +++ b/ucx/hash_key.c @@ -30,7 +30,7 @@ #include void cx_hash_murmur(CxHashKey *key) { - unsigned char const *data = key->data.cbytes; + unsigned char const *data = key->data; if (data == NULL) { // extension: special value for NULL key->hash = 1574210520u; @@ -71,7 +71,7 @@ void cx_hash_murmur(CxHashKey *key) { h *= m; __attribute__((__fallthrough__)); default: // do nothing - ; + ; } h ^= h >> 13; @@ -83,7 +83,7 @@ void cx_hash_murmur(CxHashKey *key) { CxHashKey cx_hash_key_str(char const *str) { CxHashKey key; - key.data.cstr = str; + key.data = str; key.len = str == NULL ? 0 : strlen(str); cx_hash_murmur(&key); return key; @@ -94,7 +94,7 @@ CxHashKey cx_hash_key_bytes( size_t len ) { CxHashKey key; - key.data.cbytes = bytes; + key.data = bytes; key.len = len; cx_hash_murmur(&key); return key; @@ -105,7 +105,7 @@ CxHashKey cx_hash_key( size_t len ) { CxHashKey key; - key.data.cobj = obj; + key.data = obj; key.len = len; cx_hash_murmur(&key); return key; diff --git a/ucx/hash_map.c b/ucx/hash_map.c index 48e7d3e..8b8cd20 100644 --- a/ucx/hash_map.c +++ b/ucx/hash_map.c @@ -26,10 +26,12 @@ * POSSIBILITY OF SUCH DAMAGE. */ -#include #include "cx/hash_map.h" #include "cx/utils.h" +#include +#include + struct cx_hash_map_element_s { /** A pointer to the next element in the current bucket. */ struct cx_hash_map_element_s *next; @@ -48,8 +50,10 @@ static void cx_hash_map_clear(struct cx_map_s *map) { if (elem != NULL) { do { struct cx_hash_map_element_s *next = elem->next; + // invoke the destructor + cx_invoke_destructor(map, elem->data); // free the key data - cxFree(map->allocator, elem->key.data.obj); + cxFree(map->allocator, (void *) elem->key.data); // free the node cxFree(map->allocator, elem); // proceed @@ -80,7 +84,7 @@ static int cx_hash_map_put( void *value ) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; - CxAllocator *allocator = map->allocator; + CxAllocator const *allocator = map->allocator; unsigned hash = key.hash; if (hash == 0) { @@ -98,28 +102,28 @@ static int cx_hash_map_put( } if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len && - memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) { + memcmp(elm->key.data, key.data, key.len) == 0) { // overwrite existing element - if (map->store_pointers) { + if (map->store_pointer) { memcpy(elm->data, &value, sizeof(void *)); } else { - memcpy(elm->data, value, map->itemsize); + memcpy(elm->data, value, map->item_size); } } else { // allocate new element struct cx_hash_map_element_s *e = cxMalloc( allocator, - sizeof(struct cx_hash_map_element_s) + map->itemsize + sizeof(struct cx_hash_map_element_s) + map->item_size ); if (e == NULL) { return -1; } // write the value - if (map->store_pointers) { + if (map->store_pointer) { memcpy(e->data, &value, sizeof(void *)); } else { - memcpy(e->data, value, map->itemsize); + memcpy(e->data, value, map->item_size); } // copy the key @@ -127,8 +131,8 @@ static int cx_hash_map_put( if (kd == NULL) { return -1; } - memcpy(kd, key.data.obj, key.len); - e->key.data.obj = kd; + memcpy(kd, key.data, key.len); + e->key.data = kd; e->key.len = key.len; e->key.hash = hash; @@ -160,7 +164,7 @@ static void cx_hash_map_unlink( prev->next = elm->next; } // free element - cxFree(hash_map->base.allocator, elm->key.data.obj); + cxFree(hash_map->base.allocator, (void *) elm->key.data); cxFree(hash_map->base.allocator, elm); // decrease size hash_map->base.size--; @@ -172,12 +176,14 @@ static void cx_hash_map_unlink( * @param map the map * @param key the key to look up * @param remove flag indicating whether the looked up entry shall be removed + * @param destroy flag indicating whether the destructor shall be invoked * @return a pointer to the value corresponding to the key or \c NULL */ static void *cx_hash_map_get_remove( CxMap *map, CxHashKey key, - bool remove + bool remove, + bool destroy ) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; @@ -192,12 +198,16 @@ static void *cx_hash_map_get_remove( struct cx_hash_map_element_s *prev = NULL; while (elm && elm->key.hash <= hash) { if (elm->key.hash == hash && elm->key.len == key.len) { - if (memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) { + if (memcmp(elm->key.data, key.data, key.len) == 0) { void *data = NULL; - if (map->store_pointers) { - data = *(void **) elm->data; - } else if (!remove) { - data = elm->data; + if (destroy) { + cx_invoke_destructor(map, elm->data); + } else { + if (map->store_pointer) { + data = *(void **) elm->data; + } else { + data = elm->data; + } } if (remove) { cx_hash_map_unlink(hash_map, slot, prev, elm); @@ -216,15 +226,16 @@ static void *cx_hash_map_get( CxMap const *map, CxHashKey key ) { - // we can safely cast, because we know when remove=false, the map stays untouched - return cx_hash_map_get_remove((CxMap *) map, key, false); + // we can safely cast, because we know the map stays untouched + return cx_hash_map_get_remove((CxMap *) map, key, false, false); } static void *cx_hash_map_remove( CxMap *map, - CxHashKey key + CxHashKey key, + bool destroy ) { - return cx_hash_map_get_remove(map, key, true); + return cx_hash_map_get_remove(map, key, true, destroy); } static void *cx_hash_map_iter_current_entry(void const *it) { @@ -243,7 +254,7 @@ static void *cx_hash_map_iter_current_value(void const *it) { struct cx_iterator_s const *iter = it; struct cx_hash_map_s const *map = iter->src_handle; struct cx_hash_map_element_s *elm = iter->elem_handle; - if (map->base.store_pointers) { + if (map->base.store_pointer) { return *(void **) elm->data; } else { return elm->data; @@ -280,6 +291,9 @@ static void cx_hash_map_iter_next(void *it) { } } + // destroy + cx_invoke_destructor((struct cx_map_s *) map, elm->data); + // unlink cx_hash_map_unlink(map, iter->slot, prev, elm); @@ -304,7 +318,7 @@ static void cx_hash_map_iter_next(void *it) { iter->kv_data.value = NULL; } else { iter->kv_data.key = &elm->key; - if (map->base.store_pointers) { + if (map->base.store_pointer) { iter->kv_data.value = *(void **) elm->data; } else { iter->kv_data.value = elm->data; @@ -322,13 +336,30 @@ static bool cx_hash_map_iter_flag_rm(void *it) { } } -static CxIterator cx_hash_map_iterator(CxMap const *map) { +static CxIterator cx_hash_map_iterator( + CxMap const *map, + enum cx_map_iterator_type type +) { CxIterator iter; iter.src_handle = map; iter.base.valid = cx_hash_map_iter_valid; iter.base.next = cx_hash_map_iter_next; - iter.base.current = cx_hash_map_iter_current_entry; + + switch (type) { + case CX_MAP_ITERATOR_PAIRS: + iter.base.current = cx_hash_map_iter_current_entry; + break; + case CX_MAP_ITERATOR_KEYS: + iter.base.current = cx_hash_map_iter_current_key; + break; + case CX_MAP_ITERATOR_VALUES: + iter.base.current = cx_hash_map_iter_current_value; + break; + default: + assert(false); + } + iter.base.flag_removal = cx_hash_map_iter_flag_rm; iter.base.remove = false; iter.base.mutating = false; @@ -344,7 +375,7 @@ static CxIterator cx_hash_map_iterator(CxMap const *map) { } iter.elem_handle = elm; iter.kv_data.key = &elm->key; - if (map->store_pointers) { + if (map->store_pointer) { iter.kv_data.value = *(void **) elm->data; } else { iter.kv_data.value = elm->data; @@ -358,40 +389,6 @@ static CxIterator cx_hash_map_iterator(CxMap const *map) { return iter; } -static CxIterator cx_hash_map_iterator_keys(CxMap const *map) { - CxIterator iter = cx_hash_map_iterator(map); - iter.base.current = cx_hash_map_iter_current_key; - return iter; -} - -static CxIterator cx_hash_map_iterator_values(CxMap const *map) { - CxIterator iter = cx_hash_map_iterator(map); - iter.base.current = cx_hash_map_iter_current_value; - return iter; -} - -static CxMutIterator cx_hash_map_mut_iterator(CxMap *map) { - CxIterator it = cx_hash_map_iterator(map); - it.base.mutating = true; - - // we know the iterators share the same memory layout - CxMutIterator iter; - memcpy(&iter, &it, sizeof(CxMutIterator)); - return iter; -} - -static CxMutIterator cx_hash_map_mut_iterator_keys(CxMap *map) { - CxMutIterator iter = cx_hash_map_mut_iterator(map); - iter.base.current = cx_hash_map_iter_current_key; - return iter; -} - -static CxMutIterator cx_hash_map_mut_iterator_values(CxMap *map) { - CxMutIterator iter = cx_hash_map_mut_iterator(map); - iter.base.current = cx_hash_map_iter_current_value; - return iter; -} - static cx_map_class cx_hash_map_class = { cx_hash_map_destructor, cx_hash_map_clear, @@ -399,15 +396,10 @@ static cx_map_class cx_hash_map_class = { cx_hash_map_get, cx_hash_map_remove, cx_hash_map_iterator, - cx_hash_map_iterator_keys, - cx_hash_map_iterator_values, - cx_hash_map_mut_iterator, - cx_hash_map_mut_iterator_keys, - cx_hash_map_mut_iterator_values, }; CxMap *cxHashMapCreate( - CxAllocator *allocator, + CxAllocator const *allocator, size_t itemsize, size_t buckets ) { @@ -416,12 +408,14 @@ CxMap *cxHashMapCreate( buckets = 16; } - struct cx_hash_map_s *map = cxMalloc(allocator, sizeof(struct cx_hash_map_s)); + struct cx_hash_map_s *map = cxCalloc(allocator, 1, + sizeof(struct cx_hash_map_s)); if (map == NULL) return NULL; // initialize hash map members map->bucket_count = buckets; - map->buckets = cxCalloc(allocator, buckets, sizeof(struct cx_hash_map_element_s *)); + map->buckets = cxCalloc(allocator, buckets, + sizeof(struct cx_hash_map_element_s *)); if (map->buckets == NULL) { cxFree(allocator, map); return NULL; @@ -430,14 +424,13 @@ CxMap *cxHashMapCreate( // initialize base members map->base.cl = &cx_hash_map_class; map->base.allocator = allocator; - map->base.size = 0; if (itemsize > 0) { - map->base.store_pointers = false; - map->base.itemsize = itemsize; + map->base.store_pointer = false; + map->base.item_size = itemsize; } else { - map->base.store_pointers = true; - map->base.itemsize = sizeof(void *); + map->base.store_pointer = true; + map->base.item_size = sizeof(void *); } return (CxMap *) map; @@ -448,8 +441,10 @@ int cxMapRehash(CxMap *map) { if (map->size > ((hash_map->bucket_count * 3) >> 2)) { size_t new_bucket_count = (map->size * 5) >> 1; - struct cx_hash_map_element_s **new_buckets = cxCalloc(map->allocator, - new_bucket_count, sizeof(struct cx_hash_map_element_s *)); + struct cx_hash_map_element_s **new_buckets = cxCalloc( + map->allocator, + new_bucket_count, sizeof(struct cx_hash_map_element_s *) + ); if (new_buckets == NULL) { return 1; @@ -465,7 +460,8 @@ int cxMapRehash(CxMap *map) { // find position where to insert struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot]; struct cx_hash_map_element_s *bucket_prev = NULL; - while (bucket_next != NULL && bucket_next->key.hash < elm->key.hash) { + while (bucket_next != NULL && + bucket_next->key.hash < elm->key.hash) { bucket_prev = bucket_next; bucket_next = bucket_next->next; } diff --git a/ucx/linked_list.c b/ucx/linked_list.c index c74da5f..7a8d33d 100644 --- a/ucx/linked_list.c +++ b/ucx/linked_list.c @@ -56,11 +56,11 @@ void *cx_linked_list_at( return (void *) cur; } -size_t cx_linked_list_find( +ssize_t cx_linked_list_find( void const *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, - CxListComparator cmp_func, + cx_compare_func cmp_func, void const *elem ) { assert(start != NULL); @@ -69,7 +69,7 @@ size_t cx_linked_list_find( assert(cmp_func); void const *node = start; - size_t index = 0; + ssize_t index = 0; do { void *current = ll_data(node); if (cmp_func(current, elem) == 0) { @@ -78,7 +78,7 @@ size_t cx_linked_list_find( node = ll_advance(node); index++; } while (node != NULL); - return index; + return -1; } void *cx_linked_list_first( @@ -283,7 +283,7 @@ size_t cx_linked_list_size( #define CX_LINKED_LIST_SORT_SBO_SIZE 1024 #endif -static void *cx_linked_list_sort_merge( +static void cx_linked_list_sort_merge( ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, @@ -291,7 +291,9 @@ static void *cx_linked_list_sort_merge( void *ls, void *le, void *re, - CxListComparator cmp_func + cx_compare_func cmp_func, + void **begin, + void **end ) { void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? @@ -330,11 +332,11 @@ static void *cx_linked_list_sort_merge( } ll_next(sorted[length - 1]) = NULL; - void *ret = sorted[0]; + *begin = sorted[0]; + *end = sorted[length-1]; if (sorted != sbo) { free(sorted); } - return ret; } void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function @@ -343,7 +345,7 @@ void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive fun ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, - CxListComparator cmp_func + cx_compare_func cmp_func ) { assert(begin != NULL); assert(loc_next >= 0); @@ -355,6 +357,9 @@ void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive fun // set start node ls = *begin; + // early exit when this list is empty + if (ls == NULL) return; + // check how many elements are already sorted lc = ls; size_t ln = 1; @@ -377,8 +382,10 @@ void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive fun re = ll_next(rc); // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them - void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, - ln + rn, ls, le, re, cmp_func); + void *sorted_begin, *sorted_end; + cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, + ln + rn, ls, le, re, cmp_func, + &sorted_begin, &sorted_end); // Something left? Sort it! size_t remainder_length = cx_linked_list_size(re, loc_next); @@ -387,14 +394,13 @@ void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive fun cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func); // merge sorted list with (also sorted) remainder - *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, - ln + rn + remainder_length, - sorted, remainder, NULL, cmp_func); - } else { - // no remainder - we've got our sorted list - *begin = sorted; + cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, + ln + rn + remainder_length, + sorted_begin, remainder, NULL, cmp_func, + &sorted_begin, &sorted_end); } - if (end) *end = cx_linked_list_last(sorted, loc_next); + *begin = sorted_begin; + if (end) *end = sorted_end; } } @@ -403,7 +409,7 @@ int cx_linked_list_compare( void const *begin_right, ptrdiff_t loc_advance, ptrdiff_t loc_data, - CxListComparator cmp_func + cx_compare_func cmp_func ) { void const *left = begin_left, *right = begin_right; @@ -494,14 +500,14 @@ static int cx_ll_insert_at( // create the new new_node cx_linked_list_node *new_node = cxMalloc(list->allocator, - sizeof(cx_linked_list_node) + list->itemsize); + sizeof(cx_linked_list_node) + list->item_size); // sortir if failed if (new_node == NULL) return 1; // initialize new new_node new_node->prev = new_node->next = NULL; - memcpy(new_node->payload, elem, list->itemsize); + memcpy(new_node->payload, elem, list->item_size); // insert cx_linked_list *ll = (cx_linked_list *) list; @@ -542,7 +548,7 @@ static size_t cx_ll_insert_array( // we can add the remaining nodes and immedately advance to the inserted node char const *source = array; for (size_t i = 1; i < n; i++) { - source += list->itemsize; + source += list->item_size; if (0 != cx_ll_insert_at(list, node, source)) { return i; } @@ -570,9 +576,7 @@ static int cx_ll_remove( if (node == NULL) return 1; // element destruction - if (list->content_destructor_type != CX_DESTRUCTOR_NONE) { - cx_list_invoke_destructor(list, node->payload); - } + cx_invoke_destructor(list, node->payload); // remove cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, @@ -592,44 +596,18 @@ static void cx_ll_clear(struct cx_list_s *list) { cx_linked_list *ll = (cx_linked_list *) list; cx_linked_list_node *node = ll->begin; - - // looks super redundant, but avoids repeatedly checking - // the destructor type for each element - switch (list->content_destructor_type) { - case CX_DESTRUCTOR_SIMPLE: { - while (node != NULL) { - cx_list_invoke_simple_destructor(list, node->payload); - cx_linked_list_node *next = node->next; - cxFree(list->allocator, node); - node = next; - } - break; - } - case CX_DESTRUCTOR_ADVANCED: { - while (node != NULL) { - cx_list_invoke_advanced_destructor(list, node->payload); - cx_linked_list_node *next = node->next; - cxFree(list->allocator, node); - node = next; - } - break; - } - case CX_DESTRUCTOR_NONE: { - while (node != NULL) { - cx_linked_list_node *next = node->next; - cxFree(list->allocator, node); - node = next; - } - break; - } + while (node != NULL) { + cx_invoke_destructor(list, node->payload); + cx_linked_list_node *next = node->next; + cxFree(list->allocator, node); + node = next; } - ll->begin = ll->end = NULL; list->size = 0; } #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE -#define CX_LINKED_LIST_SWAP_SBO_SIZE 16 +#define CX_LINKED_LIST_SWAP_SBO_SIZE 128 #endif static int cx_ll_swap( @@ -708,7 +686,7 @@ static int cx_ll_swap( } } - if (list->itemsize > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) { + if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) { cx_linked_list_node *prev = nleft->prev; cx_linked_list_node *next = nright->next; cx_linked_list_node *midstart = nleft->next; @@ -740,9 +718,9 @@ static int cx_ll_swap( } else { // swap payloads to avoid relinking char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; - memcpy(buf, nleft->payload, list->itemsize); - memcpy(nleft->payload, nright->payload, list->itemsize); - memcpy(nright->payload, buf, list->itemsize); + memcpy(buf, nleft->payload, list->item_size); + memcpy(nleft->payload, nright->payload, list->item_size); + memcpy(nright->payload, buf, list->item_size); } return 0; @@ -757,7 +735,7 @@ static void *cx_ll_at( return node == NULL ? NULL : node->payload; } -static size_t cx_ll_find( +static ssize_t cx_ll_find( struct cx_list_s const *list, void const *elem ) { @@ -803,9 +781,7 @@ static void cx_ll_iter_next(void *it) { cx_linked_list *ll = iter->src_handle; cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->next; - if (list->content_destructor_type != CX_DESTRUCTOR_NONE) { - cx_list_invoke_destructor(list, node->payload); - } + cx_invoke_destructor(list, node->payload); cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); list->size--; @@ -828,9 +804,7 @@ static void cx_ll_iter_prev(void *it) { cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->prev; iter->index--; - if (list->content_destructor_type != CX_DESTRUCTOR_NONE) { - cx_list_invoke_destructor(list, node->payload); - } + cx_invoke_destructor(list, node->payload); cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); list->size--; @@ -902,11 +876,13 @@ static void cx_ll_destructor(CxList *list) { cx_linked_list_node *node = ll->begin; while (node) { + cx_invoke_destructor(list, node->payload); void *next = node->next; cxFree(list->allocator, node); node = next; } - // do not free the list pointer, this is just a destructor! + + cxFree(list->allocator, list); } static cx_list_class cx_linked_list_class = { @@ -927,7 +903,7 @@ static cx_list_class cx_linked_list_class = { CxList *cxLinkedListCreate( CxAllocator const *allocator, - CxListComparator comparator, + cx_compare_func comparator, size_t item_size ) { if (allocator == NULL) { @@ -940,10 +916,9 @@ CxList *cxLinkedListCreate( list->base.cl = &cx_linked_list_class; list->base.allocator = allocator; list->base.cmpfunc = comparator; - list->base.capacity = SIZE_MAX; if (item_size > 0) { - list->base.itemsize = item_size; + list->base.item_size = item_size; } else { cxListStorePointers((CxList *) list); } diff --git a/ucx/list.c b/ucx/list.c index ebfff65..cc96710 100644 --- a/ucx/list.c +++ b/ucx/list.c @@ -32,7 +32,7 @@ // -static _Thread_local CxListComparator cx_pl_cmpfunc_impl; +static _Thread_local cx_compare_func cx_pl_cmpfunc_impl; static int cx_pl_cmpfunc( void const *l, @@ -115,12 +115,12 @@ static void *cx_pl_at( return ptr == NULL ? NULL : *ptr; } -static size_t cx_pl_find( +static ssize_t cx_pl_find( struct cx_list_s const *list, void const *elem ) { cx_pl_hack_cmpfunc(list); - size_t ret = list->climpl->find(list, &elem); + ssize_t ret = list->climpl->find(list, &elem); cx_pl_unhack_cmpfunc(list); return ret; } @@ -179,6 +179,7 @@ static cx_list_class cx_pointer_list_class = { }; void cxListStoreObjects(CxList *list) { + list->store_pointer = false; if (list->climpl != NULL) { list->cl = list->climpl; list->climpl = NULL; @@ -186,90 +187,111 @@ void cxListStoreObjects(CxList *list) { } void cxListStorePointers(CxList *list) { - list->itemsize = sizeof(void *); + list->item_size = sizeof(void *); + list->store_pointer = true; list->climpl = list->cl; list->cl = &cx_pointer_list_class; } -bool cxListIsStoringPointers(CxList const *list) { - return list->climpl != NULL; +// + +// + +static void cx_emptyl_noop(__attribute__((__unused__)) CxList *list) { + // this is a noop, but MUST be implemented } -// +static void *cx_emptyl_at( + __attribute__((__unused__)) struct cx_list_s const *list, + __attribute__((__unused__)) size_t index +) { + return NULL; +} -void cx_list_invoke_destructor( - CxList const *list, - void *elem +static ssize_t cx_emptyl_find( + __attribute__((__unused__)) struct cx_list_s const *list, + __attribute__((__unused__)) void const *elem ) { - switch (list->content_destructor_type) { - case CX_DESTRUCTOR_SIMPLE: { - cx_list_invoke_simple_destructor(list, elem); - break; - } - case CX_DESTRUCTOR_ADVANCED: { - cx_list_invoke_advanced_destructor(list, elem); - break; - } - case CX_DESTRUCTOR_NONE: - break; // nothing - } + return -1; } -void cx_list_invoke_simple_destructor( - CxList const *list, - void *elem +static int cx_emptyl_compare( + __attribute__((__unused__)) struct cx_list_s const *list, + struct cx_list_s const *other ) { - if (cxListIsStoringPointers(list)) { - elem = *((void **) elem); - } - list->simple_destructor(elem); + if (other->size == 0) return 0; + return -1; } -void cx_list_invoke_advanced_destructor( - CxList const *list, - void *elem +static bool cx_emptyl_iter_valid(__attribute__((__unused__)) void const *iter) { + return false; +} + +static CxIterator cx_emptyl_iterator( + struct cx_list_s const *list, + size_t index, + __attribute__((__unused__)) bool backwards ) { - if (cxListIsStoringPointers(list)) { - elem = *((void **) elem); - } - list->advanced_destructor.func(list->advanced_destructor.data, elem); + CxIterator iter = {0}; + iter.src_handle = list; + iter.index = index; + iter.base.valid = cx_emptyl_iter_valid; + return iter; } -void cxListDestroy(CxList *list) { - switch (list->content_destructor_type) { - case CX_DESTRUCTOR_SIMPLE: { - CxIterator iter = cxListIterator(list); - cx_foreach(void*, elem, iter) { - // already correctly resolved pointer - immediately invoke dtor - list->simple_destructor(elem); - } - break; - } - case CX_DESTRUCTOR_ADVANCED: { - CxIterator iter = cxListIterator(list); - cx_foreach(void*, elem, iter) { - // already correctly resolved pointer - immediately invoke dtor - list->advanced_destructor.func(list->advanced_destructor.data, elem); - } - break; - } - case CX_DESTRUCTOR_NONE: - break; // nothing - } +static cx_list_class cx_empty_list_class = { + cx_emptyl_noop, + NULL, + NULL, + NULL, + NULL, + cx_emptyl_noop, + NULL, + cx_emptyl_at, + cx_emptyl_find, + cx_emptyl_noop, + cx_emptyl_compare, + cx_emptyl_noop, + cx_emptyl_iterator, +}; + +CxList cx_empty_list = { + NULL, + NULL, + 0, + 0, + NULL, + NULL, + NULL, + false, + &cx_empty_list_class, + NULL +}; + +CxList *const cxEmptyList = &cx_empty_list; +// + +void cxListDestroy(CxList *list) { list->cl->destructor(list); - cxFree(list->allocator, list); } int cxListCompare( CxList const *list, CxList const *other ) { - if (list->cl->compare == other->cl->compare) { - // same compare function, lists are compatible - return list->cl->compare(list, other); - } else { - // different compare functions, use iterator + if ( + // if one is storing pointers but the other is not + (list->store_pointer ^ other->store_pointer) || + + // if one class is wrapped but the other is not + ((list->climpl == NULL) ^ (other->climpl == NULL)) || + + // if the resolved compare functions are not the same + ((list->climpl != NULL ? list->climpl->compare : list->cl->compare) != + (other->climpl != NULL ? other->climpl->compare : other->cl->compare)) + ) { + // lists are definitely different - cannot use internal compare function if (list->size == other->size) { CxIterator left = cxListIterator(list); CxIterator right = cxListIterator(other); @@ -287,6 +309,9 @@ int cxListCompare( } else { return list->size < other->size ? -1 : 1; } + } else { + // lists are compatible + return list->cl->compare(list, other); } } diff --git a/ucx/map.c b/ucx/map.c new file mode 100644 index 0000000..b9dc2ef --- /dev/null +++ b/ucx/map.c @@ -0,0 +1,112 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "cx/map.h" +#include + +// + +static void cx_empty_map_noop(__attribute__((__unused__)) CxMap *map) { + // this is a noop, but MUST be implemented +} + +static void *cx_empty_map_get( + __attribute__((__unused__)) CxMap const *map, + __attribute__((__unused__)) CxHashKey key +) { + return NULL; +} + +static bool cx_empty_map_iter_valid(__attribute__((__unused__)) void const *iter) { + return false; +} + +static CxIterator cx_empty_map_iterator( + struct cx_map_s const *map, + __attribute__((__unused__)) enum cx_map_iterator_type type +) { + CxIterator iter = {0}; + iter.src_handle = map; + iter.base.valid = cx_empty_map_iter_valid; + return iter; +} + +static struct cx_map_class_s cx_empty_map_class = { + cx_empty_map_noop, + cx_empty_map_noop, + NULL, + cx_empty_map_get, + NULL, + cx_empty_map_iterator +}; + +CxMap cx_empty_map = { + NULL, + NULL, + 0, + 0, + NULL, + NULL, + NULL, + false, + &cx_empty_map_class +}; + +CxMap *const cxEmptyMap = &cx_empty_map; + +// + +CxMutIterator cxMapMutIteratorValues(CxMap *map) { + CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_VALUES); + it.base.mutating = true; + + // we know the iterators share the same memory layout + CxMutIterator iter; + memcpy(&iter, &it, sizeof(CxMutIterator)); + return iter; +} + +CxMutIterator cxMapMutIteratorKeys(CxMap *map) { + CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_KEYS); + it.base.mutating = true; + + // we know the iterators share the same memory layout + CxMutIterator iter; + memcpy(&iter, &it, sizeof(CxMutIterator)); + return iter; +} + +CxMutIterator cxMapMutIterator(CxMap *map) { + CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_PAIRS); + it.base.mutating = true; + + // we know the iterators share the same memory layout + CxMutIterator iter; + memcpy(&iter, &it, sizeof(CxMutIterator)); + return iter; +} diff --git a/ucx/mempool.c b/ucx/mempool.c new file mode 100644 index 0000000..7b8d3a7 --- /dev/null +++ b/ucx/mempool.c @@ -0,0 +1,232 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "cx/mempool.h" +#include "cx/utils.h" +#include + +struct cx_mempool_memory_s { + /** The destructor. */ + cx_destructor_func destructor; + /** The actual memory. */ + char c[]; +}; + +static void *cx_mempool_malloc( + void *p, + size_t n +) { + struct cx_mempool_s *pool = p; + + if (pool->size >= pool->capacity) { + size_t newcap = pool->capacity - (pool->capacity % 16) + 16; + struct cx_mempool_memory_s **newdata = realloc(pool->data, newcap*sizeof(struct cx_mempool_memory_s*)); + if (newdata == NULL) { + return NULL; + } + pool->data = newdata; + pool->capacity = newcap; + } + + struct cx_mempool_memory_s *mem = malloc(sizeof(cx_destructor_func) + n); + if (mem == NULL) { + return NULL; + } + + mem->destructor = pool->auto_destr; + pool->data[pool->size] = mem; + pool->size++; + + return mem->c; +} + +static void *cx_mempool_calloc( + void *p, + size_t nelem, + size_t elsize +) { + size_t msz; + if (cx_szmul(nelem, elsize, &msz)) { + return NULL; + } + void *ptr = cx_mempool_malloc(p, msz); + if (ptr == NULL) { + return NULL; + } + memset(ptr, 0, nelem * elsize); + return ptr; +} + +static void *cx_mempool_realloc( + void *p, + void *ptr, + size_t n +) { + struct cx_mempool_s *pool = p; + + struct cx_mempool_memory_s *mem, *newm; + mem = (struct cx_mempool_memory_s*)(((char *) ptr) - sizeof(cx_destructor_func)); + newm = realloc(mem, n + sizeof(cx_destructor_func)); + + if (newm == NULL) { + return NULL; + } + if (mem != newm) { + cx_for_n(i, pool->size) { + if (pool->data[i] == mem) { + pool->data[i] = newm; + return ((char*)newm) + sizeof(cx_destructor_func); + } + } + abort(); + } else { + return ptr; + } +} + +static void cx_mempool_free( + void *p, + void *ptr +) { + struct cx_mempool_s *pool = p; + + struct cx_mempool_memory_s *mem = (struct cx_mempool_memory_s *) + ((char *) ptr - sizeof(cx_destructor_func)); + + cx_for_n(i, pool->size) { + if (mem == pool->data[i]) { + if (mem->destructor) { + mem->destructor(mem->c); + } + free(mem); + size_t last_index = pool->size - 1; + if (i != last_index) { + pool->data[i] = pool->data[last_index]; + pool->data[last_index] = NULL; + } + pool->size--; + return; + } + } + abort(); +} + +void cxMempoolDestroy(CxMempool *pool) { + struct cx_mempool_memory_s *mem; + cx_for_n(i, pool->size) { + mem = pool->data[i]; + if (mem->destructor) { + mem->destructor(mem->c); + } + free(mem); + } + free(pool->data); + free((void*) pool->allocator); + free(pool); +} + +void cxMempoolSetDestructor( + void *ptr, + cx_destructor_func func +) { + *(cx_destructor_func *) ((char *) ptr - sizeof(cx_destructor_func)) = func; +} + +struct cx_mempool_foreign_mem_s { + cx_destructor_func destr; + void* mem; +}; + +static void cx_mempool_destr_foreign_mem(void* ptr) { + struct cx_mempool_foreign_mem_s *fm = ptr; + fm->destr(fm->mem); +} + +int cxMempoolRegister( + CxMempool *pool, + void *memory, + cx_destructor_func destr +) { + struct cx_mempool_foreign_mem_s *fm = cx_mempool_malloc( + pool, + sizeof(struct cx_mempool_foreign_mem_s) + ); + if (fm == NULL) return 1; + + fm->mem = memory; + fm->destr = destr; + *(cx_destructor_func *) ((char *) fm - sizeof(cx_destructor_func)) = cx_mempool_destr_foreign_mem; + + return 0; +} + +static cx_allocator_class cx_mempool_allocator_class = { + cx_mempool_malloc, + cx_mempool_realloc, + cx_mempool_calloc, + cx_mempool_free +}; + +CxMempool *cxMempoolCreate( + size_t capacity, + cx_destructor_func destr +) { + size_t poolsize; + if (cx_szmul(capacity, sizeof(struct cx_mempool_memory_s*), &poolsize)) { + return NULL; + } + + struct cx_mempool_s *pool = + malloc(sizeof(struct cx_mempool_s)); + if (pool == NULL) { + return NULL; + } + + CxAllocator *provided_allocator = malloc(sizeof(CxAllocator)); + if (provided_allocator == NULL) { + free(pool); + return NULL; + } + provided_allocator->cl = &cx_mempool_allocator_class; + provided_allocator->data = pool; + + pool->allocator = provided_allocator; + + pool->data = malloc(poolsize); + if (pool->data == NULL) { + free(provided_allocator); + free(pool); + return NULL; + } + + pool->size = 0; + pool->capacity = capacity; + pool->auto_destr = destr; + + return (CxMempool *) pool; +} diff --git a/ucx/printf.c b/ucx/printf.c index 94a556f..3f9c4a2 100644 --- a/ucx/printf.c +++ b/ucx/printf.c @@ -80,7 +80,7 @@ int cx_vfprintf( } cxmutstr cx_asprintf_a( - CxAllocator *allocator, + CxAllocator const *allocator, char const *fmt, ... ) { @@ -93,7 +93,7 @@ cxmutstr cx_asprintf_a( } cxmutstr cx_vasprintf_a( - CxAllocator *a, + CxAllocator const *a, char const *fmt, va_list ap ) { diff --git a/ucx/string.c b/ucx/string.c index baca3a6..d4b7005 100644 --- a/ucx/string.c +++ b/ucx/string.c @@ -72,7 +72,7 @@ void cx_strfree(cxmutstr *str) { } void cx_strfree_a( - CxAllocator *alloc, + CxAllocator const *alloc, cxmutstr *str ) { cxFree(alloc, str->ptr); @@ -98,11 +98,14 @@ size_t cx_strlen( return size; } -cxmutstr cx_strcat_a( - CxAllocator *alloc, +cxmutstr cx_strcat_ma( + CxAllocator const *alloc, + cxmutstr str, size_t count, ... ) { + if (count == 0) return str; + cxstring *strings = calloc(count, sizeof(cxstring)); if (!strings) abort(); @@ -110,34 +113,38 @@ cxmutstr cx_strcat_a( va_start(ap, count); // get all args and overall length - size_t slen = 0; + size_t slen = str.length; cx_for_n(i, count) { cxstring s = va_arg (ap, cxstring); strings[i] = s; slen += s.length; } + va_end(ap); - // create new string - cxmutstr result; - result.ptr = cxMalloc(alloc, slen + 1); - result.length = slen; - if (result.ptr == NULL) abort(); + // reallocate or create new string + if (str.ptr == NULL) { + str.ptr = cxMalloc(alloc, slen + 1); + } else { + str.ptr = cxRealloc(alloc, str.ptr, slen + 1); + } + if (str.ptr == NULL) abort(); // concatenate strings - size_t pos = 0; + size_t pos = str.length; + str.length = slen; cx_for_n(i, count) { cxstring s = strings[i]; - memcpy(result.ptr + pos, s.ptr, s.length); + memcpy(str.ptr + pos, s.ptr, s.length); pos += s.length; } // terminate string - result.ptr[result.length] = '\0'; + str.ptr[str.length] = '\0'; // free temporary array free(strings); - return result; + return str; } cxstring cx_strsubs( @@ -369,7 +376,7 @@ size_t cx_strsplit( } size_t cx_strsplit_a( - CxAllocator *allocator, + CxAllocator const *allocator, cxstring string, cxstring delim, size_t limit, @@ -411,7 +418,7 @@ size_t cx_strsplit_m( } size_t cx_strsplit_ma( - CxAllocator *allocator, + CxAllocator const *allocator, cxmutstr string, cxstring delim, size_t limit, @@ -470,7 +477,7 @@ int cx_strcasecmp_p( } cxmutstr cx_strdup_a( - CxAllocator *allocator, + CxAllocator const *allocator, cxstring string ) { cxmutstr result = { @@ -579,7 +586,7 @@ static void cx_strrepl_free_ibuf(struct cx_strreplace_ibuf *buf) { } cxmutstr cx_strreplacen_a( - CxAllocator *allocator, + CxAllocator const *allocator, cxstring str, cxstring pattern, cxstring replacement, diff --git a/ucx/tree.c b/ucx/tree.c deleted file mode 100644 index e45afed..0000000 --- a/ucx/tree.c +++ /dev/null @@ -1,52 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - */ - -#include "cx/tree.h" -#include "cx/linked_list.h" - -#define CX_TR_PTR(cur, off) *((void**)(((char*)(cur))+(off))) - -void cx_tree_add_sibling(void *node, ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_parent, void *new_node) { - cx_linked_list_add(&node, NULL, loc_prev, loc_next, new_node); - - // optional parent link - if (loc_parent >= 0) { - CX_TR_PTR(new_node, loc_parent) = CX_TR_PTR(node, loc_parent); - } -} - -void cx_tree_add_child(void **children_begin, void **children_end, - ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, - ptrdiff_t loc_parent, void *parent) { - cx_linked_list_add(children_begin, children_end, loc_prev, loc_next, new_node); - - // optional parent link - if (loc_parent >= 0) { - CX_TR_PTR(new_node, loc_parent) = parent; - } -} diff --git a/ucx/utils.c b/ucx/utils.c index 860a3c1..c01979b 100644 --- a/ucx/utils.c +++ b/ucx/utils.c @@ -28,8 +28,13 @@ #include "cx/utils.h" +#ifndef CX_STREAM_BCOPY_BUF_SIZE #define CX_STREAM_BCOPY_BUF_SIZE 8192 +#endif + +#ifndef CX_STREAM_COPY_BUF_SIZE #define CX_STREAM_COPY_BUF_SIZE 1024 +#endif size_t cx_stream_bncopy( void *src, -- 2.43.5