diff options
Diffstat (limited to 'src')
29 files changed, 428 insertions, 19 deletions
diff --git a/src/libc/include/__errno.h b/src/libc/include/__errno.h index 7551ce0..7976fba 100644 --- a/src/libc/include/__errno.h +++ b/src/libc/include/__errno.h @@ -23,4 +23,7 @@ E(205, "EINTR") E(206, "EWOULDBLOCK") E(207, "EEXIST") E(208, "EAGAIN") +E(209, "EIO") +E(210, "EDOM domain error") +E(211, "EFBIG file too large") #endif diff --git a/src/libc/include/fcntl.h b/src/libc/include/fcntl.h index 6338d1f..ba9b9e0 100644 --- a/src/libc/include/fcntl.h +++ b/src/libc/include/fcntl.h @@ -11,10 +11,10 @@ #define O_CREAT 0 #define O_EXCL 0 #define O_NONBLOCK 0 -#define O_RDONLY 0 -#define O_RDWR 0 #define O_TRUNC 0 -#define O_WRONLY 0 +#define O_RDONLY 1 +#define O_WRONLY 2 +#define O_RDWR 3 #define R_OK 1 #define W_OK 2 diff --git a/src/libc/include/inttypes.h b/src/libc/include/inttypes.h index 9a6118b..d44129a 100644 --- a/src/libc/include/inttypes.h +++ b/src/libc/include/inttypes.h @@ -1 +1,19 @@ #include <stdint.h> + +#define PRId64 "ld" +#define PRIo64 "lo" +#define PRIu64 "lu" +#define PRIx64 "lx" +#define SCNu64 "lu" + +#define PRId32 "d" +#define PRIo32 "o" +#define PRIu32 "u" +#define PRIx32 "x" +#define SCNu32 "u" + +#define PRId16 "d" +#define PRIo16 "o" +#define PRIu16 "u" +#define PRIx16 "x" +#define SCNu16 "u" diff --git a/src/libc/include/memory.h b/src/libc/include/memory.h new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/src/libc/include/memory.h diff --git a/src/libc/include/sgtty.h b/src/libc/include/sgtty.h new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/src/libc/include/sgtty.h diff --git a/src/libc/include/stdio.h b/src/libc/include/stdio.h index 48d5058..169646f 100644 --- a/src/libc/include/stdio.h +++ b/src/libc/include/stdio.h @@ -29,6 +29,7 @@ int fprintf(FILE *restrict f, const char *restrict fmt, ...); int sprintf(char *restrict s, const char *restrict fmt, ...); int vprintf(const char *restrict fmt, va_list ap); +int vsprintf(char *restrict s, const char *restrict fmt, va_list ap); int vfprintf(FILE *restrict f, const char *restrict fmt, va_list ap); int _klogf(const char *fmt, ...); // for kernel debugging only @@ -40,6 +41,7 @@ FILE *fopen(const char *path, const char *mode); FILE *freopen(const char *path, const char *mode, FILE *); FILE *fdopen(int fd, const char *mode); FILE *file_clone(const FILE *, const char *mode); +int fileno(FILE *f); FILE *popen(const char *cmd, const char *mode); int pclose(FILE *f); FILE *tmpfile(void); @@ -60,6 +62,7 @@ int putc(int c, FILE *f); int ungetc(int c, FILE *f); int fseek(FILE *f, long offset, int whence); +void rewind(FILE *f); int fseeko(FILE *f, off_t offset, int whence); long ftell(FILE *f); off_t ftello(FILE *f); diff --git a/src/libc/include/stdlib.h b/src/libc/include/stdlib.h index ee9d179..c3fd4bd 100644 --- a/src/libc/include/stdlib.h +++ b/src/libc/include/stdlib.h @@ -16,13 +16,15 @@ const char *getprogname(void); void setprogname(const char *progname); void setproctitle(const char *fmt, ...); -int mkstemp(char *template); +char *mktemp(char *tmpl); +int mkstemp(char *tmpl); char *getenv(const char *name); int system(const char *cmd); int abs(int i); int atoi(const char *s); +long atol(const char *s); double atof(const char *s); long strtol(const char *restrict s, char **restrict end, int base); @@ -32,3 +34,5 @@ unsigned long long strtoull(const char *restrict s, char **restrict end, int bas double strtod(const char *restrict s, char **restrict end); void qsort(void *base, size_t nmemb, size_t size, int (*cmp)(const void *a, const void *b)); +void qsort_r(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *, void *), void *arg); +void* bsearch(const void* key, const void* base_ptr, size_t nmemb, size_t size, int (*compare)(const void*, const void*)); diff --git a/src/libc/include/string.h b/src/libc/include/string.h index 78bed9b..d9d2b74 100644 --- a/src/libc/include/string.h +++ b/src/libc/include/string.h @@ -17,8 +17,10 @@ int strcoll(const char *s1, const char *s2); char *strstr(const char *s1, const char *s2); +char *strcat(char *restrict dst, const char *restrict src); char *strcpy(char *restrict s1, const char *restrict s2); char *strncpy(char *restrict s1, const char *restrict s2, size_t n); +char *strncat(char *restrict dst, const char *restrict src, size_t n); char *stpncpy(char *restrict dst, const char *restrict src, size_t n); char *strdup(const char *s); diff --git a/src/libc/include/sys/stat.h b/src/libc/include/sys/stat.h index 343db55..b9d0e8b 100644 --- a/src/libc/include/sys/stat.h +++ b/src/libc/include/sys/stat.h @@ -38,6 +38,8 @@ struct stat { #define S_ISGID 02000 #define S_ISVTX 01000 +#define S_IRUSR 0x400 + /* inode(7) */ #define S_ISREG(m) ((m & S_IFMT) == S_IFREG) #define S_ISDIR(m) ((m & S_IFMT) == S_IFDIR) @@ -54,7 +56,7 @@ int mkdir(const char *path, mode_t mode); static inline mode_t umask(mode_t mask) { (void)mask; - __libc_panic("unimplemented"); + return 0; } static inline int chmod(const char *path, mode_t mode) { @@ -63,6 +65,12 @@ static inline int chmod(const char *path, mode_t mode) { return -1; } +static inline int fchmod(int fd, mode_t mode) { + (void)fd; (void)mode; + errno = ENOSYS; + return -1; +} + static inline int mknod(const char *path, mode_t mode, dev_t dev) { (void)path; (void)mode; (void)dev; errno = ENOSYS; diff --git a/src/libc/include/sys/time.h b/src/libc/include/sys/time.h index e69de29..54df6b3 100644 --- a/src/libc/include/sys/time.h +++ b/src/libc/include/sys/time.h @@ -0,0 +1,8 @@ +#pragma once +#include <errno.h> +#include <sys/types.h> + +struct timeval { + time_t tv_sec; + suseconds_t tv_usec; +}; diff --git a/src/libc/include/sys/types.h b/src/libc/include/sys/types.h index faf656a..2e7f54b 100644 --- a/src/libc/include/sys/types.h +++ b/src/libc/include/sys/types.h @@ -4,6 +4,7 @@ typedef long long off_t; typedef int64_t time_t; +typedef int64_t suseconds_t; typedef uint64_t clock_t; typedef int mode_t; diff --git a/src/libc/include/sys/wait.h b/src/libc/include/sys/wait.h index cff407e..5f0d2cc 100644 --- a/src/libc/include/sys/wait.h +++ b/src/libc/include/sys/wait.h @@ -10,4 +10,5 @@ #define WNOHANG 0 #define WUNTRACED 0 +pid_t wait(int *wstatus); pid_t wait3(int *wstatus, int opts, struct rusage *rusage); diff --git a/src/libc/include/time.h b/src/libc/include/time.h index 5d03664..e2bf31e 100644 --- a/src/libc/include/time.h +++ b/src/libc/include/time.h @@ -29,6 +29,8 @@ time_t mktime(struct tm *timeptr); double difftime(time_t time1, time_t time0); +char *ctime(const time_t *timep); + size_t strftime( char *restrict s, size_t maxsize, const char *restrict format, const struct tm *restrict timeptr); diff --git a/src/libc/include/unistd.h b/src/libc/include/unistd.h index 005e79c..ac5afc0 100644 --- a/src/libc/include/unistd.h +++ b/src/libc/include/unistd.h @@ -16,10 +16,12 @@ _Noreturn void _exit(int); ssize_t readlink(const char *restrict path, char *restrict buf, size_t bufsize); int link(const char *path1, const char *path2); int unlink(const char *path); +int rmdir(const char *path); int symlink(const char *path1, const char *path2); int isatty(int fd); int execv(const char *path, char *const argv[]); +int execvp(const char *path, char *const argv[]); int execve(const char *path, char *const argv[], char *const envp[]); int chdir(const char *path); @@ -30,6 +32,7 @@ uid_t geteuid(void); gid_t getgid(void); gid_t getegid(void); +int access(const char *path, int mode); int chown(const char *path, uid_t owner, gid_t group); int setpgid(pid_t pid, pid_t pgid); @@ -44,8 +47,11 @@ int getgroups(int size, gid_t list[]); ssize_t read(int fd, void *buf, size_t count); ssize_t write(int fd, const void *buf, size_t count); int pipe(int pipefd[2]); +int dup(int oldfd); int dup2(int oldfd, int newfd); +unsigned int sleep(unsigned int seconds); + /* Converts a relative path to an absolute one, simplifying it if possible. * If in == NULL - return the length of cwd. Doesn't include the trailing slash, * except for the root dir. Includes the null byte. diff --git a/src/libc/include/utime.h b/src/libc/include/utime.h new file mode 100644 index 0000000..4ae34ed --- /dev/null +++ b/src/libc/include/utime.h @@ -0,0 +1,9 @@ +#pragma once +#include <sys/time.h> + +struct utimbuf { + time_t actime; + time_t modtime; +}; + +int utime(const char *fn, const struct utimbuf *times); diff --git a/src/libc/include/wchar.h b/src/libc/include/wchar.h new file mode 100644 index 0000000..3d4bc15 --- /dev/null +++ b/src/libc/include/wchar.h @@ -0,0 +1,7 @@ +#pragma once +#include <bits/panic.h> + +static inline size_t mbstowcs(wchar_t *dst, const char *src, size_t n) { + (void)dst; (void)src; (void)n; + __libc_panic("unimplemented"); +} diff --git a/src/libc/printf.c b/src/libc/printf.c index ad1fd06..a760240 100644 --- a/src/libc/printf.c +++ b/src/libc/printf.c @@ -44,6 +44,10 @@ int vprintf(const char *restrict fmt, va_list ap) { return vfprintf(stdout, fmt, ap); } +int vsprintf(char *restrict s, const char *restrict fmt, va_list ap) { + return vsnprintf(s, ~0, fmt, ap); +} + int _klogf(const char *fmt, ...) { char buf[256]; int ret; diff --git a/src/libc/stdio/file.c b/src/libc/stdio/file.c index efaf013..984c419 100644 --- a/src/libc/stdio/file.c +++ b/src/libc/stdio/file.c @@ -107,6 +107,10 @@ FILE *file_clone(const FILE *f, const char *mode) { return f2; } +int fileno(FILE *f) { + return f->fd; +} + // TODO popen / pclose FILE *popen(const char *cmd, const char *mode) { (void)cmd; (void)mode; @@ -170,6 +174,11 @@ size_t fread(void *restrict ptr, size_t size, size_t nitems, FILE *restrict f) { while (pos < total) { long res = 0; + if (f->pushedback) { + buf[pos++] = f->pushback; + f->pushedback = false; + continue; + } if (f->readbuf) { if (0 == f->rblen && total - pos < (f->rbcap >> 1)) { res = _sys_read(f->fd, f->readbuf, f->rbcap, f->pos); @@ -270,16 +279,21 @@ int fputc(int c, FILE *f) { } int putc(int c, FILE *f) { return fputc(c, f); } -// TODO ungetc int ungetc(int c, FILE *f) { - (void)c; (void)f; - __libc_panic("unimplemented"); + if (f->pushedback) return EOF; + f->pushedback = true; + f->pushback = c; + return c; } int fseek(FILE *f, long offset, int whence) { return fseeko(f, offset, whence); } +void rewind(FILE *f) { + fseek(f, 0, SEEK_SET); +} + int fseeko(FILE *f, off_t offset, int whence) { if (fflush(f)) return -1; @@ -306,6 +320,7 @@ int fseeko(FILE *f, off_t offset, int whence) { return -1; } f->rblen = 0; + f->pushedback = false; if (base >= 0 && base + offset < 0) { /* underflow */ diff --git a/src/libc/stdio/file.h b/src/libc/stdio/file.h index 3bd64a1..86d33c1 100644 --- a/src/libc/stdio/file.h +++ b/src/libc/stdio/file.h @@ -11,4 +11,7 @@ struct _LIBC_FILE { char *readbuf; size_t rblen, rbcap; + + bool pushedback; + char pushback; }; diff --git a/src/libc/stdlib.c b/src/libc/stdlib.c index 1739230..16c8f70 100644 --- a/src/libc/stdlib.c +++ b/src/libc/stdlib.c @@ -33,9 +33,13 @@ void setproctitle(const char *fmt, ...) { va_end(argp); } -int mkstemp(char *template) { - // TODO randomize template - hid_t h = camellia_open(template, OPEN_CREATE | OPEN_RW); +char *mktemp(char *tmpl) { + // TODO mktemp mkstemp + return tmpl; +} + +int mkstemp(char *tmpl) { + hid_t h = camellia_open(tmpl, OPEN_CREATE | OPEN_RW); if (h < 0) { errno = -h; return -1; @@ -65,6 +69,10 @@ int atoi(const char *s) { return strtol(s, NULL, 10); } +long atol(const char *s) { + return strtol(s, NULL, 10); +} + double atof(const char *s) { (void)s; __libc_panic("unimplemented"); @@ -141,8 +149,3 @@ double strtod(const char *restrict s, char **restrict end) { (void)s; (void)end; __libc_panic("unimplemented"); } - -void qsort(void *base, size_t nmemb, size_t size, int (*cmp)(const void *a, const void *b)) { - (void)base; (void)nmemb; (void)size; (void)cmp; - __libc_panic("unimplemented"); -} diff --git a/src/libc/string/string.c b/src/libc/string/string.c index c65d7c5..ac1c757 100644 --- a/src/libc/string/string.c +++ b/src/libc/string/string.c @@ -1,3 +1,4 @@ +#include <bits/panic.h> #include <ctype.h> #include <errno.h> #include <stdlib.h> @@ -79,10 +80,15 @@ char *strstr(const char *s1, const char *s2) { return NULL; } +char *strcat(char *restrict dst, const char *restrict src) { + return strcpy(dst + strlen(dst), src); +} + char *strcpy(char *restrict s1, const char *restrict s2) { + char *ret = s1; while (*s2) *s1++ = *s2++; *s1 = *s2; - return s1; + return ret; } char *strncpy(char *restrict dst, const char *restrict src, size_t n) { @@ -93,6 +99,11 @@ char *strncpy(char *restrict dst, const char *restrict src, size_t n) { return dst; } +char *strncat(char *restrict dst, const char *restrict src, size_t n) { + (void)dst; (void)src; (void)n; + __libc_panic("unimplemented"); +} + char *stpncpy(char *restrict dst, const char *restrict src, size_t n) { return stpncpy(dst, src, n) + n; } diff --git a/src/libc/syswait.c b/src/libc/syswait.c index ce80c7b..43c20ae 100644 --- a/src/libc/syswait.c +++ b/src/libc/syswait.c @@ -5,6 +5,10 @@ #include <sys/resource.h> #include <sys/wait.h> +pid_t wait(int *wstatus) { + return wait3(wstatus, 0, NULL); +} + pid_t wait3(int *wstatus, int opts, struct rusage *rusage) { struct sys_wait2 res; if (opts || rusage) { diff --git a/src/libc/time.c b/src/libc/time.c index 4709ecd..c7d66bf 100644 --- a/src/libc/time.c +++ b/src/libc/time.c @@ -1,5 +1,6 @@ #include <errno.h> #include <time.h> +#include <utime.h> // TODO time time_t time(time_t *tloc) { @@ -34,6 +35,11 @@ double difftime(time_t time1, time_t time0) { return 0; } +char *ctime(const time_t *timep) { + (void)timep; + return "THE FUTURE"; +} + size_t strftime( char *restrict s, size_t maxsize, const char *restrict format, const struct tm *restrict timeptr) @@ -41,3 +47,9 @@ size_t strftime( (void)s; (void)maxsize; (void)format; (void)timeptr; return 0; } + +int utime(const char *fn, const struct utimbuf *times) { + (void)fn; (void)times; + errno = ENOSYS; + return -1; +} diff --git a/src/libc/unistd.c b/src/libc/unistd.c index 578cadc..549da89 100644 --- a/src/libc/unistd.c +++ b/src/libc/unistd.c @@ -51,6 +51,11 @@ int unlink(const char *path) { return 0; } +int rmdir(const char *path) { + (void)path; + __libc_panic("unimplemented"); +} + int symlink(const char *path1, const char *path2) { (void)path1; (void)path2; errno = ENOSYS; @@ -67,6 +72,11 @@ int execv(const char *path, char *const argv[]) { return execve(path, argv, NULL); } +int execvp(const char *path, char *const argv[]) { + // TODO execvp + return execve(path, argv, NULL); +} + int execve(const char *path, char *const argv[], char *const envp[]) { FILE *file = fopen(path, "e"); char hdr[4] = {0}; @@ -160,6 +170,12 @@ uid_t geteuid(void) { return 0; } gid_t getgid(void) { return 0; } gid_t getegid(void) { return 0; } +int access(const char *path, int mode) { + // TODO impl access() + (void)path; (void)mode; + return 0; +} + int chown(const char *path, uid_t owner, gid_t group) { (void)path; (void)owner; (void)group; errno = ENOSYS; @@ -213,11 +229,21 @@ int pipe(int pipefd[2]) { __libc_panic("unimplemented"); } +int dup(int oldfd) { + (void)oldfd; + __libc_panic("unimplemented"); +} + int dup2(int oldfd, int newfd) { (void)oldfd; (void)newfd; __libc_panic("unimplemented"); } +unsigned int sleep(unsigned int seconds) { + _sys_sleep(seconds * 1000); + return 0; +} + size_t absolutepath(char *out, const char *in, size_t size) { const char *realcwd = getrealcwd(); size_t len, pos = 0; diff --git a/src/libc/vendor/sortix/bsearch.c b/src/libc/vendor/sortix/bsearch.c new file mode 100644 index 0000000..028e08a --- /dev/null +++ b/src/libc/vendor/sortix/bsearch.c @@ -0,0 +1,70 @@ +/* + * Copyright (c) 2012, 2016 Jonas 'Sortie' Termansen. + * + * Permission to use, copy, modify, and 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. + * + * THE 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. + * + * stdlib/bsearch.c + * Binary search. + */ + +#include <stdint.h> +#include <stdlib.h> + +/* + * Semantics of binary search: + * + * bsearch(key, base, 0, size, compare) may return NULL. + * + * If 0 <= i < nmemb + * and ptr = base + size * i + * and compare(key, ptr) = 0 then + * bsearch(key, base, nmemb, size, compare) may return ptr. + * + * If 0 <= i < nmemb + * and ptr = base + size * i + * and compare(key, ptr) < 0 then + * bsearch(key, base, nmemb, size, compare) may return + * bsearch(key, base, i, size, compare). + * + * If 0 <= i < nmemb + * and ptr = base + size * i + * and compare(key, ptr) > 0 then + * bsearch(key, base, nmemb, size, compare) may return + * bsearch(key, base + size * (i + 1), nemb - (i + 1), size, compare). + */ + +void* bsearch(const void* key, + const void* base_ptr, + size_t nmemb, + size_t size, + int (*compare)(const void*, const void*)) +{ + const unsigned char* base = (const unsigned char*) base_ptr; + while ( nmemb ) + { + size_t i = nmemb / 2; + const unsigned char* candidate = base + i * size; + int rel = compare(key, candidate); + if ( rel < 0 ) /* key smaller than candidate */ + nmemb = i; + else if ( 0 < rel ) /* key greater than candidate */ + { + base = candidate + size; + nmemb -= i + 1; + } + else /* key equal to candidate */ + return (void*) candidate; + } + return NULL; +} + diff --git a/src/libc/vendor/sortix/qsort.c b/src/libc/vendor/sortix/qsort.c new file mode 100644 index 0000000..feef9ea --- /dev/null +++ b/src/libc/vendor/sortix/qsort.c @@ -0,0 +1,35 @@ +/* + * Copyright (c) 2012, 2014 Jonas 'Sortie' Termansen. + * + * Permission to use, copy, modify, and 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. + * + * THE 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. + * + * stdlib/qsort.c + * Sort an array. + */ + +#include <stdint.h> +#include <stdlib.h> +#include <string.h> + +static int compare_wrapper(const void* a, const void* b, void* arg) +{ + return ((int (*)(const void*, const void*)) arg)(a, b); +} + +void qsort(void* base_ptr, + size_t num_elements, + size_t element_size, + int (*compare)(const void*, const void*)) +{ + qsort_r(base_ptr, num_elements, element_size, compare_wrapper, (void*) compare); +} diff --git a/src/libc/vendor/sortix/qsort_r.c b/src/libc/vendor/sortix/qsort_r.c new file mode 100644 index 0000000..8aff807 --- /dev/null +++ b/src/libc/vendor/sortix/qsort_r.c @@ -0,0 +1,146 @@ +/* + * Copyright (c) 2012, 2014, 2021 Jonas 'Sortie' Termansen. + * Copyright (c) 2021 Juhani 'nortti' Krekelä. + * + * Permission to use, copy, modify, and 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. + * + * THE 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. + * + * stdlib/qsort_r.c + * Sort an array. Implemented using heapsort, which is not a stable sort. + */ + +#include <stdbool.h> +#include <stdlib.h> + +static void memswap(unsigned char* a, unsigned char* b, size_t size) +{ + unsigned char tmp; + for ( size_t i = 0; i < size; i++ ) + { + tmp = a[i]; + a[i] = b[i]; + b[i] = tmp; + } +} + +static unsigned char* array_index(unsigned char* base, + size_t element_size, + size_t index) +{ + return base + element_size * index; +} + +void qsort_r(void* base_ptr, + size_t num_elements, + size_t element_size, + int (*compare)(const void*, const void*, void*), + void* arg) +{ + unsigned char* base = base_ptr; + + if ( !element_size || num_elements < 2 ) + return; + + // Incrementally left-to-right transform the array into a max-heap, where + // each element has up to two children that aren't bigger than the element. + for ( size_t i = 0; i < num_elements; i++ ) + { + // Grow the heap by inserting another element into it (implicit, done by + // moving the boundary between the heap and the yet-to-be-processed + // array elements) and swapping it up the parent chain as long as it's + // bigger than its parent. + size_t element = i; + while ( element > 0 ) + { + unsigned char* ptr = array_index(base, element_size, element); + size_t parent = (element - 1) / 2; + unsigned char* parent_ptr = array_index(base, element_size, parent); + if ( compare(parent_ptr, ptr, arg) < 0 ) + { + memswap(parent_ptr, ptr, element_size); + element = parent; + } + else + break; + } + } + + // The array is split into two sections, first the max-heap and then the + // part of the array that has been sorted. + // Sorting progresses right-to-left, taking the biggest value of the heap + // (at its root), swapping it with the last element of the heap, and + // adjusting the boundary between the two sections such that the old biggest + // value is now part of the sorted section. + // After this, the max-heap property is restored by swapping the old last + // element down as long as it's smaller than one of its children. + for ( size_t size = num_elements; --size; ) + { + memswap(array_index(base, element_size, size), base, element_size); + + size_t first_without_left = size / 2; + size_t first_without_right = (size - 1) / 2; + + size_t element = 0; + while ( element < size ) + { + unsigned char* ptr = array_index(base, element_size, element); + + size_t left = 2 * element + 1; + unsigned char* left_ptr = NULL; + bool left_bigger = false; + if ( element < first_without_left ) + { + left_ptr = array_index(base, element_size, left); + left_bigger = compare(ptr, left_ptr, arg) < 0; + } + + size_t right = 2 * element + 2; + unsigned char* right_ptr = NULL; + bool right_bigger = false; + if ( element < first_without_right ) + { + right_ptr = array_index(base, element_size, right); + right_bigger = compare(ptr, right_ptr, arg) < 0; + } + + if ( left_bigger && right_bigger ) + { + // If both the left and right child are bigger than the element, + // then swap the element with whichever of the left and right + // child is bigger. + if ( compare(left_ptr, right_ptr, arg) < 0 ) + { + memswap(ptr, right_ptr, element_size); + element = right; + } + else + { + memswap(ptr, left_ptr, element_size); + element = left; + } + } + else if ( left_bigger ) + { + memswap(ptr, left_ptr, element_size); + element = left; + } + else if ( right_bigger ) + { + memswap(ptr, right_ptr, element_size); + element = right; + } + else + break; + } + } +} + diff --git a/src/libk/include/assert.h b/src/libk/include/assert.h index 7520aa9..affe1dc 100644 --- a/src/libk/include/assert.h +++ b/src/libk/include/assert.h @@ -1,7 +1,12 @@ #ifdef NDEBUG -#define assert(stmt) do {} while (0) +#define assert(stmt) ((void)0) #else -#define assert(stmt) do { if (!(stmt)) __badassert(__func__, __FILE__, __LINE__); } while (0) +#define assert(stmt) (void)((stmt) || (__badassert(__func__, __FILE__, __LINE__),0)) +#endif + +#ifdef __SPARSE +#undef assert +#define assert(stmt) (0) #endif _Noreturn void __badassert(const char *func, const char *file, int line); diff --git a/src/libk/include/camellia/errno.h b/src/libk/include/camellia/errno.h index 1177f54..e148b40 100644 --- a/src/libk/include/camellia/errno.h +++ b/src/libk/include/camellia/errno.h @@ -26,3 +26,6 @@ #define EWOULDBLOCK 206 #define EEXIST 207 #define EAGAIN 208 +#define EIO 209 +#define EDOM 210 /* domain error */ +#define EFBIG 211 /* file too large */ |