# HG changeset patch # User Olaf Wintermann # Date 1669478828 -3600 # Node ID 22eca559adedc1ada0aaa616dda7b0bba9412ffd # Parent 545010bc5e7114916cc534c031eb952008782c65 refactore http listener creation diff -r 545010bc5e71 -r 22eca559aded src/server/daemon/config.c --- a/src/server/daemon/config.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/server/daemon/config.c Sat Nov 26 17:07:08 2022 +0100 @@ -678,7 +678,7 @@ } int cfg_handle_vs(ServerConfiguration *cfg, ConfigNode *obj) { - VirtualServer *vs = vs_new(); + VirtualServer *vs = vs_new(cfg->pool); vs->name = cx_strdup_a(cfg->a, serverconfig_object_directive_value(obj, cx_str("Name"))); vs->host = cx_strdup_a(cfg->a, serverconfig_object_directive_value(obj, cx_str("Host"))); diff -r 545010bc5e71 -r 22eca559aded src/server/daemon/config.h --- a/src/server/daemon/config.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/server/daemon/config.h Sat Nov 26 17:07:08 2022 +0100 @@ -71,7 +71,10 @@ CxAllocator *a; CxMap *host_vs; // map of all vservers. key is the host name - CxList *listeners; // list of all listeners + CxList *listeners; // list of all listeners - TODO: remove + + CxMap *listeners2; + CxList *logfiles; AccessLog *default_log; CxMap *authdbs; diff -r 545010bc5e71 -r 22eca559aded src/server/daemon/httplistener.c --- a/src/server/daemon/httplistener.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/server/daemon/httplistener.c Sat Nov 26 17:07:08 2022 +0100 @@ -67,7 +67,33 @@ #define LISTENER_MAX_PROTOCOL_TOKENS 1024 -CxMap *listener_map = NULL; + +#define LISTENER_PROTO_IPV4 "ipv4" +#define LISTENER_PROTO_IPV6 "ipv6" + + +/* + * key: string format: : + * value: WSSocket* + * + * protocol: ipv4 | ipv6 + * port: short + */ +static CxMap *listener_socket_map; + +static pthread_mutex_t listener_mutex; + + +int http_listener_global_init(void) { + listener_socket_map = cxHashMapCreate(cxDefaultAllocator, 4); + if(!listener_socket_map) { + return 1; + } + + listener_mutex = PTHREAD_MUTEX_INITIALIZER; + + return 0; +} int start_all_listener() { ServerConfiguration *conf = cfgmgr_get_server_config(); @@ -80,91 +106,244 @@ return 0; } -HttpListener* http_listener_create(ListenerConfig *conf) { - if(listener_map == NULL) { - listener_map = cxHashMapCreate(cxDefaultAllocator, 16); +static HttpSSL* create_http_ssl(ListenerConfig *conf) { + SSL_CTX *ctx = SSL_CTX_new(SSLv23_server_method()); + if(!ctx) { + return NULL; } - - HttpListener *fl = cxMapGet(listener_map, cx_hash_key(conf->name.ptr, conf->name.length)); - if(fl == NULL) { - return http_listener_new(conf); - } + SSL_CTX_set_options( + ctx, + SSL_OP_SINGLE_DH_USE | SSL_OP_NO_SSLv3); - HttpListener* newls = calloc(1, sizeof(HttpListener)); - if(newls == NULL) { - // TODO: error + int error = 0; + if(conf->disable_proto.ptr) { + cxstring *plist = NULL; + ssize_t n = cx_strsplit_a(cxDefaultAllocator, conf->disable_proto, cx_str(","), LISTENER_MAX_PROTOCOL_TOKENS, &plist); + if(plist) { + for(int i=0;iname.ptr, + proto.ptr); + if(!cx_strcasecmp(cx_strtrim(proto), cx_str("SSLv2"))) { + SSL_CTX_set_options(ctx, SSL_OP_NO_SSLv2); + } else if(!cx_strcasecmp(cx_strtrim(proto), cx_str("SSLv3"))) { + SSL_CTX_set_options(ctx, SSL_OP_NO_SSLv3); + } else if(!cx_strcasecmp(cx_strtrim(proto), cx_str("TLSv1"))) { + SSL_CTX_set_options(ctx, SSL_OP_NO_TLSv1); + } else if(!cx_strcasecmp(cx_strtrim(proto), cx_str("TLSv1.1"))) { +#ifdef SSL_OP_NO_TLSv1_1 + SSL_CTX_set_options(ctx, SSL_OP_NO_TLSv1_1); +#else + log_ereport( + LOG_WARN, + "Listener: %s: TLSv1.1 not supported", + conf->name.ptr); +#endif + } else if(cx_strcasecmp(cx_strtrim(proto), cx_str("TLSv1.2"))) { +#ifdef SSL_OP_NO_TLSv1_2 + SSL_CTX_set_options(ctx, SSL_OP_NO_TLSv1_2); +#else + log_ereport( + LOG_WARN, + "Listener: %s: TLSv1.2 not supported", + conf->name.ptr); +#endif + } else if(cx_strcasecmp(cx_strtrim(proto), cx_str("TLSv1.3"))) { +#ifdef SSL_OP_NO_TLSv1_3 + SSL_CTX_set_options(ctx, SSL_OP_NO_TLSv1_3); +#else + log_ereport( + LOG_WARN, + "Listener: %s: TLSv1.3 not supported", + conf->name.ptr); +#endif + } else { + error = 1; + log_ereport( + LOG_MISCONFIG, + "Listener: %s: Unknown protocol %s", + conf->name.ptr, + proto.ptr); + } + } + free(plist); + } } - newls->name = conf->name; - newls->cfg = conf->cfg; - newls->nacceptors = conf->nacceptors; - newls->default_vs.vs_name = conf->vs.ptr; - newls->port = fl->port; - newls->server_socket = fl->server_socket; - newls->server_socket6 = fl->server_socket6; - newls->running = 1; - newls->threadpool = NULL; - newls->ref = 2; // 1 reference is fl->next - - newls->session_handler = fl->session_handler; // TODO - - // the listener threadpool might be changed - if(conf->threadpool.ptr != NULL) { - newls->threadpool = get_threadpool(cx_strcast(conf->threadpool)); - } - if(newls->threadpool == NULL) { - newls->threadpool = get_default_threadpool(); + if(error) { + SSL_CTX_free(ctx); + return NULL; } - // create acceptor threads - newls->acceptors = calloc(newls->nacceptors, sizeof(void*)); - for (int i=0;inacceptors;i++) { - newls->acceptors[i] = acceptor_new(newls); + int ret; + char errbuf[512]; + + error = 0; + if(!conf->chainfile.ptr) { + ret = SSL_CTX_use_certificate_file(ctx, conf->certfile.ptr, SSL_FILETYPE_PEM); + if(!ret) { + ERR_error_string(ERR_get_error(), errbuf); + log_ereport(LOG_MISCONFIG, "Cannot load ssl chain file: %s", errbuf); + error = 1; + } + } else { + ret = SSL_CTX_use_certificate_chain_file(ctx, conf->chainfile.ptr); + if(!ret) { + ERR_error_string(ERR_get_error(), errbuf); + log_ereport(LOG_MISCONFIG, "Cannot load ssl cert file: %s", errbuf); + error = 1; + } + } + + ret = SSL_CTX_use_PrivateKey_file(ctx, conf->privkeyfile.ptr, SSL_FILETYPE_PEM); + if(!ret) { + ERR_error_string(ERR_get_error(), errbuf); + log_ereport(LOG_MISCONFIG, "Cannot load ssl key file: %s", errbuf); + error = 1; + } + + if(error) { + SSL_CTX_free(ctx); + return NULL; } - newls->acceptors6 = calloc(newls->nacceptors, sizeof(void*)); - for (int i=0;inacceptors;i++) { - newls->acceptors6[i] = acceptor_new(newls); - newls->acceptors6[i]->ipv6 = TRUE; - } + HttpSSL *ssl = pool_malloc(conf->cfg->pool, sizeof(HttpSSL)); + ZERO(ssl, sizeof(HttpSSL)); + ssl->sslctx = ctx; + + return NULL; +} + +static WSSocket* create_socket(ListenerConfig *conf, const char *protocol) { + WSBool ipv4 = !strcmp(protocol, "ipv4") ? TRUE : FALSE; - // fl hold one reference of newls - fl->next = newls; - - - cxMapPut(listener_map, cx_hash_key(newls->name.ptr, newls->name.length), newls); - - for (int i=0;inacceptors;i++) { - //acceptor_start(newls->acceptors[i]); - acceptor_start(newls->acceptors6[i]); + int s = -1; + if(ipv4) { + // ipv4 socket + s = socket(AF_INET, SOCK_STREAM, 0); + } else { + // ipv6 socket + s = socket(AF_INET6, SOCK_STREAM, IPPROTO_TCP); + } + if(s < 0) { + log_ereport( + LOG_FAILURE, + "cannot create socket: protocol: %s port: %d error: %s", + protocol, + conf->port, + strerror(errno)); + return NULL; } - // check if a restart is required to apply all changes + // socket options + int o = 1; + setsockopt( + s, + SOL_SOCKET, SO_REUSEADDR, + &o, + sizeof(int)); + +#ifdef LINUX + if(!ipv4) { + o = 1; + setsockopt( + listener->server_socket6, + IPPROTO_IPV6, + IPV6_V6ONLY, + &o, + sizeof(int)); + } +#endif - if(newls->port != conf->port) { - // TODO: log + // bind server socket to address + struct sockaddr_in servaddr4; + struct sockaddr_in6 servaddr6; + struct sockaddr *servaddr; + size_t servaddr_size; + if(ipv4) { + // ipv4 + memset(&servaddr4, 0, sizeof(servaddr4)); + servaddr4.sin_family = AF_INET; + servaddr4.sin_addr.s_addr = htonl(INADDR_ANY); + servaddr4.sin_port = htons(conf->port); + servaddr = (struct sockaddr *)&servaddr4; + servaddr_size = sizeof(servaddr4); + } else { + // ipv6 + memset(&servaddr6, 0, sizeof(servaddr6)); + servaddr6.sin6_family = AF_INET6; + servaddr6.sin6_addr = in6addr_any; + servaddr6.sin6_port = htons(conf->port); + servaddr = (struct sockaddr *)&servaddr6; + servaddr_size = sizeof(servaddr6); } - return newls; + if(bind(s, servaddr, servaddr_size)) { + log_ereport( + LOG_FAILURE, + "cannot bind socket: protocol: %s port: %d error: %s", + protocol, + conf->port, + strerror(errno)); + close(s); + return NULL; + } + + // everything is ok, create WSSocket object + WSSocket *wssocket = malloc(sizeof(WSSocket)); + if(!wssocket) { + close(s); + return NULL; + } + ZERO(wssocket, sizeof(WSSocket)); + wssocket->socket = s; + + return wssocket; } -HttpListener* http_listener_new(ListenerConfig *conf) { - // TODO: remove - if(listener_map == NULL) { - listener_map = cxHashMapCreate(cxDefaultAllocator, 16); +static WSSocket* get_socket(ListenerConfig *conf, const char *protocol) { + char key_data[32]; + size_t key_len = snprintf(key_data, 32, "%s:%d", protocol, conf->port); + CxHashKey key = cx_hash_key(key_data, key_len); + + WSSocket *sock = cxMapGet(listener_socket_map, key); + if(!sock) { + sock = create_socket(conf, protocol); + if(sock) { + cxMapPut(listener_socket_map, key, sock); + } } + return sock; +} - HttpListener *fl = cxMapGet(listener_map, cx_hash_key(conf->name.ptr, conf->name.length)); - if(fl != NULL) { - return fl; +/* + * returns HttpSSL of socket1 or socket2 if ssl is available + */ +static HttpSSL* socket_get_ssl(WSSocket *socket1, WSSocket *socket2) { + if(socket1 && socket1->ssl) { + return socket1->ssl; + } + if(socket2 && socket2->ssl) { + return socket2->ssl; } - // end remove + return NULL; +} - HttpListener *listener = malloc(sizeof(HttpListener)); +static HttpListener* listener_create(ListenerConfig *conf) { + pool_handle_t *pool = conf->cfg->pool; + HttpListener *listener = pool_malloc(pool, sizeof(HttpListener)); + if(!listener) { + return NULL; + } + ZERO(listener, sizeof(HttpListener)); + listener->running = 0; listener->cfg = conf->cfg; - listener->name = conf->name; - listener->default_vs.vs_name = conf->vs.ptr; + listener->name = cx_strdup_a(pool_allocator(pool), cx_strcast(conf->name)); + listener->default_vs.vs_name = pool_strdup(pool, conf->vs.ptr); listener->threadpool = NULL; if(conf->threadpool.ptr != NULL) { listener->threadpool = get_threadpool(cx_strcast(conf->threadpool)); @@ -173,9 +352,9 @@ listener->threadpool = get_default_threadpool(); } if(conf->blockingio) { - listener->session_handler = create_basic_session_handler(); + listener->session_handler = create_basic_session_handler(pool); } else { - listener->session_handler = create_event_session_handler(); + listener->session_handler = create_event_session_handler(pool); } listener->nacceptors = conf->nacceptors; listener->port = conf->port; @@ -183,170 +362,40 @@ listener->next = NULL; listener->ssl = NULL; - int error = 0; + // create sockets + listener->server_socket = get_socket(conf, LISTENER_PROTO_IPV4); + listener->server_socket6 = get_socket(conf, LISTENER_PROTO_IPV6); + if(!listener->server_socket && !listener->server_socket6) { + log_ereport(LOG_FAILURE, "Listener %s: no server socket", conf->name.ptr); + return NULL; + } + if(listener->server_socket) { + wssocket_ref(listener->server_socket); + } + if(listener->server_socket6) { + wssocket_ref(listener->server_socket6); + } + + // create SSL context if(conf->ssl) { - listener->ssl = malloc(sizeof(HttpSSL)); - - SSL_CTX *ctx = SSL_CTX_new(SSLv23_server_method()); - SSL_CTX_set_options( - ctx, - SSL_OP_SINGLE_DH_USE | SSL_OP_NO_SSLv3); - if(conf->disable_proto.ptr) { - cxstring *plist = NULL; - ssize_t n = cx_strsplit_a(cxDefaultAllocator, conf->disable_proto, cx_str(","), LISTENER_MAX_PROTOCOL_TOKENS, &plist); - if(plist) { - for(int i=0;iname.ptr, - proto.ptr); - if(!cx_strcasecmp(cx_strtrim(proto), cx_str("SSLv2"))) { - SSL_CTX_set_options(ctx, SSL_OP_NO_SSLv2); - } else if(!cx_strcasecmp(cx_strtrim(proto), cx_str("SSLv3"))) { - SSL_CTX_set_options(ctx, SSL_OP_NO_SSLv3); - } else if(!cx_strcasecmp(cx_strtrim(proto), cx_str("TLSv1"))) { - SSL_CTX_set_options(ctx, SSL_OP_NO_TLSv1); - } else if(!cx_strcasecmp(cx_strtrim(proto), cx_str("TLSv1.1"))) { -#ifdef SSL_OP_NO_TLSv1_1 - SSL_CTX_set_options(ctx, SSL_OP_NO_TLSv1_1); -#else - log_ereport( - LOG_WARN, - "Listener: %s: TLSv1.1 already not supported", - listener->name.ptr); -#endif - } else if(cx_strcasecmp(cx_strtrim(proto), cx_str("TLSv1.2"))) { -#ifdef SSL_OP_NO_TLSv1_2 - SSL_CTX_set_options(ctx, SSL_OP_NO_TLSv1_2); -#else - log_ereport( - LOG_WARN, - "Listener: %s: TLSv1.2 already not supported", - listener->name.ptr); -#endif - } else if(cx_strcasecmp(cx_strtrim(proto), cx_str("TLSv1.3"))) { -#ifdef SSL_OP_NO_TLSv1_3 - SSL_CTX_set_options(ctx, SSL_OP_NO_TLSv1_3); -#else - log_ereport( - LOG_WARN, - "Listener: %s: TLSv1.3 already not supported", - listener->name.ptr); -#endif - } else { - error = 1; - log_ereport( - LOG_MISCONFIG, - "Listener: %s: Unknown protocol %s", - listener->name.ptr, - proto.ptr); - } - } - free(plist); - } - } - - if(error) { - return NULL; - } - // TODO: cleanup on error - - int ret; - char errbuf[512]; - - if(!conf->chainfile.ptr) { - ret = SSL_CTX_use_certificate_file(ctx, conf->certfile.ptr, SSL_FILETYPE_PEM); - if(!ret) { - ERR_error_string(ERR_get_error(), errbuf); - log_ereport(LOG_MISCONFIG, "Cannot load ssl chain file: %s", errbuf); - return NULL; - } - } else { - ret = SSL_CTX_use_certificate_chain_file(ctx, conf->chainfile.ptr); - if(!ret) { - ERR_error_string(ERR_get_error(), errbuf); - log_ereport(LOG_MISCONFIG, "Cannot load ssl cert file: %s", errbuf); + HttpSSL *ssl = socket_get_ssl(listener->server_socket, listener->server_socket6); + if(!ssl) { + ssl = create_http_ssl(conf); + if(!ssl) { + log_ereport(LOG_FAILURE, "Listener %s: cannot create SSL context", conf->name.ptr); return NULL; } } - - ret = SSL_CTX_use_PrivateKey_file(ctx, conf->privkeyfile.ptr, SSL_FILETYPE_PEM); - if(!ret) { - ERR_error_string(ERR_get_error(), errbuf); - log_ereport(LOG_MISCONFIG, "Cannot load ssl key file: %s", errbuf); - return NULL; + if(listener->server_socket) { + listener->server_socket->ssl = ssl; } - - // TODO: chain - listener->ssl->sslctx = ctx; - } - - - cxMapPut(listener_map, cx_hash_key(listener->name.ptr, listener->name.length), listener); - - struct sockaddr_in servaddr; /* server address */ - struct sockaddr_in6 servaddr6; - - /* init address structure */ - memset(&servaddr, 0, sizeof(servaddr)); - servaddr.sin_family = AF_INET; - servaddr.sin_addr.s_addr = htonl(INADDR_ANY); - servaddr.sin_port = htons(conf->port); - - memset(&servaddr6, 0, sizeof(servaddr6)); - servaddr6.sin6_family = AF_INET6; - servaddr6.sin6_addr = in6addr_any; - servaddr6.sin6_port = htons(conf->port); - - /* create socket */ - if((listener->server_socket = socket(AF_INET, SOCK_STREAM, 0)) == -1) { - perror("Error: http_listener_new: socket"); - return NULL; - } - - if((listener->server_socket6 = socket(AF_INET6, SOCK_STREAM, IPPROTO_TCP)) == -1) { - perror("Error: http_listener_new: socket v6"); - return NULL; - } - - int o = 1; - setsockopt( - listener->server_socket, - SOL_SOCKET, SO_REUSEADDR, - &o, - sizeof(int)); - o = 1; - setsockopt( - listener->server_socket6, - SOL_SOCKET, SO_REUSEADDR, - &o, - sizeof(int)); - -#ifdef LINUX - o = 1; - setsockopt( - listener->server_socket6, - IPPROTO_IPV6, - IPV6_V6ONLY, - &o, - sizeof(int)); -#endif - - /* bind server socket to address */ - if(bind(listener->server_socket, (struct sockaddr*)&servaddr, sizeof(servaddr))){ - log_ereport(LOG_FAILURE, "http_listener_new: bind failed. Port: %d", conf->port); - return NULL; - } - - if(bind(listener->server_socket6, (struct sockaddr*)&servaddr6, sizeof(servaddr6))){ - log_ereport(LOG_FAILURE, "http_listener_new: bind v6 failed. Port: %d: %s", conf->port, strerror(errno)); - return NULL; + if(listener->server_socket6) { + listener->server_socket6->ssl = ssl; + } } - /* create acceptors */ + // create acceptors listener->acceptors = calloc(listener->nacceptors, sizeof(void*)); listener->acceptors6 = calloc(listener->nacceptors, sizeof(void*)); for (int i=0;inacceptors;i++) { @@ -358,26 +407,45 @@ return listener; } +HttpListener* http_listener_create(ListenerConfig *conf) { + pthread_mutex_lock(&listener_mutex); + HttpListener *listener = listener_create(conf); + pthread_mutex_unlock(&listener_mutex); + return listener; +} + int http_listener_start(HttpListener *listener) { if(listener->running) { return 0; } log_ereport(LOG_INFORM, "start listener on port %d", listener->port); + + WSBool ipv4 = listener->server_socket ? TRUE : FALSE; + WSBool ipv6 = listener->server_socket6 ? TRUE: FALSE; - if (listen(listener->server_socket, 256) == -1) { + if (ipv4 && !listener->server_socket->listening && listen(listener->server_socket->socket, 256) == -1) { log_ereport(LOG_FAILURE, "http_listener_start: listen failed: %s", strerror(errno)); return -1; + } else { + listener->server_socket->listening = TRUE; } - if (listen(listener->server_socket6, 256) == -1) { + if (ipv6 && !listener->server_socket6->listening && listen(listener->server_socket6->socket, 256) == -1) { log_ereport(LOG_FAILURE, "http_listener_start: listen v6 failed: %s", strerror(errno)); return -1; + } else { + listener->server_socket6->listening = TRUE; } - /* start acceptor threads */ + // start acceptor threads for (int i=0;inacceptors;i++) { - acceptor_start(listener->acceptors[i]); - acceptor_start(listener->acceptors6[i]); + if(ipv4) { + acceptor_start(listener->acceptors[i]); + } + if(ipv6) { + acceptor_start(listener->acceptors6[i]); + } } + listener->running = TRUE; return 0; } @@ -389,6 +457,7 @@ void http_listener_unref(HttpListener *listener) { uint32_t ref = ws_atomic_dec32(&listener->ref); if(ref == 0) { + log_ereport(LOG_VERBOSE, "HttpListener %s: destroy", listener->name.ptr); free(listener->acceptors); // TODO: unref cfg // TODO: unref session handler @@ -412,7 +481,7 @@ (void*(*)(void*))acceptor_thread, a) != 0) { - perror("Error: acceptor_start: pthread_create"); + log_ereport(LOG_FAILURE, "Listener %s: acceptor_start: %s", a->listener->name.ptr, strerror(errno)); } } @@ -431,12 +500,12 @@ socklen_t ca_length; ConnectionAddrType addr_type; if(acceptor->ipv6) { - server_socket = listener->server_socket6; + server_socket = listener->server_socket6->socket; ca_ptr = (struct sockaddr*)&ca.address_v6; ca_length = sizeof(ca.address_v6); addr_type = CONN_ADDR_IPV6; } else { - server_socket = listener->server_socket; + server_socket = listener->server_socket->socket; ca_ptr = (struct sockaddr*)&ca.address_v4; ca_length = sizeof(ca.address_v4); addr_type = CONN_ADDR_IPV4; @@ -444,11 +513,11 @@ for (;;) { - /* accept connections */ + // accept connections int clientfd; socklen_t length = ca_length; - /* accept a connection */ + // accept a connection clientfd = accept( server_socket, ca_ptr, @@ -512,6 +581,7 @@ if(acceptor_exit) { // this acceptor is outdated + log_ereport(LOG_VERBOSE, "acceptor thread %p: exit", (void*)acceptor->tid); break; } } @@ -521,3 +591,13 @@ return NULL; } + +void wssocket_ref(WSSocket *ws) { + ws_atomic_inc32(&ws->ref); +} + +void wssocket_unref(WSSocket *ws) { + // does nothing yet, because maybe it is not a good idea to destroy + // a socket + ws_atomic_dec32(&ws->ref); +} diff -r 545010bc5e71 -r 22eca559aded src/server/daemon/httplistener.h --- a/src/server/daemon/httplistener.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/server/daemon/httplistener.h Sat Nov 26 17:07:08 2022 +0100 @@ -47,6 +47,8 @@ typedef struct _listener_config ListenerConfig; typedef struct _http_ssl HttpSSL; +typedef struct _ws_socket WSSocket; + @@ -56,18 +58,18 @@ }; struct _listener_config { ServerConfiguration *cfg; - cxmutstr name; - cxmutstr vs; - cxmutstr threadpool; + cxmutstr name; + cxmutstr vs; + cxmutstr threadpool; char *address; int port; int nacceptors; WSBool blockingio; WSBool ssl; - cxstring certfile; - cxstring privkeyfile; - cxstring chainfile; - cxstring disable_proto; + cxstring certfile; + cxstring privkeyfile; + cxstring chainfile; + cxstring disable_proto; }; struct _acceptor { @@ -81,8 +83,8 @@ cxmutstr name; union vs default_vs; int port; - int server_socket; - int server_socket6; + WSSocket *server_socket; + WSSocket *server_socket6; SessionHandler *session_handler; threadpool_t *threadpool; HttpListener *next; @@ -95,18 +97,33 @@ }; struct _http_ssl { + /* unsigned char *cert; size_t certlen; unsigned char *privkey; size_t privkeylen; unsigned char *chain; size_t chainlen; + */ SSL_CTX *sslctx; // TODO: ssl/tls cipher, ... config }; +struct _ws_socket { + int socket; + WSBool listening; + HttpSSL *ssl; + uint32_t ref; // reference counter +}; + +/* + * global listener init function + * must be called before any other listener initialization + */ +int http_listener_global_init(void); + int start_all_listener(); HttpListener* http_listener_create(ListenerConfig *conf); @@ -123,8 +140,13 @@ void acceptor_start(Acceptor *a); +void acceptor_shutdown(Acceptor *a); + void* acceptor_thread(Acceptor *a); +void wssocket_ref(WSSocket *ws); +void wssocket_unref(WSSocket *ws); + #ifdef __cplusplus } diff -r 545010bc5e71 -r 22eca559aded src/server/daemon/log.c --- a/src/server/daemon/log.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/server/daemon/log.c Sat Nov 26 17:07:08 2022 +0100 @@ -254,12 +254,12 @@ void log_remove_logdup(LogDup *ldup) { pthread_mutex_lock(&mutex); - CxIterator i = cxListIterator(log_dup_list, 0); + CxMutIterator i = cxListMutIterator(log_dup_list, 0); WSBool finished = 0; cx_foreach(LogDup *, dup, i) { if(finished) break; if(dup == ldup) { - i.remove = 1; + cxIteratorFlagRemoval(i); finished = 1; ws_atomic_dec32(&log_dup_count); } diff -r 545010bc5e71 -r 22eca559aded src/server/daemon/sessionhandler.c --- a/src/server/daemon/sessionhandler.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/server/daemon/sessionhandler.c Sat Nov 26 17:07:08 2022 +0100 @@ -124,8 +124,8 @@ } -SessionHandler* create_basic_session_handler() { - BasicSessionHandler *handler = malloc(sizeof(BasicSessionHandler)); +SessionHandler* create_basic_session_handler(pool_handle_t *pool) { + BasicSessionHandler *handler = pool_malloc(pool, sizeof(BasicSessionHandler)); handler->threadpool = threadpool_new(4, 8); threadpool_start(handler->threadpool); // TODO: handle error handler->sh.enqueue_connection = basic_enq_conn; @@ -212,8 +212,8 @@ /* ----- event session handler ----- */ -SessionHandler* create_event_session_handler() { - EventSessionHandler *handler = malloc(sizeof(EventSessionHandler)); +SessionHandler* create_event_session_handler(pool_handle_t *pool) { + EventSessionHandler *handler = pool_malloc(pool, sizeof(EventSessionHandler)); handler->eventhandler = get_default_event_handler(); handler->sh.enqueue_connection = evt_enq_conn; handler->sh.keep_alive = evt_keep_alive; diff -r 545010bc5e71 -r 22eca559aded src/server/daemon/sessionhandler.h --- a/src/server/daemon/sessionhandler.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/server/daemon/sessionhandler.h Sat Nov 26 17:07:08 2022 +0100 @@ -144,7 +144,7 @@ WSBool *ssl); -SessionHandler* create_basic_session_handler(); +SessionHandler* create_basic_session_handler(pool_handle_t *pool); void basic_enq_conn(SessionHandler *handler, Connection *conn); @@ -153,7 +153,7 @@ void basic_keep_alive(SessionHandler *handler, Connection *conn); -SessionHandler* create_event_session_handler(); +SessionHandler* create_event_session_handler(pool_handle_t *pool); void evt_enq_conn(SessionHandler *handler, Connection *conn); diff -r 545010bc5e71 -r 22eca559aded src/server/daemon/vserver.c --- a/src/server/daemon/vserver.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/server/daemon/vserver.c Sat Nov 26 17:07:08 2022 +0100 @@ -28,8 +28,12 @@ #include "vserver.h" -VirtualServer* vs_new() { - VirtualServer *vs = malloc(sizeof(VirtualServer)); +#include + +VirtualServer* vs_new(pool_handle_t *pool) { + VirtualServer *vs = pool_malloc(pool, sizeof(VirtualServer)); + ZERO(vs, sizeof(VirtualServer)); + vs->pool = pool; vs->objects = NULL; vs->document_root = cx_mutstr("docs"); vs->acls = NULL; @@ -38,7 +42,15 @@ return vs; } - +int vs_add_host(VirtualServer *vs, cxstring host) { + cxmutstr host_cp = cx_strdup_a(pool_allocator(vs->pool), host); + if(!vs->host.ptr) { + vs->host = host_cp; + } + + + return 0; +} // public API diff -r 545010bc5e71 -r 22eca559aded src/server/daemon/vserver.h --- a/src/server/daemon/vserver.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/server/daemon/vserver.h Sat Nov 26 17:07:08 2022 +0100 @@ -51,17 +51,20 @@ }; struct VirtualServer { + pool_handle_t *pool; + cxmutstr name; cxmutstr host; + CxMap hosts; // TODO: list of listeners, check listener of vs cxmutstr objectfile; - HTTPObjectConfig *objects; + HTTPObjectConfig *objects; cxmutstr document_root; - ACLData *acls; - AccessLog *log; + ACLData *acls; + AccessLog *log; VSLocation *locations_begin; VSLocation *locations_end; @@ -70,7 +73,9 @@ uint32_t ref; // reference counter }; -VirtualServer* vs_new(); +VirtualServer* vs_new(pool_handle_t *pool); + +int vs_add_host(VirtualServer *vs, cxstring host); #ifdef __cplusplus diff -r 545010bc5e71 -r 22eca559aded src/server/daemon/webserver.c --- a/src/server/daemon/webserver.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/server/daemon/webserver.c Sat Nov 26 17:07:08 2022 +0100 @@ -79,6 +79,12 @@ return -1; } + // init listener socket map + if(http_listener_global_init()) { + log_ereport(LOG_FAILURE, "listener global init failed"); + return -1; + } + // init NSAPI functions pblock_init_default_keys(); atexit(pblock_free_default_keys); diff -r 545010bc5e71 -r 22eca559aded src/ucx/allocator.c --- a/src/ucx/allocator.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/allocator.c Sat Nov 26 17:07:08 2022 +0100 @@ -77,7 +77,7 @@ }; CxAllocator *cxDefaultAllocator = &cx_default_allocator; -/* IMPLEMENTATION OF HIGH LEVEL API */ +// IMPLEMENTATION OF HIGH LEVEL API void *cxMalloc( CxAllocator const *allocator, diff -r 545010bc5e71 -r 22eca559aded src/ucx/array_list.c --- a/src/ucx/array_list.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/array_list.c Sat Nov 26 17:07:08 2022 +0100 @@ -31,7 +31,7 @@ #include #include -/* LOW LEVEL ARRAY LIST FUNCTIONS */ +// LOW LEVEL ARRAY LIST FUNCTIONS enum cx_array_copy_result cx_array_copy( void **target, @@ -43,35 +43,37 @@ size_t elem_count, struct cx_array_reallocator_s *reallocator ) { - /* assert pointers */ + // assert pointers assert(target != NULL); assert(size != NULL); assert(src != NULL); - /* determine capacity */ + // determine capacity size_t cap = capacity == NULL ? *size : *capacity; - /* check if resize is required */ - size_t newsize = index + elem_count; + // check if resize is required + size_t minsize = index + elem_count; + size_t newsize = *size < minsize ? minsize : *size; bool needrealloc = newsize > cap; - /* reallocate if possible */ + // reallocate if possible if (needrealloc) { - /* a reallocator and a capacity variable must be available */ + // a reallocator and a capacity variable must be available if (reallocator == NULL || capacity == NULL) { return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED; } - /* check, if we need to repair the src pointer */ + // check, if we need to repair the src pointer uintptr_t targetaddr = (uintptr_t) *target; uintptr_t srcaddr = (uintptr_t) src; bool repairsrc = targetaddr <= srcaddr && srcaddr < targetaddr + cap * elem_size; - /* increase capacity linearly */ - cap += 16; + // calculate new capacity (next number divisible by 16) + cap = newsize - (newsize % 16) + 16; + assert(cap > newsize); - /* perform reallocation */ + // perform reallocation void *newmem = reallocator->realloc( *target, cap, elem_size, reallocator ); @@ -79,29 +81,68 @@ return CX_ARRAY_COPY_REALLOC_FAILED; } - /* repair src pointer, if necessary */ + // repair src pointer, if necessary if (repairsrc) { src = ((char *) newmem) + (srcaddr - targetaddr); } - /* store new pointer and capacity */ + // store new pointer and capacity *target = newmem; *capacity = cap; } - /* determine target pointer */ + // determine target pointer char *start = *target; start += index * elem_size; - /* copy elements and set new size */ + // copy elements and set new size memmove(start, src, elem_count * elem_size); *size = newsize; - /* return successfully */ + // return successfully return CX_ARRAY_COPY_SUCCESS; } -/* HIGH LEVEL ARRAY LIST FUNCTIONS */ +#define CX_ARRAY_SWAP_SBO_SIZE 512 + +void cx_array_swap( + void *arr, + size_t elem_size, + size_t idx1, + size_t idx2 +) { + // short circuit + if (idx1 == idx2) return; + + char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE]; + void *tmp; + + // decide if we can use the local buffer + if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) { + tmp = malloc(elem_size); + // we don't want to enforce error handling + if (tmp == NULL) abort(); + } else { + tmp = sbo_mem; + } + + // calculate memory locations + char *left = arr, *right = arr; + left += idx1 * elem_size; + right += idx2 * elem_size; + + // three-way swap + memcpy(tmp, left, elem_size); + memcpy(left, right, elem_size); + memcpy(right, tmp, elem_size); + + // free dynamic memory, if it was needed + if (tmp != sbo_mem) { + free(tmp); + } +} + +// HIGH LEVEL ARRAY LIST FUNCTIONS typedef struct { struct cx_list_s base; @@ -115,10 +156,10 @@ size_t elem_size, struct cx_array_reallocator_s *alloc ) { - /* retrieve the pointer to the list allocator */ + // retrieve the pointer to the list allocator CxAllocator const *al = alloc->ptr1; - /* use the list allocator to reallocate the memory */ + // use the list allocator to reallocate the memory return cxRealloc(al, array, capacity * elem_size); } @@ -144,6 +185,29 @@ ); } +static size_t cx_arl_add_array( + struct cx_list_s *list, + void const *array, + size_t n +) { + cx_array_list *arl = (cx_array_list *) list; + if (CX_ARRAY_COPY_SUCCESS == cx_array_copy( + &arl->data, + &list->size, + &list->capacity, + list->size, + array, + list->itemsize, + n, + &arl->reallocator + )) { + return n; + } else { + // array list implementation is "all or nothing" + return 0; + } +} + static int cx_arl_insert( struct cx_list_s *list, size_t index, @@ -156,7 +220,7 @@ } else { cx_array_list *arl = (cx_array_list *) list; - /* move elements starting at index to the right */ + // move elements starting at index to the right if (cx_array_copy( &arl->data, &list->size, @@ -170,7 +234,7 @@ return 1; } - /* place the element */ + // place the element memcpy(((char *) arl->data) + index * list->itemsize, elem, list->itemsize); @@ -179,25 +243,46 @@ } static int cx_arl_insert_iter( - struct cx_iterator_s *iter, + struct cx_mut_iterator_s *iter, void const *elem, int prepend ) { - return 1; + struct cx_list_s *list = iter->src_handle; + if (iter->index < list->size) { + int result = cx_arl_insert( + list, + iter->index + 1 - prepend, + elem + ); + if (result == 0 && prepend != 0) { + iter->index++; + iter->elem_handle = ((char *) iter->elem_handle) + list->itemsize; + } + return result; + } else { + int result = cx_arl_add(list, elem); + iter->index = list->size; + return result; + } } static int cx_arl_remove( struct cx_list_s *list, size_t index ) { - /* out-of-bounds check */ + // out-of-bounds check if (index >= list->size) { return 1; } - cx_array_list *arl = (cx_array_list *) list; + // short-circuit removal of last element + if (index == list->size - 1) { + list->size--; + return 0; + } - /* just move the elements starting at index to the left */ + // just move the elements starting at index to the left + cx_array_list *arl = (cx_array_list *) list; int result = cx_array_copy( &arl->data, &list->size, @@ -205,11 +290,11 @@ index, ((char *) arl->data) + (index + 1) * list->itemsize, list->itemsize, - list->size - index, + list->size - index - 1, &arl->reallocator ); if (result == 0) { - /* decrease the size */ + // decrease the size list->size--; } return result; @@ -256,34 +341,70 @@ struct cx_list_s const *list, struct cx_list_s const *other ) { - + if (list->size == other->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); + if (d != 0) { + return d; + } + left += list->itemsize; + right += other->itemsize; + } + return 0; + } else { + return list->size < other->size ? -1 : 1; + } } static void cx_arl_reverse(struct cx_list_s *list) { - + if (list->size < 2) return; + void *data = ((cx_array_list const *) list)->data; + size_t half = list->size / 2; + for (size_t i = 0; i < half; i++) { + cx_array_swap(data, list->itemsize, i, list->size - 1 - i); + } } -static bool cx_arl_iter_valid(struct cx_iterator_s const *iter) { +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; } -static void *cx_arl_iter_current(struct cx_iterator_s const *iter) { +static void *cx_arl_iter_current(void const *it) { + struct cx_iterator_s const *iter = it; return iter->elem_handle; } -static void cx_arl_iter_next(struct cx_iterator_s *iter) { - if (iter->remove) { - iter->remove = false; +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); } else { + struct cx_iterator_s *iter = it; iter->index++; - iter->elem_handle = cx_arl_at(iter->src_handle, iter->index); + iter->elem_handle = + ((char *) iter->elem_handle) + + ((struct cx_list_s const *) iter->src_handle)->itemsize; + } +} + +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 *list, + struct cx_list_s const *list, size_t index ) { struct cx_iterator_s iter; @@ -291,17 +412,33 @@ iter.index = index; iter.src_handle = list; iter.elem_handle = cx_arl_at(list, index); - iter.valid = cx_arl_iter_valid; - iter.current = cx_arl_iter_current; - iter.next = cx_arl_iter_next; - iter.remove = false; + iter.base.valid = cx_arl_iter_valid; + iter.base.current = cx_arl_iter_current; + iter.base.next = cx_arl_iter_next; + iter.base.flag_removal = cx_arl_iter_flag_rm; + iter.base.remove = false; + iter.base.mutating = false; + + return iter; +} +static struct cx_mut_iterator_s cx_arl_mut_iterator( + struct cx_list_s *list, + size_t index +) { + CxIterator it = cx_arl_iterator(list, index); + it.base.mutating = true; + + // we know the iterators share the same memory layout + CxMutIterator iter; + memcpy(&iter, &it, sizeof(CxMutIterator)); return iter; } static cx_list_class cx_array_list_class = { cx_arl_destructor, cx_arl_add, + cx_arl_add_array, cx_arl_insert, cx_arl_insert_iter, cx_arl_remove, @@ -311,6 +448,7 @@ cx_arl_compare, cx_arl_reverse, cx_arl_iterator, + cx_arl_mut_iterator, }; CxList *cxArrayListCreate( @@ -334,7 +472,7 @@ list->base.itemsize = item_size; list->base.capacity = initial_capacity; - /* configure the reallocator */ + // configure the reallocator list->reallocator.realloc = cx_arl_realloc; list->reallocator.ptr1 = (void *) allocator; diff -r 545010bc5e71 -r 22eca559aded src/ucx/cx/allocator.h --- a/src/ucx/cx/allocator.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/cx/allocator.h Sat Nov 26 17:07:08 2022 +0100 @@ -254,7 +254,7 @@ __attribute__((__nonnull__)); #ifdef __cplusplus -} /* extern "C" */ +} // extern "C" #endif -#endif /* UCX_ALLOCATOR_H */ +#endif // UCX_ALLOCATOR_H diff -r 545010bc5e71 -r 22eca559aded src/ucx/cx/array_list.h --- a/src/ucx/cx/array_list.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/cx/array_list.h Sat Nov 26 17:07:08 2022 +0100 @@ -132,6 +132,22 @@ struct cx_array_reallocator_s *reallocator ) __attribute__((__nonnull__(1, 2, 5))); + +/** + * Swaps two array elements. + * + * @param arr the array + * @param elem_size the element size + * @param idx1 index of first element + * @param idx2 index of second element + */ +void cx_array_swap( + void *arr, + size_t elem_size, + size_t idx1, + size_t idx2 +) __attribute__((__nonnull__)); + /** * Allocates an array list for storing elements with \p item_size bytes each. * @@ -150,7 +166,7 @@ #ifdef __cplusplus -} /* extern "C" */ +} // extern "C" #endif -#endif /* UCX_ARRAY_LIST_H */ +#endif // UCX_ARRAY_LIST_H diff -r 545010bc5e71 -r 22eca559aded src/ucx/cx/buffer.h --- a/src/ucx/cx/buffer.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/cx/buffer.h Sat Nov 26 17:07:08 2022 +0100 @@ -411,4 +411,4 @@ } #endif -#endif /* UCX_BUFFER_H */ +#endif // UCX_BUFFER_H diff -r 545010bc5e71 -r 22eca559aded src/ucx/cx/common.h --- a/src/ucx/cx/common.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/cx/common.h Sat Nov 26 17:07:08 2022 +0100 @@ -110,12 +110,12 @@ #else #define __WORDSIZE 32 #endif -#endif /* __WORDSIZE */ -#else /* !_WIN32 */ +#endif // __WORDSIZE +#else // !_WIN32 #include -#endif /* _WIN32 */ +#endif // _WIN32 #ifndef __GNUC__ /** @@ -124,4 +124,4 @@ #define __attribute__(x) #endif -#endif /* UCX_COMMON_H */ +#endif // UCX_COMMON_H diff -r 545010bc5e71 -r 22eca559aded src/ucx/cx/hash_key.h --- a/src/ucx/cx/hash_key.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/cx/hash_key.h Sat Nov 26 17:07:08 2022 +0100 @@ -125,4 +125,4 @@ } // extern "C" #endif -#endif /* UCX_HASH_KEY_H */ +#endif // UCX_HASH_KEY_H diff -r 545010bc5e71 -r 22eca559aded src/ucx/cx/iterator.h --- a/src/ucx/cx/iterator.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/cx/iterator.h Sat Nov 26 17:07:08 2022 +0100 @@ -40,26 +40,53 @@ #include "common.h" /** - * Internal iterator struct - use CxIterator. + * The base of mutating and non-mutating iterators. */ -struct cx_iterator_s { +struct cx_iterator_base_s { /** * True iff the iterator points to valid data. */ __attribute__ ((__nonnull__)) - bool (*valid)(struct cx_iterator_s const *); + bool (*valid)(void const *); /** * Returns a pointer to the current element. */ __attribute__ ((__nonnull__)) - void *(*current)(struct cx_iterator_s const *); + void *(*current)(void const *); /** * Advances the iterator. */ __attribute__ ((__nonnull__)) - void (*next)(struct cx_iterator_s *); + void (*next)(void *); + + /** + * Flag current element for removal, if possible. + */ + __attribute__ ((__nonnull__)) + bool (*flag_removal)(void *); + + /** + * Indicates whether this iterator is muting. + */ + bool mutating; + + /** + * Internal flag for removing the current element when advancing. + */ + bool remove; +}; + +/** + * Internal iterator struct - use CxMutIterator. + */ +struct cx_mut_iterator_s { + + /** + * The base properties of this iterator. + */ + struct cx_iterator_base_s base; /** * Handle for the current element, if required. @@ -79,7 +106,7 @@ /** * A pointer to the key. */ - void *key; + void const *key; /** * A pointer to the value. */ @@ -97,13 +124,70 @@ * Otherwise, this field is usually uninitialized. */ size_t index; +}; + +/** + * 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. + * + * @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; /** - * Users may set this to true, if the current element shall be removed from the underlying collection - * when the iterator advances. - * Has no effect on iterators that are not based on a collection. + * 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. */ - bool remove; + 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; }; /** @@ -112,10 +196,11 @@ * 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 (elements added or removed), - * the iterator becomes invalid (regardless of what cxIteratorValid() returns) and MUST be re-obtained - * from the collection. + * @note Objects that are pointed to by an iterator are always mutable through that iterator. However, + * this iterator cannot mutate the collection itself (add or remove elements) and any mutation of the + * collection by other means make this iterator invalid (regardless of what cxIteratorValid() returns). + * + * @see CxMutIterator */ typedef struct cx_iterator_s CxIterator; @@ -124,36 +209,35 @@ * * This is especially false for past-the-end iterators. * - * @param iter a pointer to the iterator + * @param iter the iterator * @return true iff the iterator points to valid data */ -__attribute__ ((__nonnull__)) -static inline bool cxIteratorValid(CxIterator const *iter) { - return iter->valid(iter); -} +#define cxIteratorValid(iter) (iter).base.valid(&(iter)) /** * Returns a pointer to the current element. * * The behavior is undefined if this iterator is invalid. * - * @param iter a pointer to the iterator + * @param iter the iterator * @return a pointer to the current element */ -__attribute__ ((__nonnull__)) -static inline void *cxIteratorCurrent(CxIterator const *iter) { - return iter->current(iter); -} +#define cxIteratorCurrent(iter) (iter).base.current(&iter) /** * Advances the iterator to the next element. * - * @param iter a pointer to the iterator + * @param iter the iterator */ -__attribute__ ((__nonnull__)) -static inline void cxIteratorNext(CxIterator *iter) { - iter->next(iter); -} +#define cxIteratorNext(iter) (iter).base.next(&iter) + +/** + * Flags the current element for removal. + * + * @param iter the iterator + * @return false if this iterator cannot remove the element + */ +#define cxIteratorFlagRemoval(iter) (iter).base.flag_removal(&iter) /** * Loops over an iterator. @@ -162,6 +246,6 @@ * @param iter the iterator */ #define cx_foreach(type, elem, iter) \ -for (type elem; cxIteratorValid(&iter) && (elem = (type)cxIteratorCurrent(&iter)) != NULL ; cxIteratorNext(&iter)) // NOLINT(bugprone-macro-parentheses) +for (type elem; cxIteratorValid(iter) && (elem = (type)cxIteratorCurrent(iter)) != NULL ; cxIteratorNext(iter)) -#endif /* UCX_ITERATOR_H */ +#endif // UCX_ITERATOR_H diff -r 545010bc5e71 -r 22eca559aded src/ucx/cx/linked_list.h --- a/src/ucx/cx/linked_list.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/cx/linked_list.h Sat Nov 26 17:07:08 2022 +0100 @@ -80,27 +80,6 @@ ) __attribute__((__nonnull__)); /** - * Creates a linked list using the data from an array. - * - * @remark Elements added to the list are copied, therefore a possible destructor - * MUST NOT free the memory pointed to by its argument. - * - * @param allocator the allocator for allocating the list nodes - * @param comparator the comparator for the elements - * @param item_size the size of one item in the array - * @param num_items the number of items - * @param array the array data - * @return the created list - */ -CxList *cxLinkedListFromArray( - CxAllocator const *allocator, - CxListComparator comparator, - size_t item_size, - size_t num_items, - void const *array -) __attribute__((__nonnull__)); - -/** * Finds the node at a certain index. * * This function can be used to start at an arbitrary position within the list. @@ -444,7 +423,7 @@ ) __attribute__((__nonnull__(1))); #ifdef __cplusplus -} /* extern "C" */ +} // extern "C" #endif -#endif /* UCX_LINKED_LIST_H */ +#endif // UCX_LINKED_LIST_H diff -r 545010bc5e71 -r 22eca559aded src/ucx/cx/list.h --- a/src/ucx/cx/list.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/cx/list.h Sat Nov 26 17:07:08 2022 +0100 @@ -130,6 +130,15 @@ ); /** + * Member function for adding multiple elements. + */ + size_t (*add_array)( + struct cx_list_s *list, + void const *array, + size_t n + ); + + /** * Member function for inserting an element. */ int (*insert)( @@ -142,7 +151,7 @@ * Member function for inserting an element relative to an iterator position. */ int (*insert_iter)( - struct cx_iterator_s *iter, + struct cx_mut_iterator_s *iter, void const *elem, int prepend ); @@ -193,6 +202,14 @@ * Returns an iterator pointing to the specified index. */ struct cx_iterator_s (*iterator)( + struct cx_list_s const *list, + size_t index + ); + + /** + * Returns a mutating iterator pointing to the specified index. + */ + struct cx_mut_iterator_s (*mut_iterator)( struct cx_list_s *list, size_t index ); @@ -209,6 +226,7 @@ * @param list the list * @param elem a pointer to the element to add * @return zero on success, non-zero on memory allocation failure + * @see cxListAddArray() */ __attribute__((__nonnull__)) static inline int cxListAdd( @@ -219,6 +237,28 @@ } /** + * Adds multiple items to the end of the list. + * + * This method is more efficient than invoking cxListAdd() multiple times. + * + * If there is not enough memory to add all elements, the returned value is + * less than \p n. + * + * @param list the list + * @param array a pointer to the elements to add + * @param n the number of elements to add + * @return the number of added elements + */ +__attribute__((__nonnull__)) +static inline size_t cxListAddArray( + CxList *list, + void const *array, + size_t n +) { + return list->cl->add_array(list, array, n); +} + +/** * Inserts an item at the specified index. * * If \p index equals the list \c size, this is effectively cxListAdd(). @@ -257,7 +297,7 @@ */ __attribute__((__nonnull__)) static inline int cxListInsertAfter( - CxIterator *iter, + CxMutIterator *iter, void const *elem ) { return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0); @@ -280,7 +320,7 @@ */ __attribute__((__nonnull__)) static inline int cxListInsertBefore( - CxIterator *iter, + CxMutIterator *iter, void const *elem ) { return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1); @@ -328,10 +368,29 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) static inline CxIterator cxListIterator( + CxList const *list, + size_t index +) { + return list->cl->iterator(list, index); +} + +/** + * Returns a mutating iterator pointing to the item at the specified index. + * + * The returned iterator is position-aware. + * + * If the index is out of range, a past-the-end iterator will be returned. + * + * @param list the list + * @param index the index where the iterator shall point at + * @return a new iterator + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxMutIterator cxListMutIterator( CxList *list, size_t index ) { - return list->cl->iterator(list, index); + return list->cl->mut_iterator(list, index); } /** @@ -345,11 +404,26 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxListBegin(CxList *list) { +static inline CxIterator cxListBegin(CxList const *list) { return list->cl->iterator(list, 0); } /** + * Returns a mutating iterator pointing to the first item of the list. + * + * The returned iterator is position-aware. + * + * If the list is empty, a past-the-end iterator will be returned. + * + * @param list the list + * @return a new iterator + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxMutIterator cxListBeginMut(CxList *list) { + return list->cl->mut_iterator(list, 0); +} + +/** * Returns the index of the first element that equals \p elem. * * Determining equality is performed by the list's comparator function. @@ -360,7 +434,7 @@ */ __attribute__((__nonnull__)) static inline size_t cxListFind( - CxList *list, + CxList const *list, void const *elem ) { return list->cl->find(list, elem); @@ -391,19 +465,19 @@ /** * Compares a list to another list of the same type. * - * First, the list sizes are compared. If they match, the lists are compared element-wise. + * First, the list sizes are compared. + * If they match, the lists are compared element-wise. * * @param list the list * @param other the list to compare to - * @return zero, if both lists are equal element wise, negative if the first list is smaller, zero if the first list is larger + * @return zero, if both lists are equal element wise, + * negative if the first list is smaller, positive if the first list is larger */ __attribute__((__nonnull__)) -static inline int cxListCompare( - CxList *list, - CxList *other -) { - return list->cl->compare(list, other); -} +int cxListCompare( + CxList const *list, + CxList const *other +); /** * Deallocates the memory of the specified list structure. @@ -419,7 +493,7 @@ void cxListDestroy(CxList *list); #ifdef __cplusplus -} /* extern "C" */ +} // extern "C" #endif -#endif /* UCX_LIST_H */ +#endif // UCX_LIST_H diff -r 545010bc5e71 -r 22eca559aded src/ucx/cx/map.h --- a/src/ucx/cx/map.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/cx/map.h Sat Nov 26 17:07:08 2022 +0100 @@ -114,19 +114,37 @@ * Iterator over the key/value pairs. */ __attribute__((__nonnull__, __warn_unused_result__)) - CxIterator (*iterator)(CxMap *map); + CxIterator (*iterator)(CxMap const *map); /** * Iterator over the keys. */ __attribute__((__nonnull__, __warn_unused_result__)) - CxIterator (*iterator_keys)(CxMap *map); + CxIterator (*iterator_keys)(CxMap const *map); /** * Iterator over the values. */ __attribute__((__nonnull__, __warn_unused_result__)) - CxIterator (*iterator_values)(CxMap *map); + CxIterator (*iterator_values)(CxMap const *map); + + /** + * Mutating iterator over the key/value pairs. + */ + __attribute__((__nonnull__, __warn_unused_result__)) + CxMutIterator (*mut_iterator)(CxMap *map); + + /** + * Mutating iterator over the keys. + */ + __attribute__((__nonnull__, __warn_unused_result__)) + CxMutIterator (*mut_iterator_keys)(CxMap *map); + + /** + * Mutating iterator over the values. + */ + __attribute__((__nonnull__, __warn_unused_result__)) + CxMutIterator (*mut_iterator_values)(CxMap *map); }; /** @@ -263,6 +281,55 @@ return map->cl->iterator(map); } + +/** + * Creates a mutating iterator over the values of a map. + * + * \note An iterator iterates over all elements successively. Therefore the order + * highly depends on the map implementation and may change arbitrarily when the contents change. + * + * @param map the map to create the iterator for + * @return an iterator for the currently stored values + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) { + return map->cl->mut_iterator_values(map); +} + +/** + * Creates a mutating iterator over the keys of a map. + * + * The elements of the iterator are keys of type CxHashKey. + * + * \note An iterator iterates over all elements successively. Therefore the order + * highly depends on the map implementation and may change arbitrarily when the contents change. + * + * @param map the map to create the iterator for + * @return an iterator for the currently stored keys + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) { + return map->cl->mut_iterator_keys(map); +} + +/** + * Creates a mutating iterator for a map. + * + * The elements of the iterator are key/value pairs of type CxMapEntry. + * + * \note An iterator iterates over all elements successively. Therefore the order + * highly depends on the map implementation and may change arbitrarily when the contents change. + * + * @param map the map to create the iterator for + * @return an iterator for the currently stored entries + * @see cxMapMutIteratorKeys() + * @see cxMapMutIteratorValues() + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxMutIterator cxMapMutIterator(CxMap *map) { + return map->cl->mut_iterator(map); +} + #ifdef __cplusplus } #endif diff -r 545010bc5e71 -r 22eca559aded src/ucx/cx/tree.h --- a/src/ucx/cx/tree.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/cx/tree.h Sat Nov 26 17:07:08 2022 +0100 @@ -129,8 +129,8 @@ #ifdef __cplusplus -} /* extern "C" */ +} // extern "C" #endif -#endif /* UCX_TREE_H */ +#endif // UCX_TREE_H diff -r 545010bc5e71 -r 22eca559aded src/ucx/cx/utils.h --- a/src/ucx/cx/utils.h Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/cx/utils.h Sat Nov 26 17:07:08 2022 +0100 @@ -51,9 +51,7 @@ */ #define cx_for_n(varname, n) for (size_t varname = 0 ; (varname) < (n) ; (varname)++) -/* ---------------------- - * cx_szmul() definition. - * ---------------------- */ +// cx_szmul() definition #if (__GNUC__ >= 5 || defined(__clang__)) && !defined(CX_NO_SZMUL_BUILTIN) #define CX_SZMUL_BUILTIN @@ -72,7 +70,7 @@ * otherwise */ #define cx_szmul(a, b, result) __builtin_umul_overflow(a, b, result) -#else /* __WORDSIZE != 32 */ +#else // __WORDSIZE != 32 /** * Alias for \c __builtin_umull_overflow. * @@ -86,9 +84,9 @@ * otherwise */ #define cx_szmul(a, b, result) __builtin_umull_overflow(a, b, result) -#endif /* __WORDSIZE */ +#endif // __WORDSIZE -#else /* no GNUC or clang bultin */ +#else // no GNUC or clang bultin /** * Performs a multiplication of size_t values and checks for overflow. @@ -122,4 +120,4 @@ } #endif -#endif /* UCX_UTILS_H */ +#endif // UCX_UTILS_H diff -r 545010bc5e71 -r 22eca559aded src/ucx/hash_key.c --- a/src/ucx/hash_key.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/hash_key.c Sat Nov 26 17:07:08 2022 +0100 @@ -32,7 +32,7 @@ void cx_hash_murmur(CxHashKey *key) { unsigned char const *data = key->data.cbytes; if (data == NULL) { - /* extension: special value for NULL */ + // extension: special value for NULL key->hash = 1574210520u; return; } @@ -70,8 +70,8 @@ h ^= (data[i + 0] & 0xFF); h *= m; __attribute__((__fallthrough__)); - default: - /* do nothing */; + default: // do nothing + ; } h ^= h >> 13; diff -r 545010bc5e71 -r 22eca559aded src/ucx/hash_map.c --- a/src/ucx/hash_map.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/hash_map.c Sat Nov 26 17:07:08 2022 +0100 @@ -201,34 +201,42 @@ return cx_hash_map_get_remove(map, key, true); } -static void *cx_hash_map_iter_current_entry(CxIterator const *iter) { +static void *cx_hash_map_iter_current_entry(void const *it) { + struct cx_iterator_s const *iter = it; // struct has to have a compatible signature return (struct cx_map_entry_s *) &(iter->kv_data); } -static void *cx_hash_map_iter_current_key(CxIterator const *iter) { +static void *cx_hash_map_iter_current_key(void const *it) { + struct cx_iterator_s const *iter = it; struct cx_hash_map_element_s *elm = iter->elem_handle; return &elm->key; } -static void *cx_hash_map_iter_current_value(CxIterator const *iter) { +static void *cx_hash_map_iter_current_value(void const *it) { + struct cx_iterator_s const *iter = it; struct cx_hash_map_element_s *elm = iter->elem_handle; // TODO: return a pointer to data if this map is storing copies return elm->data; } -static bool cx_hash_map_iter_valid(CxIterator const *iter) { +static bool cx_hash_map_iter_valid(void const *it) { + struct cx_iterator_s const *iter = it; return iter->elem_handle != NULL; } -static void cx_hash_map_iter_next(CxIterator *iter) { - struct cx_hash_map_s *map = iter->src_handle; +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; // remove current element, if asked - if (iter->remove) { + 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->remove = false; + iter->base.remove = false; // determine the next element struct cx_hash_map_element_s *next = elm->next; @@ -254,6 +262,7 @@ } // 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]; } @@ -270,17 +279,29 @@ } } -static CxIterator cx_hash_map_iterator(CxMap *map) { +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) { CxIterator iter; iter.src_handle = map; - iter.valid = cx_hash_map_iter_valid; - iter.next = cx_hash_map_iter_next; - iter.current = cx_hash_map_iter_current_entry; + iter.base.valid = cx_hash_map_iter_valid; + iter.base.next = cx_hash_map_iter_next; + iter.base.current = cx_hash_map_iter_current_entry; + iter.base.flag_removal = cx_hash_map_iter_flag_rm; + iter.base.remove = false; + iter.base.mutating = false; iter.slot = 0; iter.index = 0; - iter.remove = false; if (map->size > 0) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; @@ -301,15 +322,37 @@ return iter; } -static CxIterator cx_hash_map_iterator_keys(CxMap *map) { +static CxIterator cx_hash_map_iterator_keys(CxMap const *map) { CxIterator iter = cx_hash_map_iterator(map); - iter.current = cx_hash_map_iter_current_key; + iter.base.current = cx_hash_map_iter_current_key; + return iter; +} + +static CxIterator cx_hash_map_iterator_values(CxMap const *map) { + CxIterator iter = cx_hash_map_iterator(map); + iter.base.current = cx_hash_map_iter_current_value; return iter; } -static CxIterator cx_hash_map_iterator_values(CxMap *map) { - CxIterator iter = cx_hash_map_iterator(map); - iter.current = cx_hash_map_iter_current_value; +static CxMutIterator cx_hash_map_mut_iterator(CxMap *map) { + CxIterator it = cx_hash_map_iterator(map); + it.base.mutating = true; + + // we know the iterators share the same memory layout + CxMutIterator iter; + memcpy(&iter, &it, sizeof(CxMutIterator)); + return iter; +} + +static CxMutIterator cx_hash_map_mut_iterator_keys(CxMap *map) { + CxMutIterator iter = cx_hash_map_mut_iterator(map); + iter.base.current = cx_hash_map_iter_current_key; + return iter; +} + +static CxMutIterator cx_hash_map_mut_iterator_values(CxMap *map) { + CxMutIterator iter = cx_hash_map_mut_iterator(map); + iter.base.current = cx_hash_map_iter_current_value; return iter; } @@ -322,6 +365,9 @@ cx_hash_map_iterator, cx_hash_map_iterator_keys, cx_hash_map_iterator_values, + cx_hash_map_mut_iterator, + cx_hash_map_mut_iterator_keys, + cx_hash_map_mut_iterator_values, }; CxMap *cxHashMapCreate( diff -r 545010bc5e71 -r 22eca559aded src/ucx/linked_list.c --- a/src/ucx/linked_list.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/linked_list.c Sat Nov 26 17:07:08 2022 +0100 @@ -32,7 +32,7 @@ #include #include -/* LOW LEVEL LINKED LIST FUNCTIONS */ +// LOW LEVEL LINKED LIST FUNCTIONS #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) #define ll_prev(node) CX_LL_PTR(node, loc_prev) @@ -337,7 +337,7 @@ return ret; } -void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */ +void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function void **begin, void **end, ptrdiff_t loc_prev, @@ -455,7 +455,7 @@ *begin = prev; } -/* HIGH LEVEL LINKED LIST IMPLEMENTATION */ +// HIGH LEVEL LINKED LIST IMPLEMENTATION typedef struct cx_linked_list_node cx_linked_list_node; struct cx_linked_list_node { @@ -540,6 +540,20 @@ return cx_ll_insert(list, list->size, elem); } +static size_t cx_ll_add_array( + struct cx_list_s *list, + void const *array, + size_t n +) { + // TODO: redirect to cx_ll_insert_array + cx_for_n (i, n) { + if (cx_ll_add(list, ((char const *) array) + i * list->itemsize)) { + return i; + } + } + return n; +} + static int cx_pll_insert( struct cx_list_s *list, size_t index, @@ -629,13 +643,16 @@ left->follow_ptr, right->follow_ptr, list->cmpfunc); } -static bool cx_ll_iter_valid(CxIterator const *iter) { +static bool cx_ll_iter_valid(void const *it) { + struct cx_iterator_s const *iter = it; return iter->elem_handle != NULL; } -static void cx_ll_iter_next(CxIterator *iter) { - if (iter->remove) { - iter->remove = false; +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; cx_linked_list *ll = iter->src_handle; cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->next; @@ -644,48 +661,85 @@ ll->base.size--; cxFree(ll->base.allocator, node); } else { + struct cx_iterator_s *iter = it; iter->index++; cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->next; } } -static void *cx_ll_iter_current(CxIterator const *iter) { +static void *cx_ll_iter_current(void const *it) { + struct cx_iterator_s const *iter = it; cx_linked_list_node *node = iter->elem_handle; return node->payload; } -static void *cx_pll_iter_current(CxIterator const *iter) { +static void *cx_pll_iter_current(void const *it) { + struct cx_iterator_s const *iter = it; cx_linked_list_node *node = iter->elem_handle; return *(void **) node->payload; } +static bool cx_ll_iter_flag_rm(void *it) { + struct cx_iterator_base_s *iter = it; + if (iter->mutating) { + iter->remove = true; + return true; + } else { + return false; + } +} + static CxIterator cx_ll_iterator( - struct cx_list_s *list, + struct cx_list_s const *list, size_t index ) { CxIterator iter; iter.index = index; iter.src_handle = list; iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); - iter.valid = cx_ll_iter_valid; - iter.current = cx_ll_iter_current; - iter.next = cx_ll_iter_next; - iter.remove = false; + iter.base.valid = cx_ll_iter_valid; + iter.base.current = cx_ll_iter_current; + iter.base.next = cx_ll_iter_next; + iter.base.flag_removal = cx_ll_iter_flag_rm; + iter.base.mutating = false; + iter.base.remove = false; return iter; } static CxIterator cx_pll_iterator( + struct cx_list_s const *list, + size_t index +) { + CxIterator iter = cx_ll_iterator(list, index); + iter.base.current = cx_pll_iter_current; + return iter; +} + +static CxMutIterator cx_ll_mut_iterator( struct cx_list_s *list, size_t index ) { - CxIterator iter = cx_ll_iterator(list, index); - iter.current = cx_pll_iter_current; + CxIterator it = cx_ll_iterator(list, index); + it.base.mutating = true; + + // we know the iterators share the same memory layout + CxMutIterator iter; + memcpy(&iter, &it, sizeof(CxMutIterator)); + return iter; +} + +static CxMutIterator cx_pll_mut_iterator( + struct cx_list_s *list, + size_t index +) { + CxMutIterator iter = cx_ll_mut_iterator(list, index); + iter.base.current = cx_pll_iter_current; return iter; } static int cx_ll_insert_iter( - CxIterator *iter, + CxMutIterator *iter, void const *elem, int prepend ) { @@ -705,7 +759,7 @@ } static int cx_pll_insert_iter( - CxIterator *iter, + CxMutIterator *iter, void const *elem, int prepend ) { @@ -727,6 +781,7 @@ static cx_list_class cx_linked_list_class = { cx_ll_destructor, cx_ll_add, + cx_ll_add_array, cx_ll_insert, cx_ll_insert_iter, cx_ll_remove, @@ -735,12 +790,14 @@ cx_ll_sort, cx_ll_compare, cx_ll_reverse, - cx_ll_iterator + cx_ll_iterator, + cx_ll_mut_iterator, }; static cx_list_class cx_pointer_linked_list_class = { cx_ll_destructor, cx_pll_add, + cx_ll_add_array, cx_pll_insert, cx_pll_insert_iter, cx_ll_remove, @@ -750,6 +807,7 @@ cx_ll_compare, cx_ll_reverse, cx_pll_iterator, + cx_pll_mut_iterator, }; CxList *cxLinkedListCreate( @@ -786,22 +844,3 @@ return (CxList *) list; } - -CxList *cxLinkedListFromArray( - CxAllocator const *allocator, - CxListComparator comparator, - size_t item_size, - size_t num_items, - void const *array -) { - CxList *list = cxLinkedListCreate(allocator, comparator, item_size); - if (list == NULL) return NULL; - cx_for_n (i, num_items) { - if (0 != cxListAdd(list, ((const unsigned char *) array) + i * item_size)) { - cx_ll_destructor(list); - cxFree(allocator, list); - return NULL; - } - } - return list; -} diff -r 545010bc5e71 -r 22eca559aded src/ucx/list.c --- a/src/ucx/list.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/list.c Sat Nov 26 17:07:08 2022 +0100 @@ -51,3 +51,32 @@ list->cl->destructor(list); cxFree(list->allocator, list); } + +int cxListCompare( + CxList const *list, + CxList const *other +) { + if (list->cl->compare == other->cl->compare) { + // same compare function, lists are compatible + return list->cl->compare(list, other); + } else { + // different compare functions, use iterator + if (list->size == other->size) { + CxIterator left = cxListBegin(list); + CxIterator right = cxListBegin(other); + for (size_t i = 0; i < list->size; i++) { + void *leftValue = cxIteratorCurrent(left); + void *rightValue = cxIteratorCurrent(right); + int d = list->cmpfunc(leftValue, rightValue); + if (d != 0) { + return d; + } + cxIteratorNext(left); + cxIteratorNext(right); + } + return 0; + } else { + return list->size < other->size ? -1 : 1; + } + } +} diff -r 545010bc5e71 -r 22eca559aded src/ucx/string.c --- a/src/ucx/string.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/string.c Sat Nov 26 17:07:08 2022 +0100 @@ -35,9 +35,9 @@ #ifndef _WIN32 -#include /* for strncasecmp() */ +#include // for strncasecmp() -#endif /* _WIN32 */ +#endif // _WIN32 cxmutstr cx_mutstr(char *cstring) { return (cxmutstr) {cstring, strlen(cstring)}; @@ -236,7 +236,7 @@ return haystack; } - /* optimize for single-char needles */ + // optimize for single-char needles if (needle.length == 1) { return cx_strchr(haystack, *needle.ptr); } @@ -249,19 +249,19 @@ * and we want to avoid that. */ - /* local prefix table */ + // local prefix table size_t s_prefix_table[STRSTR_SBO_BUFLEN]; - /* check needle length and use appropriate prefix table */ - /* if the pattern exceeds static prefix table, allocate on the heap */ + // check needle length and use appropriate prefix table + // if the pattern exceeds static prefix table, allocate on the heap bool useheap = needle.length >= STRSTR_SBO_BUFLEN; register size_t *ptable = useheap ? calloc(needle.length + 1, sizeof(size_t)) : s_prefix_table; - /* keep counter in registers */ + // keep counter in registers register size_t i, j; - /* fill prefix table */ + // fill prefix table i = 0; j = 0; ptable[i] = j; @@ -274,7 +274,7 @@ ptable[i] = j; } - /* search */ + // search cxstring result = {NULL, 0}; i = 0; j = 1; @@ -292,7 +292,7 @@ } } - /* if prefix table was allocated on the heap, free it */ + // if prefix table was allocated on the heap, free it if (ptable != s_prefix_table) { free(ptable); } @@ -314,23 +314,24 @@ size_t limit, cxstring *output ) { - /* special case: output limit is zero */ + // special case: output limit is zero if (limit == 0) return 0; - /* special case: delimiter is empty */ + // special case: delimiter is empty if (delim.length == 0) { output[0] = string; return 1; } - /* special cases: delimiter is at least as large as the string */ + // special cases: delimiter is at least as large as the string if (delim.length >= string.length) { - /* exact match */ + // exact match if (cx_strcmp(string, delim) == 0) { output[0] = cx_strn(string.ptr, 0); output[1] = cx_strn(string.ptr + string.length, 0); return 2; - } else /* no match possible */ { + } else { + // no match possible output[0] = string; return 1; } @@ -342,21 +343,21 @@ ++n; cxstring match = cx_strstr(curpos, delim); if (match.length > 0) { - /* is the limit reached? */ + // is the limit reached? if (n < limit) { - /* copy the current string to the array */ + // copy the current string to the array cxstring item = cx_strn(curpos.ptr, match.ptr - curpos.ptr); output[n - 1] = item; size_t processed = item.length + delim.length; curpos.ptr += processed; curpos.length -= processed; } else { - /* limit reached, copy the _full_ remaining string */ + // limit reached, copy the _full_ remaining string output[n - 1] = curpos; break; } } else { - /* no more matches, copy last string */ + // no more matches, copy last string output[n - 1] = curpos; break; } @@ -372,24 +373,24 @@ size_t limit, cxstring **output ) { - /* find out how many splits we're going to make and allocate memory */ + // find out how many splits we're going to make and allocate memory size_t n = 0; cxstring curpos = string; while (1) { ++n; cxstring match = cx_strstr(curpos, delim); if (match.length > 0) { - /* is the limit reached? */ + // is the limit reached? if (n < limit) { size_t processed = match.ptr - curpos.ptr + delim.length; curpos.ptr += processed; curpos.length -= processed; } else { - /* limit reached */ + // limit reached break; } } else { - /* no more matches */ + // no more matches break; } } @@ -566,14 +567,14 @@ if (pattern.length == 0 || pattern.length > str.length || replmax == 0) return cx_strdup_a(allocator, str); - /* Compute expected buffer length */ + // Compute expected buffer length size_t ibufmax = str.length / pattern.length; size_t ibuflen = replmax < ibufmax ? replmax : ibufmax; if (ibuflen > REPLACE_INDEX_BUFFER_MAX) { ibuflen = REPLACE_INDEX_BUFFER_MAX; } - /* Allocate first index buffer */ + // Allocate first index buffer struct cx_strreplace_ibuf *firstbuf, *curbuf; firstbuf = curbuf = calloc(1, sizeof(struct cx_strreplace_ibuf)); if (!firstbuf) return cx_mutstrn(NULL, 0); @@ -583,13 +584,13 @@ return cx_mutstrn(NULL, 0); } - /* Search occurrences */ + // Search occurrences cxstring searchstr = str; size_t found = 0; do { cxstring match = cx_strstr(searchstr, pattern); if (match.length > 0) { - /* Allocate next buffer in chain, if required */ + // Allocate next buffer in chain, if required if (curbuf->len == ibuflen) { struct cx_strreplace_ibuf *nextbuf = calloc(1, sizeof(struct cx_strreplace_ibuf)); @@ -607,7 +608,7 @@ curbuf = nextbuf; } - /* Record match index */ + // Record match index found++; size_t idx = match.ptr - str.ptr; curbuf->buf[curbuf->len++] = idx; @@ -618,7 +619,7 @@ } } while (searchstr.length > 0 && found < replmax); - /* Allocate result string */ + // Allocate result string cxmutstr result; { ssize_t adjlen = (ssize_t) replacement.length - (ssize_t) pattern.length; @@ -636,13 +637,13 @@ } } - /* Build result string */ + // Build result string curbuf = firstbuf; size_t srcidx = 0; char *destptr = result.ptr; do { for (size_t i = 0; i < curbuf->len; i++) { - /* Copy source part up to next match*/ + // Copy source part up to next match size_t idx = curbuf->buf[i]; size_t srclen = idx - srcidx; if (srclen > 0) { @@ -651,7 +652,7 @@ srcidx += srclen; } - /* Copy the replacement and skip the source pattern */ + // Copy the replacement and skip the source pattern srcidx += pattern.length; memcpy(destptr, replacement.ptr, replacement.length); destptr += replacement.length; @@ -660,10 +661,10 @@ } while (curbuf); memcpy(destptr, str.ptr + srcidx, str.length - srcidx); - /* Result is guaranteed to be zero-terminated */ + // Result is guaranteed to be zero-terminated result.ptr[result.length] = '\0'; - /* Free index buffer */ + // Free index buffer cx_strrepl_free_ibuf(firstbuf); return result;