changeset
compatibility with UCX 3.1 plus several minor code fixes
Thu, 23 May 2024 22:35:45 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Thu, 23 May 2024 22:35:45 +0200
- branch
- ucx-3.1
- changeset 816
- 839fefbdedc7
- parent 815
- 1f40ca07ae1b
- child 818
- bc782cca0759
- child 819
- 833bbb830330
compatibility with UCX 3.1 plus several minor code fixes
--- a/dav/config.c Sat Apr 20 13:01:58 2024 +0200 +++ b/dav/config.c Thu May 23 22:35:45 2024 +0200 @@ -486,7 +486,7 @@ * location strings. We need a list, that contains only urls */ CxList *locations = cxLinkedListCreate(cxDefaultAllocator, (cx_compare_func)cmp_url_cred_entry, CX_STORE_POINTERS); - locations->simple_destructor = (cx_destructor_func)free_cred_location; + cxDefineDestructor(locations, free_cred_location); CxIterator i = cxListIterator(secrets->locations); cx_foreach(PwdIndexEntry*, e, i) { CxIterator entry_iter = cxListIterator(e->locations);
--- a/dav/db.c Sat Apr 20 13:01:58 2024 +0200 +++ b/dav/db.c Thu May 23 22:35:45 2024 +0200 @@ -57,9 +57,9 @@ SyncDatabase *db = malloc(sizeof(SyncDatabase)); db->resources = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 2048); db->conflict = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 16); - - db->resources->destructor_data = (cx_destructor_func)local_resource_free; - db->conflict->destructor_data = (cx_destructor_func)local_resource_free; + + cxDefineDestructor(db->resources, local_resource_free); + cxDefineDestructor(db->conflict, local_resource_free); xmlTextReaderPtr reader = xmlReaderForFile(db_file, NULL, 0); if(!reader) { @@ -79,10 +79,10 @@ int error = 0; while(xmlTextReaderRead(reader)) { int type = xmlTextReaderNodeType(reader); - const xmlChar *name = xmlTextReaderConstName(reader); + const xmlChar *xmlName = xmlTextReaderConstName(reader); if(type == XML_READER_TYPE_ELEMENT) { - if(xstreq(name, "resource")) { + if(xstreq(xmlName, "resource")) { LocalResource *res = process_resource(reader); if(res) { cxMapPut(db->resources, cx_hash_key_str(res->path), res); @@ -90,7 +90,7 @@ error = 1; break; } - } else if(xstreq(name, "conflict")) { + } else if(xstreq(xmlName, "conflict")) { LocalResource *res = process_conflict(reader); if(res) { cxMapPut(db->conflict, cx_hash_key_str(res->path), res); @@ -115,7 +115,7 @@ // TODO: rewrite using low level array CxList *parts = cxLinkedListCreateSimple(CX_STORE_POINTERS); - parts->destructor_data = (cx_destructor_func)filepart_free; + cxDefineDestructor(parts, filepart_free); FilePart *current_part = NULL; @@ -411,9 +411,8 @@ xmlTextWriterStartElement(writer, BAD_CAST "directory"); // write all resource entries - CxIterator i = cxMapIteratorValues(db->resources); - LocalResource *res; - cx_foreach(LocalResource*, res, i) { + CxIterator iter = cxMapIteratorValues(db->resources); + cx_foreach(LocalResource*, res, iter) { // <resource> xmlTextWriterStartElement(writer, BAD_CAST "resource"); @@ -688,8 +687,8 @@ */ // write all conflict entries - i = cxMapIteratorValues(db->conflict); - cx_foreach(LocalResource*, res, i) { + iter = cxMapIteratorValues(db->conflict); + cx_foreach(LocalResource*, res, iter) { // <conflict> xmlTextWriterStartElement(writer, BAD_CAST "conflict"); @@ -825,10 +824,9 @@ } CxMap* create_hash_index(SyncDatabase *db) { - CxMap *hmap = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, db->resources->size + 64); + CxMap *hmap = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, cxMapSize(db->resources) + 64); CxIterator i = cxMapIteratorValues(db->resources); - LocalResource *res; cx_foreach(LocalResource*, res, i) { if(res->hash) { cxMapPut(hmap, cx_hash_key_str(res->hash), res);
--- a/dav/main.c Sat Apr 20 13:01:58 2024 +0200 +++ b/dav/main.c Thu May 23 22:35:45 2024 +0200 @@ -703,7 +703,7 @@ // get list of resources CxList *reslist = cxLinkedListCreateSimple(CX_STORE_POINTERS); - reslist->simple_destructor = (cx_destructor_func)free_getres; + cxDefineDestructor(reslist, free_getres); uint64_t totalsize = 0; uint64_t rescount = 0; @@ -716,7 +716,7 @@ // iterate over resource tree CxList *stack = cxLinkedListCreateSimple(CX_STORE_POINTERS); cxListInsert(stack, 0, getres); - while(stack->size > 0) { + while(cxListSize(stack) > 0) { GetResource *g = cxListAt(stack, 0); cxListRemove(stack, 0); @@ -769,9 +769,9 @@ } else { get = get_resource; } - CxIterator i = cxListIterator(reslist); - cx_foreach(GetResource *, getres, i) { - ret = get(repo, getres, a, tout); + CxIterator iter = cxListIterator(reslist); + cx_foreach(GetResource *, res_item, iter) { + ret = get(repo, res_item, a, tout); if(ret) { break; } @@ -1598,7 +1598,7 @@ } DavResource *dest = dav_resource_new(destsn, destpath); char *desthref = dav_resource_get_href(dest); - char *desturl = util_get_url(destsn, desthref); + desturl = util_get_url(destsn, desthref); DavResource *res = dav_resource_new(srcsn, srcpath); int err = cp ? dav_copyto(res, desturl, override) @@ -2102,7 +2102,7 @@ printf("path: %s\n", res->path); char *server = util_url_base(sn->base_url); - char *url = util_concat_path(server, res->href); + url = util_concat_path(server, res->href); printf("url: %s\n", url); free(url); free(server); @@ -2136,9 +2136,9 @@ // find some xml elements printf(" %s: ", p.name); DavXmlNode *x = xval->type == DAV_XML_ELEMENT ? xval : dav_xml_nextelm(xval); - for(int i=0;i<3;i++) { + for(int j=0;j<3;j++) { if(x) { - if(i == 2) { + if(j == 2) { printf(" ..."); break; } else { @@ -2150,8 +2150,6 @@ x = dav_xml_nextelm(x); } printf("\n"); - - } } @@ -2397,7 +2395,7 @@ void printxmldoc(FILE *out, char *root, char *rootns, DavXmlNode *content) { CxMap *nsmap = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 16); - nsmap->simple_destructor = free; + cxDefineDestructor(nsmap, free); cxMapPut(nsmap, cx_hash_key_str(rootns), "x0"); fprintf(out, "%s", "<?xml version=\"1.0\"?>\n"); @@ -2656,7 +2654,7 @@ // optionally, get one or more locations char *location = NULL; CxList *locations = cxLinkedListCreateSimple(CX_STORE_POINTERS); - locations->simple_destructor = free; + cxDefineDestructor(locations, free); while((location = assistant_getoptcfg("Location"))) { cxListAdd(locations, location); } @@ -2688,7 +2686,7 @@ * called before the secret store is decrypted */ static int cmd_ss_list_users_bc(CmdArgs *Args, PwdStore *secrets, int *ret) { - if(secrets->index->size == 0) { + if(cxMapSize(secrets->index) == 0) { return 1; // abort, because the secret store is empty } // set ret to 1, because decrypt could fail and this should be an error @@ -2705,8 +2703,8 @@ CxList *list = secrets->locations; for(int i=0;i<2;i++) { if(list) { - CxIterator i = cxListIterator(list); - cx_foreach(PwdIndexEntry*, index, i) { + CxIterator iter = cxListIterator(list); + cx_foreach(PwdIndexEntry*, index, iter) { PwdEntry *e = cxMapGet(secrets->ids, cx_hash_key_str(index->id)); if(e) { printf("Id: %s\n", e->id); @@ -2788,7 +2786,7 @@ } static void secrets_remove_location(PwdIndexEntry *index) { - if(!index->locations || index->locations->size == 0) { + if(!index->locations || cxListSize(index->locations) == 0) { printf("no locations\n"); return; } @@ -2895,7 +2893,7 @@ } case 4: { // list locations - if(!index->locations || index->locations->size == 0) { + if(!index->locations || cxListSize(index->locations)) { printf("no locations\n"); } else { CxIterator i = cxListIterator(index->locations);
--- a/dav/pwd.c Sat Apr 20 13:01:58 2024 +0200 +++ b/dav/pwd.c Thu May 23 22:35:45 2024 +0200 @@ -32,7 +32,6 @@ #include "pwd.h" -#include <cx/buffer.h> #include <cx/utils.h> #include <cx/hash_map.h> @@ -141,12 +140,11 @@ char *id = NULL; CxList *locations = cxLinkedListCreateSimple(CX_STORE_POINTERS); - locations->simple_destructor = free; + cxDefineDestructor(locations, free); // get id (required) int ret = 0; if(readval(in, &id, FALSE)) { - ret = 1; // get locations char *location = NULL; while((ret = readval(in, &location, TRUE)) == 1) { @@ -175,7 +173,6 @@ } char *id = NULL; - char *location = NULL; char *user = NULL; char *password = NULL; @@ -190,39 +187,33 @@ } if(id) free(id); - if(location) free(location); if(user) free(user); if(password) free(password); return ret; } -static int remove_list_entries(PwdStore *s, const char *id) { - int ret = 0; - - CxList *loc_entry = NULL; - CxList *noloc_entry = NULL; - - CxMutIterator i = cxListMutIterator(s->locations); +static void remove_list_entries(PwdStore *s, const char *id) { + CxIterator i = cxListMutIterator(s->locations); cx_foreach(PwdIndexEntry*, ie, i) { if(!strcmp(ie->id, id)) { cxIteratorFlagRemoval(i); - // TODO: break loop + cxIteratorNext(i); + break; } } i = cxListMutIterator(s->noloc); cx_foreach(PwdIndexEntry*, ie, i) { if(!strcmp(ie->id, id)) { cxIteratorFlagRemoval(i); - // TODO: break loop + cxIteratorNext(i); + break; } } - - return ret; } void pwdstore_remove_entry(PwdStore *s, const char *id) { - while(remove_list_entries(s, id)) {} + remove_list_entries(s, id); CxHashKey key = cx_hash_key_str(id); PwdIndexEntry *i = cxMapRemoveAndGet(s->index, key); @@ -331,7 +322,7 @@ } void pwdstore_free(PwdStore* p) { - p->ids->simple_destructor = (cx_destructor_func)pwdstore_free_entry; + cxDefineDestructor(p->ids, pwdstore_free_entry); cxMapDestroy(p->ids); cxListDestroy(p->locations);
--- a/dav/scfg.c Sat Apr 20 13:01:58 2024 +0200 +++ b/dav/scfg.c Thu May 23 22:35:45 2024 +0200 @@ -169,8 +169,8 @@ CxList *exclude = cxLinkedListCreate(cxDefaultAllocator, NULL, sizeof(regex_t)); CxList *tags = cxLinkedListCreate(cxDefaultAllocator, NULL, CX_STORE_POINTERS); - include->simple_destructor = (cx_destructor_func)regfree; - exclude->simple_destructor = (cx_destructor_func)regfree; + cxDefineDestructor(include, regfree); + cxDefineDestructor(exclude, regfree); // TODO: set tags destructor if(scfg_load_filter(node, include, exclude, tags)) { @@ -185,7 +185,7 @@ } void init_default_filter(Filter *filter) { - if(filter->include->size == 0) { + if(cxListSize(filter->include) == 0) { regex_t matchall; regcomp(&matchall, ".*", REG_NOSUB); cxListAdd(filter->include, &matchall);
--- a/dav/sync.c Sat Apr 20 13:01:58 2024 +0200 +++ b/dav/sync.c Thu May 23 22:35:45 2024 +0200 @@ -36,7 +36,6 @@ #include <libxml/xmlerror.h> #include <sys/types.h> #include <cx/map.h> -#include <cx/string.h> #include <cx/utils.h> #include <cx/list.h> #include <cx/hash_map.h> @@ -73,8 +72,6 @@ #include "system.h" -#include <ctype.h> - #ifdef _WIN32 #define strcasecmp _stricmp @@ -223,7 +220,11 @@ typedef void*(*clonefunc)(void *elm, void *userdata); static CxMap* mapClone(const CxAllocator *a, CxMap *map, clonefunc clone, void *userdata) { - CxMap *newmap = cxHashMapCreate(a, map->store_pointer ? CX_STORE_POINTERS : map->item_size, map->size + 4); + CxMap *newmap = cxHashMapCreate( + a, + cxMapIsStoringPointers(map) ? CX_STORE_POINTERS : map->collection.elem_size, + cxMapSize(map) + 4 + ); CxIterator i = cxMapIterator(map); if(clone) { @@ -598,7 +599,7 @@ return -strcmp(a->path, b->path); } -static DavSession* create_session(CmdArgs *a, DavContext *ctx, DavCfgRepository *repo, char *collection) { +static DavSession* create_session(CmdArgs *a, DavContext *davctx, DavCfgRepository *repo, char *collection) { int flags = dav_repository_get_flags(repo); DavBool find_collection = TRUE; if((flags & DAV_SESSION_DECRYPT_NAME) != DAV_SESSION_DECRYPT_NAME) { @@ -615,10 +616,10 @@ find_collection = FALSE; } - DavSession *sn = connect_to_repo(ctx, repo, collection, request_auth, a); + DavSession *sn = connect_to_repo(davctx, repo, collection, request_auth, a); sn->flags = flags; - sn->key = dav_context_get_key(ctx, repo->default_key.value.ptr); + sn->key = dav_context_get_key(davctx, repo->default_key.value.ptr); curl_easy_setopt(sn->handle, CURLOPT_HTTPAUTH, repo->authmethods); curl_easy_setopt(sn->handle, CURLOPT_SSLVERSION, repo->ssl_version); if(repo->cert.value.ptr) { @@ -682,7 +683,7 @@ void res2map(DavResource *root, CxMap *map) { CxList *stack = cxLinkedListCreateSimple(CX_STORE_POINTERS); cxListInsert(stack, 0, root->children); - while(stack->size > 0) { + while(cxListSize(stack) > 0) { DavResource *res = cxListAt(stack, 0); cxListRemove(stack, 0); @@ -848,7 +849,7 @@ CxList *stack = cxLinkedListCreateSimple(CX_STORE_POINTERS); cxListInsert(stack, 0, ls->children); - while(stack->size > 0) { + while(cxListSize(stack) > 0) { DavResource *res = cxListAt(stack, 0); cxListRemove(stack, 0); @@ -941,9 +942,11 @@ } if(!local->keep) { cxMapPut(lres_removed, cx_hash_key_str(local->path), local); - if(lres_removed->size > lres_removed->size * 2) { - cxMapRehash(lres_removed); - } + + // TODO: what is the meaning of this code? without overflow the condition is never true + // if(lres_removed->size > lres_removed->size * 2) { + // cxMapRehash(lres_removed); + // } } } @@ -960,7 +963,7 @@ } // we need a map for all conflicts for fast lookups - CxMap *conflicts = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, res_conflict->size+16); + CxMap *conflicts = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, cxListSize(res_conflict)+16); i = cxListIterator(res_conflict); cx_foreach(DavResource *, res, i) { cxMapPut(conflicts, cx_hash_key_str(res->path), res); @@ -969,7 +972,7 @@ if(SYNC_HASHING(dir)) { // check for moved/copied files SYS_STAT s; - CxMutIterator mut_iter = cxListMutIterator(res_new); + CxIterator mut_iter = cxListMutIterator(res_new); cx_foreach(DavResource *, res, mut_iter) { if(dav_get_property_ns(res, DAV_PROPS_NS, "link")) { continue; @@ -1031,17 +1034,17 @@ // download all new, modified and conflict files for(int n=0;n<4;n++) { - CxList *ls; + CxList *list; if(n == 0) { - ls = res_new; + list = res_new; } else if(n == 1) { - ls = res_modified; + list = res_modified; } else if(n == 2) { - ls = res_conflict; + list = res_conflict; } else { - ls = res_link; - } - CxIterator iter = cxListIterator(ls); + list = res_link; + } + CxIterator iter = cxListIterator(list); cx_foreach(DavResource *, res, iter) { if(sync_shutdown) { break; @@ -1101,10 +1104,10 @@ break; } - int ret = sync_remove_local_resource(dir, removed_res); - if(ret == -1) { + int rmlocal_ret = sync_remove_local_resource(dir, removed_res); + if(rmlocal_ret == -1) { cxListAdd(rmdirs, removed_res); - } else if(ret == 0) { + } else if(rmlocal_ret == 0) { LocalResource *local = cxMapRemoveAndGet(db->resources, cx_hash_key_str(removed_res->path)); if(local) { local_resource_free(local); @@ -1379,9 +1382,9 @@ } // update local res - SYS_STAT s; - if(!sys_stat(local_path, &s)) { - sync_set_metadata_from_stat(local, &s); + SYS_STAT statdata; + if(!sys_stat(local_path, &statdata)) { + sync_set_metadata_from_stat(local, &statdata); } else { fprintf(stderr, "stat failed for file: %s : %s", local_path, strerror(errno)); } @@ -1422,7 +1425,7 @@ int *err) { CxList *updates = cxLinkedListCreateSimple(CX_STORE_POINTERS); - updates->simple_destructor = (cx_destructor_func)filepart_free; + cxDefineDestructor(updates, filepart_free); size_t local_numparts = local ? local->numparts : 0; fseeko(out, 0, SEEK_END); @@ -2005,7 +2008,7 @@ break; } free(np.ptr); - }; + } free(parent); return new_path; @@ -2028,7 +2031,7 @@ break; } free(np.ptr); - }; + } if(!new_path) { fprintf(stderr, "Cannot move file %s to trash.\n", path); @@ -2180,7 +2183,7 @@ //UcxList *resources = cmd_getoption(a, "read") ? // read_changes(dir, db) : local_scan(dir, db); CxList *resources = local_scan(dir, db); - CxMap *resources_map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, resources->size+16); + CxMap *resources_map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, cxListSize(resources)+16); CxIterator iter = cxListIterator(resources); cx_foreach(LocalResource *, local_res, iter) { @@ -2255,7 +2258,7 @@ if(SYNC_STORE_HASH(dir)) { // calculate hashes of all new files and check if a file // was moved or is a copy - CxMutIterator mut_iter = cxListMutIterator(ls_new); + CxIterator mut_iter = cxListMutIterator(ls_new); cx_foreach(LocalResource *, local, mut_iter) { if(local->isdirectory || local->link_target) { continue; @@ -2288,7 +2291,6 @@ // find all deleted files and cleanup the database iter = cxMapIterator(db->resources); - LocalResource *local; CxList *removed_res = cxLinkedListCreateSimple(CX_STORE_POINTERS); cx_foreach(CxMapEntry *, entry, iter) { LocalResource *local = entry->value; @@ -2727,8 +2729,8 @@ // iterate over all db resources and check if any resource is // modified or deleted - CxIterator i = cxMapIterator(files ? files : db->resources); - cx_foreach(CxMapEntry *, entry, i) { + CxIterator resiter = cxMapIterator(files ? files : db->resources); + cx_foreach(CxMapEntry *, entry, resiter) { LocalResource *resource = entry->value; if(resource == &nres) { resource = cxMapGet(db->resources, *entry->key); @@ -2931,14 +2933,14 @@ { int64_t total_size = 0; - size_t len_new = ls_new->size; - size_t len_mod = ls_modified->size; - size_t len_cnf = ls_conflict->size; - size_t len_upd = ls_update->size; - size_t len_del = ls_delete->size; - size_t len_mov = ls_move->size; - size_t len_cpy = ls_copy->size; - size_t len_mkc = ls_mkcol->size; + size_t len_new = cxListSize(ls_new); + size_t len_mod = cxListSize(ls_modified); + size_t len_cnf = cxListSize(ls_conflict); + size_t len_upd = cxListSize(ls_update); + size_t len_del = cxListSize(ls_delete); + size_t len_mov = cxListSize(ls_move); + size_t len_cpy = cxListSize(ls_copy); + size_t len_mkc = cxListSize(ls_mkcol); size_t total = len_new + len_mod + len_cnf + len_upd + len_del + len_mov + len_cpy + len_mkc; if(total == 0) { @@ -2949,7 +2951,7 @@ log_printf("%s\n", "File Last Modified Size"); log_printf("%s\n", "=============================================================================="); - if(ls_mkcol->size > 0) { + if(cxListSize(ls_mkcol) > 0) { log_printf("Directories:\n"); CxIterator i = cxListIterator(ls_mkcol); cx_foreach(LocalResource *, res, i) { @@ -2957,7 +2959,7 @@ total_size += res->size; } } - if(ls_new->size > 0) { + if(cxListSize(ls_new) > 0) { log_printf("New:\n"); CxIterator i = cxListIterator(ls_new); cx_foreach(LocalResource *, res, i) { @@ -2965,7 +2967,7 @@ total_size += res->size; } } - if(ls_modified->size > 0) { + if(cxListSize(ls_modified) > 0) { log_printf("Modified:\n"); CxIterator i = cxListIterator(ls_modified); cx_foreach(LocalResource *, res, i) { @@ -2973,7 +2975,7 @@ total_size += res->size; } } - if(ls_update->size > 0) { + if(cxListSize(ls_update) > 0) { log_printf("Update:\n"); CxIterator i = cxListIterator(ls_update); cx_foreach(LocalResource *, res, i) { @@ -2982,28 +2984,28 @@ free(lastmodified); } } - if(ls_delete->size > 0) { + if(cxListSize(ls_delete) > 0) { log_printf("Delete:\n"); CxIterator i = cxListIterator(ls_delete); cx_foreach(LocalResource *, res, i) { log_printf(" %s\n", res->path+1); } } - if(ls_copy->size > 0) { + if(cxListSize(ls_copy) > 0) { log_printf("Copy:\n"); CxIterator i = cxListIterator(ls_copy); cx_foreach(LocalResource *, res, i) { log_printf("%s -> %s\n", res->origin->path+1, res->path); } } - if(ls_move->size > 0) { + if(cxListSize(ls_move) > 0) { log_printf("Move:\n"); CxIterator i = cxListIterator(ls_move); cx_foreach(LocalResource *, res, i) { log_printf("%s -> %s\n", res->origin->path+1, res->path); } } - if(ls_conflict->size > 0) { + if(cxListSize(ls_conflict) > 0) { log_printf("Conflict\n"); CxIterator i = cxListIterator(ls_conflict); cx_foreach(LocalResource *, res, i) { @@ -3032,7 +3034,7 @@ char *path = strdup("/"); CxList *stack = cxLinkedListCreateSimple(CX_STORE_POINTERS); cxListInsert(stack, 0, path); - while(stack->size > 0) { + while(cxListSize(stack) > 0) { // get a directory path from the stack and read all entries // if an entry is a directory, put it on the stack @@ -3701,16 +3703,15 @@ // to detect which xattributes are removed, we remove all new // attributes from the map and all remaining attributes must // be removed with xattr_remove - char *value = cxMapRemoveAndGet(current_xattr, cx_hash_key_str(xattr->names[i])); - if(value) { - free(value); + char *removed_value = cxMapRemoveAndGet(current_xattr, cx_hash_key_str(xattr->names[i])); + if(removed_value) { + free(removed_value); } } } if(current_xattr) { CxIterator i = cxMapIteratorValues(current_xattr); - char *value = NULL; cx_foreach(char *, value, i) { (void)xattr_remove(path, value); // don't print error free(value); @@ -4197,7 +4198,7 @@ } CxMap *updated_parts_map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, (nblocks/2)+64); - updated_parts_map->simple_destructor = (cx_destructor_func)filepart_free; + cxDefineDestructor(updated_parts_map, filepart_free); int blockindex = 0; int uploaded_parts = 0; @@ -4833,7 +4834,7 @@ } void remove_deleted_conflicts(SyncDirectory *dir, SyncDatabase *db) { - char **dc = calloc(sizeof(void*), db->conflict->size); + char **dc = calloc(sizeof(void*), cxMapSize(db->conflict)); int numdc = 0; CxIterator i = cxMapIteratorValues(db->conflict); @@ -4903,7 +4904,7 @@ int ret = 0; // remove conflicts - int num_conflict = db->conflict->size; + size_t num_conflict = cxMapSize(db->conflict); //ucx_map_free_content(db->conflict, (ucx_destructor)local_resource_free); cxMapClear(db->conflict); @@ -4920,7 +4921,7 @@ // Report if(ret != -2) { char *str_conflict = num_conflict == 1 ? "conflict" : "conflicts"; - log_printf("Result: %d %s resolved\n", num_conflict, str_conflict); + log_printf("Result: %zu %s resolved\n", num_conflict, str_conflict); } return ret; @@ -5022,14 +5023,16 @@ // get all conflict sources CxIterator i = cxMapIteratorValues(db->conflict); - CxList* conflict_sources = cxLinkedListCreateSimple(CX_STORE_POINTERS); + CxList* conflict_sources = cxLinkedListCreate( + cxDefaultAllocator, + (cx_compare_func) strcmp, + CX_STORE_POINTERS + ); cx_foreach(LocalResource *, res, i) { cxListAdd(conflict_sources, res->conflict_source); } // print unique conflict sources - // TODO: set cmpfunc at map creation - conflict_sources->cmpfunc = (cx_compare_func)strcmp; cxListSort(conflict_sources); i = cxListIterator(conflict_sources); char *prev = "";
--- a/dav/sync.h Sat Apr 20 13:01:58 2024 +0200 +++ b/dav/sync.h Thu May 23 22:35:45 2024 +0200 @@ -260,7 +260,7 @@ int cmd_add_directory(CmdArgs *args); int cmd_list_dirs(); -int cmd_check_repositories(); +int cmd_check_repositories(CmdArgs *args); char* create_locktoken_file(const char *syncdirname, const char *locktoken);
--- a/dav/tags.c Sat Apr 20 13:01:58 2024 +0200 +++ b/dav/tags.c Thu May 23 22:35:45 2024 +0200 @@ -73,7 +73,7 @@ CxList* parse_text_taglist(const char *buf, size_t length) { CxList *tags = cxLinkedListCreateSimple(CX_STORE_POINTERS); - tags->simple_destructor = (cx_destructor_func)free_dav_tag; + cxDefineDestructor(tags, free_dav_tag); int line_start = 0; for(int i=0;i<length;i++) { @@ -114,7 +114,7 @@ return cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 8); } - CxMap *map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, tags->size + 8); + CxMap *map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, cxListSize(tags) + 8); CxIterator iter = cxListIterator(tags); cx_foreach(DavTag*, t, iter) { cxMapPut(map, cx_hash_key_str(t->name), t); @@ -142,7 +142,7 @@ CxList* parse_csv_taglist(const char *buf, size_t length) { CxList *taglist = cxLinkedListCreateSimple(CX_STORE_POINTERS); - taglist->simple_destructor = (cx_destructor_func)free_dav_tag; + cxDefineDestructor(taglist, free_dav_tag); cxstring str = cx_strn(buf, length); CxStrtokCtx tags = cx_strtok(str, CX_STR(","), INT_MAX); @@ -185,16 +185,10 @@ if(value) { if(!strcmp(c->namespace, DAV_PROPS_NS)) { if(!strcmp(c->name, "name")) { - char *value = dav_xml_getstring(c->children); - if(value) { - name = value; - } + name = value; } if(!strcmp(c->name, "color")) { - char *value = dav_xml_getstring(c->children); - if(value) { - color = value; - } + color = value; } } } @@ -213,7 +207,7 @@ CxList* parse_dav_xml_taglist(DavXmlNode *taglistnode) { CxList *tags = cxLinkedListCreateSimple(CX_STORE_POINTERS); - tags->simple_destructor = (cx_destructor_func)free_dav_tag; + cxDefineDestructor(tags, free_dav_tag); DavXmlNode *node = taglistnode; while(node) { @@ -403,7 +397,7 @@ i++; } - if(i != map1->size) { + if(i != cxMapSize(map1)) { equal = 0; } cxMapDestroy(map1); @@ -425,7 +419,7 @@ CxMap *tag_map = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 32); // merged taglist CxList *new_tags = cxLinkedListCreateSimple(CX_STORE_POINTERS); - new_tags->simple_destructor = (cx_destructor_func)free_dav_tag; + cxDefineDestructor(new_tags, free_dav_tag); // add all local tags if(tags1) {
--- a/libidav/crypto.c Sat Apr 20 13:01:58 2024 +0200 +++ b/libidav/crypto.c Thu May 23 22:35:45 2024 +0200 @@ -103,8 +103,8 @@ size_t aes_write(const void *buf, size_t s, size_t n, AESDecrypter *dec) { int len = s*n; if(!dec->init) { - size_t n = 16 - dec->ivpos; - size_t cp = n > len ? len : n; + size_t m = 16 - dec->ivpos; + size_t cp = m > len ? len : m; memcpy(dec->ivtmp + dec->ivpos, buf, cp); dec->ivpos += cp; if(dec->ivpos >= 16) {
--- a/libidav/davqlexec.c Sat Apr 20 13:01:58 2024 +0200 +++ b/libidav/davqlexec.c Thu May 23 22:35:45 2024 +0200 @@ -35,7 +35,7 @@ #include <cx/map.h> #include <cx/hash_map.h> #include <cx/printf.h> -#include <cx/basic_mempool.h> +#include <cx/mempool.h> #include "davqlexec.h" #include "utils.h" @@ -621,7 +621,7 @@ result.status = 0; // do a propfind request for each resource on the stack - while(stack->size > 0) { + while(cxListSize(stack) > 0) { DavQLRes *sr_ptr = cxListAt(stack, 0); // get first element from the stack DavResource *root = sr_ptr->resource; int res_depth = sr_ptr->depth;
--- a/libidav/davqlparser.c Sat Apr 20 13:01:58 2024 +0200 +++ b/libidav/davqlparser.c Thu May 23 22:35:45 2024 +0200 @@ -105,9 +105,9 @@ static void dav_debug_ql_stmt_print(DavQLStatement *stmt) { // Basic information - size_t fieldcount = stmt->fields ? stmt->fields->size : 0; + size_t fieldcount = stmt->fields ? cxListSize(stmt->fields) : 0; int specialfield = 0; - if (stmt->fields && stmt->fields->size > 0) { + if (fieldcount > 0) { DavQLField* firstfield = (DavQLField*)cxListAt(stmt->fields, 0); if (firstfield->expr->type == DAVQL_IDENTIFIER) { switch (firstfield->expr->srctext.ptr[0]) { @@ -146,7 +146,7 @@ cx_foreach(DavQLOrderCriterion*, critdata, i) { printf("%.*s %s%s", (int)critdata->column->srctext.length, critdata->column->srctext.ptr, critdata->descending ? "desc" : "asc", - i.index+1 < stmt->orderby->size ? ", " : "\n"); + i.index+1 < cxListSize(stmt->orderby) ? ", " : "\n"); } } else { printf("nothing\n"); @@ -296,7 +296,7 @@ case DQLD_CMD_F: examineclause = DQLD_CMD_F; examineelem = stmt->fields; - if (stmt->fields && stmt->fields->size > 0) { + if (stmt->fields && cxListSize(stmt->fields) > 0) { DavQLField* field = cxListAt(stmt->fields, 0); examineexpr = field->expr; dav_debug_ql_field_print(field); @@ -312,7 +312,7 @@ case DQLD_CMD_O: examineclause = DQLD_CMD_O; examineelem = stmt->orderby; - examineexpr = stmt->orderby && stmt->orderby->size > 0 ? + examineexpr = stmt->orderby && cxListSize(stmt->orderby) > 0 ? ((DavQLOrderCriterion*)cxListAt(stmt->orderby, 0))->column : NULL; dav_debug_ql_expr_print(examineexpr); break; @@ -1092,11 +1092,11 @@ DavQLField localfield; consumed = dav_parse_named_field(stmt, token, &localfield); if (!stmt->errorcode && consumed) { - DavQLField *field; - dqlsec_malloc(stmt, field, DavQLField); - memcpy(field, &localfield, sizeof(DavQLField)); - if(dav_stmt_add_field(stmt, field)) { - free(field); + DavQLField *add_field; + dqlsec_malloc(stmt, add_field, DavQLField); + memcpy(add_field, &localfield, sizeof(DavQLField)); + if(dav_stmt_add_field(stmt, add_field)) { + free(add_field); return 0; } } @@ -1838,7 +1838,7 @@ void dav_free_statement(DavQLStatement *stmt) { if(stmt->fields) { - stmt->fields->simple_destructor = (cx_destructor_func)dav_free_field; + cxDefineDestructor(stmt->fields, dav_free_field); cxListDestroy(stmt->fields); } @@ -1850,7 +1850,7 @@ } if(stmt->orderby) { - stmt->orderby->simple_destructor = (cx_destructor_func)dav_free_order_criterion; + cxDefineDestructor(stmt->orderby, dav_free_order_criterion); cxListDestroy(stmt->orderby); } if(stmt->args) {
--- a/libidav/methods.c Sat Apr 20 13:01:58 2024 +0200 +++ b/libidav/methods.c Thu May 23 22:35:45 2024 +0200 @@ -75,7 +75,7 @@ curl_easy_setopt(handle, CURLOPT_WRITEFUNCTION, cxBufferWrite); curl_easy_setopt(handle, CURLOPT_WRITEDATA, response); CxMap *respheaders = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 32); - respheaders->simple_destructor = free; + cxDefineDestructor(respheaders, free); util_capture_header(handle, respheaders); for(int i=0;i<maxretry;i++) { @@ -831,25 +831,27 @@ cxstring s; CxMap *namespaces = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 8); - namespaces->simple_destructor = free; - - char prefix[8]; - int pfxnum = 0; - if(data->set) { - CxIterator i = cxListIterator(data->set); - cx_foreach(DavProperty*, p, i) { - if(strcmp(p->ns->name, "DAV:")) { - snprintf(prefix, 8, "x%d", pfxnum++); - cxMapPut(namespaces, cx_hash_key_str(p->ns->name), strdup(prefix)); + cxDefineDestructor(namespaces, free); + + { + char prefix[8]; + int pfxnum = 0; + if (data->set) { + CxIterator i = cxListIterator(data->set); + cx_foreach(DavProperty*, p, i) { + if (strcmp(p->ns->name, "DAV:")) { + snprintf(prefix, 8, "x%d", pfxnum++); + cxMapPut(namespaces, cx_hash_key_str(p->ns->name), strdup(prefix)); + } } } - } - if(data->remove) { - CxIterator i = cxListIterator(data->remove); - cx_foreach(DavProperty*, p, i) { - if(strcmp(p->ns->name, "DAV:")) { - snprintf(prefix, 8, "x%d", pfxnum++); - cxMapPut(namespaces, cx_hash_key_str(p->ns->name), strdup(prefix)); + if (data->remove) { + CxIterator i = cxListIterator(data->remove); + cx_foreach(DavProperty*, p, i) { + if (strcmp(p->ns->name, "DAV:")) { + snprintf(prefix, 8, "x%d", pfxnum++); + cxMapPut(namespaces, cx_hash_key_str(p->ns->name), strdup(prefix)); + } } } }
--- a/libidav/resource.c Sat Apr 20 13:01:58 2024 +0200 +++ b/libidav/resource.c Thu May 23 22:35:45 2024 +0200 @@ -127,7 +127,6 @@ if(!properties) return; CxIterator i = cxMapIteratorValues(properties); - DavProperty *property; cx_foreach(DavProperty*, property, i) { // TODO: free everything dav_session_free(sn, property); @@ -730,7 +729,7 @@ DavPropName* dav_get_property_names(DavResource *res, size_t *count) { DavResourceData *data = res->data; - *count = data->properties->size; + *count = cxMapSize(data->properties); DavPropName *names = dav_session_calloc( res->session, *count, @@ -738,15 +737,10 @@ CxIterator i = cxMapIteratorValues(data->properties); - DavProperty *value; - int j = 0; cx_foreach(DavProperty*, value, i) { - DavPropName *name = &names[j]; - + DavPropName *name = &names[i.index]; name->ns = value->ns->name; name->name = value->name; - - j++; } qsort(names, *count, sizeof(DavPropName), compare_propname); @@ -998,7 +992,7 @@ if(data->crypto_remove) { CxIterator i = cxListIterator(data->crypto_remove); cx_foreach(DavProperty *, property, i) { - if(crypto_props->size == 0) { + if(cxMapSize(crypto_props) == 0) { break; // map already empty, can't remove any more } @@ -1509,14 +1503,13 @@ // create an xml document containing all properties CxMap *nsmap = cxHashMapCreate(cxDefaultAllocator, CX_STORE_POINTERS, 8); - nsmap->simple_destructor = free; + cxDefineDestructor(nsmap, free); cxMapPut(nsmap, cx_hash_key_str("DAV:"), strdup("D")); cxBufferPutString(content, "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"); cxBufferPutString(content, "<D:prop xmlns:D=\"DAV:\">\n"); CxIterator i = cxMapIteratorValues(properties); - DavProperty *prop; cx_foreach(DavProperty*, prop, i) { DavXmlNode pnode; pnode.type = DAV_XML_ELEMENT; @@ -1600,15 +1593,15 @@ dav_session_strdup(sn, (const char*)n->ns->prefix) : NULL; property->value = n->children ? dav_convert_xml(sn, n->children) : NULL; - cxmutstr key = dav_property_key(property->ns->name, property->name); - cxMapPut(map, cx_hash_key(key.ptr, key.length), property); - free(key.ptr); + cxmutstr propkey = dav_property_key(property->ns->name, property->name); + cxMapPut(map, cx_hash_key_cxstr(propkey), property); + cx_strfree(&propkey); } n = n->next; } xmlFreeDoc(doc); - if(map->size == 0) { + if(cxMapSize(map) == 0) { cxMapDestroy(map); return NULL; }
--- a/libidav/session.c Sat Apr 20 13:01:58 2024 +0200 +++ b/libidav/session.c Thu May 23 22:35:45 2024 +0200 @@ -31,8 +31,7 @@ #include <string.h> #include <cx/buffer.h> -#include <cx/utils.h> -#include <cx/basic_mempool.h> +#include <cx/mempool.h> #include <cx/hash_map.h> #include "utils.h" @@ -636,16 +635,6 @@ if(cxMapRemoveAndGet(locks->resource_locks, cx_hash_key_str(path))) { return; } - - CxMutIterator i = cxListMutIterator(locks->collection_locks); - int rm = 0; - cx_foreach(DavLock* , cl, i) { - if(rm) { - break; - } - if(cl == lock) { - cxIteratorFlagRemoval(i); - rm = 1; - } - } + + cxListFindRemove(locks->collection_locks, lock); }
--- a/libidav/utils.c Sat Apr 20 13:01:58 2024 +0200 +++ b/libidav/utils.c Thu May 23 22:35:45 2024 +0200 @@ -522,9 +522,8 @@ // get prefix of abspath and base // this dir is the root of the link - size_t i; size_t last_dir = 0; - for(i=0;i<max;i++) { + for(size_t i=0;i<max;i++) { char c = abspath[i]; if(c != base[i]) { break; @@ -537,8 +536,8 @@ CxBuffer out; if(last_dir+1 < base_len) { // base is deeper than the link root, we have to go backwards - int dircount = 0; - for(int i=last_dir+1;i<base_len;i++) { + size_t dircount = 0; + for(size_t i=last_dir+1;i<base_len;i++) { if(IS_PATH_SEPARATOR(base[i])) { dircount++; } @@ -546,7 +545,7 @@ cxBufferInit(&out, NULL, dircount*3+path_len-last_dir, cxDefaultAllocator, CX_BUFFER_FREE_CONTENTS|CX_BUFFER_AUTO_EXTEND); - for(int i=0;i<dircount;i++) { + for(size_t i=0;i<dircount;i++) { cxBufferPutString(&out, "../"); } } else {
--- a/libidav/webdav.c Sat Apr 20 13:01:58 2024 +0200 +++ b/libidav/webdav.c Thu May 23 22:35:45 2024 +0200 @@ -51,7 +51,7 @@ return NULL; } context->sessions = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_intptr, CX_STORE_POINTERS); - context->sessions->destructor_data = dav_session_destructor; + cxDefineDestructor(context->sessions, dav_session_destructor); context->http_proxy = calloc(1, sizeof(DavProxy)); if(!context->http_proxy) { dav_context_destroy(context); @@ -302,11 +302,11 @@ char *pname = strchr(prefixed_name, ':'); char *pns = "DAV:"; if(pname) { - DavNamespace *ns = dav_get_namespace_s( + DavNamespace *davns = dav_get_namespace_s( ctx, cx_strn(prefixed_name, pname-prefixed_name)); - if(ns) { - pns = ns->name; + if(davns) { + pns = davns->name; pname++; } else { pns = NULL;
--- a/libidav/xml.c Sat Apr 20 13:01:58 2024 +0200 +++ b/libidav/xml.c Thu May 23 22:35:45 2024 +0200 @@ -72,7 +72,7 @@ DavXmlNode *ret = NULL; - while(stack->size > 0) { + while(cxListSize(stack) > 0) { ConvXmlElm *c = cxListAt(stack, 0); xmlNode *n = c->node; DavXmlNode *c_parent = c->parent; @@ -173,7 +173,7 @@ if(node->namespace) { prefix = cxMapGet(nsmap, cx_hash_key_str(node->namespace)); if(!prefix) { - cxmutstr newpre = cx_asprintf("x%d", (int)nsmap->size+1); + cxmutstr newpre = cx_asprintf("x%zu", cxMapSize(nsmap)+1); // TODO: fix namespace declaration //ucx_map_cstr_put(nsmap, node->namespace, newpre.ptr); prefix = newpre.ptr;
--- a/test/crypto.c Sat Apr 20 13:01:58 2024 +0200 +++ b/test/crypto.c Thu May 23 22:35:45 2024 +0200 @@ -236,11 +236,11 @@ char *aes128 = util_encrypt_str_k(sn, strings[i], &keys128[k]); char *aes256 = util_encrypt_str_k(sn, strings[i], &keys256[k]); - char *d1 = util_decrypt_str_k(sn, aes128, &keys128[k]); - char *d2 = util_decrypt_str_k(sn, aes256, &keys256[k]); + char *dec1 = util_decrypt_str_k(sn, aes128, &keys128[k]); + char *dec2 = util_decrypt_str_k(sn, aes256, &keys256[k]); - UCX_TEST_ASSERT(!strcmp(d1, strings[i]), "aes128 encrypt failed"); - UCX_TEST_ASSERT(!strcmp(d2, strings[i]), "aes256 encrypt failed"); + UCX_TEST_ASSERT(!strcmp(dec1, strings[i]), "aes128 encrypt failed"); + UCX_TEST_ASSERT(!strcmp(dec2, strings[i]), "aes256 encrypt failed"); } }
--- a/test/test.h Sat Apr 20 13:01:58 2024 +0200 +++ b/test/test.h Thu May 23 22:35:45 2024 +0200 @@ -68,8 +68,8 @@ * */ -#ifndef UCX_TEST_H -#define UCX_TEST_H +#ifndef UCX_21_TEST_H +#define UCX_21_TEST_H #include <stdio.h> #include <stdlib.h> @@ -237,5 +237,5 @@ } #endif -#endif /* UCX_TEST_H */ +#endif /* UCX_21_TEST_H */
--- a/ucx/Makefile Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/Makefile Thu May 23 22:35:45 2024 +0200 @@ -36,11 +36,13 @@ SRC += compare.c SRC += hash_key.c SRC += hash_map.c +SRC += iterator.c SRC += linked_list.c SRC += list.c SRC += map.c SRC += printf.c SRC += string.c +SRC += tree.c SRC += utils.c OBJ = $(SRC:%.c=../build/ucx/%$(OBJ_EXT))
--- a/ucx/array_list.c Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/array_list.c Thu May 23 22:35:45 2024 +0200 @@ -27,12 +27,30 @@ */ #include "cx/array_list.h" +#include "cx/compare.h" #include <assert.h> #include <string.h> +// Default array reallocator + +static void *cx_array_default_realloc( + void *array, + size_t capacity, + size_t elem_size, + __attribute__((__unused__)) struct cx_array_reallocator_s *alloc +) { + return realloc(array, capacity * elem_size); +} + +struct cx_array_reallocator_s cx_array_default_reallocator_impl = { + cx_array_default_realloc, NULL, NULL, 0, 0 +}; + +struct cx_array_reallocator_s *cx_array_default_reallocator = &cx_array_default_reallocator_impl; + // LOW LEVEL ARRAY LIST FUNCTIONS -enum cx_array_copy_result cx_array_copy( +enum cx_array_result cx_array_copy( void **target, size_t *size, size_t *capacity, @@ -59,7 +77,7 @@ if (needrealloc) { // a reallocator and a capacity variable must be available if (reallocator == NULL || capacity == NULL) { - return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED; + return CX_ARRAY_REALLOC_NOT_SUPPORTED; } // check, if we need to repair the src pointer @@ -77,7 +95,7 @@ *target, cap, elem_size, reallocator ); if (newmem == NULL) { - return CX_ARRAY_COPY_REALLOC_FAILED; + return CX_ARRAY_REALLOC_FAILED; } // repair src pointer, if necessary @@ -99,12 +117,13 @@ *size = newsize; // return successfully - return CX_ARRAY_COPY_SUCCESS; + return CX_ARRAY_SUCCESS; } #ifndef CX_ARRAY_SWAP_SBO_SIZE #define CX_ARRAY_SWAP_SBO_SIZE 128 #endif +unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE; void cx_array_swap( void *arr, @@ -172,21 +191,21 @@ char *ptr = arl->data; - if (list->simple_destructor) { - for (size_t i = 0; i < list->size; i++) { + if (list->collection.simple_destructor) { + for (size_t i = 0; i < list->collection.size; i++) { cx_invoke_simple_destructor(list, ptr); - ptr += list->item_size; + ptr += list->collection.elem_size; } } - if (list->advanced_destructor) { - for (size_t i = 0; i < list->size; i++) { + if (list->collection.advanced_destructor) { + for (size_t i = 0; i < list->collection.size; i++) { cx_invoke_advanced_destructor(list, ptr); - ptr += list->item_size; + ptr += list->collection.elem_size; } } - cxFree(list->allocator, arl->data); - cxFree(list->allocator, list); + cxFree(list->collection.allocator, arl->data); + cxFree(list->collection.allocator, list); } static size_t cx_arl_insert_array( @@ -196,25 +215,25 @@ size_t n ) { // out of bounds and special case check - if (index > list->size || n == 0) return 0; + if (index > list->collection.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) { + if (index < list->collection.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; + first_to_move += index * list->collection.elem_size; + size_t elems_to_move = list->collection.size - index; size_t start_of_moved = index + n; - if (CX_ARRAY_COPY_SUCCESS != cx_array_copy( + if (CX_ARRAY_SUCCESS != cx_array_copy( &arl->data, - &list->size, + &list->collection.size, &arl->capacity, start_of_moved, first_to_move, - list->item_size, + list->collection.elem_size, elems_to_move, &arl->reallocator )) { @@ -228,13 +247,13 @@ // therefore, it is impossible to leave this function with an invalid array // place the new elements - if (CX_ARRAY_COPY_SUCCESS == cx_array_copy( + if (CX_ARRAY_SUCCESS == cx_array_copy( &arl->data, - &list->size, + &list->collection.size, &arl->capacity, index, array, - list->item_size, + list->collection.elem_size, n, &arl->reallocator )) { @@ -254,12 +273,12 @@ } static int cx_arl_insert_iter( - struct cx_mut_iterator_s *iter, + struct cx_iterator_s *iter, void const *elem, int prepend ) { - struct cx_list_s *list = iter->src_handle; - if (iter->index < list->size) { + struct cx_list_s *list = iter->src_handle.m; + if (iter->index < list->collection.size) { int result = cx_arl_insert_element( list, iter->index + 1 - prepend, @@ -267,12 +286,12 @@ ); if (result == 0 && prepend != 0) { iter->index++; - iter->elem_handle = ((char *) iter->elem_handle) + list->item_size; + iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size; } return result; } else { - int result = cx_arl_insert_element(list, list->size, elem); - iter->index = list->size; + int result = cx_arl_insert_element(list, list->collection.size, elem); + iter->index = list->collection.size; return result; } } @@ -284,58 +303,61 @@ cx_array_list *arl = (cx_array_list *) list; // out-of-bounds check - if (index >= list->size) { + if (index >= list->collection.size) { return 1; } // content destruction - cx_invoke_destructor(list, ((char *) arl->data) + index * list->item_size); + cx_invoke_destructor(list, ((char *) arl->data) + index * list->collection.elem_size); // short-circuit removal of last element - if (index == list->size - 1) { - list->size--; + if (index == list->collection.size - 1) { + list->collection.size--; return 0; } // just move the elements starting at index to the left int result = cx_array_copy( &arl->data, - &list->size, + &list->collection.size, &arl->capacity, index, - ((char *) arl->data) + (index + 1) * list->item_size, - list->item_size, - list->size - index - 1, + ((char *) arl->data) + (index + 1) * list->collection.elem_size, + list->collection.elem_size, + list->collection.size - index - 1, &arl->reallocator ); - if (result == 0) { - // decrease the size - list->size--; - } - return result; + + // cx_array_copy cannot fail, array cannot grow + assert(result == 0); + + // decrease the size + list->collection.size--; + + return 0; } static void cx_arl_clear(struct cx_list_s *list) { - if (list->size == 0) return; + if (list->collection.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++) { + if (list->collection.simple_destructor) { + for (size_t i = 0; i < list->collection.size; i++) { cx_invoke_simple_destructor(list, ptr); - ptr += list->item_size; + ptr += list->collection.elem_size; } } - if (list->advanced_destructor) { - for (size_t i = 0; i < list->size; i++) { + if (list->collection.advanced_destructor) { + for (size_t i = 0; i < list->collection.size; i++) { cx_invoke_advanced_destructor(list, ptr); - ptr += list->item_size; + ptr += list->collection.elem_size; } } - memset(arl->data, 0, list->size * list->item_size); - list->size = 0; + memset(arl->data, 0, list->collection.size * list->collection.elem_size); + list->collection.size = 0; } static int cx_arl_swap( @@ -343,9 +365,9 @@ size_t i, size_t j ) { - if (i >= list->size || j >= list->size) return 1; + if (i >= list->collection.size || j >= list->collection.size) return 1; cx_array_list *arl = (cx_array_list *) list; - cx_array_swap(arl->data, list->item_size, i, j); + cx_array_swap(arl->data, list->collection.elem_size, i, j); return 0; } @@ -353,39 +375,48 @@ struct cx_list_s const *list, size_t index ) { - if (index < list->size) { + if (index < list->collection.size) { cx_array_list const *arl = (cx_array_list const *) list; char *space = arl->data; - return space + index * list->item_size; + return space + index * list->collection.elem_size; } else { return NULL; } } -static ssize_t cx_arl_find( - struct cx_list_s const *list, - void const *elem +static ssize_t cx_arl_find_remove( + struct cx_list_s *list, + void const *elem, + bool remove ) { - assert(list->cmpfunc != NULL); - assert(list->size < SIZE_MAX / 2); + assert(list->collection.cmpfunc != NULL); + assert(list->collection.size < SIZE_MAX / 2); char *cur = ((cx_array_list const *) list)->data; - for (ssize_t i = 0; i < (ssize_t) list->size; i++) { - if (0 == list->cmpfunc(elem, cur)) { - return i; + for (ssize_t i = 0; i < (ssize_t) list->collection.size; i++) { + if (0 == list->collection.cmpfunc(elem, cur)) { + if (remove) { + if (0 == cx_arl_remove(list, i)) { + return i; + } else { + return -1; + } + } else { + return i; + } } - cur += list->item_size; + cur += list->collection.elem_size; } return -1; } static void cx_arl_sort(struct cx_list_s *list) { - assert(list->cmpfunc != NULL); + assert(list->collection.cmpfunc != NULL); qsort(((cx_array_list *) list)->data, - list->size, - list->item_size, - list->cmpfunc + list->collection.size, + list->collection.elem_size, + list->collection.cmpfunc ); } @@ -393,37 +424,37 @@ struct cx_list_s const *list, struct cx_list_s const *other ) { - assert(list->cmpfunc != NULL); - if (list->size == other->size) { + assert(list->collection.cmpfunc != NULL); + if (list->collection.size == other->collection.size) { char const *left = ((cx_array_list const *) list)->data; char const *right = ((cx_array_list const *) other)->data; - for (size_t i = 0; i < list->size; i++) { - int d = list->cmpfunc(left, right); + for (size_t i = 0; i < list->collection.size; i++) { + int d = list->collection.cmpfunc(left, right); if (d != 0) { return d; } - left += list->item_size; - right += other->item_size; + left += list->collection.elem_size; + right += other->collection.elem_size; } return 0; } else { - return list->size < other->size ? -1 : 1; + return list->collection.size < other->collection.size ? -1 : 1; } } static void cx_arl_reverse(struct cx_list_s *list) { - if (list->size < 2) return; + if (list->collection.size < 2) return; void *data = ((cx_array_list const *) list)->data; - size_t half = list->size / 2; + size_t half = list->collection.size / 2; for (size_t i = 0; i < half; i++) { - cx_array_swap(data, list->item_size, i, list->size - 1 - i); + cx_array_swap(data, list->collection.elem_size, i, list->collection.size - 1 - i); } } static bool cx_arl_iter_valid(void const *it) { struct cx_iterator_s const *iter = it; - struct cx_list_s const *list = iter->src_handle; - return iter->index < list->size; + struct cx_list_s const *list = iter->src_handle.c; + return iter->index < list->collection.size; } static void *cx_arl_iter_current(void const *it) { @@ -432,44 +463,32 @@ } static void cx_arl_iter_next(void *it) { - struct cx_iterator_base_s *itbase = it; - if (itbase->remove) { - struct cx_mut_iterator_s *iter = it; - itbase->remove = false; - cx_arl_remove(iter->src_handle, iter->index); + struct cx_iterator_s *iter = it; + if (iter->base.remove) { + iter->base.remove = false; + cx_arl_remove(iter->src_handle.m, iter->index); } else { - struct cx_iterator_s *iter = it; iter->index++; iter->elem_handle = ((char *) iter->elem_handle) - + ((struct cx_list_s const *) iter->src_handle)->item_size; + + ((struct cx_list_s const *) iter->src_handle.c)->collection.elem_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); + struct cx_iterator_s *iter = it; + cx_array_list const* list = iter->src_handle.c; + if (iter->base.remove) { + iter->base.remove = false; + cx_arl_remove(iter->src_handle.m, iter->index); } iter->index--; - if (iter->index < list->base.size) { + if (iter->index < list->base.collection.size) { iter->elem_handle = ((char *) list->data) - + iter->index * list->base.item_size; + + iter->index * list->base.collection.elem_size; } } -static bool cx_arl_iter_flag_rm(void *it) { - struct cx_iterator_base_s *iter = it; - if (iter->mutating) { - iter->remove = true; - return true; - } else { - return false; - } -} static struct cx_iterator_s cx_arl_iterator( struct cx_list_s const *list, @@ -479,12 +498,13 @@ struct cx_iterator_s iter; iter.index = index; - iter.src_handle = list; + iter.src_handle.c = list; iter.elem_handle = cx_arl_at(list, index); + iter.elem_size = list->collection.elem_size; + iter.elem_count = list->collection.size; iter.base.valid = cx_arl_iter_valid; iter.base.current = cx_arl_iter_current; 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; @@ -500,7 +520,7 @@ cx_arl_clear, cx_arl_swap, cx_arl_at, - cx_arl_find, + cx_arl_find_remove, cx_arl_sort, cx_arl_compare, cx_arl_reverse, @@ -510,7 +530,7 @@ CxList *cxArrayListCreate( CxAllocator const *allocator, cx_compare_func comparator, - size_t item_size, + size_t elem_size, size_t initial_capacity ) { if (allocator == NULL) { @@ -521,19 +541,20 @@ if (list == NULL) return NULL; list->base.cl = &cx_array_list_class; - list->base.allocator = allocator; - list->base.cmpfunc = comparator; + list->base.collection.allocator = allocator; list->capacity = initial_capacity; - if (item_size > 0) { - list->base.item_size = item_size; + if (elem_size > 0) { + list->base.collection.elem_size = elem_size; + list->base.collection.cmpfunc = comparator; } else { - item_size = sizeof(void *); + elem_size = sizeof(void *); + list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; cxListStorePointers((CxList *) list); } - // allocate the array after the real item_size is known - list->data = cxCalloc(allocator, initial_capacity, item_size); + // allocate the array after the real elem_size is known + list->data = cxCalloc(allocator, initial_capacity, elem_size); if (list->data == NULL) { cxFree(allocator, list); return NULL;
--- a/ucx/buffer.c Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/buffer.c Thu May 23 22:35:45 2024 +0200 @@ -135,6 +135,11 @@ buffer->pos = 0; } +void cxBufferReset(CxBuffer *buffer) { + buffer->size = 0; + buffer->pos = 0; +} + int cxBufferEof(CxBuffer const *buffer) { return buffer->pos >= buffer->size; }
--- a/ucx/compare.c Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/compare.c Thu May 23 22:35:45 2024 +0200 @@ -199,3 +199,15 @@ } } +int cx_cmp_ptr( + void const *ptr1, + void const *ptr2 +) { + uintptr_t p1 = (uintptr_t) ptr1; + uintptr_t p2 = (uintptr_t) ptr2; + if (p1 == p2) { + return 0; + } else { + return p1 < p2 ? -1 : 1; + } +}
--- a/ucx/cx/array_list.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/array_list.h Thu May 23 22:35:45 2024 +0200 @@ -31,7 +31,6 @@ * \details Also provides several low-level functions for custom array list implementations. * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */ @@ -46,16 +45,46 @@ #endif /** + * The maximum item size in an array list that fits into stack buffer when swapped. + */ +extern unsigned cx_array_swap_sbo_size; + +/** + * Declares variables for an array that can be used with the convenience macros. + * + * @see cx_array_simple_add() + * @see cx_array_simple_copy() + * @see cx_array_initialize() + */ +#define CX_ARRAY_DECLARE(type, name) \ + type * name; \ + size_t name##_size; \ + size_t name##_capacity + +/** + * Initializes an array declared with CX_ARRAY_DECLARE(). + * + * The memory for the array is allocated with stdlib malloc(). + * @param array the array + * @param capacity the initial capacity + */ +#define cx_array_initialize(array, capacity) \ + array##_capacity = capacity; \ + array##_size = 0; \ + array = malloc(sizeof(array[0]) * capacity) + +/** * Defines a reallocation mechanism for arrays. */ struct cx_array_reallocator_s { /** - * Re-allocates space for the given array. + * Reallocates space for the given array. * * Implementations are not required to free the original array. - * This allows re-allocation of static memory by allocating heap memory - * and copying the array contents. The information in \p data can keep - * track of the state of the memory or other additional allocator info. + * This allows reallocation of static memory by allocating heap memory + * and copying the array contents. The information in the custom fields of + * the referenced allocator can be used to track the state of the memory + * or to transport other additional data. * * @param array the array to reallocate * @param capacity the new capacity (number of elements) @@ -89,12 +118,17 @@ }; /** - * Return codes for cx_array_copy(). + * A default stdlib-based array reallocator. */ -enum cx_array_copy_result { - CX_ARRAY_COPY_SUCCESS, - CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED, - CX_ARRAY_COPY_REALLOC_FAILED, +extern struct cx_array_reallocator_s *cx_array_default_reallocator; + +/** + * Return codes for array functions. + */ +enum cx_array_result { + CX_ARRAY_SUCCESS, + CX_ARRAY_REALLOC_NOT_SUPPORTED, + CX_ARRAY_REALLOC_FAILED, }; /** @@ -107,10 +141,10 @@ * 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 + * attempt is made, unless the \p reallocator is set to \c NULL, in which case * this function ultimately returns a failure. * - * @param target the target array + * @param target a pointer to the target array * @param size a pointer to the size of the target array * @param capacity a pointer to the target array's capacity - * \c NULL if only the size shall be used to bound the array @@ -118,11 +152,11 @@ * @param src the source array * @param elem_size the size of one element * @param elem_count the number of elements to copy - * @param reallocator the array re-allocator to use, or \c NULL - * if re-allocation shall not happen + * @param reallocator the array reallocator to use, or \c NULL + * if reallocation shall not happen * @return zero on success, non-zero error code on failure */ -enum cx_array_copy_result cx_array_copy( +enum cx_array_result cx_array_copy( void **target, size_t *size, size_t *capacity, @@ -133,6 +167,48 @@ struct cx_array_reallocator_s *reallocator ) __attribute__((__nonnull__(1, 2, 5))); +/** + * Convenience macro that uses cx_array_copy() with a default layout and the default reallocator. + * + * @param array the name of the array (NOT a pointer to the array) + * @param index the index where the copied elements shall be placed + * @param src the source array + * @param count the number of elements to copy + */ +#define cx_array_simple_copy(array, index, src, count) \ + cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \ + index, src, sizeof((array)[0]), count, cx_array_default_reallocator) + +/** + * Adds an element to an array with the possibility of allocating more space. + * + * The element \p elem is added to the end of the \p target array which containing + * \p size elements, already. The \p capacity must not be \c NULL and point a + * variable holding the current maximum number of elements the array can hold. + * + * If the capacity is insufficient to hold the new element, and the optional + * \p reallocator is not \c NULL, an attempt increase the \p capacity is made + * and the new capacity is written back. + * + * @param target a pointer to the target array + * @param size a pointer to the size of the target array + * @param capacity a pointer to the target array's capacity - must not be \c NULL + * @param elem_size the size of one element + * @param elem a pointer to the element to add + * @param reallocator the array reallocator to use, or \c NULL if reallocation shall not happen + * @return zero on success, non-zero error code on failure + */ +#define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \ + cx_array_copy((void**)(target), size, capacity, *(size), elem, elem_size, 1, reallocator) + +/** + * Convenience macro that uses cx_array_add() with a default layout and the default reallocator. + * + * @param array the name of the array (NOT a pointer to the array) + * @param elem the element to add (NOT a pointer, address is automatically taken) + */ +#define cx_array_simple_add(array, elem) \ + cx_array_simple_copy(array, array##_size, &(elem), 1) /** * Swaps two array elements. @@ -150,42 +226,45 @@ ) __attribute__((__nonnull__)); /** - * Allocates an array list for storing elements with \p item_size bytes each. + * Allocates an array list for storing elements with \p elem_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. + * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if + * cxListStorePointers() was called immediately after creation and the compare + * function will be automatically set to cx_cmp_ptr(), if none is given. * * @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 + * (if \c NULL, and the list is not storing pointers, sort and find + * functions will not work) + * @param elem_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, cx_compare_func comparator, - size_t item_size, + size_t elem_size, size_t initial_capacity ); /** - * Allocates an array list for storing elements with \p item_size bytes each. + * Allocates an array list for storing elements with \p elem_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. + * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if + * cxListStorePointers() was called immediately after creation and the compare + * function will be automatically set to cx_cmp_ptr(). * - * @param item_size the size of each element in bytes + * @param elem_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) +#define cxArrayListCreateSimple(elem_size, initial_capacity) \ + cxArrayListCreate(NULL, NULL, elem_size, initial_capacity) #ifdef __cplusplus } // extern "C"
--- a/ucx/cx/basic_mempool.h Sat Apr 20 13:01:58 2024 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,76 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - */ -/** - * \file basic_mempool.h - * \brief Implementation of a basic memory pool. - * \author Mike Becker - * \author Olaf Wintermann - * \version 3.0 - * \copyright 2-Clause BSD License - */ - -#ifndef UCX_BASIC_MEMPOOL_H -#define UCX_BASIC_MEMPOOL_H - -#include "mempool.h" - -#ifdef __cplusplus -extern "C" { -#endif - -/** - * Basic array-based memory pool. - */ -struct cx_basic_mempool_s { - /** Inherit base structure members. */ - CxMempool base; - - /** List of pointers to pooled memory. */ - void **data; - - /** Number of pooled memory items. */ - size_t ndata; - - /** Memory pool size. */ - size_t size; -}; - -/** - * Creates a basic array-based memory pool. - * - * @param capacity the initial capacity of the pool - * @return the created memory pool or \c NULL if allocation failed - */ -__attribute__((__warn_unused_result__)) -CxMempool *cxBasicMempoolCreate(size_t capacity); - -#ifdef __cplusplus -} // extern "C" -#endif - -#endif // UCX_BASIC_MEMPOOL_H
--- a/ucx/cx/buffer.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/buffer.h Thu May 23 22:35:45 2024 +0200 @@ -40,7 +40,6 @@ * * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */ @@ -312,18 +311,32 @@ * Clears the buffer by resetting the position and deleting the data. * * The data is deleted by zeroing it with a call to memset(). + * If you do not need that, you can use the faster cxBufferReset(). * * @param buffer the buffer to be cleared + * @see cxBufferReset() */ __attribute__((__nonnull__)) void cxBufferClear(CxBuffer *buffer); /** - * Tests, if the buffer position has exceeded the buffer capacity. + * Resets the buffer by resetting the position and size to zero. + * + * The data in the buffer is not deleted. If you need a safe + * reset of the buffer, use cxBufferClear(). + * + * @param buffer the buffer to be cleared + * @see cxBufferClear() + */ +__attribute__((__nonnull__)) +void cxBufferReset(CxBuffer *buffer); + +/** + * Tests, if the buffer position has exceeded the buffer size. * * @param buffer the buffer to test * @return non-zero, if the current buffer position has exceeded the last - * available byte of the buffer. + * byte of the buffer's contents. */ __attribute__((__nonnull__)) int cxBufferEof(CxBuffer const *buffer);
--- a/ucx/cx/collection.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/collection.h Thu May 23 22:35:45 2024 +0200 @@ -30,7 +30,6 @@ * \brief Common definitions for various collection implementations. * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */ @@ -39,6 +38,7 @@ #include "allocator.h" #include "iterator.h" +#include "compare.h" #ifdef __cplusplus extern "C" { @@ -50,56 +50,73 @@ #define CX_STORE_POINTERS 0 /** - * A comparator function comparing two collection elements. + * Base attributes of a collection. */ -typedef int(*cx_compare_func)( - void const *left, - void const *right -); +struct cx_collection_s { + /** + * The allocator to use. + */ + CxAllocator const *allocator; + /** + * The comparator function for the elements. + */ + cx_compare_func cmpfunc; + /** + * The size of each element. + */ + size_t elem_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 list is supposed to store pointers + * instead of copies of the actual objects. + */ + bool store_pointer; +}; /** * 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; +#define CX_COLLECTION_BASE struct cx_collection_s collection + +/** + * Sets a simple destructor function for this collection. + * + * @param c the collection + * @param destr the destructor function + */ +#define cxDefineDestructor(c, destr) \ + (c)->collection.simple_destructor = (cx_destructor_func) destr + +/** + * Sets a simple destructor function for this collection. + * + * @param c the collection + * @param destr the destructor function + */ +#define cxDefineAdvancedDestructor(c, destr, data) \ + (c)->collection.advanced_destructor = (cx_destructor_func2) destr; \ + (c)->collection.destructor_data = data /** * Invokes the simple destructor function for a specific element. @@ -111,7 +128,7 @@ * @param e the element */ #define cx_invoke_simple_destructor(c, e) \ - (c)->simple_destructor((c)->store_pointer ? (*((void **) (e))) : (e)) + (c)->collection.simple_destructor((c)->collection.store_pointer ? (*((void **) (e))) : (e)) /** * Invokes the advanced destructor function for a specific element. @@ -123,8 +140,8 @@ * @param e the element */ #define cx_invoke_advanced_destructor(c, e) \ - (c)->advanced_destructor((c)->destructor_data, \ - (c)->store_pointer ? (*((void **) (e))) : (e)) + (c)->collection.advanced_destructor((c)->collection.destructor_data, \ + (c)->collection.store_pointer ? (*((void **) (e))) : (e)) /** @@ -137,8 +154,8 @@ * @param e the element */ #define cx_invoke_destructor(c, e) \ - if ((c)->simple_destructor) cx_invoke_simple_destructor(c,e); \ - if ((c)->advanced_destructor) cx_invoke_advanced_destructor(c,e) + if ((c)->collection.simple_destructor) cx_invoke_simple_destructor(c,e); \ + if ((c)->collection.advanced_destructor) cx_invoke_advanced_destructor(c,e) #ifdef __cplusplus } // extern "C"
--- a/ucx/cx/common.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/common.h Thu May 23 22:35:45 2024 +0200 @@ -33,7 +33,6 @@ * * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License * * \mainpage UAP Common Extensions @@ -84,7 +83,7 @@ #define UCX_VERSION_MAJOR 3 /** Minor UCX version as integer constant. */ -#define UCX_VERSION_MINOR 0 +#define UCX_VERSION_MINOR 1 /** Version constant which ensures to increase monotonically. */ #define UCX_VERSION (((UCX_VERSION_MAJOR)<<16)|UCX_VERSION_MINOR) @@ -97,6 +96,7 @@ #include <stdint.h> #include <sys/types.h> +#ifndef UCX_TEST_H /** * Function pointer compatible with fwrite-like functions. */ @@ -106,6 +106,7 @@ size_t, void * ); +#endif // UCX_TEST_H /** * Function pointer compatible with fread-like functions.
--- a/ucx/cx/compare.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/compare.h Thu May 23 22:35:45 2024 +0200 @@ -30,7 +30,6 @@ * \brief A collection of simple compare functions. * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */ @@ -43,6 +42,17 @@ extern "C" { #endif +#ifndef CX_COMPARE_FUNC_DEFINED +#define CX_COMPARE_FUNC_DEFINED +/** + * A comparator function comparing two collection elements. + */ +typedef int(*cx_compare_func)( + void const *left, + void const *right +); +#endif // CX_COMPARE_FUNC_DEFINED + /** * Compares two integers of type int. * @@ -213,6 +223,19 @@ void const *ptr2 ); +/** + * Compares the pointers specified in the arguments without de-referencing. + * + * @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 + */ +int cx_cmp_ptr( + void const *ptr1, + void const *ptr2 +); + #ifdef __cplusplus } // extern "C" #endif
--- a/ucx/cx/hash_key.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/hash_key.h Thu May 23 22:35:45 2024 +0200 @@ -30,7 +30,6 @@ * \brief Interface for map implementations. * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */
--- a/ucx/cx/hash_map.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/hash_map.h Thu May 23 22:35:45 2024 +0200 @@ -30,7 +30,6 @@ * \brief Hash map implementation. * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */ @@ -70,7 +69,7 @@ * * 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 + * If \p elem_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. @@ -92,7 +91,7 @@ /** * 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 + * If \p elem_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.
--- a/ucx/cx/iterator.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/iterator.h Thu May 23 22:35:45 2024 +0200 @@ -30,7 +30,6 @@ * \brief Interface for iterator implementations. * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */ @@ -39,9 +38,6 @@ #include "common.h" -/** - * The base of mutating and non-mutating iterators. - */ struct cx_iterator_base_s { /** * True iff the iterator points to valid data. @@ -70,20 +66,10 @@ */ __attribute__ ((__nonnull__)) void (*next)(void *); - - /** - * Flag current element for removal, if possible. - * - * When valid returns false, the behavior of this function is undefined. - */ - __attribute__ ((__nonnull__)) - bool (*flag_removal)(void *); - /** * Indicates whether this iterator may remove elements. */ bool mutating; - /** * Internal flag for removing the current element when advancing. */ @@ -91,24 +77,34 @@ }; /** - * Internal iterator struct - use CxMutIterator. + * Declares base attributes for an iterator. */ -struct cx_mut_iterator_s { +#define CX_ITERATOR_BASE struct cx_iterator_base_s base + +/** + * Internal iterator struct - use CxIterator. + */ +struct cx_iterator_s { + CX_ITERATOR_BASE; /** - * The base properties of this iterator. - */ - struct cx_iterator_base_s base; - - /** - * Handle for the current element, if required. + * Handle for the current element. */ void *elem_handle; /** * Handle for the source collection, if any. */ - void *src_handle; + union { + /** + * Access for mutating iterators. + */ + void *m; + /** + * Access for normal iterators. + */ + void const *c; + } src_handle; /** * Field for storing a key-value pair. @@ -136,83 +132,29 @@ * Otherwise, this field is usually uninitialized. */ size_t index; + + /** + * The size of an individual element. + */ + size_t elem_size; + + /** + * May contain the total number of elements, if known. + * Shall be set to \c SIZE_MAX when the total number is unknown during iteration. + */ + size_t elem_count; }; /** - * Mutating iterator value type. - * - * An iterator points to a certain element in an (possibly unbounded) chain of elements. - * Iterators that are based on collections (which have a defined "first" element), are supposed - * to be "position-aware", which means that they keep track of the current index within the collection. - * - * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the - * iterator is based on a collection and the underlying collection is mutated by other means than this iterator - * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns) - * and MUST be re-obtained from the collection. + * Iterator type. * - * @see CxIterator - */ -typedef struct cx_mut_iterator_s CxMutIterator; - -/** - * Internal iterator struct - use CxIterator. - */ -struct cx_iterator_s { - - /** - * The base properties of this iterator. - */ - struct cx_iterator_base_s base; - - /** - * Handle for the current element, if required. - */ - void *elem_handle; - - /** - * Handle for the source collection, if any. - */ - void const *src_handle; - - /** - * Field for storing a key-value pair. - * May be used by iterators that iterate over k/v-collections. - */ - struct { - /** - * A pointer to the key. - */ - void const *key; - /** - * A pointer to the value. - */ - void *value; - } kv_data; - - /** - * Field for storing a slot number. - * May be used by iterators that iterate over multi-bucket collections. - */ - size_t slot; - - /** - * If the iterator is position-aware, contains the index of the element in the underlying collection. - * Otherwise, this field is usually uninitialized. - */ - size_t index; -}; - -/** - * Iterator value type. * An iterator points to a certain element in a (possibly unbounded) chain of elements. * Iterators that are based on collections (which have a defined "first" element), are supposed * to be "position-aware", which means that they keep track of the current index within the collection. * * @note Objects that are pointed to by an iterator are always mutable through that iterator. However, - * this iterator cannot mutate the collection itself (add or remove elements) and any mutation of the - * collection by other means makes this iterator invalid (regardless of what cxIteratorValid() returns). - * - * @see CxMutIterator + * any concurrent mutation of the collection other than by this iterator makes this iterator invalid + * and it must not be used anymore. */ typedef struct cx_iterator_s CxIterator; @@ -244,12 +186,11 @@ #define cxIteratorNext(iter) (iter).base.next(&iter) /** - * Flags the current element for removal. + * Flags the current element for removal, if this iterator is mutating. * * @param iter the iterator - * @return false if this iterator cannot remove the element */ -#define cxIteratorFlagRemoval(iter) (iter).base.flag_removal(&iter) +#define cxIteratorFlagRemoval(iter) (iter).base.remove |= (iter).base.mutating /** * Loops over an iterator. @@ -260,4 +201,55 @@ #define cx_foreach(type, elem, iter) \ for (type elem; cxIteratorValid(iter) && (elem = (type)cxIteratorCurrent(iter)) != NULL ; cxIteratorNext(iter)) + +/** + * Creates an iterator for the specified plain array. + * + * The \p array can be \c NULL in which case the iterator will be immediately + * initialized such that #cxIteratorValid() returns \c false. + * + * + * @param array a pointer to the array (can be \c NULL) + * @param elem_size the size of one array element + * @param elem_count the number of elements in the array + * @return an iterator for the specified array + */ +__attribute__((__warn_unused_result__)) +CxIterator cxIterator( + void const *array, + size_t elem_size, + size_t elem_count +); + +/** + * Creates a mutating iterator for the specified plain array. + * + * While the iterator is in use, the array may only be altered by removing + * elements through #cxIteratorFlagRemoval(). Every other change to the array + * will bring this iterator to an undefined state. + * + * When \p remove_keeps_order is set to \c false, removing an element will only + * move the last element to the position of the removed element, instead of + * moving all subsequent elements by one. Usually, when the order of elements is + * not important, this parameter should be set to \c false. + * + * The \p array can be \c NULL in which case the iterator will be immediately + * initialized such that #cxIteratorValid() returns \c false. + * + * + * @param array a pointer to the array (can be \c NULL) + * @param elem_size the size of one array element + * @param elem_count the number of elements in the array + * @param remove_keeps_order \c true if the order of elements must be preserved + * when removing an element + * @return an iterator for the specified array + */ +__attribute__((__warn_unused_result__)) +CxIterator cxMutIterator( + void *array, + size_t elem_size, + size_t elem_count, + bool remove_keeps_order +); + #endif // UCX_ITERATOR_H
--- a/ucx/cx/linked_list.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/linked_list.h Thu May 23 22:35:45 2024 +0200 @@ -31,7 +31,6 @@ * \details Also provides several low-level functions for custom linked list implementations. * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */ @@ -46,45 +45,47 @@ #endif /** - * Set this flag to true, if you want to disable the use of SBO for - * linked list swap operations. + * The maximum item size that uses SBO swap instead of relinking. */ -extern bool CX_DISABLE_LINKED_LIST_SWAP_SBO; +extern unsigned cx_linked_list_swap_sbo_size; /** - * Allocates a linked list for storing elements with \p item_size bytes each. + * Allocates a linked list for storing elements with \p elem_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. + * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if + * cxListStorePointers() was called immediately after creation and the compare + * function will be automatically set to cx_cmp_ptr(), if none is given. * * @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 + * (if \c NULL, and the list is not storing pointers, sort and find + * functions will not work) + * @param elem_size the size of each element in bytes * @return the created list */ CxList *cxLinkedListCreate( CxAllocator const *allocator, cx_compare_func comparator, - size_t item_size + size_t elem_size ); /** - * Allocates a linked list for storing elements with \p item_size bytes each. + * Allocates a linked list for storing elements with \p elem_size bytes each. * * 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(). * - * If \p item_size is CX_STORE_POINTERS, the created list will be created as if - * cxListStorePointers() was called immediately after creation. + * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if + * cxListStorePointers() was called immediately after creation and the compare + * function will be automatically set to cx_cmp_ptr(). * - * @param item_size the size of each element in bytes + * @param elem_size the size of each element in bytes * @return the created list */ -#define cxLinkedListCreateSimple(item_size) \ - cxLinkedListCreate(NULL, NULL, item_size) +#define cxLinkedListCreateSimple(elem_size) \ + cxLinkedListCreate(NULL, NULL, elem_size) /** * Finds the node at a certain index. @@ -129,6 +130,27 @@ ) __attribute__((__nonnull__)); /** + * Finds the node containing an element within a linked list. + * + * @param result a pointer to the memory where the node pointer (or \c NULL if the element + * could not be found) shall be stored to + * @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 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 negative value if it could not be found + */ +ssize_t cx_linked_list_find_node( + void **result, + void const *start, + ptrdiff_t loc_advance, + ptrdiff_t loc_data, + cx_compare_func cmp_func, + void const *elem +) __attribute__((__nonnull__)); + +/** * Finds the first node in a linked list. * * The function starts with the pointer denoted by \p node and traverses the list
--- a/ucx/cx/list.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/list.h Thu May 23 22:35:45 2024 +0200 @@ -30,7 +30,6 @@ * \brief Interface for list implementations. * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */ @@ -53,7 +52,7 @@ * Structure for holding the base data of a list. */ struct cx_list_s { - CX_COLLECTION_MEMBERS + CX_COLLECTION_BASE; /** * The list class definition. */ @@ -101,7 +100,7 @@ * Member function for inserting an element relative to an iterator position. */ int (*insert_iter)( - struct cx_mut_iterator_s *iter, + struct cx_iterator_s *iter, void const *elem, int prepend ); @@ -137,11 +136,12 @@ ); /** - * Member function for finding an element. + * Member function for finding and optionally removing an element. */ - ssize_t (*find)( - struct cx_list_s const *list, - void const *elem + ssize_t (*find_remove)( + struct cx_list_s *list, + void const *elem, + bool remove ); /** @@ -213,7 +213,7 @@ */ __attribute__((__nonnull__)) static inline bool cxListIsStoringPointers(CxList const *list) { - return list->store_pointer; + return list->collection.store_pointer; } /** @@ -224,7 +224,7 @@ */ __attribute__((__nonnull__)) static inline size_t cxListSize(CxList const *list) { - return list->size; + return list->collection.size; } /** @@ -240,7 +240,7 @@ CxList *list, void const *elem ) { - return list->cl->insert_element(list, list->size, elem); + return list->cl->insert_element(list, list->collection.size, elem); } /** @@ -265,7 +265,7 @@ void const *array, size_t n ) { - return list->cl->insert_array(list, list->size, array, n); + return list->cl->insert_array(list, list->collection.size, array, n); } /** @@ -336,10 +336,10 @@ */ __attribute__((__nonnull__)) static inline int cxListInsertAfter( - CxMutIterator *iter, + CxIterator *iter, void const *elem ) { - return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0); + return ((struct cx_list_s *) iter->src_handle.m)->cl->insert_iter(iter, elem, 0); } /** @@ -359,10 +359,10 @@ */ __attribute__((__nonnull__)) static inline int cxListInsertBefore( - CxMutIterator *iter, + CxIterator *iter, void const *elem ) { - return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1); + return ((struct cx_list_s *) iter->src_handle.m)->cl->insert_iter(iter, elem, 1); } /** @@ -481,7 +481,7 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -CxMutIterator cxListMutIteratorAt( +CxIterator cxListMutIteratorAt( CxList *list, size_t index ); @@ -499,7 +499,7 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -CxMutIterator cxListMutBackwardsIteratorAt( +CxIterator cxListMutBackwardsIteratorAt( CxList *list, size_t index ); @@ -530,7 +530,7 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxMutIterator cxListMutIterator(CxList *list) { +static inline CxIterator cxListMutIterator(CxList *list) { return cxListMutIteratorAt(list, 0); } @@ -547,7 +547,7 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) static inline CxIterator cxListBackwardsIterator(CxList const *list) { - return list->cl->iterator(list, list->size - 1, true); + return list->cl->iterator(list, list->collection.size - 1, true); } /** @@ -561,8 +561,8 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxMutIterator cxListMutBackwardsIterator(CxList *list) { - return cxListMutBackwardsIteratorAt(list, list->size - 1); +static inline CxIterator cxListMutBackwardsIterator(CxList *list) { + return cxListMutBackwardsIteratorAt(list, list->collection.size - 1); } /** @@ -580,7 +580,25 @@ CxList const *list, void const *elem ) { - return list->cl->find(list, elem); + return list->cl->find_remove((CxList*)list, elem, false); +} + +/** + * Removes and returns the index of the first element that equals \p elem. + * + * Determining equality is performed by the list's comparator function. + * + * @param list the list + * @param elem the element to find and remove + * @return the index of the now removed element or a negative + * value when the element is not found or could not be removed + */ +__attribute__((__nonnull__)) +static inline ssize_t cxListFindRemove( + CxList *list, + void const *elem +) { + return list->cl->find_remove(list, elem, true); } /**
--- a/ucx/cx/map.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/map.h Thu May 23 22:35:45 2024 +0200 @@ -30,7 +30,6 @@ * \brief Interface for map implementations. * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */ @@ -57,7 +56,10 @@ /** Structure for the UCX map. */ struct cx_map_s { - CX_COLLECTION_MEMBERS + /** + * Base attributes. + */ + CX_COLLECTION_BASE; /** The map class definition. */ cx_map_class *cl; }; @@ -164,7 +166,7 @@ */ __attribute__((__nonnull__)) static inline void cxMapStoreObjects(CxMap *map) { - map->store_pointer = false; + map->collection.store_pointer = false; } /** @@ -181,10 +183,21 @@ */ __attribute__((__nonnull__)) static inline void cxMapStorePointers(CxMap *map) { - map->store_pointer = true; - map->item_size = sizeof(void *); + map->collection.store_pointer = true; + map->collection.elem_size = sizeof(void *); } +/** + * Returns true, if this map is storing pointers instead of the actual data. + * + * @param map + * @return true, if this map is storing pointers + * @see cxMapStorePointers() + */ +__attribute__((__nonnull__)) +static inline bool cxMapIsStoringPointers(CxMap const *map) { + return map->collection.store_pointer; +} /** * Deallocates the memory of the specified map. @@ -207,6 +220,17 @@ map->cl->clear(map); } +/** + * Returns the number of elements in this map. + * + * @param map the map + * @return the number of stored elements + */ +__attribute__((__nonnull__)) +static inline size_t cxMapSize(CxMap const *map) { + return map->collection.size; +} + // TODO: set-like map operations (union, intersect, difference) @@ -269,7 +293,7 @@ * @return an iterator for the currently stored values */ __attribute__((__nonnull__, __warn_unused_result__)) -CxMutIterator cxMapMutIteratorValues(CxMap *map); +CxIterator cxMapMutIteratorValues(CxMap *map); /** * Creates a mutating iterator over the keys of a map. @@ -283,7 +307,7 @@ * @return an iterator for the currently stored keys */ __attribute__((__nonnull__, __warn_unused_result__)) -CxMutIterator cxMapMutIteratorKeys(CxMap *map); +CxIterator cxMapMutIteratorKeys(CxMap *map); /** * Creates a mutating iterator for a map. @@ -299,7 +323,7 @@ * @see cxMapMutIteratorValues() */ __attribute__((__nonnull__, __warn_unused_result__)) -CxMutIterator cxMapMutIterator(CxMap *map); +CxIterator cxMapMutIterator(CxMap *map); #ifdef __cplusplus } // end the extern "C" block here, because we want to start overloading @@ -1051,7 +1075,7 @@ CxMap *map, CxHashKey key ) { - return map->cl->remove(map, key, !map->store_pointer); + return map->cl->remove(map, key, !map->collection.store_pointer); } /** @@ -1067,7 +1091,7 @@ CxMap *map, cxstring key ) { - return map->cl->remove(map, cx_hash_key_cxstr(key), !map->store_pointer); + return map->cl->remove(map, cx_hash_key_cxstr(key), !map->collection.store_pointer); } /** @@ -1083,7 +1107,7 @@ CxMap *map, cxmutstr key ) { - return map->cl->remove(map, cx_hash_key_cxstr(key), !map->store_pointer); + return map->cl->remove(map, cx_hash_key_cxstr(key), !map->collection.store_pointer); } /** @@ -1099,7 +1123,7 @@ CxMap *map, char const *key ) { - return map->cl->remove(map, cx_hash_key_str(key), !map->store_pointer); + return map->cl->remove(map, cx_hash_key_str(key), !map->collection.store_pointer); } /**
--- a/ucx/cx/mempool.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/mempool.h Thu May 23 22:35:45 2024 +0200 @@ -30,7 +30,6 @@ * \brief Interface for memory pool implementations. * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */
--- a/ucx/cx/printf.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/printf.h Thu May 23 22:35:45 2024 +0200 @@ -30,7 +30,6 @@ * \brief Wrapper for write functions with a printf-like interface. * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */ @@ -45,6 +44,12 @@ extern "C" { #endif + +/** + * The maximum string length that fits into stack memory. + */ +extern unsigned const cx_printf_sbo_size; + /** * A \c fprintf like function which writes the output to a stream by * using a write_func. @@ -159,6 +164,170 @@ #define cx_bprintf(buffer, fmt, ...) cx_fprintf((CxBuffer*)buffer, \ (cx_write_func) cxBufferWrite, fmt, __VA_ARGS__) + +/** + * An \c sprintf like function which reallocates the string when the buffer is not large enough. + * + * The size of the buffer will be updated in \p len when necessary. + * + * \note The resulting string is guaranteed to be zero-terminated. + * + * @param str a pointer to the string buffer + * @param len a pointer to the length of the buffer + * @param fmt the format string + * @param ... additional arguments + * @return the length of produced string + */ +#define cx_sprintf(str, len, fmt, ...) cx_sprintf_a(cxDefaultAllocator, str, len, fmt, __VA_ARGS__) + +/** + * An \c sprintf like function which reallocates the string when the buffer is not large enough. + * + * The size of the buffer will be updated in \p len when necessary. + * + * \note The resulting string is guaranteed to be zero-terminated. + * + * \attention The original buffer MUST have been allocated with the same allocator! + * + * @param alloc the allocator to use + * @param str a pointer to the string buffer + * @param len a pointer to the length of the buffer + * @param fmt the format string + * @param ... additional arguments + * @return the length of produced string + */ +__attribute__((__nonnull__(1, 2, 3, 4), __format__(printf, 4, 5))) +int cx_sprintf_a(CxAllocator *alloc, char **str, size_t *len, const char *fmt, ... ); + + +/** + * An \c sprintf like function which reallocates the string when the buffer is not large enough. + * + * The size of the buffer will be updated in \p len when necessary. + * + * \note The resulting string is guaranteed to be zero-terminated. + * + * @param str a pointer to the string buffer + * @param len a pointer to the length of the buffer + * @param fmt the format string + * @param ap argument list + * @return the length of produced string + */ +#define cx_vsprintf(str, len, fmt, ap) cx_vsprintf_a(cxDefaultAllocator, str, len, fmt, ap) + +/** + * An \c sprintf like function which reallocates the string when the buffer is not large enough. + * + * The size of the buffer will be updated in \p len when necessary. + * + * \note The resulting string is guaranteed to be zero-terminated. + * + * \attention The original buffer MUST have been allocated with the same allocator! + * + * @param alloc the allocator to use + * @param str a pointer to the string buffer + * @param len a pointer to the length of the buffer + * @param fmt the format string + * @param ap argument list + * @return the length of produced string + */ +__attribute__((__nonnull__)) +int cx_vsprintf_a(CxAllocator *alloc, char **str, size_t *len, const char *fmt, va_list ap); + + +/** + * An \c sprintf like function which allocates a new string when the buffer is not large enough. + * + * The size of the buffer will be updated in \p len when necessary. + * + * The location of the resulting string will \em always be stored to \p str. When the buffer + * was sufficiently large, \p buf itself will be stored to the location of \p str. + * + * \note The resulting string is guaranteed to be zero-terminated. + * + * \remark When a new string needed to be allocated, the contents of \p buf will be + * poisoned after the call, because this function tries to produce the string in \p buf, first. + * + * @param buf a pointer to the buffer + * @param len a pointer to the length of the buffer + * @param str a pointer to the location + * @param fmt the format string + * @param ... additional arguments + * @return the length of produced string + */ +#define cx_sprintf_s(buf, len, str, fmt, ...) cx_sprintf_sa(cxDefaultAllocator, buf, len, str, fmt, __VA_ARGS__) + +/** + * An \c sprintf like function which allocates a new string when the buffer is not large enough. + * + * The size of the buffer will be updated in \p len when necessary. + * + * The location of the resulting string will \em always be stored to \p str. When the buffer + * was sufficiently large, \p buf itself will be stored to the location of \p str. + * + * \note The resulting string is guaranteed to be zero-terminated. + * + * \remark When a new string needed to be allocated, the contents of \p buf will be + * poisoned after the call, because this function tries to produce the string in \p buf, first. + * + * @param alloc the allocator to use + * @param buf a pointer to the buffer + * @param len a pointer to the length of the buffer + * @param str a pointer to the location + * @param fmt the format string + * @param ... additional arguments + * @return the length of produced string + */ +__attribute__((__nonnull__(1, 2, 4, 5), __format__(printf, 5, 6))) +int cx_sprintf_sa(CxAllocator *alloc, char *buf, size_t *len, char **str, const char *fmt, ... ); + +/** + * An \c sprintf like function which allocates a new string when the buffer is not large enough. + * + * The size of the buffer will be updated in \p len when necessary. + * + * The location of the resulting string will \em always be stored to \p str. When the buffer + * was sufficiently large, \p buf itself will be stored to the location of \p str. + * + * \note The resulting string is guaranteed to be zero-terminated. + * + * \remark When a new string needed to be allocated, the contents of \p buf will be + * poisoned after the call, because this function tries to produce the string in \p buf, first. + * + * @param buf a pointer to the buffer + * @param len a pointer to the length of the buffer + * @param str a pointer to the location + * @param fmt the format string + * @param ap argument list + * @return the length of produced string + */ +#define cx_vsprintf_s(buf, len, str, fmt, ap) cx_vsprintf_sa(cxDefaultAllocator, buf, len, str, fmt, ap) + +/** + * An \c sprintf like function which allocates a new string when the buffer is not large enough. + * + * The size of the buffer will be updated in \p len when necessary. + * + * The location of the resulting string will \em always be stored to \p str. When the buffer + * was sufficiently large, \p buf itself will be stored to the location of \p str. + * + * \note The resulting string is guaranteed to be zero-terminated. + * + * \remark When a new string needed to be allocated, the contents of \p buf will be + * poisoned after the call, because this function tries to produce the string in \p buf, first. + * + * @param alloc the allocator to use + * @param buf a pointer to the buffer + * @param len a pointer to the length of the buffer + * @param str a pointer to the location + * @param fmt the format string + * @param ap argument list + * @return the length of produced string + */ +__attribute__((__nonnull__)) +int cx_vsprintf_sa(CxAllocator *alloc, char *buf, size_t *len, char **str, const char *fmt, va_list ap); + + #ifdef __cplusplus } // extern "C" #endif
--- a/ucx/cx/string.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/string.h Thu May 23 22:35:45 2024 +0200 @@ -30,7 +30,6 @@ * \brief Strings that know their length. * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */ @@ -41,6 +40,11 @@ #include "allocator.h" /** + * The maximum length of the "needle" in cx_strstr() that can use SBO. + */ +extern unsigned const cx_strstr_sbo_size; + +/** * The UCX string structure. */ struct cx_mutstr_s {
--- a/ucx/cx/tree.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/tree.h Thu May 23 22:35:45 2024 +0200 @@ -1,7 +1,7 @@ /* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. * - * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. + * Copyright 2024 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: @@ -28,9 +28,8 @@ /** * \file tree.h * \brief Interface for tree implementations. + * \author Mike Becker * \author Olaf Wintermann - * \author Mike Becker - * \version 3.0 * \copyright 2-Clause BSD License */ @@ -38,99 +37,362 @@ #define UCX_TREE_H #include "common.h" -#include "allocator.h" + +#include "iterator.h" #ifdef __cplusplus extern "C" { #endif /** - * Adds a sibling to the current tree node. - * - * In case your struct does not have a \p prev or a \p parent pointer, - * specify a negative location. The location of the \p next pointer is - * mandatory. + * A depth-first tree iterator. * - * \attention Do not use this function to add siblings in a tree where the - * nodes store a pointer to the last sibling because that would not be modified by this function. + * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the + * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable. + * Each node, regardless of the number of passes, is counted only once. * - * \remark If yo do not provide a location to the parent pointer, a call to this function is - * effectively the same as a call to cx_linked_list_add(). + * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the + * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed), + * the iterator becomes invalid (regardless of what cxIteratorValid() returns). * - * @param node a pointer to the node - * @param loc_prev the location of a \c prev pointer within your node struct - * @param loc_next the location of a \c next pointer within your node struct - * @param loc_parent the location of a \c parent pointer within your node struct - * @param new_node the new node that shall be added as a sibling + * @see CxIterator + */ +typedef struct cx_tree_iterator_s { + /** + * Base members. + */ + CX_ITERATOR_BASE; + /** + * Indicates whether the subtree below the current node shall be skipped. + */ + bool skip; + /** + * Set to true, when the iterator shall visit a node again + * when all it's children have been processed. + */ + bool visit_on_exit; + /** + * True, if this iterator is currently leaving the node. + */ + bool exiting; + /** + * Offset in the node struct for the children linked list. + */ + ptrdiff_t loc_children; + /** + * Offset in the node struct for the next pointer. + */ + ptrdiff_t loc_next; + /** + * The total number of distinct nodes that have been passed so far. + */ + size_t counter; + /** + * The currently observed node. + * + * This is the same what cxIteratorCurrent() would return. + */ + void *node; + /** + * Stores a copy of the next pointer of the visited node. + * Allows freeing a node on exit without corrupting the iteration. + */ + void *node_next; + /** + * Internal stack. + * Will be automatically freed once the iterator becomes invalid. + * + * If you want to discard the iterator before, you need to manually + * call cxTreeIteratorDispose(). + */ + void **stack; + /** + * Internal capacity of the stack. + */ + size_t stack_capacity; + union { + /** + * Internal stack size. + */ + size_t stack_size; + /** + * The current depth in the tree. + */ + size_t depth; + }; +} CxTreeIterator; + +/** + * An element in a visitor queue. */ -void cx_tree_add_sibling(void *node, - ptrdiff_t loc_prev, ptrdiff_t loc_next, - ptrdiff_t loc_parent, - void *new_node) -__attribute__((__nonnull__)); +struct cx_tree_visitor_queue_s { + /** + * The tree node to visit. + */ + void *node; + /** + * The depth of the node. + */ + size_t depth; + /** + * The next element in the queue or \c NULL. + */ + struct cx_tree_visitor_queue_s *next; +}; + +/** + * A breadth-first tree iterator. + * + * This iterator needs to maintain a visitor queue that will be automatically freed once the iterator becomes invalid. + * If you want to discard the iterator before, you MUST manually call cxTreeVisitorDispose(). + * + * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the + * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable. + * Each node, regardless of the number of passes, is counted only once. + * + * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the + * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed), + * the iterator becomes invalid (regardless of what cxIteratorValid() returns). + * + * @see CxIterator + */ +typedef struct cx_tree_visitor_s { + /** + * Base members. + */ + CX_ITERATOR_BASE; + /** + * Indicates whether the subtree below the current node shall be skipped. + */ + bool skip; + /** + * Offset in the node struct for the children linked list. + */ + ptrdiff_t loc_children; + /** + * Offset in the node struct for the next pointer. + */ + ptrdiff_t loc_next; + /** + * The total number of distinct nodes that have been passed so far. + */ + size_t counter; + /** + * The currently observed node. + * + * This is the same what cxIteratorCurrent() would return. + */ + void *node; + /** + * The current depth in the tree. + */ + size_t depth; + /** + * The next element in the visitor queue. + */ + struct cx_tree_visitor_queue_s *queue_next; + /** + * The last element in the visitor queue. + */ + struct cx_tree_visitor_queue_s *queue_last; +} CxTreeVisitor; + +/** + * Releases internal memory of the given tree iterator. + * @param iter the iterator + */ + __attribute__((__nonnull__)) +static inline void cxTreeIteratorDispose(CxTreeIterator *iter) { + free(iter->stack); + iter->stack = NULL; +} /** - * Adds a node to the list of children. + * Releases internal memory of the given tree visitor. + * @param visitor the visitor + */ +__attribute__((__nonnull__)) +static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) { + struct cx_tree_visitor_queue_s *q = visitor->queue_next; + while (q != NULL) { + struct cx_tree_visitor_queue_s *next = q->next; + free(q); + q = next; + } +} + +/** + * Advises the iterator to skip the subtree below the current node and + * also continues the current loop. + * + * @param iterator the iterator + */ +#define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue + +/** + * Advises the visitor to skip the subtree below the current node and + * also continues the current loop. + * + * @param visitor the visitor + */ +#define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor) + +/** + * Links a node to a (new) parent. + * + * If the node has already a parent, it is unlinked, first. + * If the parent has children already, the node is \em prepended to the list + * of all currently existing children. * - * \par Example with a full structure - * A full tree node structure may look like this: - * \code - * typedef struct MyTreeNode MyTreeNode; - * struct MyTreeNode { - * MyTreeNode* parent; - * MyTreeNode* first_child; - * MyTreeNode* last_child; - * MyTreeNode* prev_sibling; - * MyTreeNode* next_sibling; - * // ...contents... - * } - * \endcode - * Adding a new child to a node with the above structure can be performed with the following call: - * \code - * MyTreeNode *node, *child; // given - * cx_tree_add_child(&node->first_child, &node->last_child, - * offsetof(MyTreeNode, prev_sibling), offsetof(MyTreeNode, next_sibling), - * child, offsetof(MyTreeNode, parent), node); - * \endcode + * @param parent the parent node + * @param node the node that shall be linked + * @param loc_parent offset in the node struct for the parent pointer + * @param loc_children offset in the node struct for the children linked list + * @param loc_prev offset in the node struct for the prev pointer + * @param loc_next offset in the node struct for the next pointer + * @see cx_tree_unlink() + */ +__attribute__((__nonnull__)) +void cx_tree_link( + void * restrict parent, + void * restrict node, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +); + +/** + * Unlinks a node from its parent. + * + * If the node has no parent, this function does nothing. + * + * @param node the node that shall be unlinked from its parent + * @param loc_parent offset in the node struct for the parent pointer + * @param loc_children offset in the node struct for the children linked list + * @param loc_prev offset in the node struct for the prev pointer + * @param loc_next offset in the node struct for the next pointer + * @see cx_tree_link() + */ +__attribute__((__nonnull__)) +void cx_tree_unlink( + void *node, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +); + +/** + * Function pointer for a search function. + * + * A function of this kind shall check if the specified \p node + * contains the given \p data or if one of the children might contain + * the data. + * + * The function should use the returned integer to indicate how close the + * match is, where a negative number means that it does not match at all. * - * \par Example with a reduced structure - * The minimal reasonable structure with parent pointer looks like this: - * \code - * typedef struct MyTreeNode MyTreeNode; - * struct MyTreeNode { - * MyTreeNode* parent; - * MyTreeNode* children; - * MyTreeNode* next_sibling; - * // ...contents... - * } - * \endcode - * This simplifies the function call to: - * \code - * MyTreeNode *node, *child; // given - * cx_tree_add_child(&node->children, NULL, -1, offsetof(MyTreeNode, next_sibling), - * child, offsetof(MyTreeNode, parent), node); - * \endcode + * For example if a tree stores file path information, a node that is + * describing a parent directory of a filename that is searched, shall + * return a positive number to indicate that a child node might contain the + * searched item. On the other hand, if the node denotes a path that is not a + * prefix of the searched filename, the function would return -1 to indicate + * that * the search does not need to be continued in that branch. + * + * @param node the node that is currently investigated + * @param data the data that is searched for + * + * @return 0 if the node contains the data, + * positive if one of the children might contain the data, + * negative if neither the node, nor the children contains the data + */ +typedef int (*cx_tree_search_func)(void const *node, void const* data); + + +/** + * Searches for data in a tree. + * + * When the data cannot be found exactly, the search function might return a + * closest result which might be a good starting point for adding a new node + * to the tree. + * + * Depending on the tree structure it is not necessarily guaranteed that the + * "closest" match is uniquely defined. This function will search for a node + * with the best match according to the \p sfunc (meaning: the return value of + * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary + * node matching the criteria is returned. * - * \remark If your tree structure does not possess a parent pointer, a call to this function is - * effectively the same as a call to cx_linked_list_add(). + * @param root the root node + * @param data the data to search for + * @param sfunc the search function + * @param result where the result shall be stored + * @param loc_children offset in the node struct for the children linked list + * @param loc_next offset in the node struct for the next pointer + * @return zero if the node was found exactly, positive if a node was found that + * could contain the node (but doesn't right now), negative if the tree does not + * contain any node that might be related to the searched data + */ +__attribute__((__nonnull__)) +int cx_tree_search( + void const *root, + void const *data, + cx_tree_search_func sfunc, + void **result, + ptrdiff_t loc_children, + ptrdiff_t loc_next +); + +/** + * Creates a depth-first iterator for a tree with the specified root node. + * + * @note A tree iterator needs to maintain a stack of visited nodes, which is allocated using stdlib malloc(). + * When the iterator becomes invalid, this memory is automatically released. However, if you wish to cancel the + * iteration before the iterator becomes invalid by itself, you MUST call cxTreeIteratorDispose() manually to release + * the memory. + * + * @remark The returned iterator does not support cxIteratorFlagRemoval(). * - * @param children_begin a pointer to the begin node pointer (if your list has one) - * @param children_end a pointer to the end node pointer (if your list has one) - * @param loc_prev the location of a \c prev pointer within your node struct - * @param loc_next the location of a \c next pointer within your node struct - * @param new_node a pointer to the node that shall be appended - * @param loc_parent the location of a \c parent pointer within your node struct - * @param parent the parent node + * @param root the root node + * @param visit_on_exit set to true, when the iterator shall visit a node again after processing all children + * @param loc_children offset in the node struct for the children linked list + * @param loc_next offset in the node struct for the next pointer + * @return the new tree iterator + * @see cxTreeIteratorDispose() */ -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) -__attribute__((__nonnull__ (5))); +__attribute__((__nonnull__)) +CxTreeIterator cx_tree_iterator( + void *root, + bool visit_on_exit, + ptrdiff_t loc_children, + ptrdiff_t loc_next +); +/** + * Creates a breadth-first iterator for a tree with the specified root node. + * + * @note A tree visitor needs to maintain a queue of to be visited nodes, which is allocated using stdlib malloc(). + * When the visitor becomes invalid, this memory is automatically released. However, if you wish to cancel the + * iteration before the visitor becomes invalid by itself, you MUST call cxTreeVisitorDispose() manually to release + * the memory. + * + * @remark The returned iterator does not support cxIteratorFlagRemoval(). + * + * @param root the root node + * @param loc_children offset in the node struct for the children linked list + * @param loc_next offset in the node struct for the next pointer + * @return the new tree visitor + * @see cxTreeVisitorDispose() + */ +__attribute__((__nonnull__)) +CxTreeVisitor cx_tree_visitor( + void *root, + ptrdiff_t loc_children, + ptrdiff_t loc_next +); #ifdef __cplusplus } // extern "C" #endif -#endif // UCX_TREE_H - +#endif //UCX_TREE_H
--- a/ucx/cx/utils.h Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/cx/utils.h Thu May 23 22:35:45 2024 +0200 @@ -33,7 +33,6 @@ * * \author Mike Becker * \author Olaf Wintermann - * \version 3.0 * \copyright 2-Clause BSD License */
--- a/ucx/hash_map.c Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/hash_map.c Thu May 23 22:35:45 2024 +0200 @@ -53,9 +53,9 @@ // invoke the destructor cx_invoke_destructor(map, elem->data); // free the key data - cxFree(map->allocator, (void *) elem->key.data); + cxFree(map->collection.allocator, (void *) elem->key.data); // free the node - cxFree(map->allocator, elem); + cxFree(map->collection.allocator, elem); // proceed elem = next; } while (elem != NULL); @@ -64,7 +64,7 @@ hash_map->buckets[i] = NULL; } } - map->size = 0; + map->collection.size = 0; } static void cx_hash_map_destructor(struct cx_map_s *map) { @@ -72,10 +72,10 @@ // free the buckets cx_hash_map_clear(map); - cxFree(map->allocator, hash_map->buckets); + cxFree(map->collection.allocator, hash_map->buckets); // free the map structure - cxFree(map->allocator, map); + cxFree(map->collection.allocator, map); } static int cx_hash_map_put( @@ -84,7 +84,7 @@ void *value ) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; - CxAllocator const *allocator = map->allocator; + CxAllocator const *allocator = map->collection.allocator; unsigned hash = key.hash; if (hash == 0) { @@ -104,26 +104,26 @@ if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len && memcmp(elm->key.data, key.data, key.len) == 0) { // overwrite existing element - if (map->store_pointer) { + if (map->collection.store_pointer) { memcpy(elm->data, &value, sizeof(void *)); } else { - memcpy(elm->data, value, map->item_size); + memcpy(elm->data, value, map->collection.elem_size); } } else { // allocate new element struct cx_hash_map_element_s *e = cxMalloc( allocator, - sizeof(struct cx_hash_map_element_s) + map->item_size + sizeof(struct cx_hash_map_element_s) + map->collection.elem_size ); if (e == NULL) { return -1; } // write the value - if (map->store_pointer) { + if (map->collection.store_pointer) { memcpy(e->data, &value, sizeof(void *)); } else { - memcpy(e->data, value, map->item_size); + memcpy(e->data, value, map->collection.elem_size); } // copy the key @@ -145,7 +145,7 @@ e->next = elm; // increase the size - map->size++; + map->collection.size++; } return 0; @@ -164,10 +164,10 @@ prev->next = elm->next; } // free element - cxFree(hash_map->base.allocator, (void *) elm->key.data); - cxFree(hash_map->base.allocator, elm); + cxFree(hash_map->base.collection.allocator, (void *) elm->key.data); + cxFree(hash_map->base.collection.allocator, elm); // decrease size - hash_map->base.size--; + hash_map->base.collection.size--; } /** @@ -203,7 +203,7 @@ if (destroy) { cx_invoke_destructor(map, elm->data); } else { - if (map->store_pointer) { + if (map->collection.store_pointer) { data = *(void **) elm->data; } else { data = elm->data; @@ -252,9 +252,9 @@ 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_s const *map = iter->src_handle.c; struct cx_hash_map_element_s *elm = iter->elem_handle; - if (map->base.store_pointer) { + if (map->base.collection.store_pointer) { return *(void **) elm->data; } else { return elm->data; @@ -269,12 +269,10 @@ static void cx_hash_map_iter_next(void *it) { struct cx_iterator_s *iter = it; struct cx_hash_map_element_s *elm = iter->elem_handle; + struct cx_hash_map_s *map = iter->src_handle.m; // remove current element, if asked if (iter->base.remove) { - // obtain mutable pointer to the map - struct cx_mut_iterator_s *miter = it; - struct cx_hash_map_s *map = miter->src_handle; // clear the flag iter->base.remove = false; @@ -306,7 +304,6 @@ } // search the next bucket, if required - struct cx_hash_map_s const *map = iter->src_handle; while (elm == NULL && ++iter->slot < map->bucket_count) { elm = map->buckets[iter->slot]; } @@ -318,7 +315,7 @@ iter->kv_data.value = NULL; } else { iter->kv_data.key = &elm->key; - if (map->base.store_pointer) { + if (map->base.collection.store_pointer) { iter->kv_data.value = *(void **) elm->data; } else { iter->kv_data.value = elm->data; @@ -326,48 +323,41 @@ } } -static bool cx_hash_map_iter_flag_rm(void *it) { - struct cx_iterator_base_s *iter = it; - if (iter->mutating) { - iter->remove = true; - return true; - } else { - return false; - } -} - static CxIterator cx_hash_map_iterator( CxMap const *map, enum cx_map_iterator_type type ) { CxIterator iter; - iter.src_handle = map; - iter.base.valid = cx_hash_map_iter_valid; - iter.base.next = cx_hash_map_iter_next; + iter.src_handle.c = map; + iter.elem_count = map->collection.size; switch (type) { case CX_MAP_ITERATOR_PAIRS: + iter.elem_size = sizeof(CxMapEntry); iter.base.current = cx_hash_map_iter_current_entry; break; case CX_MAP_ITERATOR_KEYS: + iter.elem_size = sizeof(CxHashKey); iter.base.current = cx_hash_map_iter_current_key; break; case CX_MAP_ITERATOR_VALUES: + iter.elem_size = map->collection.elem_size; iter.base.current = cx_hash_map_iter_current_value; break; default: assert(false); } - iter.base.flag_removal = cx_hash_map_iter_flag_rm; + iter.base.valid = cx_hash_map_iter_valid; + iter.base.next = cx_hash_map_iter_next; iter.base.remove = false; iter.base.mutating = false; iter.slot = 0; iter.index = 0; - if (map->size > 0) { + if (map->collection.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]; while (elm == NULL) { @@ -375,7 +365,7 @@ } iter.elem_handle = elm; iter.kv_data.key = &elm->key; - if (map->store_pointer) { + if (map->collection.store_pointer) { iter.kv_data.value = *(void **) elm->data; } else { iter.kv_data.value = elm->data; @@ -423,14 +413,14 @@ // initialize base members map->base.cl = &cx_hash_map_class; - map->base.allocator = allocator; + map->base.collection.allocator = allocator; if (itemsize > 0) { - map->base.store_pointer = false; - map->base.item_size = itemsize; + map->base.collection.store_pointer = false; + map->base.collection.elem_size = itemsize; } else { - map->base.store_pointer = true; - map->base.item_size = sizeof(void *); + map->base.collection.store_pointer = true; + map->base.collection.elem_size = sizeof(void *); } return (CxMap *) map; @@ -438,11 +428,11 @@ int cxMapRehash(CxMap *map) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; - if (map->size > ((hash_map->bucket_count * 3) >> 2)) { + if (map->collection.size > ((hash_map->bucket_count * 3) >> 2)) { - size_t new_bucket_count = (map->size * 5) >> 1; + size_t new_bucket_count = (map->collection.size * 5) >> 1; struct cx_hash_map_element_s **new_buckets = cxCalloc( - map->allocator, + map->collection.allocator, new_bucket_count, sizeof(struct cx_hash_map_element_s *) ); @@ -482,7 +472,7 @@ // assign result to the map hash_map->bucket_count = new_bucket_count; - cxFree(map->allocator, hash_map->buckets); + cxFree(map->collection.allocator, hash_map->buckets); hash_map->buckets = new_buckets; } return 0;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ucx/iterator.c Thu May 23 22:35:45 2024 +0200 @@ -0,0 +1,112 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "cx/iterator.h" + +#include <string.h> + +static bool cx_iter_valid(void const *it) { + struct cx_iterator_s const *iter = it; + return iter->index < iter->elem_count; +} + +static void *cx_iter_current(void const *it) { + struct cx_iterator_s const *iter = it; + return iter->elem_handle; +} + +static void cx_iter_next_fast(void *it) { + struct cx_iterator_s *iter = it; + if (iter->base.remove) { + iter->base.remove = false; + iter->elem_count--; + // only move the last element when we are not currently aiming + // at the last element already + if (iter->index < iter->elem_count) { + void *last = ((char *) iter->src_handle.m) + + iter->elem_count * iter->elem_size; + memcpy(iter->elem_handle, last, iter->elem_size); + } + } else { + iter->index++; + iter->elem_handle = ((char *) iter->elem_handle) + iter->elem_size; + } +} + +static void cx_iter_next_slow(void *it) { + struct cx_iterator_s *iter = it; + if (iter->base.remove) { + iter->base.remove = false; + iter->elem_count--; + + // number of elements to move + size_t remaining = iter->elem_count - iter->index; + if (remaining > 0) { + memmove( + iter->elem_handle, + ((char *) iter->elem_handle) + iter->elem_size, + remaining * iter->elem_size + ); + } + } else { + iter->index++; + iter->elem_handle = ((char *) iter->elem_handle) + iter->elem_size; + } +} + +CxIterator cxMutIterator( + void *array, + size_t elem_size, + size_t elem_count, + bool remove_keeps_order +) { + CxIterator iter; + + iter.index = 0; + iter.src_handle.m = array; + iter.elem_handle = array; + iter.elem_size = elem_size; + iter.elem_count = array == NULL ? 0 : elem_count; + iter.base.valid = cx_iter_valid; + iter.base.current = cx_iter_current; + iter.base.next = remove_keeps_order ? cx_iter_next_slow : cx_iter_next_fast; + iter.base.remove = false; + iter.base.mutating = true; + + return iter; +} + +CxIterator cxIterator( + void const *array, + size_t elem_size, + size_t elem_count +) { + CxIterator iter = cxMutIterator((void*)array, elem_size, elem_count, false); + iter.base.mutating = false; + return iter; +}
--- a/ucx/linked_list.c Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/linked_list.c Thu May 23 22:35:45 2024 +0200 @@ -28,6 +28,7 @@ #include "cx/linked_list.h" #include "cx/utils.h" +#include "cx/compare.h" #include <string.h> #include <assert.h> @@ -63,6 +64,23 @@ cx_compare_func cmp_func, void const *elem ) { + void *dummy; + return cx_linked_list_find_node( + &dummy, start, + loc_advance, loc_data, + cmp_func, elem + ); +} + +ssize_t cx_linked_list_find_node( + void **result, + void const *start, + ptrdiff_t loc_advance, + ptrdiff_t loc_data, + cx_compare_func cmp_func, + void const *elem +) { + assert(result != NULL); assert(start != NULL); assert(loc_advance >= 0); assert(loc_data >= 0); @@ -73,11 +91,13 @@ do { void *current = ll_data(node); if (cmp_func(current, elem) == 0) { + *result = (void*) node; return index; } node = ll_advance(node); index++; } while (node != NULL); + *result = NULL; return -1; } @@ -460,8 +480,6 @@ // 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; @@ -483,10 +501,10 @@ cx_linked_list const *list, size_t index ) { - if (index >= list->base.size) { + if (index >= list->base.collection.size) { return NULL; - } else if (index > list->base.size / 2) { - return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index); + } else if (index > list->base.collection.size / 2) { + return cx_linked_list_at(list->end, list->base.collection.size - 1, CX_LL_LOC_PREV, index); } else { return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); } @@ -499,15 +517,15 @@ ) { // create the new new_node - cx_linked_list_node *new_node = cxMalloc(list->allocator, - sizeof(cx_linked_list_node) + list->item_size); + cx_linked_list_node *new_node = cxMalloc(list->collection.allocator, + sizeof(cx_linked_list_node) + list->collection.elem_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->item_size); + memcpy(new_node->payload, elem, list->collection.elem_size); // insert cx_linked_list *ll = (cx_linked_list *) list; @@ -518,7 +536,7 @@ ); // increase the size and return - list->size++; + list->collection.size++; return 0; } @@ -529,7 +547,7 @@ size_t n ) { // out-of bounds and corner case check - if (index > list->size || n == 0) return 0; + if (index > list->collection.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); @@ -548,7 +566,7 @@ // 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; + source += list->collection.elem_size; if (0 != cx_ll_insert_at(list, node, source)) { return i; } @@ -583,44 +601,45 @@ CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); // adjust size - list->size--; + list->collection.size--; // free and return - cxFree(list->allocator, node); + cxFree(list->collection.allocator, node); return 0; } static void cx_ll_clear(struct cx_list_s *list) { - if (list->size == 0) return; + if (list->collection.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); + cxFree(list->collection.allocator, node); node = next; } ll->begin = ll->end = NULL; - list->size = 0; + list->collection.size = 0; } #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE #define CX_LINKED_LIST_SWAP_SBO_SIZE 128 #endif +unsigned cx_linked_list_swap_sbo_size = CX_LINKED_LIST_SWAP_SBO_SIZE; 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 >= list->collection.size || j >= list->collection.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 mid = list->collection.size / 2; size_t left, right; if (i < j) { left = i; @@ -633,6 +652,7 @@ if (left < mid && right < mid) { // case 1: both items left from mid nleft = cx_ll_node_at(ll, left); + assert(nleft != NULL); nright = nleft; for (size_t c = left; c < right; c++) { nright = nright->next; @@ -640,6 +660,7 @@ } else if (left >= mid && right >= mid) { // case 2: both items right from mid nright = cx_ll_node_at(ll, right); + assert(nright != NULL); nleft = nright; for (size_t c = right; c > left; c--) { nleft = nleft->prev; @@ -650,7 +671,7 @@ // chose the closest to begin / end size_t closest; size_t other; - size_t diff2boundary = list->size - right - 1; + size_t diff2boundary = list->collection.size - right - 1; if (left <= diff2boundary) { closest = left; other = right; @@ -686,7 +707,7 @@ } } - if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) { + if (list->collection.elem_size > CX_LINKED_LIST_SWAP_SBO_SIZE) { cx_linked_list_node *prev = nleft->prev; cx_linked_list_node *next = nright->next; cx_linked_list_node *midstart = nleft->next; @@ -718,9 +739,9 @@ } 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); + memcpy(buf, nleft->payload, list->collection.elem_size); + memcpy(nleft->payload, nright->payload, list->collection.elem_size); + memcpy(nright->payload, buf, list->collection.elem_size); } return 0; @@ -735,20 +756,42 @@ return node == NULL ? NULL : node->payload; } -static ssize_t cx_ll_find( - struct cx_list_s const *list, - void const *elem +static ssize_t cx_ll_find_remove( + struct cx_list_s *list, + void const *elem, + bool remove ) { - return cx_linked_list_find(((cx_linked_list *) list)->begin, - CX_LL_LOC_NEXT, CX_LL_LOC_DATA, - list->cmpfunc, elem); + if (remove) { + cx_linked_list *ll = ((cx_linked_list *) list); + cx_linked_list_node *node; + ssize_t index = cx_linked_list_find_node( + (void **) &node, + ll->begin, + CX_LL_LOC_NEXT, CX_LL_LOC_DATA, + list->collection.cmpfunc, elem + ); + if (node != NULL) { + 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->collection.size--; + cxFree(list->collection.allocator, node); + } + return index; + } else { + return cx_linked_list_find( + ((cx_linked_list *) list)->begin, + CX_LL_LOC_NEXT, CX_LL_LOC_DATA, + list->collection.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, - list->cmpfunc); + list->collection.cmpfunc); } static void cx_ll_reverse(struct cx_list_s *list) { @@ -764,7 +807,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, - list->cmpfunc); + list->collection.cmpfunc); } static bool cx_ll_iter_valid(void const *it) { @@ -773,21 +816,19 @@ } static void cx_ll_iter_next(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; + struct cx_iterator_s *iter = it; + if (iter->base.remove) { + iter->base.remove = false; + struct cx_list_s *list = iter->src_handle.m; + cx_linked_list *ll = iter->src_handle.m; 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); - list->size--; - cxFree(list->allocator, node); + list->collection.size--; + cxFree(list->collection.allocator, node); } else { - struct cx_iterator_s *iter = it; iter->index++; cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->next; @@ -795,22 +836,20 @@ } 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; + struct cx_iterator_s *iter = it; + if (iter->base.remove) { + iter->base.remove = false; + struct cx_list_s *list = iter->src_handle.m; + cx_linked_list *ll = iter->src_handle.m; 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); + list->collection.size--; + cxFree(list->collection.allocator, node); } else { - struct cx_iterator_s *iter = it; iter->index--; cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->prev; @@ -823,16 +862,6 @@ return node->payload; } -static bool cx_ll_iter_flag_rm(void *it) { - struct cx_iterator_base_s *iter = it; - if (iter->mutating) { - iter->remove = true; - return true; - } else { - return false; - } -} - static CxIterator cx_ll_iterator( struct cx_list_s const *list, size_t index, @@ -840,23 +869,24 @@ ) { CxIterator iter; iter.index = index; - iter.src_handle = list; + iter.src_handle.c = list; iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); + iter.elem_size = list->collection.elem_size; + iter.elem_count = list->collection.size; iter.base.valid = cx_ll_iter_valid; iter.base.current = cx_ll_iter_current; 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 int cx_ll_insert_iter( - CxMutIterator *iter, + CxIterator *iter, void const *elem, int prepend ) { - struct cx_list_s *list = iter->src_handle; + struct cx_list_s *list = iter->src_handle.m; cx_linked_list_node *node = iter->elem_handle; if (node != NULL) { assert(prepend >= 0 && prepend <= 1); @@ -865,8 +895,8 @@ iter->index += prepend * (0 == result); return result; } else { - int result = cx_ll_insert_element(list, list->size, elem); - iter->index = list->size; + int result = cx_ll_insert_element(list, list->collection.size, elem); + iter->index = list->collection.size; return result; } } @@ -878,11 +908,11 @@ while (node) { cx_invoke_destructor(list, node->payload); void *next = node->next; - cxFree(list->allocator, node); + cxFree(list->collection.allocator, node); node = next; } - cxFree(list->allocator, list); + cxFree(list->collection.allocator, list); } static cx_list_class cx_linked_list_class = { @@ -894,7 +924,7 @@ cx_ll_clear, cx_ll_swap, cx_ll_at, - cx_ll_find, + cx_ll_find_remove, cx_ll_sort, cx_ll_compare, cx_ll_reverse, @@ -904,7 +934,7 @@ CxList *cxLinkedListCreate( CxAllocator const *allocator, cx_compare_func comparator, - size_t item_size + size_t elem_size ) { if (allocator == NULL) { allocator = cxDefaultAllocator; @@ -914,12 +944,13 @@ if (list == NULL) return NULL; list->base.cl = &cx_linked_list_class; - list->base.allocator = allocator; - list->base.cmpfunc = comparator; + list->base.collection.allocator = allocator; - if (item_size > 0) { - list->base.item_size = item_size; + if (elem_size > 0) { + list->base.collection.elem_size = elem_size; + list->base.collection.cmpfunc = comparator; } else { + list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; cxListStorePointers((CxList *) list); }
--- a/ucx/list.c Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/list.c Thu May 23 22:35:45 2024 +0200 @@ -47,14 +47,14 @@ 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; + struct cx_collection_s *l = (struct cx_collection_s*) &list->collection; 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; + struct cx_collection_s *l = (struct cx_collection_s*) &list->collection; l->cmpfunc = cx_pl_cmpfunc_impl; } @@ -80,11 +80,11 @@ } static int cx_pl_insert_iter( - struct cx_mut_iterator_s *iter, + struct cx_iterator_s *iter, void const *elem, int prepend ) { - struct cx_list_s *list = iter->src_handle; + struct cx_list_s *list = iter->src_handle.m; return list->climpl->insert_iter(iter, &elem, prepend); } @@ -115,12 +115,13 @@ return ptr == NULL ? NULL : *ptr; } -static ssize_t cx_pl_find( - struct cx_list_s const *list, - void const *elem +static ssize_t cx_pl_find_remove( + struct cx_list_s *list, + void const *elem, + bool remove ) { cx_pl_hack_cmpfunc(list); - ssize_t ret = list->climpl->find(list, &elem); + ssize_t ret = list->climpl->find_remove(list, &elem, remove); cx_pl_unhack_cmpfunc(list); return ret; } @@ -171,7 +172,7 @@ cx_pl_clear, cx_pl_swap, cx_pl_at, - cx_pl_find, + cx_pl_find_remove, cx_pl_sort, cx_pl_compare, cx_pl_reverse, @@ -179,7 +180,7 @@ }; void cxListStoreObjects(CxList *list) { - list->store_pointer = false; + list->collection.store_pointer = false; if (list->climpl != NULL) { list->cl = list->climpl; list->climpl = NULL; @@ -187,8 +188,8 @@ } void cxListStorePointers(CxList *list) { - list->item_size = sizeof(void *); - list->store_pointer = true; + list->collection.elem_size = sizeof(void *); + list->collection.store_pointer = true; list->climpl = list->cl; list->cl = &cx_pointer_list_class; } @@ -208,9 +209,10 @@ return NULL; } -static ssize_t cx_emptyl_find( - __attribute__((__unused__)) struct cx_list_s const *list, - __attribute__((__unused__)) void const *elem +static ssize_t cx_emptyl_find_remove( + __attribute__((__unused__)) struct cx_list_s *list, + __attribute__((__unused__)) void const *elem, + __attribute__((__unused__)) bool remove ) { return -1; } @@ -219,7 +221,7 @@ __attribute__((__unused__)) struct cx_list_s const *list, struct cx_list_s const *other ) { - if (other->size == 0) return 0; + if (other->collection.size == 0) return 0; return -1; } @@ -233,7 +235,7 @@ __attribute__((__unused__)) bool backwards ) { CxIterator iter = {0}; - iter.src_handle = list; + iter.src_handle.c = list; iter.index = index; iter.base.valid = cx_emptyl_iter_valid; return iter; @@ -248,7 +250,7 @@ cx_emptyl_noop, NULL, cx_emptyl_at, - cx_emptyl_find, + cx_emptyl_find_remove, cx_emptyl_noop, cx_emptyl_compare, cx_emptyl_noop, @@ -256,14 +258,16 @@ }; CxList cx_empty_list = { - NULL, - NULL, - 0, - 0, - NULL, - NULL, - NULL, - false, + { + NULL, + NULL, + 0, + 0, + NULL, + NULL, + NULL, + false + }, &cx_empty_list_class, NULL }; @@ -282,7 +286,7 @@ ) { if ( // if one is storing pointers but the other is not - (list->store_pointer ^ other->store_pointer) || + (list->collection.store_pointer ^ other->collection.store_pointer) || // if one class is wrapped but the other is not ((list->climpl == NULL) ^ (other->climpl == NULL)) || @@ -292,13 +296,13 @@ (other->climpl != NULL ? other->climpl->compare : other->cl->compare)) ) { // lists are definitely different - cannot use internal compare function - if (list->size == other->size) { - CxIterator left = cxListIterator(list); - CxIterator right = cxListIterator(other); - for (size_t i = 0; i < list->size; i++) { + if (list->collection.size == other->collection.size) { + CxIterator left = list->cl->iterator(list, 0, false); + CxIterator right = other->cl->iterator(other, 0, false); + for (size_t i = 0; i < list->collection.size; i++) { void *leftValue = cxIteratorCurrent(left); void *rightValue = cxIteratorCurrent(right); - int d = list->cmpfunc(leftValue, rightValue); + int d = list->collection.cmpfunc(leftValue, rightValue); if (d != 0) { return d; } @@ -307,7 +311,7 @@ } return 0; } else { - return list->size < other->size ? -1 : 1; + return list->collection.size < other->collection.size ? -1 : 1; } } else { // lists are compatible @@ -315,28 +319,20 @@ } } -CxMutIterator cxListMutIteratorAt( +CxIterator 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; + return it; } -CxMutIterator cxListMutBackwardsIteratorAt( +CxIterator 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; + return it; }
--- a/ucx/map.c Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/map.c Thu May 23 22:35:45 2024 +0200 @@ -51,7 +51,7 @@ __attribute__((__unused__)) enum cx_map_iterator_type type ) { CxIterator iter = {0}; - iter.src_handle = map; + iter.src_handle.c = map; iter.base.valid = cx_empty_map_iter_valid; return iter; } @@ -66,14 +66,16 @@ }; CxMap cx_empty_map = { - NULL, - NULL, - 0, - 0, - NULL, - NULL, - NULL, - false, + { + NULL, + NULL, + 0, + 0, + NULL, + NULL, + NULL, + false + }, &cx_empty_map_class }; @@ -81,32 +83,20 @@ // </editor-fold> -CxMutIterator cxMapMutIteratorValues(CxMap *map) { +CxIterator cxMapMutIteratorValues(CxMap *map) { CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_VALUES); it.base.mutating = true; - - // we know the iterators share the same memory layout - CxMutIterator iter; - memcpy(&iter, &it, sizeof(CxMutIterator)); - return iter; + return it; } -CxMutIterator cxMapMutIteratorKeys(CxMap *map) { +CxIterator cxMapMutIteratorKeys(CxMap *map) { CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_KEYS); it.base.mutating = true; - - // we know the iterators share the same memory layout - CxMutIterator iter; - memcpy(&iter, &it, sizeof(CxMutIterator)); - return iter; + return it; } -CxMutIterator cxMapMutIterator(CxMap *map) { +CxIterator cxMapMutIterator(CxMap *map) { CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_PAIRS); it.base.mutating = true; - - // we know the iterators share the same memory layout - CxMutIterator iter; - memcpy(&iter, &it, sizeof(CxMutIterator)); - return iter; + return it; }
--- a/ucx/printf.c Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/printf.c Thu May 23 22:35:45 2024 +0200 @@ -34,6 +34,7 @@ #ifndef CX_PRINTF_SBO_SIZE #define CX_PRINTF_SBO_SIZE 512 #endif +unsigned const cx_printf_sbo_size = CX_PRINTF_SBO_SIZE; int cx_fprintf( void *stream, @@ -60,17 +61,21 @@ va_copy(ap2, ap); int ret = vsnprintf(buf, CX_PRINTF_SBO_SIZE, fmt, ap); if (ret < 0) { + va_end(ap2); return ret; } else if (ret < CX_PRINTF_SBO_SIZE) { + va_end(ap2); return (int) wfc(buf, 1, ret, stream); } else { int len = ret + 1; char *newbuf = malloc(len); if (!newbuf) { + va_end(ap2); return -1; } ret = vsnprintf(newbuf, len, fmt, ap2); + va_end(ap2); if (ret > 0) { ret = (int) wfc(newbuf, 1, ret, stream); } @@ -85,9 +90,8 @@ ... ) { va_list ap; - cxmutstr ret; va_start(ap, fmt); - ret = cx_vasprintf_a(allocator, fmt, ap); + cxmutstr ret = cx_vasprintf_a(allocator, fmt, ap); va_end(ap); return ret; } @@ -104,7 +108,7 @@ va_list ap2; va_copy(ap2, ap); int ret = vsnprintf(buf, CX_PRINTF_SBO_SIZE, fmt, ap); - if (ret > 0 && ret < CX_PRINTF_SBO_SIZE) { + if (ret >= 0 && ret < CX_PRINTF_SBO_SIZE) { s.ptr = cxMalloc(a, ret + 1); if (s.ptr) { s.length = (size_t) ret; @@ -124,6 +128,67 @@ } } } + va_end(ap2); return s; } +int cx_sprintf_a(CxAllocator *alloc, char **str, size_t *len, const char *fmt, ... ) { + va_list ap; + va_start(ap, fmt); + int ret = cx_vsprintf_a(alloc, str, len, fmt, ap); + va_end(ap); + return ret; +} + +int cx_vsprintf_a(CxAllocator *alloc, char **str, size_t *len, const char *fmt, va_list ap) { + va_list ap2; + va_copy(ap2, ap); + int ret = vsnprintf(*str, *len, fmt, ap); + if ((unsigned) ret >= *len) { + unsigned newlen = ret + 1; + char *ptr = cxRealloc(alloc, *str, newlen); + if (ptr) { + int newret = vsnprintf(ptr, newlen, fmt, ap2); + if (newret < 0) { + cxFree(alloc, ptr); + } else { + *len = newlen; + *str = ptr; + ret = newret; + } + } + } + va_end(ap2); + return ret; +} + +int cx_sprintf_sa(CxAllocator *alloc, char *buf, size_t *len, char **str, const char *fmt, ... ) { + va_list ap; + va_start(ap, fmt); + int ret = cx_vsprintf_sa(alloc, buf, len, str, fmt, ap); + va_end(ap); + return ret; +} + +int cx_vsprintf_sa(CxAllocator *alloc, char *buf, size_t *len, char **str, const char *fmt, va_list ap) { + va_list ap2; + va_copy(ap2, ap); + int ret = vsnprintf(buf, *len, fmt, ap); + *str = buf; + if ((unsigned) ret >= *len) { + unsigned newlen = ret + 1; + char *ptr = cxMalloc(alloc, newlen); + if (ptr) { + int newret = vsnprintf(ptr, newlen, fmt, ap2); + if (newret < 0) { + cxFree(alloc, ptr); + } else { + *len = newlen; + *str = ptr; + ret = newret; + } + } + } + va_end(ap2); + return ret; +}
--- a/ucx/string.c Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/string.c Thu May 23 22:35:45 2024 +0200 @@ -236,6 +236,7 @@ #ifndef CX_STRSTR_SBO_SIZE #define CX_STRSTR_SBO_SIZE 512 #endif +unsigned const cx_strstr_sbo_size = CX_STRSTR_SBO_SIZE; cxstring cx_strstr( cxstring haystack,
--- a/ucx/szmul.c Sat Apr 20 13:01:58 2024 +0200 +++ b/ucx/szmul.c Thu May 23 22:35:45 2024 +0200 @@ -43,4 +43,4 @@ *result = 0; return 1; } -} \ No newline at end of file +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ucx/tree.c Thu May 23 22:35:45 2024 +0200 @@ -0,0 +1,401 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "cx/tree.h" + +#include "cx/array_list.h" + +#include <assert.h> + +#define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) +#define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) +#define tree_parent(node) CX_TREE_PTR(node, loc_parent) +#define tree_children(node) CX_TREE_PTR(node, loc_children) +#define tree_prev(node) CX_TREE_PTR(node, loc_prev) +#define tree_next(node) CX_TREE_PTR(node, loc_next) + +void cx_tree_link( + void *restrict parent, + void *restrict node, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + void *current_parent = tree_parent(node); + if (current_parent == parent) return; + if (current_parent != NULL) { + cx_tree_unlink(node, loc_parent, loc_children, + loc_prev, loc_next); + } + + if (tree_children(parent) == NULL) { + tree_children(parent) = node; + } else { + void *children = tree_children(parent); + tree_prev(children) = node; + tree_next(node) = children; + tree_children(parent) = node; + } + tree_parent(node) = parent; +} + +void cx_tree_unlink( + void *node, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + if (tree_parent(node) == NULL) return; + + void *left = tree_prev(node); + void *right = tree_next(node); + assert(left == NULL || tree_children(tree_parent(node)) != node); + if (left == NULL) { + tree_children(tree_parent(node)) = right; + } else { + tree_next(left) = right; + } + if (right != NULL) tree_prev(right) = left; + tree_parent(node) = NULL; + tree_prev(node) = NULL; + tree_next(node) = NULL; +} + +int cx_tree_search( + void const *root, + void const *data, + cx_tree_search_func sfunc, + void **result, + ptrdiff_t loc_children, + ptrdiff_t loc_next +) { + int ret; + *result = NULL; + + // shortcut: compare root before doing anything else + ret = sfunc(root, data); + if (ret < 0) { + return ret; + } else if (ret == 0 || tree_children(root) == NULL) { + *result = (void*)root; + return ret; + } + + // create a working stack + CX_ARRAY_DECLARE(void const*, work); + cx_array_initialize(work, 32); + + // add the children of root to the working stack + { + void *c = tree_children(root); + while (c != NULL) { + cx_array_simple_add(work, c); + c = tree_next(c); + } + } + + // remember a candidate for adding the data + // also remember the exact return code from sfunc + void *candidate = NULL; + int ret_candidate = -1; + + // process the working stack + while (work_size > 0) { + // pop element + void const *node = work[--work_size]; + + // apply the search function + ret = sfunc(node, data); + + if (ret == 0) { + // if found, exit the search + *result = (void*) node; + work_size = 0; + break; + } else if (ret > 0) { + // if children might contain the data, add them to the stack + void *c = tree_children(node); + while (c != NULL) { + cx_array_simple_add(work, c); + c = tree_next(c); + } + + // remember this node in case no child is suitable + if (ret_candidate < 0 || ret < ret_candidate) { + candidate = (void *) node; + ret_candidate = ret; + } + } + } + + // not found, but was there a candidate? + if (ret != 0 && candidate != NULL) { + ret = ret_candidate; + *result = candidate; + } + + // free the working queue and return + free(work); + return ret; +} + +static bool cx_tree_iter_valid(void const *it) { + struct cx_tree_iterator_s const *iter = it; + return iter->node != NULL; +} + +static void *cx_tree_iter_current(void const *it) { + struct cx_tree_iterator_s const *iter = it; + return iter->node; +} + +static void cx_tree_iter_next(void *it) { + struct cx_tree_iterator_s *iter = it; + ptrdiff_t const loc_next = iter->loc_next; + ptrdiff_t const loc_children = iter->loc_children; + + void *children; + + // check if we are currently exiting or entering nodes + if (iter->exiting) { + children = NULL; + // skipping on exit is pointless, just clear the flag + iter->skip = false; + } else { + if (iter->skip) { + // skip flag is set, pretend that there are no children + iter->skip = false; + children = NULL; + } else { + // try to enter the children (if any) + children = tree_children(iter->node); + } + } + + if (children == NULL) { + // search for the next node + void *next; + cx_tree_iter_search_next: + // check if there is a sibling + if (iter->exiting) { + next = iter->node_next; + } else { + next = tree_next(iter->node); + iter->node_next = next; + } + if (next == NULL) { + // no sibling, we are done with this node and exit + if (iter->visit_on_exit && !iter->exiting) { + // iter is supposed to visit the node again + iter->exiting = true; + } else { + iter->exiting = false; + if (iter->depth == 1) { + // there is no parent - we have iterated the entire tree + // invalidate the iterator and free the node stack + iter->node = iter->node_next = NULL; + iter->stack_capacity = iter->depth = 0; + free(iter->stack); + iter->stack = NULL; + } else { + // the parent node can be obtained from the top of stack + // this way we can avoid the loc_parent in the iterator + iter->depth--; + iter->node = iter->stack[iter->depth - 1]; + // retry with the parent node to find a sibling + goto cx_tree_iter_search_next; + } + } + } else { + if (iter->visit_on_exit && !iter->exiting) { + // iter is supposed to visit the node again + iter->exiting = true; + } else { + iter->exiting = false; + // move to the sibling + iter->counter++; + iter->node = next; + // new top of stack is the sibling + iter->stack[iter->depth - 1] = next; + } + } + } else { + // node has children, push the first child onto the stack and enter it + cx_array_simple_add(iter->stack, children); + iter->node = children; + iter->counter++; + } +} + +CxTreeIterator cx_tree_iterator( + void *root, + bool visit_on_exit, + ptrdiff_t loc_children, + ptrdiff_t loc_next +) { + CxTreeIterator iter; + iter.loc_children = loc_children; + iter.loc_next = loc_next; + iter.visit_on_exit = visit_on_exit; + + // allocate stack + iter.stack_capacity = 16; + iter.stack = malloc(sizeof(void *) * 16); + iter.depth = 0; + + // visit the root node + iter.node = root; + iter.node_next = NULL; + iter.counter = 1; + iter.depth = 1; + iter.stack[0] = root; + iter.exiting = false; + iter.skip = false; + + // assign base iterator functions + iter.base.mutating = false; + iter.base.remove = false; + iter.base.current_impl = NULL; + iter.base.valid = cx_tree_iter_valid; + iter.base.next = cx_tree_iter_next; + iter.base.current = cx_tree_iter_current; + + return iter; +} + +static bool cx_tree_visitor_valid(void const *it) { + struct cx_tree_visitor_s const *iter = it; + return iter->node != NULL; +} + +static void *cx_tree_visitor_current(void const *it) { + struct cx_tree_visitor_s const *iter = it; + return iter->node; +} + +__attribute__((__nonnull__)) +static void cx_tree_visitor_enqueue_siblings( + struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) { + node = tree_next(node); + while (node != NULL) { + struct cx_tree_visitor_queue_s *q; + q = malloc(sizeof(struct cx_tree_visitor_queue_s)); + q->depth = iter->queue_last->depth; + q->node = node; + iter->queue_last->next = q; + iter->queue_last = q; + node = tree_next(node); + } + iter->queue_last->next = NULL; +} + +static void cx_tree_visitor_next(void *it) { + struct cx_tree_visitor_s *iter = it; + ptrdiff_t const loc_next = iter->loc_next; + ptrdiff_t const loc_children = iter->loc_children; + + // add the children of the current node to the queue + // unless the skip flag is set + void *children; + if (iter->skip) { + iter->skip = false; + children = NULL; + } else { + children = tree_children(iter->node); + } + if (children != NULL) { + struct cx_tree_visitor_queue_s *q; + q = malloc(sizeof(struct cx_tree_visitor_queue_s)); + q->depth = iter->depth + 1; + q->node = children; + if (iter->queue_last == NULL) { + assert(iter->queue_next == NULL); + iter->queue_next = q; + } else { + iter->queue_last->next = q; + } + iter->queue_last = q; + cx_tree_visitor_enqueue_siblings(iter, children, loc_next); + } + + // check if there is a next node + if (iter->queue_next == NULL) { + iter->node = NULL; + return; + } + + // dequeue the next node + iter->node = iter->queue_next->node; + iter->depth = iter->queue_next->depth; + { + struct cx_tree_visitor_queue_s *q = iter->queue_next; + iter->queue_next = q->next; + if (iter->queue_next == NULL) { + assert(iter->queue_last == q); + iter->queue_last = NULL; + } + free(q); + } + + // increment the node counter + iter->counter++; +} + +CxTreeVisitor cx_tree_visitor( + void *root, + ptrdiff_t loc_children, + ptrdiff_t loc_next +) { + CxTreeVisitor iter; + iter.loc_children = loc_children; + iter.loc_next = loc_next; + + // allocate stack + iter.depth = 0; + + // visit the root node + iter.node = root; + iter.counter = 1; + iter.depth = 1; + iter.skip = false; + iter.queue_next = NULL; + iter.queue_last = NULL; + + // assign base iterator functions + iter.base.mutating = false; + iter.base.remove = false; + iter.base.current_impl = NULL; + iter.base.valid = cx_tree_visitor_valid; + iter.base.next = cx_tree_visitor_next; + iter.base.current = cx_tree_visitor_current; + + return iter; +} +
