changeset
update ucx
Fri, 05 May 2023 18:02:11 +0200
- author
- Olaf Wintermann <olaf.wintermann@gmail.com>
- date
- Fri, 05 May 2023 18:02:11 +0200
- changeset 490
- d218607f5a7e
- parent 489
- 921f83a8943f
- child 491
- 5454ae7bf86b
update ucx
--- a/src/server/config/acl.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/config/acl.c Fri May 05 18:02:11 2023 +0200 @@ -41,9 +41,9 @@ ACLFile *conf = malloc(sizeof(ACLFile)); conf->parser.parse = acl_parse; - conf->namedACLs = cxPointerLinkedListCreate(cxDefaultAllocator, cx_cmp_ptr); - conf->uriACLs = cxPointerLinkedListCreate(cxDefaultAllocator, cx_cmp_ptr); - conf->pathACLs = cxPointerLinkedListCreate(cxDefaultAllocator, cx_cmp_ptr); + conf->namedACLs = cxLinkedListCreate(cxDefaultAllocator, NULL, CX_STORE_POINTERS); + conf->uriACLs = cxLinkedListCreate(cxDefaultAllocator, NULL, CX_STORE_POINTERS); + conf->pathACLs = cxLinkedListCreate(cxDefaultAllocator, NULL, CX_STORE_POINTERS); int r = cfg_parse_basic_file((ConfigParser*)conf, in); if(r != 0) {
--- a/src/server/config/objconf.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/config/objconf.c Fri May 05 18:02:11 2023 +0200 @@ -52,7 +52,7 @@ conf->file = file; //conf->conditions = NULL; conf->levels = NULL; - conf->objects = cxPointerLinkedListCreate(cxDefaultAllocator, cx_cmp_ptr); + conf->objects = cxLinkedListCreate(cxDefaultAllocator, NULL, CX_STORE_POINTERS); //conf->lines = NULL; int r = cfg_parse_basic_file((ConfigParser*)conf, in);
--- a/src/server/config/serverconfig.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/config/serverconfig.c Fri May 05 18:02:11 2023 +0200 @@ -463,7 +463,7 @@ } CxList* serverconfig_get_node_list(ConfigNode *parent, ConfigNodeType type, cxstring name) { - CxList *nodes = cxPointerLinkedListCreate(cxDefaultAllocator, cx_cmp_ptr); + CxList *nodes = cxLinkedListCreate(cxDefaultAllocator, NULL, CX_STORE_POINTERS); for(ConfigNode *node=parent->children_begin;node;node=node->next) { if(node->type == type && !cx_strcasecmp(cx_strcast(node->name), name)) {
--- a/src/server/daemon/acldata.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/daemon/acldata.c Fri May 05 18:02:11 2023 +0200 @@ -38,7 +38,7 @@ return NULL; } - dat->namedACLs = cxHashMapCreate(a, 16); + dat->namedACLs = cxHashMapCreate(a, CX_STORE_POINTERS, 16); if(!dat->namedACLs) { return NULL; }
--- a/src/server/daemon/auth.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/daemon/auth.c Fri May 05 18:02:11 2023 +0200 @@ -84,7 +84,7 @@ if(elm) { // compare the key data to be sure it is the correct user int n = (mapkey.len > elm->key.len) ? elm->key.len : mapkey.len; - if (!memcmp(elm->key.data.cbytes, mapkey.data.cbytes, n)) { + if (!memcmp(elm->key.data, mapkey.data, n)) { // elm is now the correct UserCacheElm // TODO: use configuration for expire time if(now - elm->created > 120) { @@ -170,7 +170,7 @@ memcpy(key + authdblen + 1, user->name, userlen); CxHashKey mapkey = cx_hash_key_bytes(key, keylen); - elm->key.data.bytes = key; + elm->key.data = key; elm->key.len = mapkey.len; elm->key.hash = mapkey.hash; elm->slot = mapkey.hash%cache.size; @@ -237,7 +237,7 @@ cache.map[elm->slot] = elm->next_elm; } - free(elm->key.data.bytes); + free((void*)elm->key.data); cached_user_unref(elm->user); free(elm);
--- a/src/server/daemon/config.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/daemon/config.c Fri May 05 18:02:11 2023 +0200 @@ -163,12 +163,12 @@ CxAllocator *allocator = pool_allocator(serverconfig->pool); serverconfig->a = allocator; - serverconfig->listeners = cxPointerLinkedListCreate(serverconfig->a, cx_cmp_ptr); - serverconfig->logfiles = cxPointerLinkedListCreate(serverconfig->a, cx_cmp_ptr); - serverconfig->host_vs = cxHashMapCreate(serverconfig->a, 16); - serverconfig->authdbs = cxHashMapCreate(serverconfig->a, 16); - serverconfig->resources = cxHashMapCreate(serverconfig->a, 16); - serverconfig->dav = cxHashMapCreate(serverconfig->a, 16); + serverconfig->listeners = cxLinkedListCreate(serverconfig->a, NULL, CX_STORE_POINTERS); + serverconfig->logfiles = cxLinkedListCreate(serverconfig->a, NULL, CX_STORE_POINTERS); + serverconfig->host_vs = cxHashMapCreate(serverconfig->a, CX_STORE_POINTERS, 16); + serverconfig->authdbs = cxHashMapCreate(serverconfig->a, CX_STORE_POINTERS, 16); + serverconfig->resources = cxHashMapCreate(serverconfig->a, CX_STORE_POINTERS, 16); + serverconfig->dav = cxHashMapCreate(serverconfig->a, CX_STORE_POINTERS, 16); // STAGE 1 load_server_conf: // At stage 1 we load the file and get the Runtime infos for changing @@ -181,7 +181,7 @@ // load Runtime config CxList *list = serverconfig_get_node_list(serverconf->root, CONFIG_NODE_OBJECT, cx_str("Runtime")); - CxIterator iter = cxListIterator(list, 0); + CxIterator iter = cxListIterator(list); cx_foreach(ConfigNode *, runtimeobj, iter) { if(cfg_handle_runtime(serverconfig, runtimeobj)) { // error @@ -194,7 +194,7 @@ // load threadpool config log_ereport(LOG_DEBUG, "apply config: Threadpool"); list = serverconfig_get_node_list(serverconf->root, CONFIG_NODE_OBJECT, cx_str("Threadpool")); - iter = cxListIterator(list, 0); + iter = cxListIterator(list); cx_foreach(ConfigNode *, elm, iter) { if(cfg_handle_threadpool(serverconfig, elm)) { log_ereport(LOG_FAILURE, "server.conf threadpool"); @@ -211,7 +211,7 @@ // load eventhandler config log_ereport(LOG_DEBUG, "apply config: EventHandler"); list = serverconfig_get_node_list(serverconf->root, CONFIG_NODE_OBJECT, cx_str("EventHandler")); - iter = cxListIterator(list, 0); + iter = cxListIterator(list); cx_foreach(ConfigNode *, elm, iter) { if(cfg_handle_eventhandler(serverconfig, elm)) { // error @@ -229,7 +229,7 @@ // load Listener config log_ereport(LOG_DEBUG, "apply config: Listener"); list = serverconfig_get_node_list(serverconf->root, CONFIG_NODE_OBJECT, cx_str("Listener")); - iter = cxListIterator(list, 0); + iter = cxListIterator(list); cx_foreach(ConfigNode *, scfgobj, iter) { if(cfg_handle_listener(serverconfig, scfgobj)) { return NULL; @@ -263,7 +263,7 @@ log_ereport(LOG_DEBUG, "apply config: LogFile"); list = serverconfig_get_node_list(serverconf->root, CONFIG_NODE_OBJECT, cx_str("LogFile")); - CxIterator iter = cxListIterator(list, 0); + CxIterator iter = cxListIterator(list); cx_foreach(ConfigNode *, logobj, iter) { if(!logobj) { // error @@ -282,7 +282,7 @@ log_ereport(LOG_DEBUG, "apply config: AccessLog"); list = serverconfig_get_node_list(serverconf->root, CONFIG_NODE_OBJECT, cx_str("AccessLog")); - iter = cxListIterator(list, 0); + iter = cxListIterator(list); cx_foreach(ConfigNode *, scfgobj, iter) { if(cfg_handle_accesslog(serverconfig, scfgobj)) { return NULL; @@ -292,7 +292,7 @@ log_ereport(LOG_DEBUG, "apply config: AuthDB"); list = serverconfig_get_node_list(serverconf->root, CONFIG_NODE_OBJECT, cx_str("AuthDB")); - iter = cxListIterator(list, 0); + iter = cxListIterator(list); cx_foreach(ConfigNode *, scfgobj, iter) { if(cfg_handle_authdb(serverconfig, scfgobj)) { return NULL; @@ -302,7 +302,7 @@ log_ereport(LOG_DEBUG, "apply config: VirtualServer"); list = serverconfig_get_node_list(serverconf->root, CONFIG_NODE_OBJECT, cx_str("VirtualServer")); - iter = cxListIterator(list, 0); + iter = cxListIterator(list); cx_foreach(ConfigNode *, scfgobj, iter) { if(cfg_handle_vs(serverconfig, scfgobj)) { return NULL; @@ -312,7 +312,7 @@ log_ereport(LOG_DEBUG, "apply config: ResourcePool"); list = serverconfig_get_node_list(serverconf->root, CONFIG_NODE_OBJECT, cx_str("ResourcePool")); - iter = cxListIterator(list, 0); + iter = cxListIterator(list); cx_foreach(ConfigNode *, scfgobj, iter) { if(cfg_handle_resourcepool(serverconfig, scfgobj)) { return NULL; @@ -322,7 +322,7 @@ log_ereport(LOG_DEBUG, "apply config: Dav"); list = serverconfig_get_node_list(serverconf->root, CONFIG_NODE_OBJECT, cx_str("Dav")); - iter = cxListIterator(list, 0); + iter = cxListIterator(list); cx_foreach(ConfigNode *, scfgobj, iter) { if(cfg_handle_dav(serverconfig, scfgobj)) { return NULL; @@ -332,7 +332,7 @@ // set VirtualServer for all listeners CxList *ls = serverconfig->listeners; - iter = cxListIterator(ls, 0); + iter = cxListIterator(ls); cx_foreach(HttpListener *, listener, iter) { cxstring vsname = cx_str(listener->default_vs.vs_name); @@ -358,7 +358,7 @@ // compare old/new listeners and set next listener, if they are using // the same socket - CxIterator old_listeners = cxListIterator(old_cfg->listeners, 0); + CxIterator old_listeners = cxListIterator(old_cfg->listeners); cx_foreach(HttpListener*, oldls, old_listeners) { if(oldls->next) { // maybe we can remove this check @@ -366,7 +366,7 @@ continue; } - CxIterator new_listeners = cxListIterator(new_cfg->listeners, 0); + CxIterator new_listeners = cxListIterator(new_cfg->listeners); cx_foreach(HttpListener*, newls, new_listeners) { if(http_listener_socket_eq(oldls, newls)) { http_listener_set_next(oldls, newls); @@ -393,7 +393,7 @@ } log_ereport(LOG_VERBOSE, "destroy configuration %p", cfg); - CxIterator i = cxListIterator(cfg->listeners, 0); + CxIterator i = cxListIterator(cfg->listeners); cx_foreach(HttpListener*, listener, i) { http_listener_destroy(listener); } @@ -750,7 +750,7 @@ int cfg_handle_dav(ServerConfiguration *cfg, ConfigNode *obj) { CxAllocator *a = pool_allocator(cfg->pool); - CxList *backends = cxPointerLinkedListCreate(a, cx_cmp_ptr); // list of ConfigParam* + CxList *backends = cxLinkedListCreate(a, NULL, CX_STORE_POINTERS); // list of ConfigParam* int init_error; // parse args @@ -798,10 +798,10 @@ WebdavRepository *repository = pool_malloc(cfg->pool, sizeof(WebdavRepository)); repository->vfs = NULL; repository->vfsInitData = NULL; - repository->davBackends = cxPointerLinkedListCreate(a, cx_cmp_ptr); // value type: WebdavBackendInitData* + repository->davBackends = cxLinkedListCreate(a, NULL, CX_STORE_POINTERS); // value type: WebdavBackendInitData* // initialize backends - CxIterator i = cxListIterator(backends, 0); + CxIterator i = cxListIterator(backends); cx_foreach(ConfigParam *, backendArg, i) { // the DavBackend value should contain the dav class name @@ -886,7 +886,7 @@ // list of cxmutstr, however the expression parser will use this // as list of cxstring, but that is totally fine - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxmutstr)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxmutstr)); ConfigParam *arg = node->args; while(arg) { if(arg->name.length > 0) { @@ -1140,7 +1140,7 @@ // cleanup in case of errors is done by the allocator MimeMap *mimemap = cxMalloc(cfg->a, sizeof(MimeMap)); - CxMap *map = cxHashMapCreate(cfg->a, (mimecfg->ntypes * 3) / 2); + CxMap *map = cxHashMapCreate(cfg->a, CX_STORE_POINTERS, (mimecfg->ntypes * 3) / 2); if(mimemap && map) { mimemap->map = map; @@ -1184,7 +1184,7 @@ // TODO: malloc return checks ACLData *acldata = acl_data_new(cfg->a); - CxIterator iter = cxListIterator(aclfile->namedACLs, 0); + CxIterator iter = cxListIterator(aclfile->namedACLs); cx_foreach(ACLConfig *, ac, iter) { ACLList *acl = acl_config_convert(cfg, ac); log_ereport(LOG_VERBOSE, "add acl: %.*s", (int)ac->id.length, ac->id.ptr);
--- a/src/server/daemon/event.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/daemon/event.c Fri May 05 18:02:11 2023 +0200 @@ -40,7 +40,7 @@ int create_event_handler(EventHandlerConfig *cfg) { if(event_handler_map == NULL) { - event_handler_map = cxHashMapCreate(cxDefaultAllocator, 16); + event_handler_map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 16); } CxHashKey key = cx_hash_key_bytes((const unsigned char*)cfg->name.ptr, cfg->name.length);
--- a/src/server/daemon/func.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/daemon/func.c Fri May 05 18:02:11 2023 +0200 @@ -39,7 +39,7 @@ CxMap *function_map; void func_init() { - function_map = cxHashMapCreate(cxDefaultAllocator, 256); + function_map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 256); } void add_function(FuncStruct *func) {
--- a/src/server/daemon/httplistener.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/daemon/httplistener.c Fri May 05 18:02:11 2023 +0200 @@ -77,7 +77,7 @@ int http_listener_global_init(void) { - listener_socket_map = cxHashMapCreate(cxDefaultAllocator, 4); + listener_socket_map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 4); if(!listener_socket_map) { return 1; } @@ -88,7 +88,7 @@ int start_all_listener() { ServerConfiguration *conf = cfgmgr_get_server_config(); CxList *ls = conf->listeners; - CxIterator iter = cxListIterator(ls, 0); + CxIterator iter = cxListIterator(ls); cx_foreach(HttpListener *, listener, iter) { http_listener_start(listener); }
--- a/src/server/daemon/keyfile_auth.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/daemon/keyfile_auth.c Fri May 05 18:02:11 2023 +0200 @@ -52,7 +52,7 @@ } keyfile->authdb.get_user = keyfile_get_user; keyfile->authdb.use_cache = 0; - keyfile->users = cxHashMapCreate(a, 16); + keyfile->users = cxHashMapCreate(a, CX_STORE_POINTERS, 16); return keyfile; } @@ -64,7 +64,7 @@ cxmutstr *groups, size_t ngroups) { - CxAllocator *a = keyfile->users->allocator; + const CxAllocator *a = keyfile->users->allocator; if(hash.length < 12) { // hash too short
--- a/src/server/daemon/ldap_auth.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/daemon/ldap_auth.c Fri May 05 18:02:11 2023 +0200 @@ -256,7 +256,7 @@ // initialize group cache authdb->groups.first = NULL; authdb->groups.last = NULL; - authdb->groups.map = cxHashMapCreate(cfg->a, 32); + authdb->groups.map = cxHashMapCreate(cfg->a, CX_STORE_POINTERS, 32); if(!authdb->groups.map) { return NULL; } @@ -518,7 +518,7 @@ if(!group) { return NULL; } - group->members = cxHashMapCreate(a, 32); + group->members = cxHashMapCreate(a, CX_STORE_POINTERS, 32); if(!group->members) { pool_free(sn->pool, group); return NULL;
--- a/src/server/daemon/log.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/daemon/log.c Fri May 05 18:02:11 2023 +0200 @@ -107,7 +107,7 @@ }; int init_logging(void) { - log_dup_list = cxPointerLinkedListCreate(cxDefaultAllocator, cx_cmp_ptr); + log_dup_list = cxLinkedListCreate(cxDefaultAllocator, NULL, CX_STORE_POINTERS); return log_dup_list == NULL; } @@ -201,7 +201,7 @@ msg[len] = '\n'; pthread_mutex_lock(&mutex); - CxIterator i = cxListIterator(log_dup_list, 0); + CxIterator i = cxListIterator(log_dup_list); cx_foreach(LogDup *, dup, i) { dup->write(dup->cookie, msg, len + 1); } @@ -255,7 +255,7 @@ void log_remove_logdup(LogDup *ldup) { pthread_mutex_lock(&mutex); - CxMutIterator i = cxListMutIterator(log_dup_list, 0); + CxMutIterator i = cxListMutIterator(log_dup_list); WSBool finished = 0; cx_foreach(LogDup *, dup, i) { if(finished) break; @@ -383,7 +383,7 @@ // TODO: this looks dubious if(!access_log_files) { - access_log_files = cxHashMapCreate(cxDefaultAllocator, 4); + access_log_files = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 4); } if(file.ptr == NULL || file.length == 0) {
--- a/src/server/daemon/resourcepool.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/daemon/resourcepool.c Fri May 05 18:02:11 2023 +0200 @@ -39,7 +39,7 @@ static CxMap *resource_pool_types; int init_resource_pools(void) { - resource_pool_types = cxHashMapCreate(cxDefaultAllocator, 4); + resource_pool_types = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 4); return resource_pool_types ? 0 : 1; } @@ -179,7 +179,7 @@ if(resource) { if(request && session) { if(!request->resources) { - request->resources = cxHashMapCreate(pool_allocator(session->sn.pool), 8); + request->resources = cxHashMapCreate(pool_allocator(session->sn.pool), CX_STORE_POINTERS, 8); } if(request->resources) { @@ -226,7 +226,7 @@ if(nsapi_rq && !nsapi_rq->finished) { // request processing still ongoing and SAFs will be executed - if(!cxMapRemove(nsapi_rq->resources, cx_hash_key_str(respool->name))) { + if(!cxMapRemoveAndGet(nsapi_rq->resources, cx_hash_key_str(respool->name))) { log_ereport(LOG_FAILURE, "resourcepool_free: cannot remove resource from request: potential double free"); } }
--- a/src/server/daemon/threadpools.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/daemon/threadpools.c Fri May 05 18:02:11 2023 +0200 @@ -47,7 +47,7 @@ int create_threadpool(cxstring name, ThreadPoolConfig *cfg) { if(thread_pool_map == NULL) { - thread_pool_map = cxHashMapCreate(cxDefaultAllocator, 16); + thread_pool_map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 16); } CxHashKey key = cx_hash_key_bytes((const unsigned char*)name.ptr, name.length); @@ -85,7 +85,7 @@ int create_io_pool(cxstring name, int numthreads) { if(io_pool_map == NULL) { - io_pool_map = cxHashMapCreate(cxDefaultAllocator, 4); + io_pool_map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 4); } CxHashKey key = cx_hash_key_bytes((const unsigned char*)name.ptr, name.length); threadpool_t *pool = cxMapGet(io_pool_map, key);
--- a/src/server/daemon/vfs.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/daemon/vfs.c Fri May 05 18:02:11 2023 +0200 @@ -80,7 +80,7 @@ }; int vfs_init(void) { - vfs_type_map = cxHashMapCreate(cxDefaultAllocator, 16); + vfs_type_map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 16); if(!vfs_type_map) { return -1; }
--- a/src/server/plugins/postgresql/config.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/plugins/postgresql/config.c Fri May 05 18:02:11 2023 +0200 @@ -203,7 +203,7 @@ } // prepare PgRepository - repo->prop_ext = cxHashMapCreate(a, 8); + repo->prop_ext = cxHashMapCreate(a, CX_STORE_POINTERS, 8); if(!repo->prop_ext) { log_ereport(LOG_FAILURE, "pg: cannot load config file: OOM"); return 1; @@ -245,8 +245,8 @@ int ret = 0; PgExtParser parserData; - parserData.table_lookup = cxHashMapCreate(cxDefaultAllocator, 8); - parserData.tables = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_ptr, sizeof(PgExtTable)); + parserData.table_lookup = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 8); + parserData.tables = cxLinkedListCreate(cxDefaultAllocator, NULL, sizeof(PgExtTable)); while(node && !ret) { // currently, the only possible config element is <extension> @@ -265,7 +265,7 @@ repo->tables = pool_calloc(pool, ntables, sizeof(PgExtTable)); if(repo->tables) { int i = 0; - CxIterator iter = cxListIterator(parserData.tables, 0); + CxIterator iter = cxListIterator(parserData.tables); cx_foreach(PgExtTable *, tab, iter) { repo->tables[i++] = *tab; } @@ -294,7 +294,7 @@ xmlNode *node = ext_node->children; const char *table = NULL; - CxList *properties = cxPointerLinkedListCreate(a, cx_cmp_ptr); + CxList *properties = cxLinkedListCreate(a, NULL, CX_STORE_POINTERS); while(node) { if(node->type == XML_ELEMENT_NODE) { @@ -364,7 +364,7 @@ return 1; } - CxIterator iter = cxListIterator(properties, 0); + CxIterator iter = cxListIterator(properties); cx_foreach(xmlNode *, ps, iter) { const char *value = pg_util_xml_get_text(ps); @@ -382,7 +382,7 @@ CxHashKey key = webdav_property_key(ext_col->ns, ext_col->name); int err = cxMapPut(repo->prop_ext, key, ext_col); - free(key.data.bytes); + free((void*)key.data); if(err) { return 1; }
--- a/src/server/plugins/postgresql/pgtest.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/plugins/postgresql/pgtest.c Fri May 05 18:02:11 2023 +0200 @@ -125,7 +125,7 @@ node = node->children; cxmutstr href = {NULL, 0}; - CxMap *properties = cxHashMapCreate(a, 16); + CxMap *properties = cxHashMapCreate(a, CX_STORE_POINTERS, 16); while(node) { if(node->type == XML_ELEMENT_NODE) { @@ -206,7 +206,7 @@ TestMultistatus *ms = cxMalloc(mp->allocator, sizeof(TestMultistatus)); ms->doc = doc; ms->mp = mp; - ms->responses = cxHashMapCreate((CxAllocator*)mp->allocator, 8); + ms->responses = cxHashMapCreate((CxAllocator*)mp->allocator, CX_STORE_POINTERS, 8); // parse response xmlNode *xml_root = xmlDocGetRootElement(doc);
--- a/src/server/plugins/postgresql/webdav.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/plugins/postgresql/webdav.c Fri May 05 18:02:11 2023 +0200 @@ -466,8 +466,11 @@ WSNamespace *ns = cur->property->namespace; if(ns) { CxHashKey pkey = webdav_property_key((const char*)ns->href, cur->property->name); + if(!pkey.data) { + return 1; + } PgPropertyStoreExt *cfg_ext = cxMapGet(pgdav->repository->prop_ext, pkey); - free(pkey.data.bytes); + free((void*)pkey.data); if(cfg_ext) { PgPropfindExtCol extcol; extcol.ext = cfg_ext; @@ -907,8 +910,11 @@ static PgPropertyStoreExt* pg_proppatch_prop_get_ext(PgWebdavBackend *pgdav, WebdavProperty *property) { CxHashKey pkey = webdav_property_key((const char*)property->namespace->href, property->name); + if(!pkey.data) { + return NULL; + } PgPropertyStoreExt *ext = cxMapGet(pgdav->repository->prop_ext, pkey); - free(pkey.data.bytes); + free((void*)pkey.data); return ext; }
--- a/src/server/safs/common.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/safs/common.c Fri May 05 18:02:11 2023 +0200 @@ -75,7 +75,7 @@ #define COMMONSAF_RET_ERROR -2 void common_saf_init() { - var_names = cxHashMapCreate(cxDefaultAllocator, 32); + var_names = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 32); cxMapPut(var_names, cx_hash_key_str("insert-client"), (void*)(intptr_t)COMMONSAF_INSERT_CLIENT); cxMapPut(var_names, cx_hash_key_str("insert-vars"), (void*)(intptr_t)COMMONSAF_INSERT_VARS);
--- a/src/server/safs/nametrans.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/safs/nametrans.c Fri May 05 18:02:11 2023 +0200 @@ -50,7 +50,7 @@ void *backend_first = NULL; void *backend_last = NULL; - CxIterator i = cxListIterator(repo->davBackends, 0); + CxIterator i = cxListIterator(repo->davBackends); cx_foreach(WebdavBackendInitData *, davInit, i) { WebdavBackend *backend = davInit->davType->create(sn, rq, pb, davInit->davInitData); if(!backend) {
--- a/src/server/safs/service.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/safs/service.c Fri May 05 18:02:11 2023 +0200 @@ -555,7 +555,7 @@ content_type->value, (long long)r[i].offset, (long long)r[i].offset+r[i].length - 1, - filelen); + (long long)filelen); response_len += r[i].header.length + r[i].length; @@ -642,7 +642,7 @@ "%lld-%lld/%lld", (long long)offset, (long long)offset+length - 1, - s.st_size); + (long long)s.st_size); pblock_kvinsert( pb_key_content_range, content_range.ptr,
--- a/src/server/test/object.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/test/object.c Fri May 05 18:02:11 2023 +0200 @@ -39,7 +39,7 @@ UCX_TEST(test_expr_parse_expr_value) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("123"); cxListAdd(tokens, &token); @@ -60,7 +60,7 @@ UCX_TEST(test_expr_parse_expr_neg_value) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("-123"); cxListAdd(tokens, &token); @@ -82,7 +82,7 @@ UCX_TEST(test_expr_parse_expr_value_str) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("\"hello world\""); cxListAdd(tokens, &token); @@ -104,7 +104,7 @@ UCX_TEST(test_expr_parse_expr_value_bool) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("true"); cxListAdd(tokens, &token); @@ -126,7 +126,7 @@ UCX_TEST(test_expr_parse_expr_value_var) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("$test"); cxListAdd(tokens, &token); @@ -148,7 +148,7 @@ UCX_TEST(test_expr_parse_expr_not_value) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("not"); cxListAdd(tokens, &token); token = cx_str("true"); @@ -176,13 +176,13 @@ UCX_TEST(test_expr_parse_expr_sign_value) { pool_handle_t *pool = pool_create(); - CxList *tokens1 = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens1 = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("+"); cxListAdd(tokens1, &token); token = cx_str("123"); cxListAdd(tokens1, &token); - CxList *tokens2 = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens2 = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); token = cx_str("-"); cxListAdd(tokens2, &token); token = cx_str("123"); @@ -218,7 +218,7 @@ UCX_TEST(test_expr_parse_expr_compare2values) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("2"); cxListAdd(tokens, &token); token = cx_str("=="); @@ -249,7 +249,7 @@ UCX_TEST(test_expr_parse_expr_compare2value_expr) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("2"); cxListAdd(tokens, &token); token = cx_str("=="); @@ -284,7 +284,7 @@ UCX_TEST(test_expr_parse_expr_compare2expr_value) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("1"); cxListAdd(tokens, &token); token = cx_str("+"); @@ -325,7 +325,7 @@ pool_handle_t *pool = pool_create(); // expression: 2 * (1 + 2) == 6 - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("2"); cxListAdd(tokens, &token); token = cx_str("*"); @@ -371,7 +371,7 @@ UCX_TEST(test_expr_op_defined_simple) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("defined"); cxListAdd(tokens, &token); @@ -398,7 +398,7 @@ UCX_TEST(test_expr_op_defined) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("true"); cxListAdd(tokens, &token); @@ -437,7 +437,7 @@ UCX_TEST(test_expr_op_file_exists_simple) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("-e"); cxListAdd(tokens, &token); @@ -465,7 +465,7 @@ UCX_TEST(test_expr_parse_expr_func_arg0) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("test"); cxListAdd(tokens, &token); token = cx_str("("); @@ -521,7 +521,7 @@ UCX_TEST(test_expr_parse_expr_func_arg1) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("test"); cxListAdd(tokens, &token); token = cx_str("("); @@ -556,7 +556,7 @@ UCX_TEST(test_expr_parse_expr_func_arg3) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("test"); cxListAdd(tokens, &token); token = cx_str("("); @@ -601,7 +601,7 @@ UCX_TEST(test_expr_parse_expr_func_expr1) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("test"); cxListAdd(tokens, &token); token = cx_str("("); @@ -647,7 +647,7 @@ UCX_TEST(test_expr_parse_expr_func_expr2) { pool_handle_t *pool = pool_create(); - CxList *tokens = cxLinkedListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(cxstring)); + CxList *tokens = cxLinkedListCreate(pool_allocator(pool), NULL, sizeof(cxstring)); cxstring token = cx_str("test"); cxListAdd(tokens, &token); token = cx_str("(");
--- a/src/server/test/vfs.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/test/vfs.c Fri May 05 18:02:11 2023 +0200 @@ -303,7 +303,7 @@ return 1; } - (void)cxMapRemove(vfs->files, path_key); + cxMapRemove(vfs->files, path_key); vfs->count_unlink++; return 0; } @@ -328,7 +328,7 @@ } } - (void)cxMapRemove(vfs->files, path_key); + cxMapRemove(vfs->files, path_key); vfs->count_rmdir++; return 0; } @@ -351,7 +351,7 @@ TestVFS *vfs = pool_malloc(sn->pool, sizeof(TestVFS)); vfs->count_unlink = 0; vfs->count_rmdir = 0; - vfs->files = cxHashMapCreate(pool_allocator(sn->pool), 64); + vfs->files = cxHashMapCreate(pool_allocator(sn->pool), CX_STORE_POINTERS, 64); testVFSClass.instance = vfs; return &testVFSClass; @@ -447,7 +447,7 @@ VFSDir *dir = vfs_opendir(vfs, "/dir"); UCX_TEST_ASSERT(dir, "dir not opened"); - CxMap *files = cxHashMapCreate(cxDefaultAllocator, 8); + CxMap *files = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 8); VFSEntry entry; while(vfs_readdir(dir, &entry)) {
--- a/src/server/util/object.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/util/object.c Fri May 05 18:02:11 2023 +0200 @@ -518,8 +518,8 @@ } NSAPIExpression* expr_parse_logical_expr(pool_handle_t *pool, CxList *tokens, size_t *pos) { - CxList *op_stack = cxArrayListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(ExprOpStackItem), 32); - CxList *ex_stack = cxArrayListCreate(pool_allocator(pool), cx_cmp_ptr, sizeof(NSAPIExpression*), 32); + CxList *op_stack = cxArrayListCreate(pool_allocator(pool), NULL, sizeof(ExprOpStackItem), 32); + CxList *ex_stack = cxArrayListCreate(pool_allocator(pool), NULL, sizeof(NSAPIExpression*), 32); ExprParser parser; parser.pool = pool;
--- a/src/server/webdav/multistatus.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/webdav/multistatus.c Fri May 05 18:02:11 2023 +0200 @@ -52,7 +52,7 @@ ms->response.addresource = multistatus_addresource; ms->sn = sn; ms->rq = rq; - ms->namespaces = cxHashMapCreate(pool_allocator(sn->pool), 8); + ms->namespaces = cxHashMapCreate(pool_allocator(sn->pool), CX_STORE_POINTERS, 8); ms->proppatch = FALSE; if(!ms->namespaces) { return NULL; @@ -74,7 +74,7 @@ cx_foreach(CxMapEntry*, entry, i) { WSNamespace *ns = entry->value; writer_put_lit(out, " xmlns:"); - writer_put (out, entry->key->data.str, entry->key->len); + writer_put (out, entry->key->data, entry->key->len); writer_put_lit(out, "=\""); writer_put_str(out, (char*)ns->href); writer_put_lit(out, "\""); @@ -355,7 +355,7 @@ res->resource.addproperty = msresponse_addproperty; res->resource.close = msresponse_close; - res->properties = cxHashMapCreate(pool_allocator(ms->sn->pool), 32); + res->properties = cxHashMapCreate(pool_allocator(ms->sn->pool), CX_STORE_POINTERS, 32); if(!res->properties) { return NULL; } @@ -497,13 +497,13 @@ CxAllocator *a = pool_allocator(sn->pool); CxHashKey key = ms_property_key(a, property->namespace->href, property->name); if(cxMapGet(response->properties, key)) { - cxFree(a, key.data.bytes); + cxFree(a, (void*)key.data); return 0; } if(cxMapPut(response->properties, key, property)) { return 1; // OOM } - cxFree(a, key.data.bytes); + cxFree(a, (void*)key.data); // list of namespace definitions for this property WebdavNSList *nsdef_begin = NULL;
--- a/src/server/webdav/requestparser.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/webdav/requestparser.c Fri May 05 18:02:11 2023 +0200 @@ -84,7 +84,7 @@ // check for prop duplicates CxHashKey k = webdav_property_key((const char*)ns, (const char*)name); - if(!k.data.bytes) { + if(!k.data) { *error = proppatch ? PROPPATCH_PARSER_OOM : PROPFIND_PARSER_OOM; return 1; } @@ -114,7 +114,7 @@ *error = PROPPATCH_PARSER_DUPLICATE; } - free((void*)k.data.str); + free((void*)k.data); if(*error) { return 1; } @@ -160,7 +160,7 @@ } CxAllocator *a = pool_allocator(sn->pool); - CxMap *propmap = cxHashMapCreate(a, 32); // value: intptr_t + CxMap *propmap = cxHashMapCreate(a, CX_STORE_POINTERS, 32); // value: intptr_t if(!propmap) { *error = PROPFIND_PARSER_OOM; xmlFreeDoc(doc); @@ -302,7 +302,7 @@ CxAllocator *a = pool_allocator(sn->pool); // map for duplicate checking // value type: intptr_t - CxMap *propmap = cxHashMapCreate(a, 32); + CxMap *propmap = cxHashMapCreate(a, CX_STORE_POINTERS, 32); if(!propmap) { *error = PROPPATCH_PARSER_OOM; xmlFreeDoc(doc);
--- a/src/server/webdav/webdav.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/webdav/webdav.c Fri May 05 18:02:11 2023 +0200 @@ -146,12 +146,12 @@ } webdav_is_initialized = TRUE; - webdav_type_map = cxHashMapCreate(cxDefaultAllocator, 8); + webdav_type_map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 8); if(!webdav_type_map) { return REQ_ABORTED; } - method_handler_map = cxHashMapCreate(cxDefaultAllocator, 64); + method_handler_map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 64); if(!method_handler_map) { return REQ_ABORTED; } @@ -941,15 +941,15 @@ /* ------------------------------ Utils ------------------------------ */ -CxHashKey webdav_property_key_a(CxAllocator *a, const char *ns, const char *name) { +CxHashKey webdav_property_key_a(const CxAllocator *a, const char *ns, const char *name) { CxHashKey key; cxmutstr data = cx_asprintf("%s\n%s", name, ns); if(data.ptr) { - key.data.str = data.ptr; + key.data = data.ptr; key.len = data.length; cx_hash_murmur(&key); } else { - key.data.str = NULL; + key.data = NULL; key.len = 0; key.hash = 0; }
--- a/src/server/webdav/webdav.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/webdav/webdav.h Fri May 05 18:02:11 2023 +0200 @@ -132,7 +132,7 @@ CxHashKey webdav_property_key(const char *ns, const char *name); -CxHashKey webdav_property_key_a(CxAllocator *a, const char *ns, const char *name); +CxHashKey webdav_property_key_a(const CxAllocator *a, const char *ns, const char *name); #ifdef __cplusplus }
--- a/src/server/webdav/xattrbackend.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/webdav/xattrbackend.c Fri May 05 18:02:11 2023 +0200 @@ -219,7 +219,7 @@ a, (const char*)reqprop->namespace->href, (const char*)reqprop->name); - if(!key.data.str) { + if(!key.data) { return 1; } @@ -299,7 +299,7 @@ pool_free(sn->pool, xattr_data); } else { // empty map - pmap = cxHashMapCreate(a, request->setcount + 8); + pmap = cxHashMapCreate(a, CX_STORE_POINTERS, request->setcount + 8); } if(!pmap) { return 1; @@ -321,12 +321,12 @@ a, (const char*)prop->namespace->href, (const char*)prop->name); - if(!key.data.str) { + if(!key.data) { cxMapDestroy(pmap); return 1; } - void *rmprop = cxMapRemove(pmap, key); - cxFree(a, key.data.str); + void *rmprop = cxMapRemoveAndGet(pmap, key); + cxFree(a, (void*)key.data); // TODO: free rmprop @@ -509,16 +509,16 @@ pmap->allocator, (const char*)prop->namespace->href, (const char*)prop->name); - if(!key.data.str) { + if(!key.data) { return 1; } int ret = cxMapPut(pmap, key, prop); - cxFree(pmap->allocator, key.data.str); + cxFree(pmap->allocator, (void*)key.data); return ret; } CxMap* webdav_xattr_parse_data(CxAllocator *a, const char *data, size_t len, const char *path) { - CxMap *pmap = cxHashMapCreate(a, 32); + CxMap *pmap = cxHashMapCreate(a, CX_STORE_POINTERS, 32); if(!pmap) { return NULL; }
--- a/src/server/webdav/xml.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/server/webdav/xml.c Fri May 05 18:02:11 2023 +0200 @@ -210,7 +210,7 @@ // we create a list of unique prefix-href namespaces by putting // all namespaces in a map CxHashKey nskey = xml_namespace_key(col->a, node->ns); - if(!nskey.data.bytes) { + if(!nskey.data) { col->error = 1; return 1; } @@ -257,7 +257,7 @@ if(error) *error = 0; CxAllocator *a = pool_allocator(pool); - CxMap *nsmap = cxHashMapCreate(a, 16); + CxMap *nsmap = cxHashMapCreate(a, CX_STORE_POINTERS, 16); if(!nsmap) { if(error) *error = 1; return NULL; @@ -281,11 +281,11 @@ WebdavNSList *def = col.def; while(def) { CxHashKey nskey = xml_namespace_key(a, def->namespace); - if(!nskey.data.bytes) { + if(!nskey.data) { if(error) *error = 1; break; } - (void)cxMapRemove(nsmap, nskey); + cxMapRemove(nsmap, nskey); def = def->next; }
--- a/src/ucx/allocator.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/allocator.c Fri May 05 18:02:11 2023 +0200 @@ -28,8 +28,6 @@ #include "cx/allocator.h" -#include <stdlib.h> - __attribute__((__malloc__, __alloc_size__(2))) static void *cx_malloc_stdlib( __attribute__((__unused__)) void *d,
--- a/src/ucx/array_list.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/array_list.c Fri May 05 18:02:11 2023 +0200 @@ -29,7 +29,6 @@ #include "cx/array_list.h" #include <assert.h> #include <string.h> -#include <stdint.h> // LOW LEVEL ARRAY LIST FUNCTIONS @@ -103,7 +102,9 @@ return CX_ARRAY_COPY_SUCCESS; } +#ifndef CX_ARRAY_SWAP_SBO_SIZE #define CX_ARRAY_SWAP_SBO_SIZE 512 +#endif void cx_array_swap( void *arr, @@ -111,6 +112,8 @@ size_t idx1, size_t idx2 ) { + assert(arr != NULL); + // short circuit if (idx1 == idx2) return; @@ -147,6 +150,7 @@ typedef struct { struct cx_list_s base; void *data; + size_t capacity; struct cx_array_reallocator_s reallocator; } cx_array_list; @@ -168,36 +172,52 @@ cxFree(list->allocator, arl->data); } -static int cx_arl_add( +static size_t cx_arl_insert_array( struct cx_list_s *list, - void const *elem -) { - cx_array_list *arl = (cx_array_list *) list; - return cx_array_copy( - &arl->data, - &list->size, - &list->capacity, - list->size, - elem, - list->itemsize, - 1, - &arl->reallocator - ); -} - -static size_t cx_arl_add_array( - struct cx_list_s *list, + size_t index, void const *array, size_t n ) { + // out of bounds and special case check + if (index > list->size || n == 0) return 0; + + // get a correctly typed pointer to the list cx_array_list *arl = (cx_array_list *) list; + + // 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->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, + &arl->capacity, + start_of_moved, + first_to_move, + list->item_size, + elems_to_move, + &arl->reallocator + )) { + // if moving existing elems is unsuccessful, abort + return 0; + } + } + + // note that if we had to move the elements, the following operation + // is guaranteed to succeed, because we have the memory already allocated + // therefore, it is impossible to leave this function with an invalid array + + // place the new elements if (CX_ARRAY_COPY_SUCCESS == cx_array_copy( &arl->data, &list->size, - &list->capacity, - list->size, + &arl->capacity, + index, array, - list->itemsize, + list->item_size, n, &arl->reallocator )) { @@ -208,38 +228,12 @@ } } -static int cx_arl_insert( +static int cx_arl_insert_element( struct cx_list_s *list, size_t index, - void const *elem + void const *element ) { - if (index > list->size) { - return 1; - } else if (index == list->size) { - return cx_arl_add(list, elem); - } else { - cx_array_list *arl = (cx_array_list *) list; - - // move elements starting at index to the right - if (cx_array_copy( - &arl->data, - &list->size, - &list->capacity, - index + 1, - ((char *) arl->data) + index * list->itemsize, - list->itemsize, - list->size - index, - &arl->reallocator - )) { - return 1; - } - - // place the element - memcpy(((char *) arl->data) + index * list->itemsize, - elem, list->itemsize); - - return 0; - } + return 1 != cx_arl_insert_array(list, index, element, 1); } static int cx_arl_insert_iter( @@ -249,18 +243,18 @@ ) { struct cx_list_s *list = iter->src_handle; if (iter->index < list->size) { - int result = cx_arl_insert( + int result = cx_arl_insert_element( list, iter->index + 1 - prepend, elem ); 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 { - int result = cx_arl_add(list, elem); + int result = cx_arl_insert_element(list, list->size, elem); iter->index = list->size; return result; } @@ -270,11 +264,16 @@ struct cx_list_s *list, size_t index ) { + cx_array_list *arl = (cx_array_list *) list; + // out-of-bounds check if (index >= list->size) { return 1; } + // content destruction + cx_invoke_destructor(list, ((char *) arl->data) + index * list->item_size); + // short-circuit removal of last element if (index == list->size - 1) { list->size--; @@ -282,14 +281,13 @@ } // just move the elements starting at index to the left - cx_array_list *arl = (cx_array_list *) list; 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 ); @@ -300,6 +298,40 @@ return result; } +static void cx_arl_clear(struct cx_list_s *list) { + if (list->size == 0) return; + + 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; + } + } + + memset(arl->data, 0, list->size * list->item_size); + list->size = 0; +} + +static int cx_arl_swap( + struct cx_list_s *list, + size_t i, + size_t j +) { + if (i >= list->size || j >= list->size) return 1; + cx_array_list *arl = (cx_array_list *) list; + cx_array_swap(arl->data, list->item_size, i, j); + return 0; +} + static void *cx_arl_at( struct cx_list_s const *list, size_t index @@ -307,32 +339,35 @@ 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 ); } @@ -341,6 +376,7 @@ struct cx_list_s const *list, struct cx_list_s const *other ) { + assert(list->cmpfunc != NULL); if (list->size == other->size) { char const *left = ((cx_array_list const *) list)->data; char const *right = ((cx_array_list const *) other)->data; @@ -349,8 +385,8 @@ if (d != 0) { return d; } - left += list->itemsize; - right += other->itemsize; + left += list->item_size; + right += other->item_size; } return 0; } else { @@ -363,7 +399,7 @@ 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); } } @@ -389,7 +425,22 @@ 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; + } +} + +static void cx_arl_iter_prev(void *it) { + struct cx_iterator_base_s *itbase = it; + struct cx_mut_iterator_s *iter = it; + cx_array_list *const list = iter->src_handle; + if (itbase->remove) { + itbase->remove = false; + cx_arl_remove(iter->src_handle, iter->index); + } + iter->index--; + if (iter->index < list->base.size) { + iter->elem_handle = ((char *) list->data) + + iter->index * list->base.item_size; } } @@ -405,7 +456,8 @@ static struct cx_iterator_s cx_arl_iterator( struct cx_list_s const *list, - size_t index + size_t index, + bool backwards ) { struct cx_iterator_s iter; @@ -414,7 +466,7 @@ iter.elem_handle = cx_arl_at(list, index); iter.base.valid = cx_arl_iter_valid; iter.base.current = cx_arl_iter_current; - iter.base.next = cx_arl_iter_next; + iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next; iter.base.flag_removal = cx_arl_iter_flag_rm; iter.base.remove = false; iter.base.mutating = false; @@ -422,56 +474,54 @@ return iter; } -static struct cx_mut_iterator_s cx_arl_mut_iterator( - struct cx_list_s *list, - size_t index -) { - CxIterator it = cx_arl_iterator(list, index); - it.base.mutating = true; - - // we know the iterators share the same memory layout - CxMutIterator iter; - memcpy(&iter, &it, sizeof(CxMutIterator)); - return iter; -} - static cx_list_class cx_array_list_class = { cx_arl_destructor, - cx_arl_add, - cx_arl_add_array, - cx_arl_insert, + cx_arl_insert_element, + cx_arl_insert_array, cx_arl_insert_iter, cx_arl_remove, + cx_arl_clear, + cx_arl_swap, cx_arl_at, cx_arl_find, cx_arl_sort, cx_arl_compare, cx_arl_reverse, cx_arl_iterator, - cx_arl_mut_iterator, }; CxList *cxArrayListCreate( CxAllocator const *allocator, - CxListComparator comparator, + cx_compare_func comparator, size_t item_size, size_t initial_capacity ) { + if (allocator == NULL) { + allocator = cxDefaultAllocator; + } + cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); if (list == NULL) return NULL; + list->base.cl = &cx_array_list_class; + list->base.allocator = allocator; + list->base.cmpfunc = comparator; + list->capacity = initial_capacity; + + if (item_size > 0) { + list->base.item_size = item_size; + } else { + item_size = sizeof(void *); + cxListStorePointers((CxList *) list); + } + + // allocate the array after the real item_size is known list->data = cxCalloc(allocator, initial_capacity, item_size); if (list->data == NULL) { cxFree(allocator, list); return NULL; } - list->base.cl = &cx_array_list_class; - list->base.allocator = allocator; - list->base.cmpfunc = comparator; - list->base.itemsize = item_size; - list->base.capacity = initial_capacity; - // configure the reallocator list->reallocator.realloc = cx_arl_realloc; list->reallocator.ptr1 = (void *) allocator;
--- a/src/ucx/basic_mempool.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/basic_mempool.c Fri May 05 18:02:11 2023 +0200 @@ -28,7 +28,6 @@ #include "cx/basic_mempool.h" #include "cx/utils.h" -#include <stdint.h> #include <string.h> #define of_chk_(n) if (SIZE_MAX - sizeof(cx_destructor_func) < (n)) return NULL
--- a/src/ucx/buffer.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/buffer.c Fri May 05 18:02:11 2023 +0200 @@ -29,10 +29,8 @@ #include "cx/buffer.h" #include "cx/utils.h" -#include <stdlib.h> #include <stdio.h> #include <string.h> -#include <stdint.h> int cxBufferInit( CxBuffer *buffer, @@ -41,6 +39,7 @@ CxAllocator const *allocator, int flags ) { + if (allocator == NULL) allocator = cxDefaultAllocator; buffer->allocator = allocator; buffer->flags = flags; if (!space) { @@ -71,6 +70,29 @@ } } +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,
--- a/src/ucx/compare.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/compare.c Fri May 05 18:02:11 2023 +0200 @@ -28,12 +28,11 @@ #include "cx/compare.h" -#include <stdint.h> #include <math.h> 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 { @@ -42,8 +41,8 @@ } 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 { @@ -52,8 +51,8 @@ } 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 { @@ -62,8 +61,8 @@ } 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 { @@ -72,8 +71,8 @@ } 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 { @@ -82,8 +81,8 @@ } 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 { @@ -92,8 +91,8 @@ } 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 { @@ -102,8 +101,8 @@ } 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 { @@ -112,8 +111,8 @@ } 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 { @@ -122,8 +121,8 @@ } 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 { @@ -132,8 +131,8 @@ } 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 { @@ -142,8 +141,8 @@ } 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 { @@ -152,8 +151,8 @@ } 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 { @@ -161,9 +160,12 @@ } } -int cx_cmp_double(void const *d1, void const *d2) { - double a = *((const double*) d1); - double b = *((const double*) d2); +int cx_cmp_double( + void const *d1, + void const *d2 +) { + double a = *((const double *) d1); + double b = *((const double *) d2); if (fabs(a - b) < 1e-14) { return 0; } else { @@ -171,12 +173,29 @@ } } -int cx_cmp_ptr(void const *ptr1, void const *ptr2) { - const intptr_t p1 = (const intptr_t) ptr1; - const intptr_t p2 = (const intptr_t) ptr2; +int cx_cmp_intptr( + void const *ptr1, + void const *ptr2 +) { + intptr_t p1 = *(const intptr_t *) ptr1; + intptr_t p2 = *(const intptr_t *) ptr2; if (p1 == p2) { return 0; } else { - return p1 < p2 ? -1 : 1; + return p1 < p2 ? -1 : 1; } } + +int cx_cmp_uintptr( + void const *ptr1, + void const *ptr2 +) { + uintptr_t p1 = *(const uintptr_t *) ptr1; + uintptr_t p2 = *(const uintptr_t *) ptr2; + if (p1 == p2) { + return 0; + } else { + return p1 < p2 ? -1 : 1; + } +} +
--- a/src/ucx/cx/allocator.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/allocator.h Fri May 05 18:02:11 2023 +0200 @@ -133,41 +133,6 @@ ) __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. - */ -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 -}; - -/** * Allocate \p n bytes of memory. * * @param allocator the allocator
--- a/src/ucx/cx/array_list.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/array_list.h Fri May 05 18:02:11 2023 +0200 @@ -101,9 +101,10 @@ * Copies elements from one array to another. * * The elements are copied to the \p target array at the specified \p index, - * overwriting possible elements. The index must be in range of the current - * array \p size. If the number of elements added would extend the array's size, - * and \p capacity is not \c NULL, the remaining capacity is used. + * overwriting possible elements. The \p index does not need to be in range of + * the current array \p size. If the new index plus the number of elements added + * would extend the array's size, and \p capacity is not \c NULL, the remaining + * capacity is used. * * If the capacity is insufficient to hold the new data, a reallocation * attempt is made, unless the allocator is set to \c NULL, in which case @@ -151,19 +152,40 @@ /** * Allocates an array list for storing elements with \p item_size bytes each. * + * If \p item_size is CX_STORE_POINTERS, the created list will be created as if + * cxListStorePointers() was called immediately after creation. + * * @param allocator the allocator for allocating the list memory + * (if \c NULL the cxDefaultAllocator will be used) * @param comparator the comparator for the elements + * (if \c NULL sort and find functions will not work) * @param item_size the size of each element in bytes * @param initial_capacity the initial number of elements the array can store * @return the created list */ CxList *cxArrayListCreate( CxAllocator const *allocator, - CxListComparator comparator, + cx_compare_func comparator, size_t item_size, size_t initial_capacity -) __attribute__((__nonnull__)); +); +/** + * Allocates an array list for storing elements with \p item_size bytes each. + * + * The list will use the cxDefaultAllocator and \em NO compare function. + * If you want to call functions that need a compare function, you have to + * set it immediately after creation or use cxArrayListCreate(). + * + * If \p item_size is CX_STORE_POINTERS, the created list will be created as if + * cxListStorePointers() was called immediately after creation. + * + * @param item_size the size of each element in bytes + * @param initial_capacity the initial number of elements the array can store + * @return the created list + */ +#define cxArrayListCreateSimple(item_size, initial_capacity) \ + cxArrayListCreate(NULL, NULL, item_size, initial_capacity) #ifdef __cplusplus } // extern "C"
--- a/src/ucx/cx/buffer.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/buffer.h Fri May 05 18:02:11 2023 +0200 @@ -149,11 +149,12 @@ * @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 this buffer shall use for automatic memory management + * @param allocator the allocator this buffer shall use for automatic + * memory management. If \c NULL, the default heap allocator will be used. * @param flags buffer features (see cx_buffer_s.flags) * @return zero on success, non-zero if a required allocation failed */ -__attribute__((__nonnull__(1, 4))) +__attribute__((__nonnull__(1))) int cxBufferInit( CxBuffer *buffer, void *space, @@ -163,16 +164,52 @@ ); /** + * 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. * * If the offset is positive, the contents are shifted to the right.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/ucx/cx/collection.h Fri May 05 18:02:11 2023 +0200 @@ -0,0 +1,138 @@ +/* + * 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)) + + +#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
--- a/src/ucx/cx/common.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/common.h Fri May 05 18:02:11 2023 +0200 @@ -89,9 +89,13 @@ /** Version constant which ensures to increase monotonically. */ #define UCX_VERSION (((UCX_VERSION_MAJOR)<<16)|UCX_VERSION_MINOR) +// Common Includes + #include <stdlib.h> #include <stddef.h> #include <stdbool.h> +#include <stdint.h> +#include <sys/types.h> /** * Function pointer compatible with fwrite-like functions. @@ -103,19 +107,18 @@ void * ); -#ifdef _WIN32 -#ifndef __WORDSIZE -#ifdef _WIN64 -#define __WORDSIZE 64 -#else -#define __WORDSIZE 32 -#endif -#endif // __WORDSIZE -#else // !_WIN32 +/** + * Function pointer compatible with fread-like functions. + */ +typedef size_t (*cx_read_func)( + void *, + size_t, + size_t, + void * +); -#include <sys/types.h> -#endif // _WIN32 +// Compiler specific stuff #ifndef __GNUC__ /** @@ -124,4 +127,15 @@ #define __attribute__(x) #endif +#ifdef _MSC_VER + +// fix missing ssize_t definition +#include <BaseTsd.h> +typedef SSIZE_T ssize_t; + +// fix missing _Thread_local support +#define _Thread_local __declspec(thread) + +#endif + #endif // UCX_COMMON_H
--- a/src/ucx/cx/compare.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/compare.h Fri May 05 18:02:11 2023 +0200 @@ -37,6 +37,8 @@ #ifndef UCX_COMPARE_H #define UCX_COMPARE_H +#include "common.h" + #ifdef __cplusplus extern "C" { #endif @@ -180,17 +182,36 @@ * @return -1, if *d1 is less than *d2, 0 if both are equal, * 1 if *d1 is greater than *d2 */ -int cx_cmp_double(void const *d1, void const *d2); +int cx_cmp_double( + void const *d1, + void const *d2 +); /** - * Compares two pointers. + * Compares the integer representation of two pointers. * - * @param ptr1 pointer one - * @param ptr2 pointer two - * @return -1 if ptr1 is less than ptr2, 0 if both are equal, - * 1 if ptr1 is greater than ptr2 + * @param ptr1 pointer to pointer one (intptr_t const*) + * @param ptr2 pointer to pointer two (intptr_t const*) + * @return -1 if *ptr1 is less than *ptr2, 0 if both are equal, + * 1 if *ptr1 is greater than *ptr2 */ -int cx_cmp_ptr(void const *ptr1, void const *ptr2); +int cx_cmp_intptr( + void const *ptr1, + void const *ptr2 +); + +/** + * Compares the unsigned integer representation of two pointers. + * + * @param ptr1 pointer to pointer one (uintptr_t const*) + * @param ptr2 pointer to pointer two (uintptr_t const*) + * @return -1 if *ptr1 is less than *ptr2, 0 if both are equal, + * 1 if *ptr1 is greater than *ptr2 + */ +int cx_cmp_uintptr( + void const *ptr1, + void const *ptr2 +); #ifdef __cplusplus } // extern "C"
--- a/src/ucx/cx/hash_key.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/hash_key.h Fri May 05 18:02:11 2023 +0200 @@ -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 @@ /** 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. */ @@ -121,6 +114,14 @@ size_t len ); +/** + * Computes a hash key from a UCX string. + * + * @param str the string + * @return the hash key + */ +#define cx_hash_key_cxstr(str) cx_hash_key((void*)(str).ptr, (str).length) + #ifdef __cplusplus } // extern "C" #endif
--- a/src/ucx/cx/hash_map.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/hash_map.h Fri May 05 18:02:11 2023 +0200 @@ -44,16 +44,7 @@ #endif /** Internal structure for an element of a hash map. */ -struct cx_hash_map_element_s { - /** The value data. */ - void *data; - - /** A pointer to the next element in the current bucket. */ - struct cx_hash_map_element_s *next; - - /** The corresponding key. */ - CxHashKey key; -}; +struct cx_hash_map_element_s; /** * Internal structure for a hash map. @@ -79,21 +70,42 @@ * * If \p buckets is zero, an implementation defined default will be used. * + * 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. * In other words, when the iterator is finished, \c index==size . * * @param allocator the allocator to use + * @param itemsize the size of one element * @param buckets the initial number of buckets in this hash map * @return a pointer to the new hash map */ __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 the 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. * * The load threshold is \c 0.75*buckets. If the element count exceeds the load
--- a/src/ucx/cx/iterator.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/iterator.h Fri May 05 18:02:11 2023 +0200 @@ -56,6 +56,12 @@ void *(*current)(void const *); /** + * Original implementation in case the function needs to be wrapped. + */ + __attribute__ ((__nonnull__)) + void *(*current_impl)(void const *); + + /** * Advances the iterator. */ __attribute__ ((__nonnull__)) @@ -68,7 +74,7 @@ bool (*flag_removal)(void *); /** - * Indicates whether this iterator is muting. + * Indicates whether this iterator may remove elements. */ bool mutating;
--- a/src/ucx/cx/linked_list.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/linked_list.h Fri May 05 18:02:11 2023 +0200 @@ -46,38 +46,45 @@ #endif /** + * Set this flag to true, if you want to disable the use of SBO for + * linked list swap operations. + */ +extern bool CX_DISABLE_LINKED_LIST_SWAP_SBO; + +/** * Allocates a linked list for storing elements with \p item_size bytes each. * - * @remark Elements added to the list are copied, therefore a possible destructor - * MUST NOT free the memory pointed to by its argument. + * If \p item_size is CX_STORE_POINTERS, the created list will be created as if + * cxListStorePointers() was called immediately after creation. * * @param allocator the allocator for allocating the list nodes + * (if \c NULL the cxDefaultAllocator will be used) * @param comparator the comparator for the elements + * (if \c NULL sort and find functions will not work) * @param item_size the size of each element in bytes * @return the created list */ CxList *cxLinkedListCreate( CxAllocator const *allocator, - CxListComparator comparator, + cx_compare_func comparator, size_t item_size -) __attribute__((__nonnull__)); +); /** - * Allocates a linked list for storing pointers. - * - * If you want to store the elements directly in this list, use cxLinkedListCreate(). + * Allocates a linked list for storing elements with \p item_size bytes each. * - * @remark Since only pointers are stored in this list, a possible destructor - * MAY free the memory pointed to by its argument in order to prevent memory leaks. + * The list will use cxDefaultAllocator and no comparator function. If you want + * to call functions that need a comparator, you must either set one immediately + * after list creation or use cxLinkedListCreate(). * - * @param allocator the allocator for allocating the list nodes - * @param comparator the comparator for the elements + * If \p item_size is CX_STORE_POINTERS, the created list will be created as if + * cxListStorePointers() was called immediately after creation. + * + * @param item_size the size of each element in bytes * @return the created list */ -CxList *cxPointerLinkedListCreate( - CxAllocator const *allocator, - CxListComparator comparator -) __attribute__((__nonnull__)); +#define cxLinkedListCreateSimple(item_size) \ + cxLinkedListCreate(NULL, NULL, item_size) /** * Finds the node at a certain index. @@ -109,18 +116,15 @@ * @param start a pointer to the start node * @param loc_advance the location of the pointer to advance * @param loc_data the location of the \c data pointer within your node struct - * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func. - * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. * @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, - bool follow_ptr, - CxListComparator cmp_func, + cx_compare_func cmp_func, void const *elem ) __attribute__((__nonnull__)); @@ -339,20 +343,13 @@ /** * Sorts a linked list based on a comparison function. * - * This function can work with linked lists of the following structures: + * This function can work with linked lists of the following structure: * \code * typedef struct node node; * struct node { * node* prev; * node* next; - * my_payload data; // in this case set follow_ptr = 0 - * } - * - * typedef struct ptr_node ptr_node; - * struct ptr_node { - * ptr_node* prev; - * ptr_node* next; - * my_payload* data; // in this case set follow_ptr = 1 + * my_payload data; * } * \endcode * @@ -363,8 +360,6 @@ * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present) * @param loc_next the location of a \c next pointer within your node struct (required) * @param loc_data the location of the \c data pointer within your node struct - * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func. - * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. * @param cmp_func the compare function defining the sort order */ void cx_linked_list_sort( @@ -373,26 +368,19 @@ ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, - bool follow_ptr, - CxListComparator cmp_func -) __attribute__((__nonnull__(1, 7))); + cx_compare_func cmp_func +) __attribute__((__nonnull__(1, 6))); /** * Compares two lists element wise. * - * The \c follow_ptr flags have the following meaning: if \c false, the pointer denoted by \p loc_data shall - * directly be passed to the \p cmp_func. - * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. - * * \note Both list must have the same structure. * * @param begin_left the begin of the left list (\c NULL denotes an empty list) * @param begin_right the begin of the right list (\c NULL denotes an empty list) * @param loc_advance the location of the pointer to advance * @param loc_data the location of the \c data pointer within your node struct - * @param follow_ptr_left indicates whether pointers in the left list shall be dereferenced - * @param follow_ptr_right indicates whether pointers in the right list shall be dereferenced * @param cmp_func the function to compare the elements * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the * right list, positive if the left list is larger than the right list, zero if both lists are equal. @@ -402,10 +390,8 @@ void const *begin_right, ptrdiff_t loc_advance, ptrdiff_t loc_data, - bool follow_ptr_left, - bool follow_ptr_right, - CxListComparator cmp_func -) __attribute__((__nonnull__(7))); + cx_compare_func cmp_func +) __attribute__((__nonnull__(5))); /** * Reverses the order of the nodes in a linked list.
--- a/src/ucx/cx/list.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/list.h Fri May 05 18:02:11 2023 +0200 @@ -38,22 +38,13 @@ #define UCX_LIST_H #include "common.h" -#include "allocator.h" -#include "iterator.h" +#include "collection.h" #ifdef __cplusplus extern "C" { #endif /** - * A comparator function comparing two list elements. - */ -typedef int(*CxListComparator)( - void const *left, - void const *right -); - -/** * List class type. */ typedef struct cx_list_class_s cx_list_class; @@ -62,54 +53,15 @@ * Structure for holding the base data of a list. */ struct cx_list_s { + CX_COLLECTION_MEMBERS /** * The list class definition. */ - cx_list_class *cl; - /** - * The allocator to use. - */ - CxAllocator const *allocator; - /** - * The comparator function for the elements. - */ - CxListComparator cmpfunc; + cx_list_class const *cl; /** - * 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). + * The actual implementation in case the list class is delegating. */ - 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; + cx_list_class const *climpl; }; /** @@ -122,29 +74,24 @@ void (*destructor)(struct cx_list_s *list); /** - * Member function for adding an element. + * Member function for inserting a single elements. + * Implementors SHOULD see to performant implementations for corner cases. */ - int (*add)( + int (*insert_element)( struct cx_list_s *list, - void const *elem + size_t index, + void const *data ); /** - * Member function for adding multiple elements. + * Member function for inserting multiple elements. + * Implementors SHOULD see to performant implementations for corner cases. */ - size_t (*add_array)( - struct cx_list_s *list, - void const *array, - size_t n - ); - - /** - * Member function for inserting an element. - */ - int (*insert)( + size_t (*insert_array)( struct cx_list_s *list, size_t index, - void const *elem + void const *data, + size_t n ); /** @@ -165,6 +112,20 @@ ); /** + * Member function for removing all elements. + */ + void (*clear)(struct cx_list_s *list); + + /** + * Member function for swapping two elements. + */ + int (*swap)( + struct cx_list_s *list, + size_t i, + size_t j + ); + + /** * Member function for element lookup. */ void *(*at)( @@ -175,7 +136,7 @@ /** * Member function for finding an element. */ - size_t (*find)( + ssize_t (*find)( struct cx_list_s const *list, void const *elem ); @@ -199,19 +160,12 @@ void (*reverse)(struct cx_list_s *list); /** - * Returns an iterator pointing to the specified index. + * Member function for returning an iterator pointing to the specified index. */ struct cx_iterator_s (*iterator)( struct cx_list_s const *list, - size_t index - ); - - /** - * Returns a mutating iterator pointing to the specified index. - */ - struct cx_mut_iterator_s (*mut_iterator)( - struct cx_list_s *list, - size_t index + size_t index, + bool backward ); }; @@ -221,6 +175,56 @@ typedef struct cx_list_s CxList; /** + * Advises the list to store copies of the objects (default mode of operation). + * + * Retrieving objects from this list will yield pointers to the copies stored + * within this list. + * + * @param list the list + * @see cxListStorePointers() + */ +__attribute__((__nonnull__)) +void cxListStoreObjects(CxList *list); + +/** + * Advises the list to only store pointers to the objects. + * + * Retrieving objects from this list will yield the original pointers stored. + * + * @note This function forcibly sets the element size to the size of a pointer. + * Invoking this function on a non-empty list that already stores copies of + * objects is undefined. + * + * @param list the list + * @see cxListStoreObjects() + */ +__attribute__((__nonnull__)) +void cxListStorePointers(CxList *list); + +/** + * Returns true, if this list is storing pointers instead of the actual data. + * + * @param list + * @return true, if this list is storing pointers + * @see cxListStorePointers() + */ +__attribute__((__nonnull__)) +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. * * @param list the list @@ -233,7 +237,7 @@ CxList *list, void const *elem ) { - return list->cl->add(list, elem); + return list->cl->insert_element(list, list->size, elem); } /** @@ -244,6 +248,9 @@ * If there is not enough memory to add all elements, the returned value is * less than \p n. * + * If this list is storing pointers instead of objects \p array is expected to + * be an array of pointers. + * * @param list the list * @param array a pointer to the elements to add * @param n the number of elements to add @@ -255,7 +262,7 @@ void const *array, size_t n ) { - return list->cl->add_array(list, array, n); + return list->cl->insert_array(list, list->size, array, n); } /** @@ -277,7 +284,36 @@ size_t index, void const *elem ) { - return list->cl->insert(list, index, elem); + return list->cl->insert_element(list, index, elem); +} + +/** + * Inserts multiple items to the list at the specified index. + * If \p index equals the list size, this is effectively cxListAddArray(). + * + * This method is usually more efficient than invoking cxListInsert() + * multiple times. + * + * If there is not enough memory to add all elements, the returned value is + * less than \p n. + * + * If this list is storing pointers instead of objects \p array is expected to + * be an array of pointers. + * + * @param list the list + * @param index the index where to add the elements + * @param array a pointer to the elements to add + * @param n the number of elements to add + * @return the number of added elements + */ +__attribute__((__nonnull__)) +static inline size_t cxListInsertArray( + CxList *list, + size_t index, + void const *array, + size_t n +) { + return list->cl->insert_array(list, index, array, n); } /** @@ -328,6 +364,10 @@ /** * Removes the element at the specified index. + * + * If an element destructor function is specified, it is called before + * removing the element. + * * @param list the list * @param index the index of the element * @return zero on success, non-zero if the index is out of bounds @@ -341,6 +381,39 @@ } /** + * Removes all elements from this list. + * + * If an element destructor function is specified, it is called for each + * element before removing them. + * + * @param list the list + */ +__attribute__((__nonnull__)) +static inline void cxListClear(CxList *list) { + list->cl->clear(list); +} + +/** + * Swaps two items in the list. + * + * Implementations should only allocate temporary memory for the swap, if + * it is necessary. + * + * @param list the list + * @param i the index of the first element + * @param j the index of the second element + * @return zero on success, non-zero if one of the indices is out of bounds + */ +__attribute__((__nonnull__)) +static inline int cxListSwap( + CxList *list, + size_t i, + size_t j +) { + return list->cl->swap(list, i, j); +} + +/** * Returns a pointer to the element at the specified index. * * @param list the list @@ -367,11 +440,30 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxListIterator( +static inline CxIterator cxListIteratorAt( CxList const *list, size_t index ) { - return list->cl->iterator(list, index); + return list->cl->iterator(list, index, false); +} + +/** + * Returns a backwards iterator pointing to the item at the specified index. + * + * The returned iterator is position-aware. + * + * If the index is out of range, a past-the-end iterator will be returned. + * + * @param list the list + * @param index the index where the iterator shall point at + * @return a new iterator + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxIterator cxListBackwardsIteratorAt( + CxList const *list, + size_t index +) { + return list->cl->iterator(list, index, true); } /** @@ -386,12 +478,28 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxMutIterator cxListMutIterator( +CxMutIterator cxListMutIteratorAt( CxList *list, size_t index -) { - return list->cl->mut_iterator(list, index); -} +); + +/** + * Returns a mutating backwards iterator pointing to the item at the + * specified index. + * + * The returned iterator is position-aware. + * + * If the index is out of range, a past-the-end iterator will be returned. + * + * @param list the list + * @param index the index where the iterator shall point at + * @return a new iterator + */ +__attribute__((__nonnull__, __warn_unused_result__)) +CxMutIterator cxListMutBackwardsIteratorAt( + CxList *list, + size_t index +); /** * Returns an iterator pointing to the first item of the list. @@ -404,8 +512,8 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxListBegin(CxList const *list) { - return list->cl->iterator(list, 0); +static inline CxIterator cxListIterator(CxList const *list) { + return list->cl->iterator(list, 0, false); } /** @@ -419,8 +527,39 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxMutIterator cxListBeginMut(CxList *list) { - return list->cl->mut_iterator(list, 0); +static inline CxMutIterator cxListMutIterator(CxList *list) { + return cxListMutIteratorAt(list, 0); +} + + +/** + * Returns a backwards iterator pointing to the last item of the list. + * + * The returned iterator is position-aware. + * + * If the list is empty, a past-the-end iterator will be returned. + * + * @param list the list + * @return a new iterator + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxIterator cxListBackwardsIterator(CxList const *list) { + return list->cl->iterator(list, list->size - 1, true); +} + +/** + * Returns a mutating backwards iterator pointing to the last item of the list. + * + * The returned iterator is position-aware. + * + * If the list is empty, a past-the-end iterator will be returned. + * + * @param list the list + * @return a new iterator + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxMutIterator cxListMutBackwardsIterator(CxList *list) { + return cxListMutBackwardsIteratorAt(list, list->size - 1); } /** @@ -430,10 +569,11 @@ * * @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 ) {
--- a/src/ucx/cx/map.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/map.h Fri May 05 18:02:11 2023 +0200 @@ -38,8 +38,8 @@ #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 @@ -57,13 +57,9 @@ /** 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; - // TODO: elemsize + a flag if values shall be copied to the map }; /** @@ -104,10 +100,11 @@ /** * Removes an element. */ - __attribute__((__nonnull__, __warn_unused_result__)) + __attribute__((__nonnull__)) void *(*remove)( CxMap *map, - CxHashKey key + CxHashKey key, + bool destroy ); /** @@ -161,6 +158,38 @@ void *value; }; +/** + * Advises the map to store copies of the objects (default mode of operation). + * + * Retrieving objects from this map will yield pointers to the copies stored + * within this list. + * + * @param map the map + * @see cxMapStorePointers() + */ +__attribute__((__nonnull__)) +static inline void cxMapStoreObjects(CxMap *map) { + map->store_pointer = false; +} + +/** + * Advises the map to only store pointers to the objects. + * + * Retrieving objects from this list will yield the original pointers stored. + * + * @note This function forcibly sets the element size to the size of a pointer. + * Invoking this function on a non-empty map that already stores copies of + * objects is undefined. + * + * @param map the map + * @see cxMapStoreObjects() + */ +__attribute__((__nonnull__)) +static inline void cxMapStorePointers(CxMap *map) { + map->store_pointer = true; + map->item_size = sizeof(void *); +} + /** * Deallocates the memory of the specified map. @@ -169,7 +198,6 @@ */ __attribute__((__nonnull__)) static inline void cxMapDestroy(CxMap *map) { - // TODO: likely to add auto-free feature for contents in the future map->cl->destructor(map); } @@ -184,52 +212,6 @@ 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. - * - * @param map the map - * @param key the key - * @return the removed value - */ -__attribute__((__nonnull__, __warn_unused_result__)) -static inline void *cxMapRemove( - CxMap *map, - CxHashKey key -) { - return map->cl->remove(map, key); -} // TODO: set-like map operations (union, intersect, difference) @@ -330,8 +312,834 @@ return map->cl->mut_iterator(map); } -#ifdef __cplusplus +#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); +} + + +/** + * 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); +} + +/** + * 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); } -#endif + +#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); +} -#endif // UCX_MAP_H \ No newline at end of file +/** + * 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
--- a/src/ucx/cx/mempool.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/mempool.h Fri May 05 18:02:11 2023 +0200 @@ -37,6 +37,7 @@ #ifndef UCX_MEMPOOL_H #define UCX_MEMPOOL_H +#include "common.h" #include "allocator.h" #ifdef __cplusplus
--- a/src/ucx/cx/printf.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/printf.h Fri May 05 18:02:11 2023 +0200 @@ -55,7 +55,13 @@ * @param ... additional arguments * @return the total number of bytes written */ -int cx_fprintf(void *stream, cx_write_func wfc, char const *fmt, ...); +__attribute__((__nonnull__(1, 2, 3), __format__(printf, 3, 4))) +int cx_fprintf( + void *stream, + cx_write_func wfc, + char const *fmt, + ... +); /** * A \c vfprintf like function which writes the output to a stream by @@ -68,7 +74,13 @@ * @return the total number of bytes written * @see cx_fprintf() */ -int cx_vfprintf(void *stream, cx_write_func wfc, char const *fmt, va_list ap); +__attribute__((__nonnull__)) +int cx_vfprintf( + void *stream, + cx_write_func wfc, + char const *fmt, + va_list ap +); /** * A \c asprintf like function which allocates space for a string @@ -82,7 +94,12 @@ * @return the formatted string * @see cx_strfree_a() */ -cxmutstr cx_asprintf_a(CxAllocator *allocator, char const *fmt, ...); +__attribute__((__nonnull__(1, 2), __format__(printf, 2, 3))) +cxmutstr cx_asprintf_a( + CxAllocator const *allocator, + char const *fmt, + ... +); /** * A \c asprintf like function which allocates space for a string @@ -110,7 +127,12 @@ * @return the formatted string * @see cx_asprintf_a() */ -cxmutstr cx_vasprintf_a(CxAllocator *allocator, char const *fmt, va_list ap); +__attribute__((__nonnull__)) +cxmutstr cx_vasprintf_a( + CxAllocator const *allocator, + char const *fmt, + va_list ap +); /** * A \c vasprintf like function which allocates space for a string @@ -128,7 +150,7 @@ /** * A \c printf like function which writes the output to a CxBuffer. * - * @param buffer the buffer the data is written to + * @param buffer a pointer to the buffer the data is written to * @param fmt the format string * @param ... additional arguments * @return the total number of bytes written
--- a/src/ucx/cx/string.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/string.h Fri May 05 18:02:11 2023 +0200 @@ -79,16 +79,77 @@ typedef struct cx_string_s cxstring; /** + * Context for string tokenizing. + */ +struct cx_strtok_ctx_s { + /** + * The string to tokenize. + */ + cxstring str; + /** + * The primary delimiter. + */ + cxstring delim; + /** + * Optional array of more delimiters. + */ + cxstring const *delim_more; + /** + * Length of the array containing more delimiters. + */ + size_t delim_more_count; + /** + * Position of the currently active token in the source string. + */ + size_t pos; + /** + * Position of next delimiter in the source string. + * + * If the tokenizer has not yet returned a token, the content of this field + * is undefined. If the tokenizer reached the end of the string, this field + * contains the length of the source string. + */ + size_t delim_pos; + /** + * The position of the next token in the source string. + */ + size_t next_pos; + /** + * The number of already found tokens. + */ + size_t found; + /** + * The maximum number of tokens that shall be returned. + */ + size_t limit; +}; + +/** + * A string tokenizing context. + */ +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. * * The argument MUST be a string (const char*) \em literal. * * @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 @@ -214,7 +275,7 @@ */ __attribute__((__nonnull__)) void cx_strfree_a( - CxAllocator *alloc, + CxAllocator const *alloc, cxmutstr *str ); @@ -235,28 +296,50 @@ ); /** - * 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. @@ -264,12 +347,32 @@ * \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. @@ -522,7 +625,7 @@ */ __attribute__((__warn_unused_result__, __nonnull__)) size_t cx_strsplit_a( - CxAllocator *allocator, + CxAllocator const *allocator, cxstring string, cxstring delim, size_t limit, @@ -571,7 +674,7 @@ */ __attribute__((__warn_unused_result__, __nonnull__)) size_t cx_strsplit_ma( - CxAllocator *allocator, + CxAllocator const *allocator, cxmutstr string, cxstring delim, size_t limit, @@ -606,6 +709,38 @@ cxstring s2 ); +/** + * Compares two strings. + * + * This function has a compatible signature for the use as a cx_compare_func. + * + * @param s1 the first string + * @param s2 the second string + * @return negative if \p s1 is smaller than \p s2, positive if \p s1 is larger + * than \p s2, zero if both strings equal + */ +__attribute__((__warn_unused_result__, __nonnull__)) +int cx_strcmp_p( + void const *s1, + void const *s2 +); + +/** + * Compares two strings ignoring case. + * + * This function has a compatible signature for the use as a cx_compare_func. + * + * @param s1 the first string + * @param s2 the second string + * @return negative if \p s1 is smaller than \p s2, positive if \p s1 is larger + * than \p s2, zero if both strings equal ignoring case + */ +__attribute__((__warn_unused_result__, __nonnull__)) +int cx_strcasecmp_p( + void const *s1, + void const *s2 +); + /** * Creates a duplicate of the specified string. @@ -621,7 +756,7 @@ */ __attribute__((__warn_unused_result__, __nonnull__)) cxmutstr cx_strdup_a( - CxAllocator *allocator, + CxAllocator const *allocator, cxstring string ); @@ -639,6 +774,35 @@ */ #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. * @@ -760,7 +924,7 @@ */ __attribute__((__warn_unused_result__, __nonnull__)) cxmutstr cx_strreplacen_a( - CxAllocator *allocator, + CxAllocator const *allocator, cxstring str, cxstring pattern, cxstring replacement, @@ -828,6 +992,85 @@ #define cx_strreplace(str, pattern, replacement) \ cx_strreplacen_a(cxDefaultAllocator, str, pattern, replacement, SIZE_MAX) +/** + * Creates a string tokenization context. + * + * @param str the string to tokenize + * @param delim the delimiter (must not be empty) + * @param limit the maximum number of tokens that shall be returned + * @return a new string tokenization context + */ +__attribute__((__warn_unused_result__)) +CxStrtokCtx cx_strtok( + cxstring str, + cxstring delim, + size_t limit +); + +/** +* Creates a string tokenization context for a mutable string. +* +* @param str the string to tokenize +* @param delim the delimiter (must not be empty) +* @param limit the maximum number of tokens that shall be returned +* @return a new string tokenization context +*/ +__attribute__((__warn_unused_result__)) +CxStrtokCtx cx_strtok_m( + cxmutstr str, + cxstring delim, + size_t limit +); + +/** + * Returns the next token. + * + * The token will point to the source string. + * + * @param ctx the tokenization context + * @param token a pointer to memory where the next token shall be stored + * @return true if successful, false if the limit or the end of the string + * has been reached + */ +__attribute__((__warn_unused_result__, __nonnull__)) +bool cx_strtok_next( + CxStrtokCtx *ctx, + cxstring *token +); + +/** + * Returns the next token of a mutable string. + * + * The token will point to the source string. + * If the context was not initialized over a mutable string, modifying + * the data of the returned token is undefined behavior. + * + * @param ctx the tokenization context + * @param token a pointer to memory where the next token shall be stored + * @return true if successful, false if the limit or the end of the string + * has been reached + */ +__attribute__((__warn_unused_result__, __nonnull__)) +bool cx_strtok_next_m( + CxStrtokCtx *ctx, + cxmutstr *token +); + +/** + * Defines an array of more delimiters for the specified tokenization context. + * + * @param ctx the tokenization context + * @param delim array of more delimiters + * @param count number of elements in the array + */ +__attribute__((__nonnull__)) +void cx_strtok_delim( + CxStrtokCtx *ctx, + cxstring const *delim, + size_t count +); + + #ifdef __cplusplus } // extern "C" #endif
--- a/src/ucx/cx/utils.h Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/cx/utils.h Fri May 05 18:02:11 2023 +0200 @@ -51,14 +51,22 @@ */ #define cx_for_n(varname, n) for (size_t varname = 0 ; (varname) < (n) ; (varname)++) +/** + * Convenience macro for swapping two pointers. + */ +#ifdef __cplusplus +#define cx_swap_ptr(left, right) do {auto cx_tmp_swap_var = left; left = right; right = cx_tmp_swap_var;} while(0) +#else +#define cx_swap_ptr(left, right) do {void *cx_tmp_swap_var = left; left = right; right = cx_tmp_swap_var;} while(0) +#endif + // cx_szmul() definition #if (__GNUC__ >= 5 || defined(__clang__)) && !defined(CX_NO_SZMUL_BUILTIN) #define CX_SZMUL_BUILTIN -#if __WORDSIZE == 32 /** - * Alias for \c __builtin_umul_overflow. + * Alias for \c __builtin_mul_overflow. * * Performs a multiplication of size_t values and checks for overflow. * @@ -69,22 +77,7 @@ * @return zero, if no overflow occurred and the result is correct, non-zero * otherwise */ -#define cx_szmul(a, b, result) __builtin_umul_overflow(a, b, result) -#else // __WORDSIZE != 32 -/** - * Alias for \c __builtin_umull_overflow. - * - * Performs a multiplication of size_t values and checks for overflow. - * - * @param a first operand - * @param b second operand - * @param result a pointer to a size_t, where the result should - * be stored - * @return zero, if no overflow occurred and the result is correct, non-zero - * otherwise - */ -#define cx_szmul(a, b, result) __builtin_umull_overflow(a, b, result) -#endif // __WORDSIZE +#define cx_szmul(a, b, result) __builtin_mul_overflow(a, b, result) #else // no GNUC or clang bultin @@ -114,7 +107,87 @@ */ int cx_szmul_impl(size_t a, size_t b, size_t *result); -#endif +#endif // cx_szmul + + +/** + * Reads data from a stream and writes it to another stream. + * + * @param src the source stream + * @param dest the destination stream + * @param rfnc the read function + * @param wfnc the write function + * @param buf a pointer to the copy buffer or \c NULL if a buffer + * shall be implicitly created on the heap + * @param bufsize the size of the copy buffer - if \p buf is \c NULL you can + * set this to zero to let the implementation decide + * @param n the maximum number of bytes that shall be copied. + * If this is larger than \p bufsize, the content is copied over multiple + * iterations. + * @return the total number of bytes copied + */ +__attribute__((__nonnull__(1, 2, 3, 4))) +size_t cx_stream_bncopy( + void *src, + void *dest, + cx_read_func rfnc, + cx_write_func wfnc, + char *buf, + size_t bufsize, + size_t n +); + +/** + * Reads data from a stream and writes it to another stream. + * + * @param src the source stream + * @param dest the destination stream + * @param rfnc the read function + * @param wfnc the write function + * @param buf a pointer to the copy buffer or \c NULL if a buffer + * shall be implicitly created on the heap + * @param bufsize the size of the copy buffer - if \p buf is \c NULL you can + * set this to zero to let the implementation decide + * @return total number of bytes copied + */ +#define cx_stream_bcopy(src, dest, rfnc, wfnc, buf, bufsize) \ + cx_stream_bncopy(src, dest, rfnc, wfnc, buf, bufsize, SIZE_MAX) + +/** + * Reads data from a stream and writes it to another stream. + * + * The data is temporarily stored in a stack allocated buffer. + * + * @param src the source stream + * @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 + */ +__attribute__((__nonnull__)) +size_t cx_stream_ncopy( + void *src, + void *dest, + cx_read_func rfnc, + cx_write_func wfnc, + size_t n +); + +/** + * Reads data from a stream and writes it to another stream. + * + * The data is temporarily stored in a stack allocated buffer. + * + * @param src the source stream + * @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) \ + cx_stream_ncopy(src, dest, rfnc, wfnc, SIZE_MAX) #ifdef __cplusplus }
--- a/src/ucx/hash_key.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/hash_key.c Fri May 05 18:02:11 2023 +0200 @@ -30,7 +30,7 @@ #include <string.h> 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 @@ h *= m; __attribute__((__fallthrough__)); default: // do nothing - ; + ; } h ^= h >> 13; @@ -83,7 +83,7 @@ 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 @@ 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 @@ size_t len ) { CxHashKey key; - key.data.cobj = obj; + key.data = obj; key.len = len; cx_hash_murmur(&key); return key;
--- a/src/ucx/hash_map.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/hash_map.c Fri May 05 18:02:11 2023 +0200 @@ -30,6 +30,17 @@ #include "cx/hash_map.h" #include "cx/utils.h" +struct cx_hash_map_element_s { + /** A pointer to the next element in the current bucket. */ + struct cx_hash_map_element_s *next; + + /** The corresponding key. */ + CxHashKey key; + + /** The value data. */ + char data[]; +}; + static void cx_hash_map_clear(struct cx_map_s *map) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; cx_for_n(i, hash_map->bucket_count) { @@ -37,8 +48,10 @@ 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 @@ -69,7 +82,7 @@ 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) { @@ -87,27 +100,37 @@ } 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 - elm->data = value; + if (map->store_pointer) { + memcpy(elm->data, &value, sizeof(void *)); + } else { + 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)); + struct cx_hash_map_element_s *e = cxMalloc( + allocator, + sizeof(struct cx_hash_map_element_s) + map->item_size + ); if (e == NULL) { return -1; } // write the value - // TODO: depending on future map features, we may want to copy here - e->data = value; + if (map->store_pointer) { + memcpy(e->data, &value, sizeof(void *)); + } else { + memcpy(e->data, value, map->item_size); + } // copy the key void *kd = cxMalloc(allocator, key.len); 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; @@ -139,7 +162,7 @@ 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--; @@ -151,12 +174,14 @@ * @param map the map * @param key the key to look up * @param remove flag indicating whether the looked up entry shall be removed - * @return the value corresponding to the key or \c NULL + * @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; @@ -171,8 +196,17 @@ 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) { - void *data = elm->data; + if (memcmp(elm->key.data, key.data, key.len) == 0) { + void *data = NULL; + 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); } @@ -190,15 +224,16 @@ 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) { @@ -215,9 +250,13 @@ 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; - // TODO: return a pointer to data if this map is storing copies - return elm->data; + if (map->base.store_pointer) { + return *(void **) elm->data; + } else { + return elm->data; + } } static bool cx_hash_map_iter_valid(void const *it) { @@ -250,6 +289,9 @@ } } + // destroy + cx_invoke_destructor((struct cx_map_s *) map, elm->data); + // unlink cx_hash_map_unlink(map, iter->slot, prev, elm); @@ -274,8 +316,11 @@ iter->kv_data.value = NULL; } else { iter->kv_data.key = &elm->key; - // TODO: pointer to data if this map is storing copies - iter->kv_data.value = elm->data; + if (map->base.store_pointer) { + iter->kv_data.value = *(void **) elm->data; + } else { + iter->kv_data.value = elm->data; + } } } @@ -302,7 +347,7 @@ iter.slot = 0; iter.index = 0; - + if (map->size > 0) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; struct cx_hash_map_element_s *elm = hash_map->buckets[0]; @@ -311,8 +356,11 @@ } iter.elem_handle = elm; iter.kv_data.key = &elm->key; - // TODO: pointer to data if this map is storing copies - iter.kv_data.value = elm->data; + if (map->store_pointer) { + iter.kv_data.value = *(void **) elm->data; + } else { + iter.kv_data.value = elm->data; + } } else { iter.elem_handle = NULL; iter.kv_data.key = NULL; @@ -371,7 +419,8 @@ }; CxMap *cxHashMapCreate( - CxAllocator *allocator, + CxAllocator const *allocator, + size_t itemsize, size_t buckets ) { if (buckets == 0) { @@ -379,12 +428,14 @@ 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; @@ -393,7 +444,14 @@ // initialize base members map->base.cl = &cx_hash_map_class; map->base.allocator = allocator; - map->base.size = 0; + + if (itemsize > 0) { + map->base.store_pointer = false; + map->base.item_size = itemsize; + } else { + map->base.store_pointer = true; + map->base.item_size = sizeof(void *); + } return (CxMap *) map; } @@ -403,8 +461,10 @@ 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; @@ -420,7 +480,8 @@ // 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; }
--- a/src/ucx/linked_list.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/linked_list.c Fri May 05 18:02:11 2023 +0200 @@ -28,7 +28,6 @@ #include "cx/linked_list.h" #include "cx/utils.h" -#include <stdint.h> #include <string.h> #include <assert.h> @@ -38,8 +37,7 @@ #define ll_prev(node) CX_LL_PTR(node, loc_prev) #define ll_next(node) CX_LL_PTR(node, loc_next) #define ll_advance(node) CX_LL_PTR(node, loc_advance) -#define ll_data_f(node, follow_ptr) ((follow_ptr)?CX_LL_PTR(node, loc_data):(((char*)(node))+loc_data)) -#define ll_data(node) ll_data_f(node,follow_ptr) +#define ll_data(node) (((char*)(node))+loc_data) void *cx_linked_list_at( void const *start, @@ -58,12 +56,11 @@ 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, - bool follow_ptr, - CxListComparator cmp_func, + cx_compare_func cmp_func, void const *elem ) { assert(start != NULL); @@ -72,7 +69,7 @@ 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) { @@ -81,7 +78,7 @@ node = ll_advance(node); index++; } while (node != NULL); - return index; + return -1; } void *cx_linked_list_first( @@ -282,20 +279,23 @@ return size; } +#ifndef CX_LINKED_LIST_SORT_SBO_SIZE +#define CX_LINKED_LIST_SORT_SBO_SIZE 1024 +#endif + static void *cx_linked_list_sort_merge( ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, - bool follow_ptr, size_t length, void *ls, void *le, void *re, - CxListComparator cmp_func + cx_compare_func cmp_func ) { - const size_t sbo_len = 1024; - void *sbo[sbo_len]; - void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo; + void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; + void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? + malloc(sizeof(void *) * length) : sbo; if (sorted == NULL) abort(); void *rc, *lc; @@ -343,8 +343,7 @@ ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, - bool follow_ptr, - CxListComparator cmp_func + cx_compare_func cmp_func ) { assert(begin != NULL); assert(loc_next >= 0); @@ -378,17 +377,17 @@ 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, follow_ptr, + void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, ln + rn, ls, le, re, cmp_func); // Something left? Sort it! size_t remainder_length = cx_linked_list_size(re, loc_next); if (remainder_length > 0) { void *remainder = re; - cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func); + 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, follow_ptr, + *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, ln + rn + remainder_length, sorted, remainder, NULL, cmp_func); } else { @@ -404,15 +403,13 @@ void const *begin_right, ptrdiff_t loc_advance, ptrdiff_t loc_data, - bool follow_ptr_left, - bool follow_ptr_right, - CxListComparator cmp_func + cx_compare_func cmp_func ) { void const *left = begin_left, *right = begin_right; while (left != NULL && right != NULL) { - void const *left_data = ll_data_f(left, follow_ptr_left); - void const *right_data = ll_data_f(right, follow_ptr_right); + void const *left_data = ll_data(left); + void const *right_data = ll_data(right); int result = cmp_func(left_data, right_data); if (result != 0) return result; left = ll_advance(left); @@ -457,6 +454,8 @@ // HIGH LEVEL LINKED LIST IMPLEMENTATION +bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false; + typedef struct cx_linked_list_node cx_linked_list_node; struct cx_linked_list_node { cx_linked_list_node *prev; @@ -472,7 +471,6 @@ struct cx_list_s base; cx_linked_list_node *begin; cx_linked_list_node *end; - bool follow_ptr; } cx_linked_list; static cx_linked_list_node *cx_ll_node_at( @@ -496,14 +494,14 @@ // 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; @@ -518,55 +516,47 @@ return 0; } -static int cx_ll_insert( +static size_t cx_ll_insert_array( struct cx_list_s *list, size_t index, - void const *elem + void const *array, + size_t n ) { - // out-of bounds check - if (index > list->size) return 1; + // out-of bounds and corner case check + if (index > list->size || n == 0) return 0; // find position efficiently cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); - // perform insert - return cx_ll_insert_at(list, node, elem); -} + // perform first insert + if (0 != cx_ll_insert_at(list, node, array)) { + return 1; + } + + // is there more? + if (n == 1) return 1; -static int cx_ll_add( - struct cx_list_s *list, - void const *elem -) { - return cx_ll_insert(list, list->size, elem); -} + // we now know exactly where we are + node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; -static size_t cx_ll_add_array( - struct cx_list_s *list, - void const *array, - size_t n -) { - // TODO: redirect to cx_ll_insert_array - cx_for_n (i, n) { - if (cx_ll_add(list, ((char const *) array) + i * list->itemsize)) { + // 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->item_size; + if (0 != cx_ll_insert_at(list, node, source)) { return i; } + node = node->next; } return n; } -static int cx_pll_insert( +static int cx_ll_insert_element( struct cx_list_s *list, size_t index, - void const *elem + void const *element ) { - return cx_ll_insert(list, index, &elem); -} - -static int cx_pll_add( - struct cx_list_s *list, - void const *elem -) { - return cx_ll_insert(list, list->size, &elem); + return 1 != cx_ll_insert_array(list, index, element, 1); } static int cx_ll_remove( @@ -579,6 +569,9 @@ // out-of-bounds check if (node == NULL) return 1; + // element destruction + cx_invoke_destructor(list, node->payload); + // remove cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); @@ -592,6 +585,141 @@ return 0; } +static void cx_ll_clear(struct cx_list_s *list) { + if (list->size == 0) return; + + cx_linked_list *ll = (cx_linked_list *) list; + cx_linked_list_node *node = ll->begin; + 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 +#endif + +static int cx_ll_swap( + struct cx_list_s *list, + size_t i, + size_t j +) { + if (i >= list->size || j >= list->size) return 1; + if (i == j) return 0; + + // perform an optimized search that finds both elements in one run + cx_linked_list *ll = (cx_linked_list *) list; + size_t mid = list->size / 2; + size_t left, right; + if (i < j) { + left = i; + right = j; + } else { + left = j; + right = i; + } + cx_linked_list_node *nleft, *nright; + if (left < mid && right < mid) { + // case 1: both items left from mid + nleft = cx_ll_node_at(ll, left); + nright = nleft; + for (size_t c = left; c < right; c++) { + nright = nright->next; + } + } else if (left >= mid && right >= mid) { + // case 2: both items right from mid + nright = cx_ll_node_at(ll, right); + nleft = nright; + for (size_t c = right; c > left; c--) { + nleft = nleft->prev; + } + } else { + // case 3: one item left, one item right + + // chose the closest to begin / end + size_t closest; + size_t other; + size_t diff2boundary = list->size - right - 1; + if (left <= diff2boundary) { + closest = left; + other = right; + nleft = cx_ll_node_at(ll, left); + } else { + closest = right; + other = left; + diff2boundary = left; + nright = cx_ll_node_at(ll, right); + } + + // is other element closer to us or closer to boundary? + if (right - left <= diff2boundary) { + // search other element starting from already found element + if (closest == left) { + nright = nleft; + for (size_t c = left; c < right; c++) { + nright = nright->next; + } + } else { + nleft = nright; + for (size_t c = right; c > left; c--) { + nleft = nleft->prev; + } + } + } else { + // search other element starting at the boundary + if (closest == left) { + nright = cx_ll_node_at(ll, other); + } else { + nleft = cx_ll_node_at(ll, other); + } + } + } + + 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; + cx_linked_list_node *midend = nright->prev; + + if (prev == NULL) { + ll->begin = nright; + } else { + prev->next = nright; + } + nright->prev = prev; + if (midstart == nright) { + // special case: both nodes are adjacent + nright->next = nleft; + nleft->prev = nright; + } else { + // likely case: a chain is between the two nodes + nright->next = midstart; + midstart->prev = nright; + midend->next = nleft; + nleft->prev = midend; + } + nleft->next = next; + if (next == NULL) { + ll->end = nleft; + } else { + next->prev = nleft; + } + } else { + // swap payloads to avoid relinking + char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; + memcpy(buf, nleft->payload, list->item_size); + memcpy(nleft->payload, nright->payload, list->item_size); + memcpy(nright->payload, buf, list->item_size); + } + + return 0; +} + static void *cx_ll_at( struct cx_list_s const *list, size_t index @@ -601,30 +729,20 @@ return node == NULL ? NULL : node->payload; } -static void *cx_pll_at( - struct cx_list_s const *list, - size_t index -) { - cx_linked_list *ll = (cx_linked_list *) list; - cx_linked_list_node *node = cx_ll_node_at(ll, index); - return node == NULL ? NULL : *(void **) node->payload; -} - -static size_t cx_ll_find( +static ssize_t cx_ll_find( struct cx_list_s const *list, void const *elem ) { - cx_linked_list *ll = (cx_linked_list *) list; return cx_linked_list_find(((cx_linked_list *) list)->begin, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, - ll->follow_ptr, list->cmpfunc, elem); + list->cmpfunc, elem); } static void cx_ll_sort(struct cx_list_s *list) { cx_linked_list *ll = (cx_linked_list *) list; cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, - ll->follow_ptr, list->cmpfunc); + list->cmpfunc); } static void cx_ll_reverse(struct cx_list_s *list) { @@ -640,7 +758,7 @@ cx_linked_list *right = (cx_linked_list *) other; return cx_linked_list_compare(left->begin, right->begin, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, - left->follow_ptr, right->follow_ptr, list->cmpfunc); + list->cmpfunc); } static bool cx_ll_iter_valid(void const *it) { @@ -653,13 +771,15 @@ if (itbase->remove) { itbase->remove = false; struct cx_mut_iterator_s *iter = it; + struct cx_list_s *list = iter->src_handle; cx_linked_list *ll = iter->src_handle; cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->next; + 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); - ll->base.size--; - cxFree(ll->base.allocator, node); + list->size--; + cxFree(list->allocator, node); } else { struct cx_iterator_s *iter = it; iter->index++; @@ -668,18 +788,35 @@ } } +static void cx_ll_iter_prev(void *it) { + struct cx_iterator_base_s *itbase = it; + if (itbase->remove) { + itbase->remove = false; + struct cx_mut_iterator_s *iter = it; + struct cx_list_s *list = iter->src_handle; + cx_linked_list *ll = iter->src_handle; + cx_linked_list_node *node = iter->elem_handle; + iter->elem_handle = node->prev; + iter->index--; + 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--; + cxFree(list->allocator, node); + } else { + struct cx_iterator_s *iter = it; + iter->index--; + cx_linked_list_node *node = iter->elem_handle; + iter->elem_handle = node->prev; + } +} + static void *cx_ll_iter_current(void const *it) { struct cx_iterator_s const *iter = it; cx_linked_list_node *node = iter->elem_handle; return node->payload; } -static void *cx_pll_iter_current(void const *it) { - struct cx_iterator_s const *iter = it; - cx_linked_list_node *node = iter->elem_handle; - return *(void **) node->payload; -} - static bool cx_ll_iter_flag_rm(void *it) { struct cx_iterator_base_s *iter = it; if (iter->mutating) { @@ -692,7 +829,8 @@ static CxIterator cx_ll_iterator( struct cx_list_s const *list, - size_t index + size_t index, + bool backwards ) { CxIterator iter; iter.index = index; @@ -700,44 +838,13 @@ iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); iter.base.valid = cx_ll_iter_valid; iter.base.current = cx_ll_iter_current; - iter.base.next = cx_ll_iter_next; + iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; iter.base.flag_removal = cx_ll_iter_flag_rm; iter.base.mutating = false; iter.base.remove = false; return iter; } -static CxIterator cx_pll_iterator( - struct cx_list_s const *list, - size_t index -) { - CxIterator iter = cx_ll_iterator(list, index); - iter.base.current = cx_pll_iter_current; - return iter; -} - -static CxMutIterator cx_ll_mut_iterator( - struct cx_list_s *list, - size_t index -) { - CxIterator it = cx_ll_iterator(list, index); - 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_pll_mut_iterator( - struct cx_list_s *list, - size_t index -) { - CxMutIterator iter = cx_ll_mut_iterator(list, index); - iter.base.current = cx_pll_iter_current; - return iter; -} - static int cx_ll_insert_iter( CxMutIterator *iter, void const *elem, @@ -752,20 +859,12 @@ iter->index += prepend * (0 == result); return result; } else { - int result = cx_ll_insert(list, list->size, elem); + int result = cx_ll_insert_element(list, list->size, elem); iter->index = list->size; return result; } } -static int cx_pll_insert_iter( - CxMutIterator *iter, - void const *elem, - int prepend -) { - return cx_ll_insert_iter(iter, &elem, prepend); -} - static void cx_ll_destructor(CxList *list) { cx_linked_list *ll = (cx_linked_list *) list; @@ -780,67 +879,41 @@ static cx_list_class cx_linked_list_class = { cx_ll_destructor, - cx_ll_add, - cx_ll_add_array, - cx_ll_insert, + cx_ll_insert_element, + cx_ll_insert_array, cx_ll_insert_iter, cx_ll_remove, + cx_ll_clear, + cx_ll_swap, cx_ll_at, cx_ll_find, cx_ll_sort, cx_ll_compare, cx_ll_reverse, cx_ll_iterator, - cx_ll_mut_iterator, -}; - -static cx_list_class cx_pointer_linked_list_class = { - cx_ll_destructor, - cx_pll_add, - cx_ll_add_array, - cx_pll_insert, - cx_pll_insert_iter, - cx_ll_remove, - cx_pll_at, - cx_ll_find, - cx_ll_sort, - cx_ll_compare, - cx_ll_reverse, - cx_pll_iterator, - cx_pll_mut_iterator, }; CxList *cxLinkedListCreate( CxAllocator const *allocator, - CxListComparator comparator, + cx_compare_func comparator, size_t item_size ) { + if (allocator == NULL) { + allocator = cxDefaultAllocator; + } + cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); if (list == NULL) return NULL; - list->follow_ptr = false; list->base.cl = &cx_linked_list_class; list->base.allocator = allocator; list->base.cmpfunc = comparator; - list->base.itemsize = item_size; - list->base.capacity = SIZE_MAX; + + if (item_size > 0) { + list->base.item_size = item_size; + } else { + cxListStorePointers((CxList *) list); + } return (CxList *) list; } - -CxList *cxPointerLinkedListCreate( - CxAllocator const *allocator, - CxListComparator comparator -) { - cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); - if (list == NULL) return NULL; - - list->follow_ptr = true; - list->base.cl = &cx_pointer_linked_list_class; - list->base.allocator = allocator; - list->base.cmpfunc = comparator; - list->base.itemsize = sizeof(void *); - list->base.capacity = SIZE_MAX; - - return (CxList *) list; -}
--- a/src/ucx/list.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/list.c Fri May 05 18:02:11 2023 +0200 @@ -28,24 +28,187 @@ #include "cx/list.h" +#include <string.h> + +// <editor-fold desc="Store Pointers Functionality"> + +static _Thread_local cx_compare_func cx_pl_cmpfunc_impl; + +static int cx_pl_cmpfunc( + void const *l, + void const *r +) { + void *const *lptr = l; + void *const *rptr = r; + void const *left = lptr == NULL ? NULL : *lptr; + void const *right = rptr == NULL ? NULL : *rptr; + return cx_pl_cmpfunc_impl(left, right); +} + +static void cx_pl_hack_cmpfunc(struct cx_list_s const *list) { + // cast away const - this is the hacky thing + struct cx_list_s *l = (struct cx_list_s *) list; + cx_pl_cmpfunc_impl = l->cmpfunc; + l->cmpfunc = cx_pl_cmpfunc; +} + +static void cx_pl_unhack_cmpfunc(struct cx_list_s const *list) { + // cast away const - this is the hacky thing + struct cx_list_s *l = (struct cx_list_s *) list; + l->cmpfunc = cx_pl_cmpfunc_impl; +} + +static void cx_pl_destructor(struct cx_list_s *list) { + list->climpl->destructor(list); +} + +static int cx_pl_insert_element( + struct cx_list_s *list, + size_t index, + void const *element +) { + return list->climpl->insert_element(list, index, &element); +} + +static size_t cx_pl_insert_array( + struct cx_list_s *list, + size_t index, + void const *array, + size_t n +) { + return list->climpl->insert_array(list, index, array, n); +} + +static int cx_pl_insert_iter( + struct cx_mut_iterator_s *iter, + void const *elem, + int prepend +) { + struct cx_list_s *list = iter->src_handle; + return list->climpl->insert_iter(iter, &elem, prepend); +} + +static int cx_pl_remove( + struct cx_list_s *list, + size_t index +) { + return list->climpl->remove(list, index); +} + +static void cx_pl_clear(struct cx_list_s *list) { + list->climpl->clear(list); +} + +static int cx_pl_swap( + struct cx_list_s *list, + size_t i, + size_t j +) { + return list->climpl->swap(list, i, j); +} + +static void *cx_pl_at( + struct cx_list_s const *list, + size_t index +) { + void **ptr = list->climpl->at(list, index); + return ptr == NULL ? NULL : *ptr; +} + +static ssize_t cx_pl_find( + struct cx_list_s const *list, + void const *elem +) { + cx_pl_hack_cmpfunc(list); + ssize_t ret = list->climpl->find(list, &elem); + cx_pl_unhack_cmpfunc(list); + return ret; +} + +static void cx_pl_sort(struct cx_list_s *list) { + cx_pl_hack_cmpfunc(list); + list->climpl->sort(list); + cx_pl_unhack_cmpfunc(list); +} + +static int cx_pl_compare( + struct cx_list_s const *list, + struct cx_list_s const *other +) { + cx_pl_hack_cmpfunc(list); + int ret = list->climpl->compare(list, other); + cx_pl_unhack_cmpfunc(list); + return ret; +} + +static void cx_pl_reverse(struct cx_list_s *list) { + list->climpl->reverse(list); +} + +static void *cx_pl_iter_current(void const *it) { + struct cx_iterator_s const *iter = it; + void **ptr = iter->base.current_impl(it); + return ptr == NULL ? NULL : *ptr; +} + +static struct cx_iterator_s cx_pl_iterator( + struct cx_list_s const *list, + size_t index, + bool backwards +) { + struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards); + iter.base.current_impl = iter.base.current; + iter.base.current = cx_pl_iter_current; + return iter; +} + +static cx_list_class cx_pointer_list_class = { + cx_pl_destructor, + cx_pl_insert_element, + cx_pl_insert_array, + cx_pl_insert_iter, + cx_pl_remove, + cx_pl_clear, + cx_pl_swap, + cx_pl_at, + cx_pl_find, + cx_pl_sort, + cx_pl_compare, + cx_pl_reverse, + cx_pl_iterator, +}; + +void cxListStoreObjects(CxList *list) { + list->store_pointer = false; + if (list->climpl != NULL) { + list->cl = list->climpl; + list->climpl = NULL; + } +} + +void cxListStorePointers(CxList *list) { + list->item_size = sizeof(void *); + list->store_pointer = true; + list->climpl = list->cl; + list->cl = &cx_pointer_list_class; +} + +// </editor-fold> + void cxListDestroy(CxList *list) { - switch (list->content_destructor_type) { - case CX_DESTRUCTOR_SIMPLE: { - CxIterator iter = cxListBegin(list); - cx_foreach(void*, elem, iter) { - list->simple_destructor(elem); - } - break; + if (list->simple_destructor) { + CxIterator iter = cxListIterator(list); + cx_foreach(void*, elem, iter) { + // already correctly resolved pointer - immediately invoke dtor + list->simple_destructor(elem); } - case CX_DESTRUCTOR_ADVANCED: { - CxIterator iter = cxListBegin(list); - cx_foreach(void*, elem, iter) { - list->advanced_destructor.func(list->advanced_destructor.data, elem); - } - break; + } + if (list->advanced_destructor) { + CxIterator iter = cxListIterator(list); + cx_foreach(void*, elem, iter) { + // already correctly resolved pointer - immediately invoke dtor + list->advanced_destructor(list->destructor_data, elem); } - case CX_DESTRUCTOR_NONE: - break; // nothing } list->cl->destructor(list); @@ -56,14 +219,14 @@ 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 ((list->store_pointer ^ other->store_pointer) || + ((list->climpl == NULL) ^ (other->climpl != NULL)) || + ((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 = cxListBegin(list); - CxIterator right = cxListBegin(other); + CxIterator left = cxListIterator(list); + CxIterator right = cxListIterator(other); for (size_t i = 0; i < list->size; i++) { void *leftValue = cxIteratorCurrent(left); void *rightValue = cxIteratorCurrent(right); @@ -78,5 +241,34 @@ } else { return list->size < other->size ? -1 : 1; } + } else { + // lists are compatible + return list->cl->compare(list, other); } } + +CxMutIterator cxListMutIteratorAt( + CxList *list, + size_t index +) { + CxIterator it = list->cl->iterator(list, index, false); + it.base.mutating = true; + + // we know the iterators share the same memory layout + CxMutIterator iter; + memcpy(&iter, &it, sizeof(CxMutIterator)); + return iter; +} + +CxMutIterator cxListMutBackwardsIteratorAt( + CxList *list, + size_t index +) { + CxIterator it = list->cl->iterator(list, index, true); + it.base.mutating = true; + + // we know the iterators share the same memory layout + CxMutIterator iter; + memcpy(&iter, &it, sizeof(CxMutIterator)); + return iter; +}
--- a/src/ucx/printf.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/printf.c Fri May 05 18:02:11 2023 +0200 @@ -31,9 +31,16 @@ #include <stdio.h> #include <string.h> -#define UCX_PRINTF_BUFSIZE 256 +#ifndef CX_PRINTF_SBO_SIZE +#define CX_PRINTF_SBO_SIZE 512 +#endif -int cx_fprintf(void *stream, cx_write_func wfc, char const *fmt, ...) { +int cx_fprintf( + void *stream, + cx_write_func wfc, + char const *fmt, + ... +) { int ret; va_list ap; va_start(ap, fmt); @@ -42,14 +49,19 @@ return ret; } -int cx_vfprintf(void *stream, cx_write_func wfc, char const *fmt, va_list ap) { - char buf[UCX_PRINTF_BUFSIZE]; +int cx_vfprintf( + void *stream, + cx_write_func wfc, + char const *fmt, + va_list ap +) { + char buf[CX_PRINTF_SBO_SIZE]; va_list ap2; va_copy(ap2, ap); - int ret = vsnprintf(buf, UCX_PRINTF_BUFSIZE, fmt, ap); + int ret = vsnprintf(buf, CX_PRINTF_SBO_SIZE, fmt, ap); if (ret < 0) { return ret; - } else if (ret < UCX_PRINTF_BUFSIZE) { + } else if (ret < CX_PRINTF_SBO_SIZE) { return (int) wfc(buf, 1, ret, stream); } else { int len = ret + 1; @@ -67,7 +79,11 @@ return ret; } -cxmutstr cx_asprintf_a(CxAllocator *allocator, char const *fmt, ...) { +cxmutstr cx_asprintf_a( + CxAllocator const *allocator, + char const *fmt, + ... +) { va_list ap; cxmutstr ret; va_start(ap, fmt); @@ -76,15 +92,19 @@ return ret; } -cxmutstr cx_vasprintf_a(CxAllocator *a, char const *fmt, va_list ap) { +cxmutstr cx_vasprintf_a( + CxAllocator const *a, + char const *fmt, + va_list ap +) { cxmutstr s; s.ptr = NULL; s.length = 0; - char buf[UCX_PRINTF_BUFSIZE]; + char buf[CX_PRINTF_SBO_SIZE]; va_list ap2; va_copy(ap2, ap); - int ret = vsnprintf(buf, UCX_PRINTF_BUFSIZE, fmt, ap); - if (ret > 0 && ret < UCX_PRINTF_BUFSIZE) { + int ret = vsnprintf(buf, CX_PRINTF_SBO_SIZE, fmt, ap); + if (ret > 0 && ret < CX_PRINTF_SBO_SIZE) { s.ptr = cxMalloc(a, ret + 1); if (s.ptr) { s.length = (size_t) ret;
--- a/src/ucx/string.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/string.c Fri May 05 18:02:11 2023 +0200 @@ -72,7 +72,7 @@ } void cx_strfree_a( - CxAllocator *alloc, + CxAllocator const *alloc, cxmutstr *str ) { cxFree(alloc, str->ptr); @@ -98,11 +98,14 @@ 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 @@ 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( @@ -226,7 +233,9 @@ return (cxmutstr) {(char *) result.ptr, result.length}; } -#define STRSTR_SBO_BUFLEN 512 +#ifndef CX_STRSTR_SBO_SIZE +#define CX_STRSTR_SBO_SIZE 512 +#endif cxstring cx_strstr( cxstring haystack, @@ -250,11 +259,11 @@ */ // local prefix table - size_t s_prefix_table[STRSTR_SBO_BUFLEN]; + size_t s_prefix_table[CX_STRSTR_SBO_SIZE]; // check needle length and use appropriate prefix table // if the pattern exceeds static prefix table, allocate on the heap - bool useheap = needle.length >= STRSTR_SBO_BUFLEN; + bool useheap = needle.length >= CX_STRSTR_SBO_SIZE; register size_t *ptable = useheap ? calloc(needle.length + 1, sizeof(size_t)) : s_prefix_table; @@ -367,7 +376,7 @@ } size_t cx_strsplit_a( - CxAllocator *allocator, + CxAllocator const *allocator, cxstring string, cxstring delim, size_t limit, @@ -409,7 +418,7 @@ } size_t cx_strsplit_ma( - CxAllocator *allocator, + CxAllocator const *allocator, cxmutstr string, cxstring delim, size_t limit, @@ -449,8 +458,26 @@ } } +int cx_strcmp_p( + void const *s1, + void const *s2 +) { + cxstring const *left = s1; + cxstring const *right = s2; + return cx_strcmp(*left, *right); +} + +int cx_strcasecmp_p( + void const *s1, + void const *s2 +) { + cxstring const *left = s1; + cxstring const *right = s2; + return cx_strcasecmp(*left, *right); +} + cxmutstr cx_strdup_a( - CxAllocator *allocator, + CxAllocator const *allocator, cxstring string ) { cxmutstr result = { @@ -539,7 +566,9 @@ } } -#define REPLACE_INDEX_BUFFER_MAX 100 +#ifndef CX_STRREPLACE_INDEX_BUFFER_SIZE +#define CX_STRREPLACE_INDEX_BUFFER_SIZE 64 +#endif struct cx_strreplace_ibuf { size_t *buf; @@ -557,7 +586,7 @@ } cxmutstr cx_strreplacen_a( - CxAllocator *allocator, + CxAllocator const *allocator, cxstring str, cxstring pattern, cxstring replacement, @@ -570,8 +599,8 @@ // Compute expected buffer length size_t ibufmax = str.length / pattern.length; size_t ibuflen = replmax < ibufmax ? replmax : ibufmax; - if (ibuflen > REPLACE_INDEX_BUFFER_MAX) { - ibuflen = REPLACE_INDEX_BUFFER_MAX; + if (ibuflen > CX_STRREPLACE_INDEX_BUFFER_SIZE) { + ibuflen = CX_STRREPLACE_INDEX_BUFFER_SIZE; } // Allocate first index buffer @@ -670,4 +699,87 @@ return result; } +CxStrtokCtx cx_strtok( + cxstring str, + cxstring delim, + size_t limit +) { + CxStrtokCtx ctx; + ctx.str = str; + ctx.delim = delim; + ctx.limit = limit; + ctx.pos = 0; + ctx.next_pos = 0; + ctx.delim_pos = 0; + ctx.found = 0; + ctx.delim_more = NULL; + ctx.delim_more_count = 0; + return ctx; +} +CxStrtokCtx cx_strtok_m( + cxmutstr str, + cxstring delim, + size_t limit +) { + return cx_strtok(cx_strcast(str), delim, limit); +} + +bool cx_strtok_next( + CxStrtokCtx *ctx, + cxstring *token +) { + // abortion criteria + if (ctx->found >= ctx->limit || ctx->delim_pos >= ctx->str.length) { + return false; + } + + // determine the search start + cxstring haystack = cx_strsubs(ctx->str, ctx->next_pos); + + // search the next delimiter + cxstring delim = cx_strstr(haystack, ctx->delim); + + // if found, make delim capture exactly the delimiter + if (delim.length > 0) { + delim.length = ctx->delim.length; + } + + // if more delimiters are specified, check them now + if (ctx->delim_more_count > 0) { + cx_for_n(i, ctx->delim_more_count) { + cxstring d = cx_strstr(haystack, ctx->delim_more[i]); + if (d.length > 0 && (delim.length == 0 || d.ptr < delim.ptr)) { + delim.ptr = d.ptr; + delim.length = ctx->delim_more[i].length; + } + } + } + + // store the token information and adjust the context + ctx->found++; + ctx->pos = ctx->next_pos; + token->ptr = &ctx->str.ptr[ctx->pos]; + ctx->delim_pos = delim.length == 0 ? + ctx->str.length : (size_t) (delim.ptr - ctx->str.ptr); + token->length = ctx->delim_pos - ctx->pos; + ctx->next_pos = ctx->delim_pos + delim.length; + + return true; +} + +bool cx_strtok_next_m( + CxStrtokCtx *ctx, + cxmutstr *token +) { + return cx_strtok_next(ctx, (cxstring *) token); +} + +void cx_strtok_delim( + CxStrtokCtx *ctx, + cxstring const *delim, + size_t count +) { + ctx->delim_more = delim; + ctx->delim_more_count = count; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/ucx/szmul.c Fri May 05 18:02:11 2023 +0200 @@ -0,0 +1,46 @@ +/* + * 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. + */ + +int cx_szmul_impl( + size_t a, + size_t b, + size_t *result +) { + if (a == 0 || b == 0) { + *result = 0; + return 0; + } + size_t r = a * b; + if (r / b == a) { + *result = r; + return 0; + } else { + *result = 0; + return 1; + } +} \ No newline at end of file
--- a/src/ucx/tree.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/tree.c Fri May 05 18:02:11 2023 +0200 @@ -41,8 +41,8 @@ } 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) { + 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
--- a/src/ucx/utils.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/utils.c Fri May 05 18:02:11 2023 +0200 @@ -28,19 +28,67 @@ #include "cx/utils.h" -#ifndef CX_SZMUL_BUILTIN -int cx_szmul_impl(size_t a, size_t b, size_t *result) { - if(a == 0 || b == 0) { - *result = 0; +#define CX_STREAM_BCOPY_BUF_SIZE 8192 +#define CX_STREAM_COPY_BUF_SIZE 1024 + +size_t cx_stream_bncopy( + void *src, + void *dest, + cx_read_func rfnc, + cx_write_func wfnc, + char *buf, + size_t bufsize, + size_t n +) { + if (n == 0) { return 0; } - size_t r = a * b; - if(r / b == a) { - *result = r; - return 0; + + char *lbuf; + size_t ncp = 0; + + if (buf) { + if (bufsize == 0) return 0; + lbuf = buf; } else { - *result = 0; - return 1; + if (bufsize == 0) bufsize = CX_STREAM_BCOPY_BUF_SIZE; + lbuf = malloc(bufsize); + if (lbuf == NULL) { + return 0; + } + } + + size_t r; + size_t rn = bufsize > n ? n : bufsize; + while ((r = rfnc(lbuf, 1, rn, src)) != 0) { + r = wfnc(lbuf, 1, r, dest); + ncp += r; + n -= r; + rn = bufsize > n ? n : bufsize; + if (r == 0 || n == 0) { + break; + } } + + if (lbuf != buf) { + free(lbuf); + } + + return ncp; } + +size_t cx_stream_ncopy( + void *src, + void *dest, + cx_read_func rfnc, + cx_write_func wfnc, + size_t n +) { + char buf[CX_STREAM_COPY_BUF_SIZE]; + return cx_stream_bncopy(src, dest, rfnc, wfnc, + buf, CX_STREAM_COPY_BUF_SIZE, n); +} + +#ifndef CX_SZMUL_BUILTIN +#include "szmul.c" #endif
