diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/.clang-tidy | 21 | ||||
-rw-r--r-- | src/collections.c | 52 | ||||
-rw-r--r-- | src/filesystem.c | 564 | ||||
-rw-r--r-- | src/filesystem.h | 182 | ||||
-rw-r--r-- | src/instance.c | 17 | ||||
-rw-r--r-- | src/lib.c | 17 | ||||
-rw-r--r-- | src/lilv_config.h | 115 | ||||
-rw-r--r-- | src/lilv_internal.h | 40 | ||||
-rw-r--r-- | src/node.c | 41 | ||||
-rw-r--r-- | src/plugin.c | 27 | ||||
-rw-r--r-- | src/pluginclass.c | 22 | ||||
-rw-r--r-- | src/port.c | 26 | ||||
-rw-r--r-- | src/query.c | 24 | ||||
-rw-r--r-- | src/scalepoint.c | 17 | ||||
-rw-r--r-- | src/state.c | 339 | ||||
-rw-r--r-- | src/ui.c | 17 | ||||
-rw-r--r-- | src/util.c | 53 | ||||
-rw-r--r-- | src/world.c | 86 | ||||
-rw-r--r-- | src/zix/common.h | 138 | ||||
-rw-r--r-- | src/zix/tree.c | 727 | ||||
-rw-r--r-- | src/zix/tree.h | 164 |
21 files changed, 369 insertions, 2320 deletions
diff --git a/src/.clang-tidy b/src/.clang-tidy new file mode 100644 index 0000000..0673649 --- /dev/null +++ b/src/.clang-tidy @@ -0,0 +1,21 @@ +# Copyright 2020-2022 David Robillard <d@drobilla.net> +# SPDX-License-Identifier: 0BSD OR ISC + +Checks: > + -*-magic-numbers, + -android-cloexec-fopen, + -bugprone-narrowing-conversions, + -cert-err33-c, + -cert-err34-c, + -clang-analyzer-security.insecureAPI.DeprecatedOrUnsafeBufferHandling, + -clang-analyzer-valist.Uninitialized, + -concurrency-mt-unsafe, + -cppcoreguidelines-narrowing-conversions, + -google-readability-todo, + -hicpp-multiway-paths-covered, + -hicpp-signed-bitwise, + -llvm-header-guard, + -performance-no-int-to-ptr, + -readability-function-cognitive-complexity, + -readability-suspicious-call-argument, +InheritParentConfig: true diff --git a/src/collections.c b/src/collections.c index c2c752a..a7b6923 100644 --- a/src/collections.c +++ b/src/collections.c @@ -1,36 +1,23 @@ -/* - Copyright 2008-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ +// Copyright 2008-2019 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC #include "lilv_internal.h" #include "lilv/lilv.h" #include "sord/sord.h" -#include "zix/common.h" #include "zix/tree.h" #include <stdbool.h> #include <stddef.h> -#include <stdint.h> + +typedef void (*LilvFreeFunc)(void* ptr); int lilv_ptr_cmp(const void* a, const void* b, const void* user_data) { (void)user_data; - return (intptr_t)a - (intptr_t)b; + return a < b ? -1 : b < a ? 1 : 0; } int @@ -41,18 +28,26 @@ lilv_resource_node_cmp(const void* a, const void* b, const void* user_data) const SordNode* an = ((const LilvNode*)a)->node; const SordNode* bn = ((const LilvNode*)b)->node; - return (intptr_t)an - (intptr_t)bn; + return an < bn ? -1 : bn < an ? 1 : 0; } /* Generic collection functions */ +static void +destroy(void* const ptr, const void* const user_data) +{ + if (user_data) { + ((LilvFreeFunc)user_data)(ptr); + } +} + static inline LilvCollection* -lilv_collection_new(ZixComparator cmp, ZixDestroyFunc destructor) +lilv_collection_new(ZixTreeCompareFunc cmp, LilvFreeFunc free_func) { - return zix_tree_new(false, cmp, NULL, destructor); + return zix_tree_new(NULL, false, cmp, NULL, destroy, (const void*)free_func); } -void +static void lilv_collection_free(LilvCollection* collection) { if (collection) { @@ -60,13 +55,13 @@ lilv_collection_free(LilvCollection* collection) } } -unsigned +static unsigned lilv_collection_size(const LilvCollection* collection) { return (collection ? zix_tree_size((const ZixTree*)collection) : 0); } -LilvIter* +static LilvIter* lilv_collection_begin(const LilvCollection* collection) { return collection ? (LilvIter*)zix_tree_begin((ZixTree*)collection) : NULL; @@ -85,28 +80,27 @@ lilv_collection_get(const LilvCollection* collection, const LilvIter* i) LilvScalePoints* lilv_scale_points_new(void) { - return lilv_collection_new(lilv_ptr_cmp, - (ZixDestroyFunc)lilv_scale_point_free); + return lilv_collection_new(lilv_ptr_cmp, (LilvFreeFunc)lilv_scale_point_free); } LilvNodes* lilv_nodes_new(void) { - return lilv_collection_new(lilv_ptr_cmp, (ZixDestroyFunc)lilv_node_free); + return lilv_collection_new(lilv_ptr_cmp, (LilvFreeFunc)lilv_node_free); } LilvUIs* lilv_uis_new(void) { return lilv_collection_new(lilv_header_compare_by_uri, - (ZixDestroyFunc)lilv_ui_free); + (LilvFreeFunc)lilv_ui_free); } LilvPluginClasses* lilv_plugin_classes_new(void) { return lilv_collection_new(lilv_header_compare_by_uri, - (ZixDestroyFunc)lilv_plugin_class_free); + (LilvFreeFunc)lilv_plugin_class_free); } /* URI based accessors (for collections of things with URIs) */ diff --git a/src/filesystem.c b/src/filesystem.c deleted file mode 100644 index 03614ce..0000000 --- a/src/filesystem.c +++ /dev/null @@ -1,564 +0,0 @@ -/* - Copyright 2007-2021 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#define _POSIX_C_SOURCE 200809L /* for fileno */ -#define _BSD_SOURCE 1 /* for realpath, symlink */ -#define _DEFAULT_SOURCE 1 /* for realpath, symlink */ - -#ifdef __APPLE__ -# define _DARWIN_C_SOURCE 1 /* for flock */ -#endif - -#include "filesystem.h" -#include "lilv_config.h" -#include "lilv_internal.h" - -#ifdef _WIN32 -# include <direct.h> -# include <io.h> -# include <windows.h> -# define F_OK 0 -# define mkdir(path, flags) _mkdir(path) -# define S_ISDIR(mode) (((mode)&S_IFMT) == S_IFDIR) -#else -# include <dirent.h> -# include <unistd.h> -#endif - -#if USE_FLOCK && USE_FILENO -# include <sys/file.h> -#endif - -#include <sys/stat.h> - -#include <errno.h> -#include <stdbool.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -#ifndef PAGE_SIZE -# define PAGE_SIZE 4096 -#endif - -static bool -lilv_is_dir_sep(const char c) -{ - return c == '/' || c == LILV_DIR_SEP[0]; -} - -#ifdef _WIN32 -static inline bool -is_windows_path(const char* path) -{ - return (isalpha(path[0]) && (path[1] == ':' || path[1] == '|') && - (path[2] == '/' || path[2] == '\\')); -} -#endif - -char* -lilv_temp_directory_path(void) -{ -#ifdef _WIN32 - DWORD len = GetTempPath(0, NULL); - char* buf = (char*)calloc(len, 1); - if (GetTempPath(len, buf) == 0) { - free(buf); - return NULL; - } - - return buf; -#else - const char* const tmpdir = getenv("TMPDIR"); - - return tmpdir ? lilv_strdup(tmpdir) : lilv_strdup("/tmp"); -#endif -} - -bool -lilv_path_is_absolute(const char* path) -{ - if (lilv_is_dir_sep(path[0])) { - return true; - } - -#ifdef _WIN32 - if (is_windows_path(path)) { - return true; - } -#endif - - return false; -} - -bool -lilv_path_is_child(const char* path, const char* dir) -{ - if (path && dir) { - const size_t path_len = strlen(path); - const size_t dir_len = strlen(dir); - return dir && path_len >= dir_len && !strncmp(path, dir, dir_len); - } - return false; -} - -char* -lilv_path_current(void) -{ - return getcwd(NULL, 0); -} - -char* -lilv_path_absolute(const char* path) -{ - if (lilv_path_is_absolute(path)) { - return lilv_strdup(path); - } - - char* cwd = getcwd(NULL, 0); - char* abs_path = lilv_path_join(cwd, path); - free(cwd); - return abs_path; -} - -char* -lilv_path_absolute_child(const char* path, const char* parent) -{ - if (lilv_path_is_absolute(path)) { - return lilv_strdup(path); - } - - return lilv_path_join(parent, path); -} - -char* -lilv_path_relative_to(const char* path, const char* base) -{ - const size_t path_len = strlen(path); - const size_t base_len = strlen(base); - const size_t min_len = (path_len < base_len) ? path_len : base_len; - - // Find the last separator common to both paths - size_t last_shared_sep = 0; - for (size_t i = 0; i < min_len && path[i] == base[i]; ++i) { - if (lilv_is_dir_sep(path[i])) { - last_shared_sep = i; - } - } - - if (last_shared_sep == 0) { - // No common components, return path - return lilv_strdup(path); - } - - // Find the number of up references ("..") required - size_t up = 0; - for (size_t i = last_shared_sep + 1; i < base_len; ++i) { - if (lilv_is_dir_sep(base[i])) { - ++up; - } - } - -#ifdef _WIN32 - const bool use_slash = strchr(path, '/'); -#else - static const bool use_slash = true; -#endif - - // Write up references - const size_t suffix_len = path_len - last_shared_sep; - char* rel = (char*)calloc(1, suffix_len + (up * 3) + 1); - for (size_t i = 0; i < up; ++i) { - if (use_slash) { - memcpy(rel + (i * 3), "../", 3); - } else { - memcpy(rel + (i * 3), "..\\", 3); - } - } - - // Write suffix - memcpy(rel + (up * 3), path + last_shared_sep + 1, suffix_len); - return rel; -} - -char* -lilv_path_parent(const char* path) -{ - const char* s = path + strlen(path) - 1; // Last character - - // Last non-slash - for (; s > path && lilv_is_dir_sep(*s); --s) { - } - - // Last internal slash - for (; s > path && !lilv_is_dir_sep(*s); --s) { - } - - // Skip duplicates - for (; s > path && lilv_is_dir_sep(*s); --s) { - } - - if (s == path) { // Hit beginning - return lilv_is_dir_sep(*s) ? lilv_strdup("/") : lilv_strdup("."); - } - - // Pointing to the last character of the result (inclusive) - char* dirname = (char*)malloc(s - path + 2); - memcpy(dirname, path, s - path + 1); - dirname[s - path + 1] = '\0'; - return dirname; -} - -char* -lilv_path_filename(const char* path) -{ - const size_t path_len = strlen(path); - size_t last_sep = path_len; - for (size_t i = 0; i < path_len; ++i) { - if (lilv_is_dir_sep(path[i])) { - last_sep = i; - } - } - - if (last_sep >= path_len) { - return lilv_strdup(path); - } - - const size_t ret_len = path_len - last_sep; - char* const ret = (char*)calloc(ret_len + 1, 1); - - strncpy(ret, path + last_sep + 1, ret_len); - return ret; -} - -char* -lilv_path_join(const char* a, const char* b) -{ - if (!a) { - return (b && b[0]) ? lilv_strdup(b) : NULL; - } - - const size_t a_len = strlen(a); - const size_t b_len = b ? strlen(b) : 0; - const bool a_end_is_sep = a_len > 0 && lilv_is_dir_sep(a[a_len - 1]); - const size_t pre_len = a_len - (a_end_is_sep ? 1 : 0); - char* path = (char*)calloc(1, a_len + b_len + 2); - memcpy(path, a, pre_len); - -#ifdef _WIN32 - // Use forward slash if it seems that the input paths do - const bool a_has_slash = strchr(a, '/'); - const bool b_has_slash = b && strchr(b, '/'); - if (a_has_slash || b_has_slash) { - path[pre_len] = '/'; - } else { - path[pre_len] = '\\'; - } -#else - path[pre_len] = '/'; -#endif - - if (b) { - memcpy(path + pre_len + 1, - b + (lilv_is_dir_sep(b[0]) ? 1 : 0), - lilv_is_dir_sep(b[0]) ? b_len - 1 : b_len); - } - return path; -} - -char* -lilv_path_canonical(const char* path) -{ - if (!path) { - return NULL; - } - -#if defined(_WIN32) - char* out = (char*)malloc(MAX_PATH); - GetFullPathName(path, MAX_PATH, out, NULL); - return out; -#else - char* real_path = realpath(path, NULL); - return real_path ? real_path : lilv_strdup(path); -#endif -} - -bool -lilv_path_exists(const char* path) -{ -#if USE_LSTAT - struct stat st; - return !lstat(path, &st); -#else - return !access(path, F_OK); -#endif -} - -bool -lilv_is_directory(const char* path) -{ - struct stat st; - return !stat(path, &st) && S_ISDIR(st.st_mode); -} - -int -lilv_copy_file(const char* src, const char* dst) -{ - FILE* in = fopen(src, "r"); - if (!in) { - return errno; - } - - FILE* out = fopen(dst, "w"); - if (!out) { - fclose(in); - return errno; - } - - char* page = (char*)malloc(PAGE_SIZE); - size_t n_read = 0; - int st = 0; - while ((n_read = fread(page, 1, PAGE_SIZE, in)) > 0) { - if (fwrite(page, 1, n_read, out) != n_read) { - st = errno; - break; - } - } - - if (!st && fflush(out)) { - st = errno; - } - - if (!st && (ferror(in) || ferror(out))) { - st = EBADF; - } - - free(page); - fclose(in); - fclose(out); - - return st; -} - -int -lilv_symlink(const char* oldpath, const char* newpath) -{ - int ret = 0; - if (strcmp(oldpath, newpath)) { -#ifdef _WIN32 - ret = !CreateHardLink(newpath, oldpath, 0); -#else - char* target = lilv_path_relative_to(oldpath, newpath); - - ret = symlink(target, newpath); - - free(target); -#endif - } - return ret; -} - -int -lilv_flock(FILE* file, bool lock, bool block) -{ -#ifdef _WIN32 - HANDLE handle = (HANDLE)_get_osfhandle(fileno(file)); - OVERLAPPED overlapped = {0}; - - if (lock) { - const DWORD flags = - (LOCKFILE_EXCLUSIVE_LOCK | (block ? 0 : LOCKFILE_FAIL_IMMEDIATELY)); - - return !LockFileEx(handle, flags, 0, UINT32_MAX, UINT32_MAX, &overlapped); - } else { - return !UnlockFileEx(handle, 0, UINT32_MAX, UINT32_MAX, &overlapped); - } -#elif USE_FLOCK && USE_FILENO - return flock(fileno(file), - (lock ? LOCK_EX : LOCK_UN) | (block ? 0 : LOCK_NB)); -#else - return 0; -#endif -} - -void -lilv_dir_for_each(const char* path, - void* data, - void (*f)(const char* path, const char* name, void* data)) -{ -#ifdef _WIN32 - char* pat = lilv_path_join(path, "*"); - WIN32_FIND_DATA fd; - HANDLE fh = FindFirstFile(pat, &fd); - if (fh != INVALID_HANDLE_VALUE) { - do { - if (strcmp(fd.cFileName, ".") && strcmp(fd.cFileName, "..")) { - f(path, fd.cFileName, data); - } - } while (FindNextFile(fh, &fd)); - } - FindClose(fh); - free(pat); -#else - DIR* dir = opendir(path); - if (dir) { - for (struct dirent* entry = NULL; (entry = readdir(dir));) { - if (strcmp(entry->d_name, ".") && strcmp(entry->d_name, "..")) { - f(path, entry->d_name, data); - } - } - closedir(dir); - } -#endif -} - -char* -lilv_create_temporary_directory_in(const char* pattern, const char* parent) -{ -#ifdef _WIN32 - static const char chars[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; - static const int n_chars = sizeof(chars) - 1; - - const size_t pattern_len = strlen(pattern); - if (pattern_len < 7 || strcmp(pattern + pattern_len - 6, "XXXXXX")) { - errno = EINVAL; - return NULL; - } - - char* const path_pattern = lilv_path_join(parent, pattern); - const size_t path_pattern_len = strlen(path_pattern); - char* const suffix = path_pattern + path_pattern_len - 6; - - for (unsigned attempt = 0; attempt < 128; ++attempt) { - for (unsigned i = 0; i < 6; ++i) { - suffix[i] = chars[rand() % n_chars]; - } - - if (!mkdir(path_pattern, 0700)) { - return path_pattern; - } - } - - return NULL; -#else - char* const path_pattern = lilv_path_join(parent, pattern); - - return mkdtemp(path_pattern); // NOLINT (not a leak) -#endif -} - -char* -lilv_create_temporary_directory(const char* pattern) -{ - char* const tmpdir = lilv_temp_directory_path(); - char* const result = lilv_create_temporary_directory_in(pattern, tmpdir); - - free(tmpdir); - - return result; -} - -int -lilv_create_directories(const char* dir_path) -{ - char* path = lilv_strdup(dir_path); - const size_t path_len = strlen(path); - size_t i = 1; - -#ifdef _WIN32 - if (is_windows_path(dir_path)) { - i = 3; - } -#endif - - for (; i <= path_len; ++i) { - const char c = path[i]; - if (c == LILV_DIR_SEP[0] || c == '/' || c == '\0') { - path[i] = '\0'; - if (mkdir(path, 0755) && (errno != EEXIST || !lilv_is_directory(path))) { - free(path); - return errno; - } - path[i] = c; - } - } - - free(path); - return 0; -} - -static off_t -lilv_file_size(const char* path) -{ - struct stat buf; - if (stat(path, &buf)) { - return 0; - } - return buf.st_size; -} - -int -lilv_remove(const char* path) -{ -#ifdef _WIN32 - if (lilv_is_directory(path)) { - return !RemoveDirectory(path); - } -#endif - - return remove(path); -} - -bool -lilv_file_equals(const char* a_path, const char* b_path) -{ - if (!strcmp(a_path, b_path)) { - return true; // Paths match - } - - bool match = false; - FILE* a_file = NULL; - FILE* b_file = NULL; - char* const a_real = lilv_path_canonical(a_path); - char* const b_real = lilv_path_canonical(b_path); - if (!strcmp(a_real, b_real)) { - match = true; // Real paths match - } else if (lilv_file_size(a_path) != lilv_file_size(b_path)) { - match = false; // Sizes differ - } else if (!(a_file = fopen(a_real, "rb")) || - !(b_file = fopen(b_real, "rb"))) { - match = false; // Missing file matches nothing - } else { - // TODO: Improve performance by reading chunks - match = true; - while (!feof(a_file) && !feof(b_file)) { - if (fgetc(a_file) != fgetc(b_file)) { - match = false; - break; - } - } - } - - if (a_file) { - fclose(a_file); - } - if (b_file) { - fclose(b_file); - } - free(a_real); - free(b_real); - return match; -} diff --git a/src/filesystem.h b/src/filesystem.h deleted file mode 100644 index 1a8dc68..0000000 --- a/src/filesystem.h +++ /dev/null @@ -1,182 +0,0 @@ -/* - Copyright 2007-2020 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#include <stdbool.h> -#include <stdio.h> - -/// Return the path to a directory suitable for making temporary files -char* -lilv_temp_directory_path(void); - -/// Return true iff `path` is an absolute path -bool -lilv_path_is_absolute(const char* path); - -/// Return true iff `path` is a child of `dir` -bool -lilv_path_is_child(const char* path, const char* dir); - -/// Return the current working directory -char* -lilv_path_current(void); - -/** - Return `path` as an absolute path. - - If `path` is absolute, an identical copy of it is returned. Otherwise, the - returned path is relative to the current working directory. -*/ -char* -lilv_path_absolute(const char* path); - -/** - Return `path` as an absolute path relative to `parent`. - - If `path` is absolute, an identical copy of it is returned. Otherwise, the - returned path is relative to `parent`. -*/ -char* -lilv_path_absolute_child(const char* path, const char* parent); - -/** - Return `path` relative to `base` if possible. - - If `path` is not within `base`, a copy is returned. Otherwise, an - equivalent path relative to `base` is returned (which may contain - up-references). -*/ -char* -lilv_path_relative_to(const char* path, const char* base); - -/** - Return the path to the directory that contains `path`. - - Returns the root path if `path` is the root path. -*/ -char* -lilv_path_parent(const char* path); - -/** - Return the filename component of `path` without any directories. - - Returns the empty string if `path` is the root path. -*/ -char* -lilv_path_filename(const char* path); - -/// Join path `a` and path `b` with a single directory separator between them -char* -lilv_path_join(const char* a, const char* b); - -/** - Return `path` as a canonicalized absolute path. - - This expands all symbolic links, relative references, and removes extra - directory separators. -*/ -char* -lilv_path_canonical(const char* path); - -/// Return true iff `path` points to an existing file system entry -bool -lilv_path_exists(const char* path); - -/// Return true iff `path` points to an existing directory -bool -lilv_is_directory(const char* path); - -/** - Copy the file at path `src` to path `dst`. - - @return Zero on success, or a standard `errno` error code. -*/ -int -lilv_copy_file(const char* src, const char* dst); - -/** - Create a symlink at `newpath` that points to `oldpath`. - - @return Zero on success, otherwise non-zero and `errno` is set. -*/ -int -lilv_symlink(const char* oldpath, const char* newpath); - -/** - Set or remove an advisory exclusive lock on `file`. - - If the `lock` is true and the file is already locked by another process, or - by this process via a different file handle, then this will not succeed and - non-zero will be returned. - - @param file Handle for open file to lock. - @param lock True to set lock, false to release lock. - @param block If true, then this call will block until the lock is acquired. - @return Zero on success. -*/ -int -lilv_flock(FILE* file, bool lock, bool block); - -/** - Visit every file in the directory at `path`. - - @param path A path to a directory. - - @param data Opaque user data that is passed to `f`. - - @param f A function called on every entry in the directory. The `path` - parameter is always the directory path passed to this function, the `name` - parameter is the name of the directory entry (not its full path). -*/ -void -lilv_dir_for_each(const char* path, - void* data, - void (*f)(const char* path, const char* name, void* data)); - -/** - Create a unique temporary directory in a specific directory. - - The last six characters of `pattern` must be `XXXXXX` and will be replaced - with random characters. This works roughly like mkdtemp, except the pattern - should only be a directory name, not a full path. The created path will be - a child of the given parent directory. -*/ -char* -lilv_create_temporary_directory_in(const char* pattern, const char* parent); - -/** - Create a unique temporary directory. - - This is like lilv_create_temporary_directory_in(), except it creates the - directory in the system temporary directory. -*/ -char* -lilv_create_temporary_directory(const char* pattern); - -/** - Create the directory `dir_path` and any parent directories if necessary. - - @return Zero on success, or an `errno` error code. -*/ -int -lilv_create_directories(const char* dir_path); - -/// Remove the file or empty directory at `path` -int -lilv_remove(const char* path); - -/// Return true iff the given paths point to files with identical contents -bool -lilv_file_equals(const char* a_path, const char* b_path); diff --git a/src/instance.c b/src/instance.c index 6a2b856..379fe24 100644 --- a/src/instance.c +++ b/src/instance.c @@ -1,18 +1,5 @@ -/* - Copyright 2007-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ +// Copyright 2007-2019 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC #include "lilv_internal.h" @@ -1,18 +1,5 @@ -/* - Copyright 2012-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ +// Copyright 2012-2019 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC #include "lilv_internal.h" diff --git a/src/lilv_config.h b/src/lilv_config.h index 10231c5..2f7c498 100644 --- a/src/lilv_config.h +++ b/src/lilv_config.h @@ -1,102 +1,11 @@ -/* - Copyright 2021 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -/* - Configuration header that defines reasonable defaults at compile time. - - This allows compile-time configuration from the command line (typically via - the build system) while still allowing the source to be built without any - configuration. The build system can define LILV_NO_DEFAULT_CONFIG to disable - defaults, in which case it must define things like HAVE_FEATURE to enable - features. The design here ensures that compiler warnings or - include-what-you-use will catch any mistakes. -*/ +// Copyright 2021-2024 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC #ifndef LILV_CONFIG_H #define LILV_CONFIG_H // Define version unconditionally so a warning will catch a mismatch -#define LILV_VERSION "0.24.13" - -#if !defined(LILV_NO_DEFAULT_CONFIG) - -// We need unistd.h to check _POSIX_VERSION -# ifndef LILV_NO_POSIX -# ifdef __has_include -# if __has_include(<unistd.h>) -# include <unistd.h> -# endif -# elif defined(__unix__) -# include <unistd.h> -# endif -# endif - -// POSIX.1-2001: fileno() -# ifndef HAVE_FILENO -# if defined(_POSIX_VERSION) && _POSIX_VERSION >= 200112L -# define HAVE_FILENO -# endif -# endif - -// Classic UNIX: flock() -# ifndef HAVE_FLOCK -# if defined(__unix__) -# define HAVE_FLOCK -# endif -# endif - -// POSIX.1-2001: lstat() -# ifndef HAVE_LSTAT -# if defined(_POSIX_VERSION) && _POSIX_VERSION >= 200112L -# define HAVE_LSTAT -# endif -# endif - -#endif // !defined(LILV_NO_DEFAULT_CONFIG) - -/* - Make corresponding USE_FEATURE defines based on the HAVE_FEATURE defines from - above or the command line. The code checks for these using #if (not #ifdef), - so there will be an undefined warning if it checks for an unknown feature, - and this header is always required by any code that checks for features, even - if the build system defines them all. -*/ - -#ifdef HAVE_FILENO -# define USE_FILENO 1 -#else -# define USE_FILENO 0 -#endif - -#ifdef HAVE_FLOCK -# define USE_FLOCK 1 -#else -# define USE_FLOCK 0 -#endif - -#ifdef HAVE_LSTAT -# define USE_LSTAT 1 -#else -# define USE_LSTAT 0 -#endif - -/* - Define required values. These are always used as a fallback, even with - LILV_NO_DEFAULT_CONFIG, since they must be defined for the build to work. -*/ +#define LILV_VERSION "0.24.25" // Separator between entries in variables like PATH #ifndef LILV_PATH_SEP @@ -107,21 +16,17 @@ # endif #endif -// Separator between directories in a path -#ifndef LILV_DIR_SEP -# ifdef _WIN32 -# define LILV_DIR_SEP "\\" -# else -# define LILV_DIR_SEP "/" -# endif -#endif - // Default value for LV2_PATH environment variable #ifndef LILV_DEFAULT_LV2_PATH -# ifdef _WIN32 +# if defined(__APPLE__) +# define LILV_DEFAULT_LV2_PATH \ + "~/.lv2:~/Library/Audio/Plug-Ins/LV2:" \ + "/usr/local/lib/lv2:/usr/lib/lv2:" \ + "/Library/Audio/Plug-Ins/LV2" +# elif defined(_WIN32) # define LILV_DEFAULT_LV2_PATH "%APPDATA%\\LV2;%COMMONPROGRAMFILES%\\LV2" # else -# define LILV_DEFAULT_LV2_PATH "~/.lv2:/usr/lib/lv2:/usr/local/lib/lv2" +# define LILV_DEFAULT_LV2_PATH "~/.lv2:/usr/local/lib/lv2:/usr/lib/lv2" # endif #endif diff --git a/src/lilv_internal.h b/src/lilv_internal.h index 12b56de..f1bca25 100644 --- a/src/lilv_internal.h +++ b/src/lilv_internal.h @@ -1,18 +1,5 @@ -/* - Copyright 2007-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ +// Copyright 2007-2019 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC #ifndef LILV_INTERNAL_H #define LILV_INTERNAL_H @@ -35,22 +22,14 @@ extern "C" { #ifdef _WIN32 # include <direct.h> -# include <stdio.h> # include <windows.h> # define dlopen(path, flags) LoadLibrary(path) # define dlclose(lib) FreeLibrary((HMODULE)lib) # ifdef _MSC_VER -# define __func__ __FUNCTION__ # ifndef snprintf # define snprintf _snprintf # endif # endif -# ifndef INFINITY -# define INFINITY DBL_MAX + DBL_MAX -# endif -# ifndef NAN -# define NAN INFINITY - INFINITY -# endif static inline const char* dlerror(void) { @@ -275,15 +254,6 @@ lilv_plugin_get_unique(const LilvPlugin* plugin, const SordNode* subject, const SordNode* predicate); -void -lilv_collection_free(LilvCollection* collection); - -unsigned -lilv_collection_size(const LilvCollection* collection); - -LilvIter* -lilv_collection_begin(const LilvCollection* collection); - void* lilv_collection_get(const LilvCollection* collection, const LilvIter* i); @@ -332,9 +302,6 @@ lilv_world_blank_node_prefix(LilvWorld* world); SerdStatus lilv_world_load_file(LilvWorld* world, SerdReader* reader, const LilvNode* uri); -SerdStatus -lilv_world_load_graph(LilvWorld* world, SordNode* graph, const LilvNode* uri); - LilvUI* lilv_ui_new(LilvWorld* world, LilvNode* uri, @@ -354,9 +321,6 @@ int lilv_header_compare_by_uri(const void* a, const void* b, const void* user_data); int -lilv_lib_compare(const void* a, const void* b, const void* user_data); - -int lilv_ptr_cmp(const void* a, const void* b, const void* user_data); int @@ -1,25 +1,14 @@ -/* - Copyright 2007-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#include "filesystem.h" +// Copyright 2007-2019 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC + #include "lilv_internal.h" #include "lilv/lilv.h" #include "serd/serd.h" #include "sord/sord.h" +#include "zix/allocator.h" +#include "zix/filesystem.h" +#include "zix/path.h" #include <math.h> #include <stdbool.h> @@ -160,13 +149,23 @@ lilv_new_uri(LilvWorld* world, const char* uri) LilvNode* lilv_new_file_uri(LilvWorld* world, const char* host, const char* path) { - char* abs_path = lilv_path_absolute(path); - SerdNode s = serd_node_new_file_uri( - (const uint8_t*)abs_path, (const uint8_t*)host, NULL, true); + SerdNode s = SERD_NODE_NULL; + if (zix_path_root_directory(path).length) { + s = serd_node_new_file_uri( + (const uint8_t*)path, (const uint8_t*)host, NULL, true); + } else { + char* const cwd = zix_current_path(NULL); + char* const abs_path = zix_path_join(NULL, cwd, path); + + s = serd_node_new_file_uri( + (const uint8_t*)abs_path, (const uint8_t*)host, NULL, true); + + zix_free(NULL, abs_path); + zix_free(NULL, cwd); + } LilvNode* ret = lilv_node_new(world, LILV_VALUE_URI, (const char*)s.buf); serd_node_free(&s); - free(abs_path); return ret; } diff --git a/src/plugin.c b/src/plugin.c index 9c7cbfd..f191eda 100644 --- a/src/plugin.c +++ b/src/plugin.c @@ -1,18 +1,5 @@ -/* - Copyright 2007-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ +// Copyright 2007-2019 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC #include "lilv_internal.h" @@ -580,9 +567,11 @@ lilv_plugin_get_port_ranges_float(const LilvPlugin* plugin, } uint32_t -lilv_plugin_get_num_ports_of_class_va(const LilvPlugin* plugin, - const LilvNode* class_1, - va_list args) +lilv_plugin_get_num_ports_of_class_va( + const LilvPlugin* plugin, + const LilvNode* class_1, + va_list args // NOLINT(readability-non-const-parameter) +) { lilv_plugin_load_ports_if_necessary(plugin); @@ -624,7 +613,7 @@ lilv_plugin_get_num_ports_of_class(const LilvPlugin* plugin, const LilvNode* class_1, ...) { - va_list args; + va_list args; // NOLINT(cppcoreguidelines-init-variables) va_start(args, class_1); uint32_t count = lilv_plugin_get_num_ports_of_class_va(plugin, class_1, args); diff --git a/src/pluginclass.c b/src/pluginclass.c index 2f0afe7..18109f3 100644 --- a/src/pluginclass.c +++ b/src/pluginclass.c @@ -1,18 +1,5 @@ -/* - Copyright 2007-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ +// Copyright 2007-2019 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC #include "lilv_internal.h" @@ -73,8 +60,9 @@ LilvPluginClasses* lilv_plugin_class_get_children(const LilvPluginClass* plugin_class) { // Returned list doesn't own categories - LilvPluginClasses* all = plugin_class->world->plugin_classes; - LilvPluginClasses* result = zix_tree_new(false, lilv_ptr_cmp, NULL, NULL); + LilvPluginClasses* all = plugin_class->world->plugin_classes; + LilvPluginClasses* result = + zix_tree_new(NULL, false, lilv_header_compare_by_uri, NULL, NULL, NULL); for (ZixTreeIter* i = zix_tree_begin((ZixTree*)all); i != zix_tree_end((ZixTree*)all); @@ -1,18 +1,5 @@ -/* - Copyright 2007-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ +// Copyright 2007-2019 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC #include "lilv_internal.h" @@ -237,11 +224,12 @@ lilv_port_get_scale_points(const LilvPlugin* plugin, const LilvPort* port) sord_new_uri(plugin->world->world, (const uint8_t*)LV2_CORE__scalePoint), NULL); - LilvScalePoints* ret = NULL; - if (!sord_iter_end(points)) { - ret = lilv_scale_points_new(); + if (sord_iter_end(points)) { + return NULL; } + LilvScalePoints* ret = lilv_scale_points_new(); + FOREACH_MATCH (points) { const SordNode* point = sord_iter_get_node(points, SORD_OBJECT); @@ -257,7 +245,7 @@ lilv_port_get_scale_points(const LilvPlugin* plugin, const LilvPort* port) } sord_iter_free(points); - assert(!ret || lilv_nodes_size(ret) > 0); + assert(lilv_nodes_size(ret) > 0); return ret; } diff --git a/src/query.c b/src/query.c index eb179f2..3dd8eca 100644 --- a/src/query.c +++ b/src/query.c @@ -1,18 +1,5 @@ -/* - Copyright 2007-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ +// Copyright 2007-2019 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC #include "lilv_internal.h" @@ -96,12 +83,7 @@ lilv_nodes_from_stream_objects_i18n(LilvWorld* world, } const SordNode* best = nolang; - if (syslang && partial) { - // Partial language match for system language - best = partial; - } else if (!best) { - // No languages matches at all, and no untranslated value - // Use any value, if possible + if ((syslang && partial) || !best) { best = partial; } diff --git a/src/scalepoint.c b/src/scalepoint.c index e2db948..60cc905 100644 --- a/src/scalepoint.c +++ b/src/scalepoint.c @@ -1,18 +1,5 @@ -/* - Copyright 2007-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ +// Copyright 2007-2019 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC #include "lilv_internal.h" diff --git a/src/state.c b/src/state.c index a4a50a9..0ed5715 100644 --- a/src/state.c +++ b/src/state.c @@ -1,26 +1,17 @@ -/* - Copyright 2007-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#include "filesystem.h" +// Copyright 2007-2022 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC + #include "lilv_internal.h" #include "lilv/lilv.h" #include "serd/serd.h" #include "sord/sord.h" #include "sratom/sratom.h" +#include "zix/allocator.h" +#include "zix/filesystem.h" +#include "zix/path.h" +#include "zix/status.h" +#include "zix/string_view.h" #include "zix/tree.h" #include "lv2/atom/atom.h" @@ -120,8 +111,9 @@ value_cmp(const void* a, const void* b) } static void -path_rel_free(void* ptr) +map_free(void* ptr, const void* user_data) { + (void)user_data; free(((PathMap*)ptr)->abs); free(((PathMap*)ptr)->rel); free(ptr); @@ -234,9 +226,15 @@ retrieve_callback(LV2_State_Handle handle, const Property* const prop = find_property((const LilvState*)handle, key); if (prop) { - *size = prop->size; - *type = prop->type; - *flags = prop->flags; + if (size) { + *size = prop->size; + } + if (type) { + *type = prop->type; + } + if (flags) { + *flags = prop->flags; + } return prop->value; } return NULL; @@ -247,7 +245,7 @@ path_exists(const char* path, const void* ignored) { (void)ignored; - return lilv_path_exists(path); + return zix_file_type(path) != ZIX_FILE_TYPE_NONE; } static bool @@ -260,19 +258,34 @@ static char* make_path(LV2_State_Make_Path_Handle handle, const char* path) { LilvState* state = (LilvState*)handle; - lilv_create_directories(state->dir); + zix_create_directories(NULL, state->dir); - return lilv_path_join(state->dir, path); + return zix_path_join(NULL, state->dir, path); +} + +static bool +path_is_child(const char* path, const char* dir) +{ + if (path && dir) { + const size_t path_len = strlen(path); + const size_t dir_len = strlen(dir); + return dir && path_len >= dir_len && !strncmp(path, dir, dir_len); + } + return false; } static char* abstract_path(LV2_State_Map_Path_Handle handle, const char* abs_path) { - LilvState* state = (LilvState*)handle; - char* path = NULL; - char* real_path = lilv_path_canonical(abs_path); - const PathMap key = {real_path, NULL}; - ZixTreeIter* iter = NULL; + LilvState* state = (LilvState*)handle; + char* path = NULL; + char* real_path = zix_canonical_path(NULL, abs_path); + if (!real_path) { + real_path = zix_path_lexically_normal(NULL, abs_path); + } + + const PathMap key = {real_path, NULL}; + ZixTreeIter* iter = NULL; if (abs_path[0] == '\0') { return lilv_strdup(abs_path); @@ -281,47 +294,47 @@ abstract_path(LV2_State_Map_Path_Handle handle, const char* abs_path) if (!zix_tree_find(state->abs2rel, &key, &iter)) { // Already mapped path in a previous call PathMap* pm = (PathMap*)zix_tree_get(iter); - free(real_path); + zix_free(NULL, real_path); return lilv_strdup(pm->rel); } - if (lilv_path_is_child(real_path, state->dir)) { + if (path_is_child(real_path, state->dir)) { // File in state directory (loaded, or created by plugin during save) - path = lilv_path_relative_to(real_path, state->dir); - } else if (lilv_path_is_child(real_path, state->scratch_dir)) { + path = zix_path_lexically_relative(NULL, real_path, state->dir); + } else if (path_is_child(real_path, state->scratch_dir)) { // File created by plugin earlier - path = lilv_path_relative_to(real_path, state->scratch_dir); + path = zix_path_lexically_relative(NULL, real_path, state->scratch_dir); if (state->copy_dir) { - int st = lilv_create_directories(state->copy_dir); + ZixStatus st = zix_create_directories(NULL, state->copy_dir); if (st) { - LILV_ERRORF( - "Error creating directory %s (%s)\n", state->copy_dir, strerror(st)); + LILV_ERRORF("Error creating directory %s (%s)\n", + state->copy_dir, + zix_strerror(st)); } - char* cpath = lilv_path_join(state->copy_dir, path); + char* cpath = zix_path_join(NULL, state->copy_dir, path); char* copy = lilv_get_latest_copy(real_path, cpath); - if (!copy || !lilv_file_equals(real_path, copy)) { + if (!copy || !zix_file_equals(NULL, real_path, copy)) { // No recent enough copy, make a new one free(copy); copy = lilv_find_free_path(cpath, path_exists, NULL); - if ((st = lilv_copy_file(real_path, copy))) { - LILV_ERRORF("Error copying state file %s (%s)\n", copy, strerror(st)); + if ((st = zix_copy_file(NULL, real_path, copy, 0U))) { + LILV_ERRORF( + "Error copying state file %s (%s)\n", copy, zix_strerror(st)); } } - free(real_path); - free(cpath); + zix_free(NULL, real_path); + zix_free(NULL, cpath); // Refer to the latest copy in plugin state real_path = copy; } } else if (state->link_dir) { // New path outside state directory, make a link - char* const name = lilv_path_filename(real_path); + const ZixStringView name = zix_path_filename(real_path); // Find a free name in the (virtual) state directory - path = lilv_find_free_path(name, lilv_state_has_path, state); - - free(name); + path = lilv_find_free_path(name.data, lilv_state_has_path, state); } else { // No link directory, preserve absolute path path = lilv_strdup(abs_path); @@ -342,12 +355,12 @@ absolute_path(LV2_State_Map_Path_Handle handle, const char* state_path) { LilvState* state = (LilvState*)handle; char* path = NULL; - if (lilv_path_is_absolute(state_path)) { + if (zix_path_is_absolute(state_path)) { // Absolute path, return identical path path = lilv_strdup(state_path); } else if (state->dir) { // Relative path inside state directory - path = lilv_path_join(state->dir, state_path); + path = zix_path_join(NULL, state->dir, state_path); } else { // State has not been saved, unmap path = lilv_strdup(lilv_state_rel2abs(state, state_path)); @@ -365,6 +378,15 @@ add_features(const LV2_Feature* const* features, { size_t n_features = 0; for (; features && features[n_features]; ++n_features) { + if (!strcmp(features[n_features]->URI, LV2_STATE__mapPath)) { + map = NULL; + } + if (!strcmp(features[n_features]->URI, LV2_STATE__makePath)) { + make = NULL; + } + if (!strcmp(features[n_features]->URI, LV2_STATE__freePath)) { + free = NULL; + } } const LV2_Feature** ret = @@ -388,14 +410,15 @@ add_features(const LV2_Feature* const* features, return ret; } -/// Return the canonical path for a directory with a trailing separator +/// Return a normal path for a directory with a trailing separator static char* -real_dir(const char* path) +normal_dir(const char* path) { - char* abs_path = lilv_path_canonical(path); - char* base = lilv_path_join(abs_path, NULL); - free(abs_path); - return base; + char* const normal_path = zix_path_lexically_normal(NULL, path); + char* const base_path = zix_path_join(NULL, normal_path, NULL); + + zix_free(NULL, normal_path); + return base_path; } static const char* @@ -442,12 +465,12 @@ lilv_state_new_from_instance(const LilvPlugin* plugin, LilvWorld* const world = plugin->world; LilvState* const state = (LilvState*)calloc(1, sizeof(LilvState)); state->plugin_uri = lilv_node_duplicate(lilv_plugin_get_uri(plugin)); - state->abs2rel = zix_tree_new(false, abs_cmp, NULL, path_rel_free); - state->rel2abs = zix_tree_new(false, rel_cmp, NULL, NULL); - state->scratch_dir = scratch_dir ? real_dir(scratch_dir) : NULL; - state->copy_dir = copy_dir ? real_dir(copy_dir) : NULL; - state->link_dir = link_dir ? real_dir(link_dir) : NULL; - state->dir = save_dir ? real_dir(save_dir) : NULL; + state->abs2rel = zix_tree_new(NULL, false, abs_cmp, NULL, map_free, NULL); + state->rel2abs = zix_tree_new(NULL, false, rel_cmp, NULL, NULL, NULL); + state->scratch_dir = scratch_dir ? normal_dir(scratch_dir) : NULL; + state->copy_dir = copy_dir ? normal_dir(copy_dir) : NULL; + state->link_dir = link_dir ? normal_dir(link_dir) : NULL; + state->dir = save_dir ? normal_dir(save_dir) : NULL; state->atom_Path = map->map(map->handle, LV2_ATOM__Path); LV2_State_Map_Path pmap = {state, abstract_path, absolute_path}; @@ -571,10 +594,10 @@ set_state_dir_from_model(LilvState* state, const SordNode* graph) const char* uri = (const char*)sord_node_get_string(graph); char* path = lilv_file_uri_parse(uri, NULL); - state->dir = lilv_path_join(path, NULL); + state->dir = zix_path_join(NULL, path, NULL); free(path); } - assert(!state->dir || lilv_path_is_absolute(state->dir)); + assert(!state->dir || zix_path_is_absolute(state->dir)); } static LilvState* @@ -591,7 +614,7 @@ new_state_from_model(LilvWorld* world, // Allocate state LilvState* const state = (LilvState*)calloc(1, sizeof(LilvState)); - state->dir = lilv_path_join(dir, NULL); + state->dir = dir ? zix_path_join(NULL, dir, NULL) : NULL; state->atom_Path = map->map(map->handle, LV2_ATOM__Path); state->uri = lilv_node_new_from_node(world, node); @@ -742,29 +765,34 @@ lilv_state_new_from_file(LilvWorld* world, return NULL; } - uint8_t* abs_path = (uint8_t*)lilv_path_absolute(path); - SerdNode node = serd_node_new_file_uri(abs_path, NULL, NULL, true); - SerdEnv* env = serd_env_new(&node); - SordModel* model = sord_new(world->world, SORD_SPO, false); - SerdReader* reader = sord_new_reader(model, env, SERD_TURTLE, NULL); + uint8_t* const abs_path = (uint8_t*)zix_canonical_path(NULL, path); + if (!abs_path) { + return NULL; + } + + SerdNode node = serd_node_new_file_uri(abs_path, NULL, NULL, true); + SerdEnv* env = serd_env_new(&node); + SordModel* model = sord_new(world->world, SORD_SPO, false); + SerdReader* reader = sord_new_reader(model, env, SERD_TURTLE, NULL); - serd_reader_read_file(reader, node.buf); + serd_reader_read_file(reader, (const uint8_t*)node.buf); SordNode* subject_node = (subject) ? subject->node : sord_node_from_serd_node(world->world, env, &node, NULL, NULL); - char* dirname = lilv_path_parent(path); - char* real_path = lilv_path_canonical(dirname); - char* dir_path = lilv_path_join(real_path, NULL); - LilvState* state = + const ZixStringView dirname = zix_path_parent_path(path); + char* const real_path = zix_canonical_path(NULL, dirname.data); + char* const dir_path = zix_path_join(NULL, real_path, NULL); + + LilvState* const state = new_state_from_model(world, map, model, subject_node, dir_path); - free(dir_path); - free(real_path); - free(dirname); + + zix_free(NULL, dir_path); + zix_free(NULL, real_path); serd_node_free(&node); - free(abs_path); + zix_free(NULL, abs_path); serd_reader_free(reader); sord_free(model); serd_env_free(env); @@ -818,7 +846,7 @@ ttl_writer(SerdSink sink, void* stream, const SerdNode* base, SerdEnv** new_env) { SerdURI base_uri = SERD_URI_NULL; if (base && base->buf) { - serd_uri_parse(base->buf, &base_uri); + serd_uri_parse((const uint8_t*)base->buf, &base_uri); } SerdEnv* env = *new_env ? *new_env : serd_env_new(base); @@ -895,11 +923,12 @@ write_manifest(LilvWorld* world, { (void)world; - char* const path = (char*)serd_file_uri_parse(file_uri->buf, NULL); - FILE* const wfd = fopen(path, "w"); + char* const path = + (char*)serd_file_uri_parse((const uint8_t*)file_uri->buf, NULL); + + FILE* const wfd = path ? fopen(path, "w") : NULL; if (!wfd) { LILV_ERRORF("Failed to open %s for writing (%s)\n", path, strerror(errno)); - serd_free(path); return 1; } @@ -925,10 +954,11 @@ add_state_to_manifest(LilvWorld* lworld, SerdEnv* env = serd_env_new(&manifest); SordModel* model = sord_new(world, SORD_SPO, false); - if (lilv_path_exists(manifest_path)) { + const uint8_t* const manifest_uri = manifest.buf; + if (manifest_uri && zix_file_type(manifest_path) == ZIX_FILE_TYPE_REGULAR) { // Read manifest into model SerdReader* reader = sord_new_reader(model, env, SERD_TURTLE, NULL); - SerdStatus st = serd_reader_read_file(reader, manifest.buf); + SerdStatus st = serd_reader_read_file(reader, manifest_uri); if (st) { LILV_WARNF("Failed to read manifest (%s)\n", serd_strerror(st)); } @@ -988,15 +1018,15 @@ add_state_to_manifest(LilvWorld* lworld, LILV_ERRORF( "Failed to open %s for writing (%s)\n", manifest_path, strerror(errno)); r = 1; + } else { + SerdWriter* writer = ttl_file_writer(wfd, &manifest, &env); + zix_file_lock(wfd, ZIX_FILE_LOCK_BLOCK); + sord_write(model, writer, NULL); + zix_file_unlock(wfd, ZIX_FILE_LOCK_BLOCK); + serd_writer_free(writer); + fclose(wfd); } - SerdWriter* writer = ttl_file_writer(wfd, &manifest, &env); - lilv_flock(wfd, true, true); - sord_write(model, writer, NULL); - lilv_flock(wfd, false, true); - serd_writer_free(writer); - fclose(wfd); - sord_free(model); serd_node_free(&file); serd_node_free(&manifest); @@ -1009,31 +1039,44 @@ static bool link_exists(const char* path, const void* data) { const char* target = (const char*)data; - if (!lilv_path_exists(path)) { + if (zix_file_type(path) == ZIX_FILE_TYPE_NONE) { return false; } - char* real_path = lilv_path_canonical(path); - bool matches = !strcmp(real_path, target); - free(real_path); + + char* const real_path = zix_canonical_path(NULL, path); + const bool matches = real_path && !strcmp(real_path, target); + zix_free(NULL, real_path); return !matches; } -static int -maybe_symlink(const char* oldpath, const char* newpath) +static ZixStatus +create_link(const char* oldpath, const char* newpath) { - if (link_exists(newpath, oldpath)) { - return 0; - } + const ZixStringView parent_path = zix_path_parent_path(newpath); + char* const parent = zix_string_view_copy(NULL, parent_path); - const int st = lilv_symlink(oldpath, newpath); - if (st) { - LILV_ERRORF( - "Failed to link %s => %s (%s)\n", newpath, oldpath, strerror(errno)); + char* const relpath = zix_path_lexically_relative(NULL, oldpath, parent); + + ZixStatus st = ZIX_STATUS_SUCCESS; + if ((st = zix_create_symlink(relpath, newpath))) { + if ((st = zix_create_hard_link(oldpath, newpath))) { + LILV_ERRORF( + "Failed to link %s => %s (%s)\n", newpath, oldpath, zix_strerror(st)); + } } + zix_free(NULL, relpath); + zix_free(NULL, parent); return st; } +static ZixStatus +maybe_symlink(const char* oldpath, const char* newpath) +{ + return link_exists(newpath, oldpath) ? ZIX_STATUS_SUCCESS + : create_link(oldpath, newpath); +} + static void write_property_array(const LilvState* state, const PropertyArray* array, @@ -1178,16 +1221,17 @@ lilv_state_make_links(const LilvState* state, const char* dir) for (ZixTreeIter* i = zix_tree_begin(state->abs2rel); i != zix_tree_end(state->abs2rel); i = zix_tree_iter_next(i)) { - const PathMap* pm = (const PathMap*)zix_tree_get(i); + const PathMap* const pm = (const PathMap*)zix_tree_get(i); + char* const path = zix_path_join(NULL, dir, pm->rel); - char* path = lilv_path_absolute_child(pm->rel, dir); - if (lilv_path_is_child(pm->abs, state->copy_dir) && - strcmp(state->copy_dir, dir)) { + if (state->copy_dir && path_is_child(pm->abs, state->copy_dir) && + !!strcmp(state->copy_dir, dir)) { // Link directly to snapshot in the copy directory maybe_symlink(pm->abs, path); - } else if (!lilv_path_is_child(pm->abs, dir)) { + } else if (!path_is_child(pm->abs, dir)) { const char* link_dir = state->link_dir ? state->link_dir : dir; - char* pat = lilv_path_absolute_child(pm->rel, link_dir); + char* pat = zix_path_join(NULL, link_dir, pm->rel); + if (!strcmp(dir, link_dir)) { // Link directory is save directory, make link at exact path remove(pat); @@ -1195,17 +1239,18 @@ lilv_state_make_links(const LilvState* state, const char* dir) } else { // Make a link in the link directory to external file char* lpath = lilv_find_free_path(pat, link_exists, pm->abs); - if (!lilv_path_exists(lpath)) { - if (lilv_symlink(pm->abs, lpath)) { + if (zix_file_type(lpath) == ZIX_FILE_TYPE_NONE) { + const ZixStatus st = create_link(pm->abs, lpath); + if (st) { LILV_ERRORF("Failed to link %s => %s (%s)\n", pm->abs, lpath, - strerror(errno)); + zix_strerror(st)); } } // Make a link in the save directory to the external link - char* target = lilv_path_relative_to(lpath, dir); + char* target = zix_path_lexically_relative(NULL, lpath, dir); maybe_symlink(lpath, path); free(target); free(lpath); @@ -1225,17 +1270,21 @@ lilv_state_save(LilvWorld* world, const char* dir, const char* filename) { - if (!filename || !dir || lilv_create_directories(dir)) { + if (!filename || !dir || zix_create_directories(NULL, dir)) { return 1; } - char* abs_dir = real_dir(dir); - char* const path = lilv_path_join(abs_dir, filename); - FILE* fd = fopen(path, "w"); + char* const abs_dir = zix_canonical_path(NULL, dir); + if (!abs_dir) { + return 2; + } + + char* const path = zix_path_join(NULL, abs_dir, filename); + FILE* fd = path ? fopen(path, "w") : NULL; if (!fd) { LILV_ERRORF("Failed to open %s (%s)\n", path, strerror(errno)); - free(abs_dir); - free(path); + zix_free(NULL, abs_dir); + zix_free(NULL, path); return 4; } @@ -1251,9 +1300,9 @@ lilv_state_save(LilvWorld* world, lilv_state_write(world, map, unmap, state, ttl, (const char*)node.buf, dir); // Set saved dir and uri (FIXME: const violation) - free(state->dir); + zix_free(NULL, state->dir); lilv_node_free(state->uri); - ((LilvState*)state)->dir = lilv_strdup(abs_dir); + ((LilvState*)state)->dir = zix_path_join(NULL, abs_dir, ""); ((LilvState*)state)->uri = lilv_new_uri(world, (const char*)node.buf); serd_node_free(&file); @@ -1263,15 +1312,15 @@ lilv_state_save(LilvWorld* world, // Add entry to manifest if (!ret) { - char* const manifest = lilv_path_join(abs_dir, "manifest.ttl"); + char* const manifest = zix_path_join(NULL, abs_dir, "manifest.ttl"); ret = add_state_to_manifest(world, state->plugin_uri, manifest, uri, path); - free(manifest); + zix_free(NULL, manifest); } - free(abs_dir); - free(path); + zix_free(NULL, abs_dir); + zix_free(NULL, path); return ret; } @@ -1307,7 +1356,7 @@ static void try_unlink(const char* state_dir, const char* path) { if (!strncmp(state_dir, path, strlen(state_dir))) { - if (lilv_path_exists(path) && lilv_remove(path)) { + if (zix_file_type(path) != ZIX_FILE_TYPE_NONE && zix_remove(path)) { LILV_ERRORF("Failed to remove %s (%s)\n", path, strerror(errno)); } } @@ -1317,7 +1366,7 @@ static char* get_canonical_path(const LilvNode* const node) { char* const path = lilv_node_get_path(node, NULL); - char* const real_path = lilv_path_canonical(path); + char* const real_path = zix_canonical_path(NULL, path); free(path); return real_path; @@ -1334,8 +1383,10 @@ lilv_state_delete(LilvWorld* world, const LilvState* state) LilvNode* bundle = lilv_new_file_uri(world, NULL, state->dir); LilvNode* manifest = lilv_world_get_manifest_uri(world, bundle); char* manifest_path = get_canonical_path(manifest); - const bool has_manifest = lilv_path_exists(manifest_path); - SordModel* model = sord_new(world->world, SORD_SPO, false); + const bool has_manifest = + manifest_path && zix_file_type(manifest_path) == ZIX_FILE_TYPE_REGULAR; + + SordModel* model = sord_new(world->world, SORD_SPO, false); if (has_manifest) { // Read manifest into temporary local model @@ -1353,11 +1404,11 @@ lilv_state_delete(LilvWorld* world, const LilvState* state) // Remove state file const uint8_t* uri = sord_node_get_string(file); char* path = (char*)serd_file_uri_parse(uri, NULL); - char* real_path = lilv_path_canonical(path); - if (path) { + char* real_path = zix_canonical_path(NULL, path); + if (real_path) { try_unlink(state->dir, real_path); } - serd_free(real_path); + zix_free(NULL, real_path); serd_free(path); } @@ -1383,9 +1434,9 @@ lilv_state_delete(LilvWorld* world, const LilvState* state) i != zix_tree_end(state->abs2rel); i = zix_tree_iter_next(i)) { const PathMap* pm = (const PathMap*)zix_tree_get(i); - char* path = lilv_path_join(state->dir, pm->rel); + char* path = zix_path_join(NULL, state->dir, pm->rel); try_unlink(state->dir, path); - free(path); + zix_free(NULL, path); } } else { // State loaded from model, get paths from loaded properties @@ -1397,7 +1448,7 @@ lilv_state_delete(LilvWorld* world, const LilvState* state) } } - if (lilv_remove(state->dir)) { + if (zix_remove(state->dir)) { LILV_ERRORF( "Failed to remove directory %s (%s)\n", state->dir, strerror(errno)); } @@ -1412,7 +1463,7 @@ lilv_state_delete(LilvWorld* world, const LilvState* state) } sord_free(model); - lilv_free(manifest_path); + zix_free(NULL, manifest_path); lilv_node_free(manifest); lilv_node_free(bundle); @@ -1460,7 +1511,7 @@ lilv_state_equals(const LilvState* a, const LilvState* b) { if (!lilv_node_equals(a->plugin_uri, b->plugin_uri) || (a->label && !b->label) || (b->label && !a->label) || - (a->label && b->label && strcmp(a->label, b->label)) || + (a->label && b->label && !!strcmp(a->label, b->label)) || a->props.n != b->props.n || a->n_values != b->n_values) { return false; } @@ -1469,8 +1520,8 @@ lilv_state_equals(const LilvState* a, const LilvState* b) PortValue* const av = &a->values[i]; PortValue* const bv = &b->values[i]; if (av->atom->size != bv->atom->size || av->atom->type != bv->atom->type || - strcmp(av->symbol, bv->symbol) || - memcmp(av->atom + 1, bv->atom + 1, av->atom->size)) { + !!strcmp(av->symbol, bv->symbol) || + !!memcmp(av->atom + 1, bv->atom + 1, av->atom->size)) { return false; } } @@ -1483,11 +1534,13 @@ lilv_state_equals(const LilvState* a, const LilvState* b) } if (ap->type == a->atom_Path) { - if (!lilv_file_equals(lilv_state_rel2abs(a, (char*)ap->value), - lilv_state_rel2abs(b, (char*)bp->value))) { + if (!zix_file_equals(NULL, + lilv_state_rel2abs(a, (char*)ap->value), + lilv_state_rel2abs(b, (char*)bp->value))) { return false; } - } else if (ap->size != bp->size || memcmp(ap->value, bp->value, ap->size)) { + } else if (ap->size != bp->size || + !!memcmp(ap->value, bp->value, ap->size)) { return false; } } @@ -1,18 +1,5 @@ -/* - Copyright 2007-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ +// Copyright 2007-2019 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC #include "lilv_internal.h" @@ -1,37 +1,26 @@ -/* - Copyright 2007-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#include "filesystem.h" +// Copyright 2007-2019 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC + #include "lilv_internal.h" #include "lilv/lilv.h" #include "serd/serd.h" +#include "zix/allocator.h" +#include "zix/filesystem.h" +#include "zix/path.h" +#include "zix/string_view.h" #include <sys/stat.h> -#include <sys/types.h> #include <ctype.h> #include <errno.h> #include <stdarg.h> #include <stdbool.h> -#include <stddef.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> +#include <time.h> // IWYU pragma: keep void lilv_free(void* ptr) @@ -47,7 +36,7 @@ lilv_strjoin(const char* first, ...) memcpy(result, first, len); - va_list args; + va_list args; // NOLINT(cppcoreguidelines-init-variables) va_start(args, first); while (1) { const char* const s = va_arg(args, const char*); @@ -127,10 +116,9 @@ lilv_get_lang(void) lang[i] = '-'; // Convert _ to - } else if (env_lang[i] >= 'A' && env_lang[i] <= 'Z') { lang[i] = env_lang[i] + ('a' - 'A'); // Convert to lowercase - } else if (env_lang[i] >= 'a' && env_lang[i] <= 'z') { - lang[i] = env_lang[i]; // Lowercase letter, copy verbatim - } else if (env_lang[i] >= '0' && env_lang[i] <= '9') { - lang[i] = env_lang[i]; // Digit, copy verbatim + } else if ((env_lang[i] >= 'a' && env_lang[i] <= 'z') || + (env_lang[i] >= '0' && env_lang[i] <= '9')) { + lang[i] = env_lang[i]; // Lowercase letter or digit, copy verbatim } else if (env_lang[i] == '\0' || env_lang[i] == '.') { // End, or start of suffix (e.g. en_CA.utf-8), finished lang[i] = '\0'; @@ -231,7 +219,7 @@ lilv_find_free_path(const char* in_path, char* path = (char*)malloc(in_path_len + 7); memcpy(path, in_path, in_path_len + 1); - for (unsigned i = 2; i < 1000000u; ++i) { + for (unsigned i = 2U; i < 1000000U; ++i) { if (!exists(path, user_data)) { return path; } @@ -251,13 +239,13 @@ static void update_latest(const char* path, const char* name, void* data) { Latest* latest = (Latest*)data; - char* entry_path = lilv_path_join(path, name); + char* entry_path = zix_path_join(NULL, path, name); unsigned num = 0; if (sscanf(entry_path, latest->pattern, &num) == 1) { struct stat st; if (!stat(entry_path, &st)) { if (st.st_mtime >= latest->time) { - free(latest->latest); + zix_free(NULL, latest->latest); latest->latest = entry_path; } } else { @@ -265,7 +253,7 @@ update_latest(const char* path, const char* name, void* data) } } if (entry_path != latest->latest) { - free(entry_path); + zix_free(NULL, entry_path); } } @@ -273,8 +261,9 @@ update_latest(const char* path, const char* name, void* data) char* lilv_get_latest_copy(const char* path, const char* copy_path) { - char* copy_dir = lilv_path_parent(copy_path); - Latest latest = {lilv_strjoin(copy_path, ".%u", NULL), 0, NULL}; + char* copy_dir = zix_string_view_copy(NULL, zix_path_parent_path(copy_path)); + + Latest latest = {lilv_strjoin(copy_path, ".%u", NULL), 0, NULL}; struct stat st; if (!stat(path, &st)) { @@ -283,9 +272,9 @@ lilv_get_latest_copy(const char* path, const char* copy_path) LILV_ERRORF("stat(%s) (%s)\n", path, strerror(errno)); } - lilv_dir_for_each(copy_dir, &latest, update_latest); + zix_dir_for_each(copy_dir, &latest, update_latest); free(latest.pattern); - free(copy_dir); + zix_free(NULL, copy_dir); return latest.latest; } diff --git a/src/world.c b/src/world.c index 47dc147..b0ef24d 100644 --- a/src/world.c +++ b/src/world.c @@ -1,27 +1,13 @@ -/* - Copyright 2007-2019 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#include "filesystem.h" +// Copyright 2007-2019 David Robillard <d@drobilla.net> +// SPDX-License-Identifier: ISC + #include "lilv_config.h" // IWYU pragma: keep #include "lilv_internal.h" #include "lilv/lilv.h" #include "serd/serd.h" #include "sord/sord.h" -#include "zix/common.h" +#include "zix/filesystem.h" #include "zix/tree.h" #include "lv2/core/lv2.h" @@ -29,7 +15,6 @@ #ifdef LILV_DYN_MANIFEST # include "lv2/dynmanifest/dynmanifest.h" -# include <dlfcn.h> #endif #include <assert.h> @@ -42,6 +27,16 @@ static int lilv_world_drop_graph(LilvWorld* world, const SordNode* graph); +static int +lilv_lib_compare(const void* a, const void* b, const void* user_data); + +static void +destroy_node(void* const ptr, const void* const user_data) +{ + (void)user_data; + lilv_node_free((LilvNode*)ptr); +} + LilvWorld* lilv_world_new(void) { @@ -61,10 +56,11 @@ lilv_world_new(void) world->plugin_classes = lilv_plugin_classes_new(); world->plugins = lilv_plugins_new(); world->zombies = lilv_plugins_new(); - world->loaded_files = zix_tree_new( - false, lilv_resource_node_cmp, NULL, (ZixDestroyFunc)lilv_node_free); - world->libs = zix_tree_new(false, lilv_lib_compare, NULL, NULL); + world->loaded_files = + zix_tree_new(NULL, false, lilv_resource_node_cmp, NULL, destroy_node, NULL); + + world->libs = zix_tree_new(NULL, false, lilv_lib_compare, NULL, NULL, NULL); #define NS_DCTERMS "http://purl.org/dc/terms/" #define NS_DYNMAN "http://lv2plug.in/ns/ext/dynmanifest#" @@ -337,15 +333,6 @@ lilv_world_find_nodes_internal(LilvWorld* world, (object == NULL) ? SORD_OBJECT : SORD_SUBJECT); } -static SerdNode -lilv_new_uri_relative_to_base(const uint8_t* uri_str, - const uint8_t* base_uri_str) -{ - SerdURI base_uri; - serd_uri_parse(base_uri_str, &base_uri); - return serd_node_new_uri_from_string(uri_str, &base_uri, NULL); -} - const uint8_t* lilv_world_blank_node_prefix(LilvWorld* world) { @@ -374,7 +361,7 @@ lilv_header_compare_by_uri(const void* a, const void* b, const void* user_data) handle the case where the same library is loaded with different bundles, and consequently different contents (mainly plugins). */ -int +static int lilv_lib_compare(const void* a, const void* b, const void* user_data) { (void)user_data; @@ -506,7 +493,7 @@ lilv_world_add_plugin(LilvWorld* world, sord_iter_free(files); } -SerdStatus +static SerdStatus lilv_world_load_graph(LilvWorld* world, SordNode* graph, const LilvNode* uri) { const SerdNode* base = sord_node_to_serd_node(uri->node); @@ -674,10 +661,24 @@ lilv_dynmanifest_free(LilvDynManifest* dynmanifest) LilvNode* lilv_world_get_manifest_uri(LilvWorld* world, const LilvNode* bundle_uri) { - SerdNode manifest_uri = lilv_new_uri_relative_to_base( - (const uint8_t*)"manifest.ttl", sord_node_get_string(bundle_uri->node)); - LilvNode* manifest = lilv_new_uri(world, (const char*)manifest_uri.buf); - serd_node_free(&manifest_uri); + // Get the string and length of the given bundle URI + size_t bundle_uri_length = 0U; + const char* const bundle_uri_string = + (const char*)sord_node_get_string_counted(bundle_uri->node, + &bundle_uri_length); + if (!bundle_uri_length) { + return NULL; + } + + // Build the manifest URI by inserting a separating "/" if necessary + const char last = bundle_uri_string[bundle_uri_length - 1U]; + char* const manifest_uri_string = + (last == '/') ? lilv_strjoin(bundle_uri_string, "manifest.ttl", NULL) + : lilv_strjoin(bundle_uri_string, "/", "manifest.ttl", NULL); + + // Make a node from the manifeset URI to return + LilvNode* const manifest = lilv_new_uri(world, manifest_uri_string); + free(manifest_uri_string); return manifest; } @@ -749,6 +750,9 @@ lilv_world_load_bundle(LilvWorld* world, const LilvNode* bundle_uri) SordNode* bundle_node = bundle_uri->node; LilvNode* manifest = lilv_world_get_manifest_uri(world, bundle_uri); + if (!manifest) { + return; + } // Read manifest into model with graph = bundle_node SerdStatus st = lilv_world_load_graph(world, bundle_node, manifest); @@ -928,7 +932,7 @@ lilv_world_unload_bundle(LilvWorld* world, const LilvNode* bundle_uri) still be used. */ ZixTreeIter* i = zix_tree_begin((ZixTree*)world->plugins); - while (i != zix_tree_end((ZixTree*)world->plugins)) { + while (i && i != zix_tree_end((ZixTree*)world->plugins)) { LilvPlugin* p = (LilvPlugin*)zix_tree_get(i); ZixTreeIter* next = zix_tree_iter_next(i); @@ -964,7 +968,7 @@ lilv_world_load_directory(LilvWorld* world, const char* dir_path) { char* path = lilv_expand(dir_path); if (path) { - lilv_dir_for_each(path, world, load_dir_entry); + zix_dir_for_each(path, world, load_dir_entry); free(path); } } @@ -1100,11 +1104,11 @@ lilv_world_load_file(LilvWorld* world, SerdReader* reader, const LilvNode* uri) size_t uri_len = 0; const uint8_t* const uri_str = sord_node_get_string_counted(uri->node, &uri_len); - if (strncmp((const char*)uri_str, "file:", 5)) { + if (!!strncmp((const char*)uri_str, "file:", 5)) { return SERD_FAILURE; // Not a local file } - if (strcmp((const char*)uri_str + uri_len - 4, ".ttl")) { + if (!!strcmp((const char*)uri_str + uri_len - 4, ".ttl")) { return SERD_FAILURE; // Not a Turtle file } diff --git a/src/zix/common.h b/src/zix/common.h deleted file mode 100644 index d47586c..0000000 --- a/src/zix/common.h +++ /dev/null @@ -1,138 +0,0 @@ -/* - Copyright 2016-2020 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#ifndef ZIX_COMMON_H -#define ZIX_COMMON_H - -#include <stdbool.h> - -/** - @addtogroup zix - @{ -*/ - -/** @cond */ -#if defined(_WIN32) && !defined(ZIX_STATIC) && defined(ZIX_INTERNAL) -# define ZIX_API __declspec(dllexport) -#elif defined(_WIN32) && !defined(ZIX_STATIC) -# define ZIX_API __declspec(dllimport) -#elif defined(__GNUC__) -# define ZIX_API __attribute__((visibility("default"))) -#else -# define ZIX_API -#endif - -#ifdef __GNUC__ -# define ZIX_PURE_FUNC __attribute__((pure)) -# define ZIX_CONST_FUNC __attribute__((const)) -# define ZIX_MALLOC_FUNC __attribute__((malloc)) -#else -# define ZIX_PURE_FUNC -# define ZIX_CONST_FUNC -# define ZIX_MALLOC_FUNC -#endif - -#define ZIX_PURE_API \ - ZIX_API \ - ZIX_PURE_FUNC - -#define ZIX_CONST_API \ - ZIX_API \ - ZIX_CONST_FUNC - -#define ZIX_MALLOC_API \ - ZIX_API \ - ZIX_MALLOC_FUNC - -/** @endcond */ - -#ifdef __cplusplus -extern "C" { -#endif - -#ifdef __GNUC__ -# define ZIX_LOG_FUNC(fmt, arg1) __attribute__((format(printf, fmt, arg1))) -#else -# define ZIX_LOG_FUNC(fmt, arg1) -#endif - -// Unused parameter macro to suppresses warnings and make it impossible to use -#if defined(__cplusplus) -# define ZIX_UNUSED(name) -#elif defined(__GNUC__) -# define ZIX_UNUSED(name) name##_unused __attribute__((__unused__)) -#else -# define ZIX_UNUSED(name) name -#endif - -typedef enum { - ZIX_STATUS_SUCCESS, - ZIX_STATUS_ERROR, - ZIX_STATUS_NO_MEM, - ZIX_STATUS_NOT_FOUND, - ZIX_STATUS_EXISTS, - ZIX_STATUS_BAD_ARG, - ZIX_STATUS_BAD_PERMS -} ZixStatus; - -static inline const char* -zix_strerror(const ZixStatus status) -{ - switch (status) { - case ZIX_STATUS_SUCCESS: - return "Success"; - case ZIX_STATUS_ERROR: - return "Unknown error"; - case ZIX_STATUS_NO_MEM: - return "Out of memory"; - case ZIX_STATUS_NOT_FOUND: - return "Not found"; - case ZIX_STATUS_EXISTS: - return "Exists"; - case ZIX_STATUS_BAD_ARG: - return "Bad argument"; - case ZIX_STATUS_BAD_PERMS: - return "Bad permissions"; - } - return "Unknown error"; -} - -/** - Function for comparing two elements. -*/ -typedef int (*ZixComparator)(const void* a, - const void* b, - const void* user_data); - -/** - Function for testing equality of two elements. -*/ -typedef bool (*ZixEqualFunc)(const void* a, const void* b); - -/** - Function to destroy an element. -*/ -typedef void (*ZixDestroyFunc)(void* ptr); - -/** - @} -*/ - -#ifdef __cplusplus -} /* extern "C" */ -#endif - -#endif /* ZIX_COMMON_H */ diff --git a/src/zix/tree.c b/src/zix/tree.c deleted file mode 100644 index 9faf13c..0000000 --- a/src/zix/tree.c +++ /dev/null @@ -1,727 +0,0 @@ -/* - Copyright 2011-2020 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#include "zix/tree.h" - -#include "zix/common.h" - -#include <assert.h> -#include <stdlib.h> -#include <string.h> - -typedef struct ZixTreeNodeImpl ZixTreeNode; - -struct ZixTreeImpl { - ZixTreeNode* root; - ZixDestroyFunc destroy; - ZixComparator cmp; - void* cmp_data; - size_t size; - bool allow_duplicates; -}; - -struct ZixTreeNodeImpl { - void* data; - struct ZixTreeNodeImpl* left; - struct ZixTreeNodeImpl* right; - struct ZixTreeNodeImpl* parent; - int balance; -}; - -#define MIN(a, b) (((a) < (b)) ? (a) : (b)) -#define MAX(a, b) (((a) > (b)) ? (a) : (b)) - -// Uncomment these for debugging features -// #define ZIX_TREE_DUMP 1 -// #define ZIX_TREE_VERIFY 1 -// #define ZIX_TREE_HYPER_VERIFY 1 - -#if defined(ZIX_TREE_VERIFY) || defined(ZIX_TREE_HYPER_VERIFY) -# include "tree_debug.h" -# define ASSERT_BALANCE(n) assert(verify_balance(n)) -#else -# define ASSERT_BALANCE(n) -#endif - -#ifdef ZIX_TREE_DUMP -# include "tree_debug.h" -# define DUMP(t) zix_tree_print(t->root, 0) -# define DEBUG_PRINTF(fmt, ...) printf(fmt, __VA_ARGS__) -#else -# define DUMP(t) -# define DEBUG_PRINTF(fmt, ...) -#endif - -ZixTree* -zix_tree_new(bool allow_duplicates, - ZixComparator cmp, - void* cmp_data, - ZixDestroyFunc destroy) -{ - ZixTree* t = (ZixTree*)malloc(sizeof(ZixTree)); - t->root = NULL; - t->destroy = destroy; - t->cmp = cmp; - t->cmp_data = cmp_data; - t->size = 0; - t->allow_duplicates = allow_duplicates; - return t; -} - -static void -zix_tree_free_rec(ZixTree* t, ZixTreeNode* n) -{ - if (n) { - zix_tree_free_rec(t, n->left); - zix_tree_free_rec(t, n->right); - if (t->destroy) { - t->destroy(n->data); - } - free(n); - } -} - -void -zix_tree_free(ZixTree* t) -{ - if (t) { - zix_tree_free_rec(t, t->root); - free(t); - } -} - -size_t -zix_tree_size(const ZixTree* t) -{ - return t->size; -} - -static void -rotate(ZixTreeNode* p, ZixTreeNode* q) -{ - assert(q->parent == p); - assert(p->left == q || p->right == q); - - q->parent = p->parent; - if (q->parent) { - if (q->parent->left == p) { - q->parent->left = q; - } else { - q->parent->right = q; - } - } - - if (p->right == q) { - // Rotate left - p->right = q->left; - q->left = p; - if (p->right) { - p->right->parent = p; - } - } else { - // Rotate right - assert(p->left == q); - p->left = q->right; - q->right = p; - if (p->left) { - p->left->parent = p; - } - } - - p->parent = q; -} - -/** - * Rotate left about `p`. - * - * p q - * / \ / \ - * A q => p C - * / \ / \ - * B C A B - */ -static ZixTreeNode* -rotate_left(ZixTreeNode* p, int* height_change) -{ - ZixTreeNode* const q = p->right; - *height_change = (q->balance == 0) ? 0 : -1; - - DEBUG_PRINTF("LL %ld\n", (intptr_t)p->data); - - assert(p->balance == 2); - assert(q->balance == 0 || q->balance == 1); - - rotate(p, q); - - // p->balance -= 1 + MAX(0, q->balance); - // q->balance -= 1 - MIN(0, p->balance); - --q->balance; - p->balance = -(q->balance); - - ASSERT_BALANCE(p); - ASSERT_BALANCE(q); - return q; -} - -/** - * Rotate right about `p`. - * - * p q - * / \ / \ - * q C => A p - * / \ / \ - * A B B C - * - */ -static ZixTreeNode* -rotate_right(ZixTreeNode* p, int* height_change) -{ - ZixTreeNode* const q = p->left; - *height_change = (q->balance == 0) ? 0 : -1; - - DEBUG_PRINTF("RR %ld\n", (intptr_t)p->data); - - assert(p->balance == -2); - assert(q->balance == 0 || q->balance == -1); - - rotate(p, q); - - // p->balance += 1 - MIN(0, q->balance); - // q->balance += 1 + MAX(0, p->balance); - ++q->balance; - p->balance = -(q->balance); - - ASSERT_BALANCE(p); - ASSERT_BALANCE(q); - return q; -} - -/** - * Rotate left about `p->left` then right about `p`. - * - * p r - * / \ / \ - * q D => q p - * / \ / \ / \ - * A r A B C D - * / \ - * B C - * - */ -static ZixTreeNode* -rotate_left_right(ZixTreeNode* p, int* height_change) -{ - ZixTreeNode* const q = p->left; - ZixTreeNode* const r = q->right; - - assert(p->balance == -2); - assert(q->balance == 1); - assert(r->balance == -1 || r->balance == 0 || r->balance == 1); - - DEBUG_PRINTF("LR %ld P: %2d Q: %2d R: %2d\n", - (intptr_t)p->data, - p->balance, - q->balance, - r->balance); - - rotate(q, r); - rotate(p, r); - - q->balance -= 1 + MAX(0, r->balance); - p->balance += 1 - MIN(MIN(0, r->balance) - 1, r->balance + q->balance); - // r->balance += MAX(0, p->balance) + MIN(0, q->balance); - - // p->balance = (p->left && p->right) ? -MIN(r->balance, 0) : 0; - // q->balance = - MAX(r->balance, 0); - r->balance = 0; - - *height_change = -1; - - ASSERT_BALANCE(p); - ASSERT_BALANCE(q); - ASSERT_BALANCE(r); - return r; -} - -/** - * Rotate right about `p->right` then right about `p`. - * - * p r - * / \ / \ - * A q => p q - * / \ / \ / \ - * r D A B C D - * / \ - * B C - * - */ -static ZixTreeNode* -rotate_right_left(ZixTreeNode* p, int* height_change) -{ - ZixTreeNode* const q = p->right; - ZixTreeNode* const r = q->left; - - assert(p->balance == 2); - assert(q->balance == -1); - assert(r->balance == -1 || r->balance == 0 || r->balance == 1); - - DEBUG_PRINTF("RL %ld P: %2d Q: %2d R: %2d\n", - (intptr_t)p->data, - p->balance, - q->balance, - r->balance); - - rotate(q, r); - rotate(p, r); - - q->balance += 1 - MIN(0, r->balance); - p->balance -= 1 + MAX(MAX(0, r->balance) + 1, r->balance + q->balance); - // r->balance += MAX(0, q->balance) + MIN(0, p->balance); - - // p->balance = (p->left && p->right) ? -MAX(r->balance, 0) : 0; - // q->balance = - MIN(r->balance, 0); - r->balance = 0; - // assert(r->balance == 0); - - *height_change = -1; - - ASSERT_BALANCE(p); - ASSERT_BALANCE(q); - ASSERT_BALANCE(r); - return r; -} - -static ZixTreeNode* -zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) -{ -#ifdef ZIX_TREE_HYPER_VERIFY - const size_t old_height = height(node); -#endif - DEBUG_PRINTF("REBALANCE %ld (%d)\n", (intptr_t)node->data, node->balance); - *height_change = 0; - const bool is_root = !node->parent; - assert((is_root && t->root == node) || (!is_root && t->root != node)); - ZixTreeNode* replacement = node; - if (node->balance == -2) { - assert(node->left); - if (node->left->balance == 1) { - replacement = rotate_left_right(node, height_change); - } else { - replacement = rotate_right(node, height_change); - } - } else if (node->balance == 2) { - assert(node->right); - if (node->right->balance == -1) { - replacement = rotate_right_left(node, height_change); - } else { - replacement = rotate_left(node, height_change); - } - } - if (is_root) { - assert(!replacement->parent); - t->root = replacement; - } - DUMP(t); -#ifdef ZIX_TREE_HYPER_VERIFY - assert(old_height + *height_change == height(replacement)); -#endif - return replacement; -} - -ZixStatus -zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) -{ - DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e); - int cmp = 0; - ZixTreeNode* n = t->root; - ZixTreeNode* p = NULL; - - // Find the parent p of e - while (n) { - p = n; - cmp = t->cmp(e, n->data, t->cmp_data); - if (cmp < 0) { - n = n->left; - } else if (cmp > 0 || t->allow_duplicates) { - n = n->right; - } else { - if (ti) { - *ti = n; - } - DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e); - return ZIX_STATUS_EXISTS; - } - } - - // Allocate a new node n - if (!(n = (ZixTreeNode*)malloc(sizeof(ZixTreeNode)))) { - return ZIX_STATUS_NO_MEM; - } - memset(n, '\0', sizeof(ZixTreeNode)); - n->data = e; - n->balance = 0; - if (ti) { - *ti = n; - } - - bool p_height_increased = false; - - // Make p the parent of n - n->parent = p; - if (!p) { - t->root = n; - } else { - if (cmp < 0) { - assert(!p->left); - assert(p->balance == 0 || p->balance == 1); - p->left = n; - --p->balance; - p_height_increased = !p->right; - } else { - assert(!p->right); - assert(p->balance == 0 || p->balance == -1); - p->right = n; - ++p->balance; - p_height_increased = !p->left; - } - } - - DUMP(t); - - // Rebalance if necessary (at most 1 rotation) - assert(!p || p->balance == -1 || p->balance == 0 || p->balance == 1); - if (p && p_height_increased) { - int height_change = 0; - for (ZixTreeNode* i = p; i && i->parent; i = i->parent) { - if (i == i->parent->left) { - if (--i->parent->balance == -2) { - zix_tree_rebalance(t, i->parent, &height_change); - break; - } - } else { - assert(i == i->parent->right); - if (++i->parent->balance == 2) { - zix_tree_rebalance(t, i->parent, &height_change); - break; - } - } - - if (i->parent->balance == 0) { - break; - } - } - } - - DUMP(t); - - ++t->size; - -#ifdef ZIX_TREE_VERIFY - if (!verify(t, t->root)) { - return ZIX_STATUS_ERROR; - } -#endif - - return ZIX_STATUS_SUCCESS; -} - -ZixStatus -zix_tree_remove(ZixTree* t, ZixTreeIter* ti) -{ - ZixTreeNode* const n = ti; - ZixTreeNode** pp = NULL; // parent pointer - ZixTreeNode* to_balance = n->parent; // lowest node to balance - int d_balance = 0; // delta(balance) for n->parent - - DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data); - - if ((n == t->root) && !n->left && !n->right) { - t->root = NULL; - if (t->destroy) { - t->destroy(n->data); - } - free(n); - --t->size; - assert(t->size == 0); - return ZIX_STATUS_SUCCESS; - } - - // Set pp to the parent pointer to n, if applicable - if (n->parent) { - assert(n->parent->left == n || n->parent->right == n); - if (n->parent->left == n) { // n is left child - pp = &n->parent->left; - d_balance = 1; - } else { // n is right child - assert(n->parent->right == n); - pp = &n->parent->right; - d_balance = -1; - } - } - - assert(!pp || *pp == n); - - int height_change = 0; - if (!n->left && !n->right) { - // n is a leaf, just remove it - if (pp) { - *pp = NULL; - to_balance = n->parent; - height_change = (!n->parent->left && !n->parent->right) ? -1 : 0; - } - - } else if (!n->left) { - // Replace n with right (only) child - if (pp) { - *pp = n->right; - to_balance = n->parent; - } else { - t->root = n->right; - } - n->right->parent = n->parent; - height_change = -1; - - } else if (!n->right) { - // Replace n with left (only) child - if (pp) { - *pp = n->left; - to_balance = n->parent; - } else { - t->root = n->left; - } - n->left->parent = n->parent; - height_change = -1; - - } else { - // Replace n with in-order successor (leftmost child of right subtree) - ZixTreeNode* replace = n->right; - while (replace->left) { - assert(replace->left->parent == replace); - replace = replace->left; - } - - // Remove replace from parent (replace_p) - if (replace->parent->left == replace) { - height_change = replace->parent->right ? 0 : -1; - d_balance = 1; - to_balance = replace->parent; - replace->parent->left = replace->right; - } else { - assert(replace->parent == n); - height_change = replace->parent->left ? 0 : -1; - d_balance = -1; - to_balance = replace->parent; - replace->parent->right = replace->right; - } - - if (to_balance == n) { - to_balance = replace; - } - - if (replace->right) { - replace->right->parent = replace->parent; - } - - replace->balance = n->balance; - - // Swap node to delete with replace - if (pp) { - *pp = replace; - } else { - assert(t->root == n); - t->root = replace; - } - - replace->parent = n->parent; - replace->left = n->left; - n->left->parent = replace; - replace->right = n->right; - if (n->right) { - n->right->parent = replace; - } - - assert(!replace->parent || replace->parent->left == replace || - replace->parent->right == replace); - } - - // Rebalance starting at to_balance upwards. - for (ZixTreeNode* i = to_balance; i; i = i->parent) { - i->balance += d_balance; - if (d_balance == 0 || i->balance == -1 || i->balance == 1) { - break; - } - - assert(i != n); - i = zix_tree_rebalance(t, i, &height_change); - if (i->balance == 0) { - height_change = -1; - } - - if (i->parent) { - if (i == i->parent->left) { - d_balance = height_change * -1; - } else { - assert(i == i->parent->right); - d_balance = height_change; - } - } - } - - DUMP(t); - - if (t->destroy) { - t->destroy(n->data); - } - free(n); - - --t->size; - -#ifdef ZIX_TREE_VERIFY - if (!verify(t, t->root)) { - return ZIX_STATUS_ERROR; - } -#endif - - return ZIX_STATUS_SUCCESS; -} - -ZixStatus -zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti) -{ - ZixTreeNode* n = t->root; - while (n) { - const int cmp = t->cmp(e, n->data, t->cmp_data); - if (cmp == 0) { - break; - } - - if (cmp < 0) { - n = n->left; - } else { - n = n->right; - } - } - - *ti = n; - return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND; -} - -void* -zix_tree_get(const ZixTreeIter* ti) -{ - return ti ? ti->data : NULL; -} - -ZixTreeIter* -zix_tree_begin(ZixTree* t) -{ - if (!t->root) { - return NULL; - } - - ZixTreeNode* n = t->root; - while (n->left) { - n = n->left; - } - - return n; -} - -ZixTreeIter* -zix_tree_end(ZixTree* ZIX_UNUSED(t)) -{ - return NULL; -} - -ZixTreeIter* -zix_tree_rbegin(ZixTree* t) -{ - if (!t->root) { - return NULL; - } - - ZixTreeNode* n = t->root; - while (n->right) { - n = n->right; - } - - return n; -} - -ZixTreeIter* -zix_tree_rend(ZixTree* ZIX_UNUSED(t)) -{ - return NULL; -} - -bool -zix_tree_iter_is_end(const ZixTreeIter* i) -{ - return !i; -} - -bool -zix_tree_iter_is_rend(const ZixTreeIter* i) -{ - return !i; -} - -ZixTreeIter* -zix_tree_iter_next(ZixTreeIter* i) -{ - if (!i) { - return NULL; - } - - if (i->right) { - i = i->right; - while (i->left) { - i = i->left; - } - } else { - while (i->parent && i->parent->right == i) { // i is a right child - i = i->parent; - } - - i = i->parent; - } - - return i; -} - -ZixTreeIter* -zix_tree_iter_prev(ZixTreeIter* i) -{ - if (!i) { - return NULL; - } - - if (i->left) { - i = i->left; - while (i->right) { - i = i->right; - } - - } else { - while (i->parent && i->parent->left == i) { // i is a left child - i = i->parent; - } - - i = i->parent; - } - - return i; -} diff --git a/src/zix/tree.h b/src/zix/tree.h deleted file mode 100644 index a2d5fe7..0000000 --- a/src/zix/tree.h +++ /dev/null @@ -1,164 +0,0 @@ -/* - Copyright 2011-2020 David Robillard <d@drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#ifndef ZIX_TREE_H -#define ZIX_TREE_H - -#include "zix/common.h" - -#include <stdbool.h> -#include <stddef.h> - -#ifdef __cplusplus -extern "C" { -#endif - -/** - @addtogroup zix - @{ - @name Tree - @{ -*/ - -/** - A balanced binary search tree. -*/ -typedef struct ZixTreeImpl ZixTree; - -/** - An iterator over a @ref ZixTree. -*/ -typedef struct ZixTreeNodeImpl ZixTreeIter; - -/** - Create a new (empty) tree. -*/ -ZIX_API -ZixTree* -zix_tree_new(bool allow_duplicates, - ZixComparator cmp, - void* cmp_data, - ZixDestroyFunc destroy); - -/** - Free `t`. -*/ -ZIX_API -void -zix_tree_free(ZixTree* t); - -/** - Return the number of elements in `t`. -*/ -ZIX_PURE_API -size_t -zix_tree_size(const ZixTree* t); - -/** - Insert the element `e` into `t` and point `ti` at the new element. -*/ -ZIX_API -ZixStatus -zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti); - -/** - Remove the item pointed at by `ti` from `t`. -*/ -ZIX_API -ZixStatus -zix_tree_remove(ZixTree* t, ZixTreeIter* ti); - -/** - Set `ti` to an element equal to `e` in `t`. - If no such item exists, `ti` is set to NULL. -*/ -ZIX_API -ZixStatus -zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti); - -/** - Return the data associated with the given tree item. -*/ -ZIX_PURE_API -void* -zix_tree_get(const ZixTreeIter* ti); - -/** - Return an iterator to the first (smallest) element in `t`. -*/ -ZIX_PURE_API -ZixTreeIter* -zix_tree_begin(ZixTree* t); - -/** - Return an iterator the the element one past the last element in `t`. -*/ -ZIX_CONST_API -ZixTreeIter* -zix_tree_end(ZixTree* t); - -/** - Return true iff `i` is an iterator to the end of its tree. -*/ -ZIX_CONST_API -bool -zix_tree_iter_is_end(const ZixTreeIter* i); - -/** - Return an iterator to the last (largest) element in `t`. -*/ -ZIX_PURE_API -ZixTreeIter* -zix_tree_rbegin(ZixTree* t); - -/** - Return an iterator the the element one before the first element in `t`. -*/ -ZIX_CONST_API -ZixTreeIter* -zix_tree_rend(ZixTree* t); - -/** - Return true iff `i` is an iterator to the reverse end of its tree. -*/ -ZIX_CONST_API -bool -zix_tree_iter_is_rend(const ZixTreeIter* i); - -/** - Return an iterator that points to the element one past `i`. -*/ -ZIX_PURE_API -ZixTreeIter* -zix_tree_iter_next(ZixTreeIter* i); - -/** - Return an iterator that points to the element one before `i`. -*/ -ZIX_PURE_API -ZixTreeIter* -zix_tree_iter_prev(ZixTreeIter* i); - -/** - @} - @} -*/ - -#ifdef __cplusplus -} /* extern "C" */ -#endif - -#endif /* ZIX_TREE_H */ |