diff options
Diffstat (limited to 'semestr-5/so/lista5')
| -rw-r--r-- | semestr-5/so/lista5/so21_lista_5.pdf | bin | 0 -> 277248 bytes | |||
| -rw-r--r-- | semestr-5/so/lista5/so21_lista_5.tar.gz | bin | 0 -> 45364 bytes | |||
| -rw-r--r-- | semestr-5/so/lista5/so21_lista_5/Makefile.include | 105 | ||||
| -rwxr-xr-x | semestr-5/so/lista5/so21_lista_5/gen-nums.py | 11 | ||||
| -rw-r--r-- | semestr-5/so/lista5/so21_lista_5/include/bitstring.h | 138 | ||||
| -rw-r--r-- | semestr-5/so/lista5/so21_lista_5/include/csapp.h | 240 | ||||
| -rw-r--r-- | semestr-5/so/lista5/so21_lista_5/include/queue.h | 587 | ||||
| -rw-r--r-- | semestr-5/so/lista5/so21_lista_5/include/rio.h | 27 | ||||
| -rw-r--r-- | semestr-5/so/lista5/so21_lista_5/include/terminal.h | 27 | ||||
| -rw-r--r-- | semestr-5/so/lista5/so21_lista_5/include/tree.h | 735 | ||||
| -rw-r--r-- | semestr-5/so/lista5/so21_lista_5/listdir.c | 118 | ||||
| -rw-r--r-- | semestr-5/so/lista5/so21_lista_5/mergesort.c | 141 | ||||
| -rw-r--r-- | semestr-5/so/lista5/so21_lista_5/prime.c | 97 |
13 files changed, 2226 insertions, 0 deletions
diff --git a/semestr-5/so/lista5/so21_lista_5.pdf b/semestr-5/so/lista5/so21_lista_5.pdf Binary files differnew file mode 100644 index 0000000..dbc63d2 --- /dev/null +++ b/semestr-5/so/lista5/so21_lista_5.pdf diff --git a/semestr-5/so/lista5/so21_lista_5.tar.gz b/semestr-5/so/lista5/so21_lista_5.tar.gz Binary files differnew file mode 100644 index 0000000..125e8b8 --- /dev/null +++ b/semestr-5/so/lista5/so21_lista_5.tar.gz diff --git a/semestr-5/so/lista5/so21_lista_5/Makefile.include b/semestr-5/so/lista5/so21_lista_5/Makefile.include new file mode 100644 index 0000000..196c9a5 --- /dev/null +++ b/semestr-5/so/lista5/so21_lista_5/Makefile.include @@ -0,0 +1,105 @@ +CC = gcc -g +CFLAGS = -Og -Wall -Werror -Wstrict-prototypes +AS = as -g +ASFLAGS = +CPPFLAGS = -Iinclude +LDLIBS = -Llibcsapp -lcsapp +SED = sed + +# Recognize operating system +ifeq ($(shell uname -s), Darwin) +CPPFLAGS += -DMACOS +SED = gsed +endif + +ifeq ($(shell uname -s), Linux) +CPPFLAGS += -DLINUX +endif + +ifeq ($(shell uname -s), FreeBSD) +CPPFLAGS += -DFREEBSD +endif + +# Pass "VERBOSE=1" at command line to display command being invoked by GNU Make +ifneq ($(VERBOSE), 1) +.SILENT: +endif + +LIBSRC_C = $(wildcard libcsapp/*.c) +LIBSRC_S = $(wildcard libcsapp/*.s) +LIBSRC_H = $(wildcard include/*.h) +LIBSRCS = $(LIBSRC_C) $(LIBSRC_S) $(LIBSRC_H) +LIBOBJS = $(LIBSRC_C:%.c=%.o) +ifneq ($(shell uname -s), Darwin) +LIBOBJS += $(LIBSRC_S:%.s=%.o) +endif +LIB = libcsapp/libcsapp.a + +SRC_C = $(wildcard *.c) +SRC_S = $(wildcard *.s) +SRC_H = $(wildcard *.h) +SRCS = $(SRC_C) $(SRC_S) +OBJS = $(SRC_C:%.c=%.o) + +SOURCES = $(SRCS) $(LIBSRCS) +OBJECTS = $(OBJS) $(LIBOBJS) +DEPFILES = $(foreach f,$(SRC_C) $(LIBSRC_C),\ + $(dir $(f))$(patsubst %.c,.%.d,$(notdir $(f)))) + +ARCHIVE = so$(shell date +'%y')_$(shell basename $(PWD)) +FILES = Makefile Makefile.include $(EXTRA-FILES) + +all: $(DEPFILES) $(LIB) $(PROGS) + +$(LIB): $(LIBOBJS) + +# Generate dependencies automatically +ifeq ($(words $(findstring $(MAKECMDGOALS), archive clean)), 0) + -include $(DEPFILES) +endif + +# Disable all built-in recipes and define our own +.SUFFIXES: + +.%.d: %.c + $(CC) $(CPPFLAGS) -MM -MG -o $@ $< + +%.o: %.c .%.d + @echo "[CC] $@ <- $<" + $(CC) $(CPPFLAGS) $(CFLAGS) -c -o $@ $< + +%.o: %.s + @echo "[AS] $@ <- $<" + $(AS) $(ASFLAGS) -c -o $@ $< + +%.a: + @echo "[AR] $@ <- $^" + $(AR) rc $@ $^ + +%: %.o $(LIB) + @echo "[LD] $@ <- $^" + $(CC) $(LDFLAGS) -o $@ $^ $(LDLIBS) + +clean: + rm -vf $(PROGS) $(OBJECTS) $(DEPFILES) $(LIB) + rm -vf $(shell find -L . -iname '*~') + rm -vf $(ARCHIVE).tar.gz + rm -vrf $(EXTRA-CLEAN) *.dSYM + +format: + clang-format --style=file -i $(LIBSRC_C) $(LIBSRC_H) $(SRC_C) $(SRC_H) + +archive: clean + mkdir -p $(ARCHIVE) $(ARCHIVE)/libcsapp $(ARCHIVE)/include + cp -L $(SRCS) $(SRC_H) $(FILES) $(ARCHIVE)/ + cp -L $(LIBSRCS) $(ARCHIVE)/libcsapp/ + cp -L $(LIBSRC_H) $(ARCHIVE)/include/ + for f in $(SRCS:%=$(ARCHIVE)/%); do \ + $(SED) --in-place='' -e '/^#if.*STUDENT/,/^#endif.*STUDENT/d' $$f; \ + done + tar cvzhf $(ARCHIVE).tar.gz $(ARCHIVE) + rm -rf $(ARCHIVE) + +.PHONY: all clean format archive + +# vim: ts=8 sw=8 noet diff --git a/semestr-5/so/lista5/so21_lista_5/gen-nums.py b/semestr-5/so/lista5/so21_lista_5/gen-nums.py new file mode 100755 index 0000000..06c7522 --- /dev/null +++ b/semestr-5/so/lista5/so21_lista_5/gen-nums.py @@ -0,0 +1,11 @@ +#!/usr/bin/env python3 + +import random +import sys + + +if __name__ == '__main__': + nelem = int(sys.argv[1]) + print(nelem) + for i in range(nelem): + print(random.randint(-nelem * 10, nelem * 10)) diff --git a/semestr-5/so/lista5/so21_lista_5/include/bitstring.h b/semestr-5/so/lista5/so21_lista_5/include/bitstring.h new file mode 100644 index 0000000..66503f0 --- /dev/null +++ b/semestr-5/so/lista5/so21_lista_5/include/bitstring.h @@ -0,0 +1,138 @@ +/* $NetBSD: bitstring.h,v 1.14 2016/03/17 02:25:32 christos Exp $ */ + +/* + * Copyright (c) 1989, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Paul Vixie. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)bitstring.h 8.1 (Berkeley) 7/19/93 + */ + +#ifndef _BITSTRING_H_ +#define _BITSTRING_H_ + +/* modified for SV/AT and bitstring bugfix by M.R.Murphy, 11oct91 + * bitstr_size changed gratuitously, but shorter + * bit_alloc spelling error fixed + * the following were efficient, but didn't work, they've been made to + * work, but are no longer as efficient :-) + * bit_nclear, bit_nset, bit_ffc, bit_ffs + */ +/* + * The comment above may or may not bear any resemblance to reality. + * This code has been maintained in a confusing way, with little + * information available on the provenance of much of it. "At least it + * works." + * /s/ Perry E. Metzger, 2 Feb 98 + */ +typedef unsigned char bitstr_t; + +/* internal macros */ +/* byte of the bitstring bit is in */ +#define _bit_byte(bit) (uint32_t)((bit) >> 3) + +/* mask for the bit within its byte */ +#define _bit_mask(bit) (uint32_t)((1 << (uint32_t)((bit)&0x7))) + +/* external macros */ +/* bytes in a bitstring of nbits bits */ +#define bitstr_size(nbits) (size_t)((uint32_t)((nbits) + 7) >> 3) + +/* allocate a bitstring */ +#define bit_alloc(nbits) calloc(bitstr_size(nbits), sizeof(bitstr_t)) + +/* allocate a bitstring on the stack */ +#define bit_decl(name, nbits) ((name)[bitstr_size(nbits)]) + +/* is bit N of bitstring name set? */ +#define bit_test(name, bit) \ + /*LINTED bitwise on signed*/ ((name)[_bit_byte(bit)] & _bit_mask(bit)) + +/* set bit N of bitstring name */ +#define bit_set(name, bit) \ + /*LINTED bitwise on signed*/ \ + ((name)[_bit_byte(bit)] = \ + (unsigned char)(_bit_mask(bit) | (name)[_bit_byte(bit)])) + +/* clear bit N of bitstring name */ +#define bit_clear(name, bit) \ + /*LINTED bitwise on signed*/ \ + ((name)[_bit_byte(bit)] &= (unsigned char)~_bit_mask(bit)) + +/* clear bits start ... stop in bitstring */ +#define bit_nclear(name, start, stop) \ + do { \ + bitstr_t *_name = name; \ + size_t _start = start, _stop = stop; \ + while (_start <= _stop) { \ + bit_clear(_name, _start); \ + _start++; \ + } \ + } while (/*CONSTCOND*/ 0) + +/* set bits start ... stop in bitstring */ +#define bit_nset(name, start, stop) \ + do { \ + bitstr_t *_name = name; \ + size_t _start = start, _stop = stop; \ + while (_start <= _stop) { \ + bit_set(_name, _start); \ + _start++; \ + } \ + } while (/*CONSTCOND*/ 0) + +/* find first bit clear in name */ +#define bit_ffc(name, nbits, value) \ + do { \ + const bitstr_t *_name = name; \ + size_t _bit, _nbits = nbits; \ + int _value = -1; \ + for (_bit = 0; _bit < _nbits; ++_bit) \ + if (!bit_test(_name, _bit)) { \ + _value = _bit; \ + break; \ + } \ + *(value) = _value; \ + } while (/*CONSTCOND*/ 0) + +/* find first bit set in name */ +#define bit_ffs(name, nbits, value) \ + do { \ + const bitstr_t *_name = name; \ + size_t _bit, _nbits = nbits; \ + int _value = -1; \ + for (_bit = 0; _bit < _nbits; ++_bit) \ + if (bit_test(_name, _bit)) { \ + _value = _bit; \ + break; \ + } \ + *(value) = _value; \ + } while (/*CONSTCOND*/ 0) + +#endif /* !_BITSTRING_H_ */ diff --git a/semestr-5/so/lista5/so21_lista_5/include/csapp.h b/semestr-5/so/lista5/so21_lista_5/include/csapp.h new file mode 100644 index 0000000..dabdf77 --- /dev/null +++ b/semestr-5/so/lista5/so21_lista_5/include/csapp.h @@ -0,0 +1,240 @@ +#ifndef __CSAPP_H__ +#define __CSAPP_H__ + +#include <sys/types.h> +#include <sys/mman.h> +#ifdef LINUX +#include <sys/sysmacros.h> +#include <sys/prctl.h> +#endif +#include <sys/select.h> +#include <sys/socket.h> +#include <sys/stat.h> +#include <sys/time.h> +#include <sys/uio.h> +#include <sys/user.h> +#include <sys/wait.h> +#include <arpa/inet.h> +#include <assert.h> +#include <ctype.h> +#include <errno.h> +#include <fcntl.h> +#include <grp.h> +#include <limits.h> +#include <netdb.h> +#include <netinet/in.h> +#include <poll.h> +#include <pthread.h> +#include <pwd.h> +#include <semaphore.h> +#include <setjmp.h> +#include <signal.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <stdbool.h> +#include <stdnoreturn.h> +#include <string.h> +#include <termios.h> +#include <time.h> +#include <unistd.h> + +#define _CONCAT(x, y) x##y +#define CONCAT(x, y) _CONCAT(x, y) + +#define min(a, b) \ + ({ \ + typeof(a) _a = (a); \ + typeof(b) _b = (b); \ + _a < _b ? _a : _b; \ + }) + +#define max(a, b) \ + ({ \ + typeof(a) _a = (a); \ + typeof(b) _b = (b); \ + _a > _b ? _a : _b; \ + }) + +#ifndef powerof2 +#define powerof2(x) (((x) & ((x)-1)) == 0) +#endif + +#ifndef __unused +#define __unused __attribute__((unused)) +#endif + +extern char **environ; + +/* Useful constants. */ +#define MAXLINE 4096 + +/* Our own error-handling functions */ +noreturn void unix_error(const char *fmt, ...) + __attribute__((format(printf, 1, 2))); +noreturn void posix_error(int code, const char *fmt, ...) + __attribute__((format(printf, 2, 3))); +noreturn void app_error(const char *fmt, ...) + __attribute__((format(printf, 1, 2))); +noreturn void gai_error(int code, const char *fmt, ...) + __attribute__((format(printf, 2, 3))); + +/* Signal safe I/O functions */ +void safe_printf(const char *fmt, ...) __attribute__((format(printf, 1, 2))); +void safe_error(const char *fmt, ...) __attribute__((format(printf, 1, 2))); + +/* Decent hashing function. */ +#define HASHINIT 5381 + +uint32_t jenkins_hash(const void *key, size_t length, uint32_t initval); + +/* Memory allocation wrappers */ +void *Malloc(size_t size); +void *Realloc(void *ptr, size_t size); +void *Calloc(size_t nmemb, size_t size); + +/* Process control wrappers */ +pid_t Fork(void); +pid_t Waitpid(pid_t pid, int *iptr, int options); +#define Wait(iptr) Waitpid(-1, iptr, 0) +void Prctl(int option, long arg); + +/* Process environment */ +char *Getcwd(char *buf, size_t buflen); + +/* Signal control wrappers */ +void (*Signal(int sig, void (*func)(int)))(int); +void Kill(pid_t pid, int sig); +void Sigprocmask(int how, const sigset_t *set, sigset_t *oldset); +void Sigaction(int signum, const struct sigaction *act, + struct sigaction *oldact); +void Sigsuspend(const sigset_t *mask); + +/* Process group control wrappers */ +void Setpgid(pid_t pid, pid_t pgid); + +/* Stdio wrappers */ +char *Fgets(char *ptr, int n, FILE *stream); +void Fputs(const char *ptr, FILE *stream); + +/* Unix I/O wrappers */ +int Open(const char *pathname, int flags, mode_t mode); +size_t Read(int fd, void *buf, size_t count); +size_t Write(int fd, const void *buf, size_t count); +size_t Writev(int fd, const struct iovec *iov, int iovcnt); +off_t Lseek(int fildes, off_t offset, int whence); +void Close(int fd); +void Ftruncate(int fd, off_t length); +int Dup(int fd); +int Dup2(int oldfd, int newfd); +void Pipe(int fds[2]); +void Socketpair(int domain, int type, int protocol, int sv[2]); +int Select(int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, + struct timeval *timeout); +int Poll(struct pollfd *fds, nfds_t nfds, int timeout); + +/* Directory access (Linux specific) */ +struct linux_dirent { + unsigned long d_ino; /* Inode number */ + unsigned long d_off; /* Offset to next linux_dirent */ + unsigned short d_reclen; /* Length of this linux_dirent */ + char d_name[]; /* Filename (null-terminated) */ +}; + +int Getdents(int fd, struct linux_dirent *dirp, unsigned count); + +/* Directory operations */ +void Rename(const char *oldpath, const char *newpath); +void Unlink(const char *pathname); + +/* File metadata access wrapper */ +void Fstat(int fd, struct stat *statbuf); +void Fstatat(int dirfd, const char *pathname, struct stat *statbuf, int flags); +size_t Readlink(const char *pathname, char *buf, size_t bufsiz); +size_t Readlinkat(int dirfd, const char *pathname, char *buf, size_t bufsiz); + +/* Memory mapped files & anonymous memory */ +void *Mmap(void *addr, size_t length, int prot, int flags, int fd, + off_t offset); +void Mprotect(void *addr, size_t len, int prot); +void Munmap(void *addr, size_t len); +void Madvise(void *addr, size_t length, int advice); + +/* Terminal control */ +void Tcsetpgrp(int fd, pid_t pgrp); +pid_t Tcgetpgrp(int fd); +void Tcsetattr(int fd, int action, const struct termios *termios_p); +void Tcgetattr(int fd, struct termios *termios_p); + +/* Setjmp & longjmp implementation without sigprocmask */ +typedef struct { + long rbx; + long rbp; + long r12; + long r13; + long r14; + long r15; + void *rsp; + void *rip; +} Jmpbuf[1]; + +int Setjmp(Jmpbuf env); +noreturn void Longjmp(Jmpbuf env, int val); + +/* Socket interface wrappers. */ +typedef struct sockaddr SA; +int Socket(int domain, int type, int protocol); +void Setsockopt(int s, int level, int optname, const void *optval, int optlen); +void Bind(int sockfd, struct sockaddr *my_addr, int addrlen); +void Listen(int s, int backlog); +int Accept(int s, struct sockaddr *addr, socklen_t *addrlen); +void Connect(int sockfd, struct sockaddr *serv_addr, int addrlen); + +/* Protocol-independent wrappers. */ +void Getaddrinfo(const char *node, const char *service, + const struct addrinfo *hints, struct addrinfo **res); +void Getnameinfo(const struct sockaddr *sa, socklen_t salen, char *host, + size_t hostlen, char *serv, size_t servlen, int flags); +int open_clientfd(char *hostname, char *port); +int Open_clientfd(char *hostname, char *port); +int open_listenfd(char *port, int backlog); +int Open_listenfd(char *port, int backlog); + +/* POSIX thread control wrappers. */ + +void Pthread_create(pthread_t *tidp, pthread_attr_t *attrp, + void *(*routine)(void *), void *argp); +void Pthread_cancel(pthread_t tid); +void Pthread_join(pthread_t tid, void **thread_return); +void Pthread_detach(pthread_t tid); + +/* POSIX semaphore wrappers. */ +void Sem_init(sem_t *sem, int pshared, unsigned value); +void Sem_destroy(sem_t *sem); +void Sem_wait(sem_t *sem); +void Sem_getvalue(sem_t *sem, int *sval); +void Sem_post(sem_t *sem); + +/* POSIX mutex wrappers. */ +void Pthread_mutex_init(pthread_mutex_t *mutex, + const pthread_mutexattr_t *mutexattr); +void Pthread_mutex_destroy(pthread_mutex_t *mutex); +void Pthread_mutex_lock(pthread_mutex_t *mutex); +void Pthread_mutex_unlock(pthread_mutex_t *mutex); + +/* POSIX conditional variable wrappers. */ +void Pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *cond_attr); +void Pthread_cond_destroy(pthread_cond_t *cond); +void Pthread_cond_signal(pthread_cond_t *cond); +void Pthread_cond_broadcast(pthread_cond_t *cond); +void Pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex); + +/* POSIX reader-writer lock wrappers. */ +void Pthread_rwlock_init(pthread_rwlock_t *rwlock, + const pthread_rwlockattr_t *rwlockattr); +void Pthread_rwlock_destroy(pthread_rwlock_t *rwlock); +void Pthread_rwlock_rdlock(pthread_rwlock_t *rwlock); +void Pthread_rwlock_wrlock(pthread_rwlock_t *rwlock); +void Pthread_rwlock_unlock(pthread_rwlock_t *rwlock); + +#endif /* __CSAPP_H__ */ diff --git a/semestr-5/so/lista5/so21_lista_5/include/queue.h b/semestr-5/so/lista5/so21_lista_5/include/queue.h new file mode 100644 index 0000000..de4ddc9 --- /dev/null +++ b/semestr-5/so/lista5/so21_lista_5/include/queue.h @@ -0,0 +1,587 @@ +/* $NetBSD: queue.h,v 1.74 2019/03/23 12:01:18 maxv Exp $ */ + +/* + * Copyright (c) 1991, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)queue.h 8.5 (Berkeley) 8/20/94 + */ + +#ifndef _QUEUE_H_ +#define _QUEUE_H_ + +/* + * This file defines five types of data structures: singly-linked lists, + * lists, simple queues, tail queues, and circular queues. + * + * A singly-linked list is headed by a single forward pointer. The + * elements are singly linked for minimum space and pointer manipulation + * overhead at the expense of O(n) removal for arbitrary elements. New + * elements can be added to the list after an existing element or at the + * head of the list. Elements being removed from the head of the list + * should use the explicit macro for this purpose for optimum + * efficiency. A singly-linked list may only be traversed in the forward + * direction. Singly-linked lists are ideal for applications with large + * datasets and few or no removals or for implementing a LIFO queue. + * + * A list is headed by a single forward pointer (or an array of forward + * pointers for a hash table header). The elements are doubly linked + * so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before + * or after an existing element or at the head of the list. A list + * may only be traversed in the forward direction. + * + * A simple queue is headed by a pair of pointers, one the head of the + * list and the other to the tail of the list. The elements are singly + * linked to save space, so elements can only be removed from the + * head of the list. New elements can be added to the list after + * an existing element, at the head of the list, or at the end of the + * list. A simple queue may only be traversed in the forward direction. + * + * A tail queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or + * after an existing element, at the head of the list, or at the end of + * the list. A tail queue may be traversed in either direction. + * + * A circle queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or after + * an existing element, at the head of the list, or at the end of the list. + * A circle queue may be traversed in either direction, but has a more + * complex end of list detection. + * + * For details on the use of these macros, see the queue(3) manual page. + */ + +/* + * Include the definition of NULL only on NetBSD because sys/null.h + * is not available elsewhere. This conditional makes the header + * portable and it can simply be dropped verbatim into any system. + * The caveat is that on other systems some other header + * must provide NULL before the macros can be used. + */ + +/* + * Singly-linked List definitions. + */ +#define SLIST_HEAD(name, type) \ + struct name { \ + struct type *slh_first; /* first element */ \ + } + +#define SLIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define SLIST_ENTRY(type) \ + struct { \ + struct type *sle_next; /* next element */ \ + } + +/* + * Singly-linked List access methods. + */ +#define SLIST_FIRST(head) ((head)->slh_first) +#define SLIST_END(head) NULL +#define SLIST_EMPTY(head) ((head)->slh_first == NULL) +#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) + +#define SLIST_FOREACH(var, head, field) \ + for ((var) = (head)->slh_first; (var) != SLIST_END(head); \ + (var) = (var)->field.sle_next) + +#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = SLIST_FIRST((head)); \ + (var) != SLIST_END(head) && ((tvar) = SLIST_NEXT((var), field), 1); \ + (var) = (tvar)) + +/* + * Singly-linked List functions. + */ +#define SLIST_INIT(head) \ + do { \ + (head)->slh_first = SLIST_END(head); \ + } while (/*CONSTCOND*/ 0) + +#define SLIST_INSERT_AFTER(slistelm, elm, field) \ + do { \ + (elm)->field.sle_next = (slistelm)->field.sle_next; \ + (slistelm)->field.sle_next = (elm); \ + } while (/*CONSTCOND*/ 0) + +#define SLIST_INSERT_HEAD(head, elm, field) \ + do { \ + (elm)->field.sle_next = (head)->slh_first; \ + (head)->slh_first = (elm); \ + } while (/*CONSTCOND*/ 0) + +#define SLIST_REMOVE_AFTER(slistelm, field) \ + do { \ + (slistelm)->field.sle_next = \ + SLIST_NEXT(SLIST_NEXT((slistelm), field), field); \ + } while (/*CONSTCOND*/ 0) + +#define SLIST_REMOVE_HEAD(head, field) \ + do { \ + (head)->slh_first = (head)->slh_first->field.sle_next; \ + } while (/*CONSTCOND*/ 0) + +#define SLIST_REMOVE(head, elm, type, field) \ + do { \ + if ((head)->slh_first == (elm)) { \ + SLIST_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = (head)->slh_first; \ + while (curelm->field.sle_next != (elm)) \ + curelm = curelm->field.sle_next; \ + curelm->field.sle_next = curelm->field.sle_next->field.sle_next; \ + } \ + } while (/*CONSTCOND*/ 0) + +/* + * List definitions. + */ +#define LIST_HEAD(name, type) \ + struct name { \ + struct type *lh_first; /* first element */ \ + } + +#define LIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define LIST_ENTRY(type) \ + struct { \ + struct type *le_next; /* next element */ \ + struct type **le_prev; /* address of previous next element */ \ + } + +/* + * List access methods. + */ +#define LIST_FIRST(head) ((head)->lh_first) +#define LIST_END(head) NULL +#define LIST_EMPTY(head) ((head)->lh_first == LIST_END(head)) +#define LIST_NEXT(elm, field) ((elm)->field.le_next) + +#define LIST_FOREACH(var, head, field) \ + for ((var) = ((head)->lh_first); (var) != LIST_END(head); \ + (var) = ((var)->field.le_next)) + +#define LIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = LIST_FIRST((head)); \ + (var) != LIST_END(head) && ((tvar) = LIST_NEXT((var), field), 1); \ + (var) = (tvar)) + +#define LIST_MOVE(head1, head2, field) \ + do { \ + LIST_INIT((head2)); \ + if (!LIST_EMPTY((head1))) { \ + (head2)->lh_first = (head1)->lh_first; \ + (head2)->lh_first->field.le_prev = &(head2)->lh_first; \ + LIST_INIT((head1)); \ + } \ + } while (/*CONSTCOND*/ 0) + +/* + * List functions. + */ +#define LIST_INIT(head) \ + do { \ + (head)->lh_first = LIST_END(head); \ + } while (/*CONSTCOND*/ 0) + +#define LIST_INSERT_AFTER(listelm, elm, field) \ + do { \ + if (((elm)->field.le_next = (listelm)->field.le_next) != LIST_END(head)) \ + (listelm)->field.le_next->field.le_prev = &(elm)->field.le_next; \ + (listelm)->field.le_next = (elm); \ + (elm)->field.le_prev = &(listelm)->field.le_next; \ + } while (/*CONSTCOND*/ 0) + +#define LIST_INSERT_BEFORE(listelm, elm, field) \ + do { \ + (elm)->field.le_prev = (listelm)->field.le_prev; \ + (elm)->field.le_next = (listelm); \ + *(listelm)->field.le_prev = (elm); \ + (listelm)->field.le_prev = &(elm)->field.le_next; \ + } while (/*CONSTCOND*/ 0) + +#define LIST_INSERT_HEAD(head, elm, field) \ + do { \ + if (((elm)->field.le_next = (head)->lh_first) != LIST_END(head)) \ + (head)->lh_first->field.le_prev = &(elm)->field.le_next; \ + (head)->lh_first = (elm); \ + (elm)->field.le_prev = &(head)->lh_first; \ + } while (/*CONSTCOND*/ 0) + +#define LIST_REMOVE(elm, field) \ + do { \ + if ((elm)->field.le_next != NULL) \ + (elm)->field.le_next->field.le_prev = (elm)->field.le_prev; \ + *(elm)->field.le_prev = (elm)->field.le_next; \ + } while (/*CONSTCOND*/ 0) + +#define LIST_REPLACE(elm, elm2, field) \ + do { \ + if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \ + (elm2)->field.le_next->field.le_prev = &(elm2)->field.le_next; \ + (elm2)->field.le_prev = (elm)->field.le_prev; \ + *(elm2)->field.le_prev = (elm2); \ + } while (/*CONSTCOND*/ 0) + +/* + * Simple queue definitions. + */ +#define SIMPLEQ_HEAD(name, type) \ + struct name { \ + struct type *sqh_first; /* first element */ \ + struct type **sqh_last; /* addr of last next element */ \ + } + +#define SIMPLEQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).sqh_first } + +#define SIMPLEQ_ENTRY(type) \ + struct { \ + struct type *sqe_next; /* next element */ \ + } + +/* + * Simple queue access methods. + */ +#define SIMPLEQ_FIRST(head) ((head)->sqh_first) +#define SIMPLEQ_END(head) NULL +#define SIMPLEQ_EMPTY(head) ((head)->sqh_first == SIMPLEQ_END(head)) +#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) + +#define SIMPLEQ_FOREACH(var, head, field) \ + for ((var) = ((head)->sqh_first); (var) != SIMPLEQ_END(head); \ + (var) = ((var)->field.sqe_next)) + +#define SIMPLEQ_FOREACH_SAFE(var, head, field, next) \ + for ((var) = ((head)->sqh_first); \ + (var) != SIMPLEQ_END(head) && ((next = ((var)->field.sqe_next)), 1); \ + (var) = (next)) + +/* + * Simple queue functions. + */ +#define SIMPLEQ_INIT(head) \ + do { \ + (head)->sqh_first = NULL; \ + (head)->sqh_last = &(head)->sqh_first; \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_INSERT_HEAD(head, elm, field) \ + do { \ + if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ + (head)->sqh_first = (elm); \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_INSERT_TAIL(head, elm, field) \ + do { \ + (elm)->field.sqe_next = NULL; \ + *(head)->sqh_last = (elm); \ + (head)->sqh_last = &(elm)->field.sqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) \ + do { \ + if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ + (listelm)->field.sqe_next = (elm); \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_REMOVE_HEAD(head, field) \ + do { \ + if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \ + (head)->sqh_last = &(head)->sqh_first; \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_REMOVE_AFTER(head, elm, field) \ + do { \ + if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) == \ + NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_REMOVE(head, elm, type, field) \ + do { \ + if ((head)->sqh_first == (elm)) { \ + SIMPLEQ_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = (head)->sqh_first; \ + while (curelm->field.sqe_next != (elm)) \ + curelm = curelm->field.sqe_next; \ + if ((curelm->field.sqe_next = curelm->field.sqe_next->field.sqe_next) == \ + NULL) \ + (head)->sqh_last = &(curelm)->field.sqe_next; \ + } \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_CONCAT(head1, head2) \ + do { \ + if (!SIMPLEQ_EMPTY((head2))) { \ + *(head1)->sqh_last = (head2)->sqh_first; \ + (head1)->sqh_last = (head2)->sqh_last; \ + SIMPLEQ_INIT((head2)); \ + } \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_LAST(head, type, field) \ + (SIMPLEQ_EMPTY((head)) \ + ? NULL \ + : ((struct type *)(void *)((char *)((head)->sqh_last) - \ + offsetof(struct type, field)))) + +/* + * Tail queue definitions. + */ +#define _TAILQ_HEAD(name, type, qual) \ + struct name { \ + qual type *tqh_first; /* first element */ \ + qual type *qual *tqh_last; /* addr of last next element */ \ + } +#define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type, ) + +#define TAILQ_HEAD_INITIALIZER(head) \ + { TAILQ_END(head), &(head).tqh_first } + +#define _TAILQ_ENTRY(type, qual) \ + struct { \ + qual type *tqe_next; /* next element */ \ + qual type *qual *tqe_prev; /* address of previous next element */ \ + } +#define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type, ) + +/* + * Tail queue access methods. + */ +#define TAILQ_FIRST(head) ((head)->tqh_first) +#define TAILQ_END(head) (NULL) +#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) +#define TAILQ_LAST(head, headname) \ + (*(((struct headname *)(void *)((head)->tqh_last))->tqh_last)) +#define TAILQ_PREV(elm, headname, field) \ + (*(((struct headname *)(void *)((elm)->field.tqe_prev))->tqh_last)) +#define TAILQ_EMPTY(head) (TAILQ_FIRST(head) == TAILQ_END(head)) + +#define TAILQ_FOREACH(var, head, field) \ + for ((var) = ((head)->tqh_first); (var) != TAILQ_END(head); \ + (var) = ((var)->field.tqe_next)) + +#define TAILQ_FOREACH_SAFE(var, head, field, next) \ + for ((var) = ((head)->tqh_first); \ + (var) != TAILQ_END(head) && ((next) = TAILQ_NEXT(var, field), 1); \ + (var) = (next)) + +#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ + for ((var) = TAILQ_LAST((head), headname); (var) != TAILQ_END(head); \ + (var) = TAILQ_PREV((var), headname, field)) + +#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, prev) \ + for ((var) = TAILQ_LAST((head), headname); \ + (var) != TAILQ_END(head) && \ + ((prev) = TAILQ_PREV((var), headname, field), 1); \ + (var) = (prev)) + +/* + * Tail queue functions. + */ +#define TAILQ_INIT(head) \ + do { \ + (head)->tqh_first = TAILQ_END(head); \ + (head)->tqh_last = &(head)->tqh_first; \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_INSERT_HEAD(head, elm, field) \ + do { \ + if (((elm)->field.tqe_next = (head)->tqh_first) != TAILQ_END(head)) \ + (head)->tqh_first->field.tqe_prev = &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (head)->tqh_first = (elm); \ + (elm)->field.tqe_prev = &(head)->tqh_first; \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_INSERT_TAIL(head, elm, field) \ + do { \ + (elm)->field.tqe_next = TAILQ_END(head); \ + (elm)->field.tqe_prev = (head)->tqh_last; \ + *(head)->tqh_last = (elm); \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_INSERT_AFTER(head, listelm, elm, field) \ + do { \ + if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != \ + TAILQ_END(head)) \ + (elm)->field.tqe_next->field.tqe_prev = &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (listelm)->field.tqe_next = (elm); \ + (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_INSERT_BEFORE(listelm, elm, field) \ + do { \ + (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ + (elm)->field.tqe_next = (listelm); \ + *(listelm)->field.tqe_prev = (elm); \ + (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_REMOVE(head, elm, field) \ + do { \ + if (((elm)->field.tqe_next) != TAILQ_END(head)) \ + (elm)->field.tqe_next->field.tqe_prev = (elm)->field.tqe_prev; \ + else \ + (head)->tqh_last = (elm)->field.tqe_prev; \ + *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_REPLACE(head, elm, elm2, field) \ + do { \ + if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != TAILQ_END(head)) \ + (elm2)->field.tqe_next->field.tqe_prev = &(elm2)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm2)->field.tqe_next; \ + (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ + *(elm2)->field.tqe_prev = (elm2); \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_CONCAT(head1, head2, field) \ + do { \ + if (!TAILQ_EMPTY(head2)) { \ + *(head1)->tqh_last = (head2)->tqh_first; \ + (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ + (head1)->tqh_last = (head2)->tqh_last; \ + TAILQ_INIT((head2)); \ + } \ + } while (/*CONSTCOND*/ 0) + +/* + * Singly-linked Tail queue declarations. + */ +#define STAILQ_HEAD(name, type) \ + struct name { \ + struct type *stqh_first; /* first element */ \ + struct type **stqh_last; /* addr of last next element */ \ + } + +#define STAILQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).stqh_first } + +#define STAILQ_ENTRY(type) \ + struct { \ + struct type *stqe_next; /* next element */ \ + } + +/* + * Singly-linked Tail queue access methods. + */ +#define STAILQ_FIRST(head) ((head)->stqh_first) +#define STAILQ_END(head) NULL +#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) +#define STAILQ_EMPTY(head) (STAILQ_FIRST(head) == STAILQ_END(head)) + +/* + * Singly-linked Tail queue functions. + */ +#define STAILQ_INIT(head) \ + do { \ + (head)->stqh_first = NULL; \ + (head)->stqh_last = &(head)->stqh_first; \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_INSERT_HEAD(head, elm, field) \ + do { \ + if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \ + (head)->stqh_last = &(elm)->field.stqe_next; \ + (head)->stqh_first = (elm); \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_INSERT_TAIL(head, elm, field) \ + do { \ + (elm)->field.stqe_next = NULL; \ + *(head)->stqh_last = (elm); \ + (head)->stqh_last = &(elm)->field.stqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_INSERT_AFTER(head, listelm, elm, field) \ + do { \ + if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL) \ + (head)->stqh_last = &(elm)->field.stqe_next; \ + (listelm)->field.stqe_next = (elm); \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_REMOVE_HEAD(head, field) \ + do { \ + if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \ + (head)->stqh_last = &(head)->stqh_first; \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_REMOVE(head, elm, type, field) \ + do { \ + if ((head)->stqh_first == (elm)) { \ + STAILQ_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = (head)->stqh_first; \ + while (curelm->field.stqe_next != (elm)) \ + curelm = curelm->field.stqe_next; \ + if ((curelm->field.stqe_next = \ + curelm->field.stqe_next->field.stqe_next) == NULL) \ + (head)->stqh_last = &(curelm)->field.stqe_next; \ + } \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_FOREACH(var, head, field) \ + for ((var) = ((head)->stqh_first); (var); (var) = ((var)->field.stqe_next)) + +#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = STAILQ_FIRST((head)); \ + (var) && ((tvar) = STAILQ_NEXT((var), field), 1); (var) = (tvar)) + +#define STAILQ_CONCAT(head1, head2) \ + do { \ + if (!STAILQ_EMPTY((head2))) { \ + *(head1)->stqh_last = (head2)->stqh_first; \ + (head1)->stqh_last = (head2)->stqh_last; \ + STAILQ_INIT((head2)); \ + } \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_LAST(head, type, field) \ + (STAILQ_EMPTY((head)) \ + ? NULL \ + : ((struct type *)(void *)((char *)((head)->stqh_last) - \ + offsetof(struct type, field)))) + +#endif /* !_QUEUE_H_ */ diff --git a/semestr-5/so/lista5/so21_lista_5/include/rio.h b/semestr-5/so/lista5/so21_lista_5/include/rio.h new file mode 100644 index 0000000..bd62723 --- /dev/null +++ b/semestr-5/so/lista5/so21_lista_5/include/rio.h @@ -0,0 +1,27 @@ +#ifndef _RIO_H_ +#define _RIO_H_ + +/* Persistent state for the robust I/O (Rio) package */ +#define RIO_BUFSIZE 8192 + +typedef struct { + int rio_fd; /* Descriptor for this internal buf */ + int rio_cnt; /* Unread bytes in internal buf */ + char *rio_bufptr; /* Next unread byte in internal buf */ + char rio_buf[RIO_BUFSIZE]; /* Internal buffer */ +} rio_t; + +/* Rio (Robust I/O) package */ +ssize_t rio_readn(int fd, void *usrbuf, size_t n); +ssize_t rio_writen(int fd, const void *usrbuf, size_t n); +void rio_readinitb(rio_t *rp, int fd); +ssize_t rio_readnb(rio_t *rp, void *usrbuf, size_t n); +ssize_t rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen); + +/* Wrappers that exit on failure */ +ssize_t Rio_readn(int fd, void *ptr, size_t nbytes); +void Rio_writen(int fd, const void *usrbuf, size_t n); +ssize_t Rio_readnb(rio_t *rp, void *usrbuf, size_t n); +ssize_t Rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen); + +#endif /* !_RIO_H_ */ diff --git a/semestr-5/so/lista5/so21_lista_5/include/terminal.h b/semestr-5/so/lista5/so21_lista_5/include/terminal.h new file mode 100644 index 0000000..f221df2 --- /dev/null +++ b/semestr-5/so/lista5/so21_lista_5/include/terminal.h @@ -0,0 +1,27 @@ +#ifndef _TERMINAL_H_ +#define _TERMINAL_H_ + +int tty_open(void); +void tty_curpos(int fd, int *x, int *y); + +/* https://en.wikipedia.org/wiki/ANSI_escape_code#CSI_(Control_Sequence_Introducer)_sequences */ + +#define ESC "\033" +#define CSI ESC "[" + +#define CUU(n) CSI #n "A" /* Cursor Up */ +#define CUD(n) CSI #n "B" /* Cursor Down */ +#define CUF(n) CSI #n "C" /* Cursor Forward */ +#define CUB(n) CSI #n "D" /* Cursor Back */ +#define CNL(n) CSI #n "E" /* Cursor Next Line */ +#define CPL(n) CSI #n "F" /* Cursor Previous Line */ +#define CHA(n) CSI #n "G" /* Cursor Horizontal Absolute */ +#define CUP(n, m) CSI #n ";" #m "H" /* Cursor Position */ +#define ED(n) CSI #n "J" /* Erase in Display */ +#define EL(n) CSI #n "K" /* Erase in Line */ +#define SU(n) CSI #n "S" /* Scroll Up Scroll */ +#define SD(n) CSI #n "T" /* Scroll Down Scroll */ +#define CPR() CSI "6n" /* Cursor Position Report */ +#define SGR(x) CSI x "m" + +#endif /* !_ANSICODES_H_ */ diff --git a/semestr-5/so/lista5/so21_lista_5/include/tree.h b/semestr-5/so/lista5/so21_lista_5/include/tree.h new file mode 100644 index 0000000..3355bad --- /dev/null +++ b/semestr-5/so/lista5/so21_lista_5/include/tree.h @@ -0,0 +1,735 @@ +/* $NetBSD: tree.h,v 1.20 2013/09/14 13:20:45 joerg Exp $ */ +/* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */ +/* + * Copyright 2002 Niels Provos <provos@citi.umich.edu> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef _TREE_H_ +#define _TREE_H_ + +/* + * This file defines data structures for different types of trees: + * splay trees and red-black trees. + * + * A splay tree is a self-organizing data structure. Every operation + * on the tree causes a splay to happen. The splay moves the requested + * node to the root of the tree and partly rebalances it. + * + * This has the benefit that request locality causes faster lookups as + * the requested nodes move to the top of the tree. On the other hand, + * every lookup causes memory writes. + * + * The Balance Theorem bounds the total access time for m operations + * and n inserts on an initially empty tree as O((m + n)lg n). The + * amortized cost for a sequence of m accesses to a splay tree is O(lg n); + * + * A red-black tree is a binary search tree with the node color as an + * extra attribute. It fulfills a set of conditions: + * - every search path from the root to a leaf consists of the + * same number of black nodes, + * - each red node (except for the root) has a black parent, + * - each leaf node is black. + * + * Every operation on a red-black tree is bounded as O(lg n). + * The maximum height of a red-black tree is 2lg (n+1). + */ + +#define SPLAY_HEAD(name, type) \ + struct name { \ + struct type *sph_root; /* root of the tree */ \ + } + +#define SPLAY_INITIALIZER(root) \ + { NULL } + +#define SPLAY_INIT(root) \ + do { \ + (root)->sph_root = NULL; \ + } while (/*CONSTCOND*/ 0) + +#define SPLAY_ENTRY(type) \ + struct { \ + struct type *spe_left; /* left element */ \ + struct type *spe_right; /* right element */ \ + } + +#define SPLAY_LEFT(elm, field) (elm)->field.spe_left +#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right +#define SPLAY_ROOT(head) (head)->sph_root +#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) + +/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ +#define SPLAY_ROTATE_RIGHT(head, tmp, field) \ + do { \ + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ + (head)->sph_root = tmp; \ + } while (/*CONSTCOND*/ 0) + +#define SPLAY_ROTATE_LEFT(head, tmp, field) \ + do { \ + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ + SPLAY_LEFT(tmp, field) = (head)->sph_root; \ + (head)->sph_root = tmp; \ + } while (/*CONSTCOND*/ 0) + +#define SPLAY_LINKLEFT(head, tmp, field) \ + do { \ + SPLAY_LEFT(tmp, field) = (head)->sph_root; \ + tmp = (head)->sph_root; \ + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ + } while (/*CONSTCOND*/ 0) + +#define SPLAY_LINKRIGHT(head, tmp, field) \ + do { \ + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ + tmp = (head)->sph_root; \ + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ + } while (/*CONSTCOND*/ 0) + +#define SPLAY_ASSEMBLE(head, node, left, right, field) \ + do { \ + SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ + SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \ + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ + } while (/*CONSTCOND*/ 0) + +/* Generates prototypes and inline functions */ + +#define SPLAY_PROTOTYPE(name, type, field, cmp) \ + void name##_SPLAY(struct name *, struct type *); \ + void name##_SPLAY_MINMAX(struct name *, int); \ + struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ + struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ + \ + /* Finds the node with the same key as elm */ \ + static __inline struct type *name##_SPLAY_FIND(struct name *head, \ + struct type *elm) { \ + if (SPLAY_EMPTY(head)) \ + return (NULL); \ + name##_SPLAY(head, elm); \ + if ((cmp)(elm, (head)->sph_root) == 0) \ + return (head->sph_root); \ + return (NULL); \ + } \ + \ + static __inline __unused struct type *name##_SPLAY_NEXT(struct name *head, \ + struct type *elm) { \ + name##_SPLAY(head, elm); \ + if (SPLAY_RIGHT(elm, field) != NULL) { \ + elm = SPLAY_RIGHT(elm, field); \ + while (SPLAY_LEFT(elm, field) != NULL) { \ + elm = SPLAY_LEFT(elm, field); \ + } \ + } else \ + elm = NULL; \ + return (elm); \ + } \ + \ + static __unused __inline struct type *name##_SPLAY_MIN_MAX( \ + struct name *head, int val) { \ + name##_SPLAY_MINMAX(head, val); \ + return (SPLAY_ROOT(head)); \ + } + +/* Main splay operation. + * Moves node close to the key of elm to top + */ +#define SPLAY_GENERATE(name, type, field, cmp) \ + struct type *name##_SPLAY_INSERT(struct name *head, struct type *elm) { \ + if (SPLAY_EMPTY(head)) { \ + SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ + } else { \ + int __comp; \ + name##_SPLAY(head, elm); \ + __comp = (cmp)(elm, (head)->sph_root); \ + if (__comp < 0) { \ + SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \ + SPLAY_RIGHT(elm, field) = (head)->sph_root; \ + SPLAY_LEFT((head)->sph_root, field) = NULL; \ + } else if (__comp > 0) { \ + SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \ + SPLAY_LEFT(elm, field) = (head)->sph_root; \ + SPLAY_RIGHT((head)->sph_root, field) = NULL; \ + } else \ + return ((head)->sph_root); \ + } \ + (head)->sph_root = (elm); \ + return (NULL); \ + } \ + \ + struct type *name##_SPLAY_REMOVE(struct name *head, struct type *elm) { \ + struct type *__tmp; \ + if (SPLAY_EMPTY(head)) \ + return (NULL); \ + name##_SPLAY(head, elm); \ + if ((cmp)(elm, (head)->sph_root) == 0) { \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ + } else { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ + name##_SPLAY(head, elm); \ + SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ + } \ + return (elm); \ + } \ + return (NULL); \ + } \ + \ + void name##_SPLAY(struct name *head, struct type *elm) { \ + struct type __node, *__left, *__right, *__tmp; \ + int __comp; \ + \ + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ + __left = __right = &__node; \ + \ + while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ + if (__comp < 0) { \ + __tmp = SPLAY_LEFT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if ((cmp)(elm, __tmp) < 0) { \ + SPLAY_ROTATE_RIGHT(head, __tmp, field); \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ + break; \ + } \ + SPLAY_LINKLEFT(head, __right, field); \ + } else if (__comp > 0) { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if ((cmp)(elm, __tmp) > 0) { \ + SPLAY_ROTATE_LEFT(head, __tmp, field); \ + if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ + break; \ + } \ + SPLAY_LINKRIGHT(head, __left, field); \ + } \ + } \ + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ + } \ + \ + /* Splay with either the minimum or the maximum element \ + * Used to find minimum or maximum element in tree. \ + */ \ + void name##_SPLAY_MINMAX(struct name *head, int __comp) { \ + struct type __node, *__left, *__right, *__tmp; \ + \ + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ + __left = __right = &__node; \ + \ + while (1) { \ + if (__comp < 0) { \ + __tmp = SPLAY_LEFT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if (__comp < 0) { \ + SPLAY_ROTATE_RIGHT(head, __tmp, field); \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ + break; \ + } \ + SPLAY_LINKLEFT(head, __right, field); \ + } else if (__comp > 0) { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if (__comp > 0) { \ + SPLAY_ROTATE_LEFT(head, __tmp, field); \ + if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ + break; \ + } \ + SPLAY_LINKRIGHT(head, __left, field); \ + } \ + } \ + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ + } + +#define SPLAY_NEGINF -1 +#define SPLAY_INF 1 + +#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) +#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) +#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) +#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) +#define SPLAY_MIN(name, x) \ + (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) +#define SPLAY_MAX(name, x) \ + (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) + +#define SPLAY_FOREACH(x, name, head) \ + for ((x) = SPLAY_MIN(name, head); (x) != NULL; \ + (x) = SPLAY_NEXT(name, head, x)) + +/* Macros that define a red-black tree */ +#define RB_HEAD(name, type) \ + struct name { \ + struct type *rbh_root; /* root of the tree */ \ + } + +#define RB_INITIALIZER(root) \ + { NULL } + +#define RB_INIT(root) \ + do { \ + (root)->rbh_root = NULL; \ + } while (/*CONSTCOND*/ 0) + +#define RB_BLACK 0 +#define RB_RED 1 +#define RB_ENTRY(type) \ + struct { \ + struct type *rbe_left; /* left element */ \ + struct type *rbe_right; /* right element */ \ + struct type *rbe_parent; /* parent element */ \ + int rbe_color; /* node color */ \ + } + +#define RB_LEFT(elm, field) (elm)->field.rbe_left +#define RB_RIGHT(elm, field) (elm)->field.rbe_right +#define RB_PARENT(elm, field) (elm)->field.rbe_parent +#define RB_COLOR(elm, field) (elm)->field.rbe_color +#define RB_ROOT(head) (head)->rbh_root +#define RB_EMPTY(head) (RB_ROOT(head) == NULL) + +#define RB_SET(elm, parent, field) \ + do { \ + RB_PARENT(elm, field) = parent; \ + RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ + RB_COLOR(elm, field) = RB_RED; \ + } while (/*CONSTCOND*/ 0) + +#define RB_SET_BLACKRED(black, red, field) \ + do { \ + RB_COLOR(black, field) = RB_BLACK; \ + RB_COLOR(red, field) = RB_RED; \ + } while (/*CONSTCOND*/ 0) + +#ifndef RB_AUGMENT +#define RB_AUGMENT(x) \ + do { \ + } while (/*CONSTCOND*/ 0) +#endif + +#define RB_ROTATE_LEFT(head, elm, tmp, field) \ + do { \ + (tmp) = RB_RIGHT(elm, field); \ + if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ + RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ + } \ + RB_AUGMENT(elm); \ + if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ + if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ + RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ + else \ + RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ + } else \ + (head)->rbh_root = (tmp); \ + RB_LEFT(tmp, field) = (elm); \ + RB_PARENT(elm, field) = (tmp); \ + RB_AUGMENT(tmp); \ + if ((RB_PARENT(tmp, field))) \ + RB_AUGMENT(RB_PARENT(tmp, field)); \ + } while (/*CONSTCOND*/ 0) + +#define RB_ROTATE_RIGHT(head, elm, tmp, field) \ + do { \ + (tmp) = RB_LEFT(elm, field); \ + if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ + RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ + } \ + RB_AUGMENT(elm); \ + if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ + if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ + RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ + else \ + RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ + } else \ + (head)->rbh_root = (tmp); \ + RB_RIGHT(tmp, field) = (elm); \ + RB_PARENT(elm, field) = (tmp); \ + RB_AUGMENT(tmp); \ + if ((RB_PARENT(tmp, field))) \ + RB_AUGMENT(RB_PARENT(tmp, field)); \ + } while (/*CONSTCOND*/ 0) + +/* Generates prototypes and inline functions */ +#define RB_PROTOTYPE(name, type, field, cmp) \ + RB_PROTOTYPE_INTERNAL(name, type, field, cmp, ) +#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ + RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) +#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ + attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ + attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, \ + struct type *); \ + attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ + attr struct type *name##_RB_INSERT(struct name *, struct type *); \ + attr struct type *name##_RB_FIND(struct name *, struct type *); \ + attr struct type *name##_RB_NFIND(struct name *, struct type *); \ + attr struct type *name##_RB_NEXT(struct type *); \ + attr struct type *name##_RB_PREV(struct type *); \ + attr struct type *name##_RB_MINMAX(struct name *, int); + +/* Main rb operation. + * Moves node close to the key of elm to top + */ +#define RB_GENERATE(name, type, field, cmp) \ + RB_GENERATE_INTERNAL(name, type, field, cmp, ) +#define RB_GENERATE_STATIC(name, type, field, cmp) \ + RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) +#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ + attr void name##_RB_INSERT_COLOR(struct name *head, struct type *elm) { \ + struct type *parent, *gparent, *tmp; \ + while ((parent = RB_PARENT(elm, field)) != NULL && \ + RB_COLOR(parent, field) == RB_RED) { \ + gparent = RB_PARENT(parent, field); \ + if (parent == RB_LEFT(gparent, field)) { \ + tmp = RB_RIGHT(gparent, field); \ + if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ + RB_COLOR(tmp, field) = RB_BLACK; \ + RB_SET_BLACKRED(parent, gparent, field); \ + elm = gparent; \ + continue; \ + } \ + if (RB_RIGHT(parent, field) == elm) { \ + RB_ROTATE_LEFT(head, parent, tmp, field); \ + tmp = parent; \ + parent = elm; \ + elm = tmp; \ + } \ + RB_SET_BLACKRED(parent, gparent, field); \ + RB_ROTATE_RIGHT(head, gparent, tmp, field); \ + } else { \ + tmp = RB_LEFT(gparent, field); \ + if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ + RB_COLOR(tmp, field) = RB_BLACK; \ + RB_SET_BLACKRED(parent, gparent, field); \ + elm = gparent; \ + continue; \ + } \ + if (RB_LEFT(parent, field) == elm) { \ + RB_ROTATE_RIGHT(head, parent, tmp, field); \ + tmp = parent; \ + parent = elm; \ + elm = tmp; \ + } \ + RB_SET_BLACKRED(parent, gparent, field); \ + RB_ROTATE_LEFT(head, gparent, tmp, field); \ + } \ + } \ + RB_COLOR(head->rbh_root, field) = RB_BLACK; \ + } \ + \ + attr void name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, \ + struct type *elm) { \ + struct type *tmp; \ + while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ + elm != RB_ROOT(head)) { \ + if (RB_LEFT(parent, field) == elm) { \ + tmp = RB_RIGHT(parent, field); \ + if (RB_COLOR(tmp, field) == RB_RED) { \ + RB_SET_BLACKRED(tmp, parent, field); \ + RB_ROTATE_LEFT(head, parent, tmp, field); \ + tmp = RB_RIGHT(parent, field); \ + } \ + if ((RB_LEFT(tmp, field) == NULL || \ + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ + (RB_RIGHT(tmp, field) == NULL || \ + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ + RB_COLOR(tmp, field) = RB_RED; \ + elm = parent; \ + parent = RB_PARENT(elm, field); \ + } else { \ + if (RB_RIGHT(tmp, field) == NULL || \ + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \ + struct type *oleft; \ + if ((oleft = RB_LEFT(tmp, field)) != NULL) \ + RB_COLOR(oleft, field) = RB_BLACK; \ + RB_COLOR(tmp, field) = RB_RED; \ + RB_ROTATE_RIGHT(head, tmp, oleft, field); \ + tmp = RB_RIGHT(parent, field); \ + } \ + RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ + RB_COLOR(parent, field) = RB_BLACK; \ + if (RB_RIGHT(tmp, field)) \ + RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ + RB_ROTATE_LEFT(head, parent, tmp, field); \ + elm = RB_ROOT(head); \ + break; \ + } \ + } else { \ + tmp = RB_LEFT(parent, field); \ + if (RB_COLOR(tmp, field) == RB_RED) { \ + RB_SET_BLACKRED(tmp, parent, field); \ + RB_ROTATE_RIGHT(head, parent, tmp, field); \ + tmp = RB_LEFT(parent, field); \ + } \ + if ((RB_LEFT(tmp, field) == NULL || \ + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ + (RB_RIGHT(tmp, field) == NULL || \ + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ + RB_COLOR(tmp, field) = RB_RED; \ + elm = parent; \ + parent = RB_PARENT(elm, field); \ + } else { \ + if (RB_LEFT(tmp, field) == NULL || \ + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \ + struct type *oright; \ + if ((oright = RB_RIGHT(tmp, field)) != NULL) \ + RB_COLOR(oright, field) = RB_BLACK; \ + RB_COLOR(tmp, field) = RB_RED; \ + RB_ROTATE_LEFT(head, tmp, oright, field); \ + tmp = RB_LEFT(parent, field); \ + } \ + RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ + RB_COLOR(parent, field) = RB_BLACK; \ + if (RB_LEFT(tmp, field)) \ + RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ + RB_ROTATE_RIGHT(head, parent, tmp, field); \ + elm = RB_ROOT(head); \ + break; \ + } \ + } \ + } \ + if (elm) \ + RB_COLOR(elm, field) = RB_BLACK; \ + } \ + \ + attr struct type *name##_RB_REMOVE(struct name *head, struct type *elm) { \ + struct type *child, *parent, *old = elm; \ + int color; \ + if (RB_LEFT(elm, field) == NULL) \ + child = RB_RIGHT(elm, field); \ + else if (RB_RIGHT(elm, field) == NULL) \ + child = RB_LEFT(elm, field); \ + else { \ + struct type *left; \ + elm = RB_RIGHT(elm, field); \ + while ((left = RB_LEFT(elm, field)) != NULL) \ + elm = left; \ + child = RB_RIGHT(elm, field); \ + parent = RB_PARENT(elm, field); \ + color = RB_COLOR(elm, field); \ + if (child) \ + RB_PARENT(child, field) = parent; \ + if (parent) { \ + if (RB_LEFT(parent, field) == elm) \ + RB_LEFT(parent, field) = child; \ + else \ + RB_RIGHT(parent, field) = child; \ + RB_AUGMENT(parent); \ + } else \ + RB_ROOT(head) = child; \ + if (RB_PARENT(elm, field) == old) \ + parent = elm; \ + (elm)->field = (old)->field; \ + if (RB_PARENT(old, field)) { \ + if (RB_LEFT(RB_PARENT(old, field), field) == old) \ + RB_LEFT(RB_PARENT(old, field), field) = elm; \ + else \ + RB_RIGHT(RB_PARENT(old, field), field) = elm; \ + RB_AUGMENT(RB_PARENT(old, field)); \ + } else \ + RB_ROOT(head) = elm; \ + RB_PARENT(RB_LEFT(old, field), field) = elm; \ + if (RB_RIGHT(old, field)) \ + RB_PARENT(RB_RIGHT(old, field), field) = elm; \ + if (parent) { \ + left = parent; \ + do { \ + RB_AUGMENT(left); \ + } while ((left = RB_PARENT(left, field)) != NULL); \ + } \ + goto color; \ + } \ + parent = RB_PARENT(elm, field); \ + color = RB_COLOR(elm, field); \ + if (child) \ + RB_PARENT(child, field) = parent; \ + if (parent) { \ + if (RB_LEFT(parent, field) == elm) \ + RB_LEFT(parent, field) = child; \ + else \ + RB_RIGHT(parent, field) = child; \ + RB_AUGMENT(parent); \ + } else \ + RB_ROOT(head) = child; \ + color: \ + if (color == RB_BLACK) \ + name##_RB_REMOVE_COLOR(head, parent, child); \ + return (old); \ + } \ + \ + /* Inserts a node into the RB tree */ \ + attr struct type *name##_RB_INSERT(struct name *head, struct type *elm) { \ + struct type *tmp; \ + struct type *parent = NULL; \ + int comp = 0; \ + tmp = RB_ROOT(head); \ + while (tmp) { \ + parent = tmp; \ + comp = (cmp)(elm, parent); \ + if (comp < 0) \ + tmp = RB_LEFT(tmp, field); \ + else if (comp > 0) \ + tmp = RB_RIGHT(tmp, field); \ + else \ + return (tmp); \ + } \ + RB_SET(elm, parent, field); \ + if (parent != NULL) { \ + if (comp < 0) \ + RB_LEFT(parent, field) = elm; \ + else \ + RB_RIGHT(parent, field) = elm; \ + RB_AUGMENT(parent); \ + } else \ + RB_ROOT(head) = elm; \ + name##_RB_INSERT_COLOR(head, elm); \ + return (NULL); \ + } \ + \ + /* Finds the node with the same key as elm */ \ + attr struct type *name##_RB_FIND(struct name *head, struct type *elm) { \ + struct type *tmp = RB_ROOT(head); \ + int comp; \ + while (tmp) { \ + comp = cmp(elm, tmp); \ + if (comp < 0) \ + tmp = RB_LEFT(tmp, field); \ + else if (comp > 0) \ + tmp = RB_RIGHT(tmp, field); \ + else \ + return (tmp); \ + } \ + return (NULL); \ + } \ + \ + /* Finds the first node greater than or equal to the search key */ \ + attr struct type *name##_RB_NFIND(struct name *head, struct type *elm) { \ + struct type *tmp = RB_ROOT(head); \ + struct type *res = NULL; \ + int comp; \ + while (tmp) { \ + comp = cmp(elm, tmp); \ + if (comp < 0) { \ + res = tmp; \ + tmp = RB_LEFT(tmp, field); \ + } else if (comp > 0) \ + tmp = RB_RIGHT(tmp, field); \ + else \ + return (tmp); \ + } \ + return (res); \ + } \ + \ + /* ARGSUSED */ \ + attr struct type *name##_RB_NEXT(struct type *elm) { \ + if (RB_RIGHT(elm, field)) { \ + elm = RB_RIGHT(elm, field); \ + while (RB_LEFT(elm, field)) \ + elm = RB_LEFT(elm, field); \ + } else { \ + if (RB_PARENT(elm, field) && \ + (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ + elm = RB_PARENT(elm, field); \ + else { \ + while (RB_PARENT(elm, field) && \ + (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ + elm = RB_PARENT(elm, field); \ + elm = RB_PARENT(elm, field); \ + } \ + } \ + return (elm); \ + } \ + \ + /* ARGSUSED */ \ + attr struct type *name##_RB_PREV(struct type *elm) { \ + if (RB_LEFT(elm, field)) { \ + elm = RB_LEFT(elm, field); \ + while (RB_RIGHT(elm, field)) \ + elm = RB_RIGHT(elm, field); \ + } else { \ + if (RB_PARENT(elm, field) && \ + (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ + elm = RB_PARENT(elm, field); \ + else { \ + while (RB_PARENT(elm, field) && \ + (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ + elm = RB_PARENT(elm, field); \ + elm = RB_PARENT(elm, field); \ + } \ + } \ + return (elm); \ + } \ + \ + attr struct type *name##_RB_MINMAX(struct name *head, int val) { \ + struct type *tmp = RB_ROOT(head); \ + struct type *parent = NULL; \ + while (tmp) { \ + parent = tmp; \ + if (val < 0) \ + tmp = RB_LEFT(tmp, field); \ + else \ + tmp = RB_RIGHT(tmp, field); \ + } \ + return (parent); \ + } + +#define RB_NEGINF -1 +#define RB_INF 1 + +#define RB_INSERT(name, x, y) CONCAT(name,_RB_INSERT(x, y)) +#define RB_REMOVE(name, x, y) CONCAT(name,_RB_REMOVE(x, y)) +#define RB_FIND(name, x, y) CONCAT(name,_RB_FIND(x, y)) +#define RB_NFIND(name, x, y) CONCAT(name,_RB_NFIND(x, y)) +#define RB_NEXT(name, x, y) CONCAT(name,_RB_NEXT(y)) +#define RB_PREV(name, x, y) CONCAT(name,_RB_PREV(y)) +#define RB_MIN(name, x) CONCAT(name,_RB_MINMAX(x, RB_NEGINF)) +#define RB_MAX(name, x) CONCAT(name,_RB_MINMAX(x, RB_INF)) + +#define RB_FOREACH(x, name, head) \ + for ((x) = RB_MIN(name, head); (x) != NULL; (x) = name##_RB_NEXT(x)) + +#define RB_FOREACH_FROM(x, name, y) \ + for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ + (x) = (y)) + +#define RB_FOREACH_SAFE(x, name, head, y) \ + for ((x) = RB_MIN(name, head); \ + ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); (x) = (y)) + +#define RB_FOREACH_REVERSE(x, name, head) \ + for ((x) = RB_MAX(name, head); (x) != NULL; (x) = name##_RB_PREV(x)) + +#define RB_FOREACH_REVERSE_FROM(x, name, y) \ + for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ + (x) = (y)) + +#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ + for ((x) = RB_MAX(name, head); \ + ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); (x) = (y)) + +#endif /* !_TREE_H_ */ diff --git a/semestr-5/so/lista5/so21_lista_5/listdir.c b/semestr-5/so/lista5/so21_lista_5/listdir.c new file mode 100644 index 0000000..9ae906c --- /dev/null +++ b/semestr-5/so/lista5/so21_lista_5/listdir.c @@ -0,0 +1,118 @@ +#include "csapp.h" + +#define DIRBUFSZ 256 + +static void print_mode(mode_t m) { + char t; + + if (S_ISDIR(m)) + t = 'd'; + else if (S_ISCHR(m)) + t = 'c'; + else if (S_ISBLK(m)) + t = 'b'; + else if (S_ISREG(m)) + t = '-'; + else if (S_ISFIFO(m)) + t = 'f'; + else if (S_ISLNK(m)) + t = 'l'; + else if (S_ISSOCK(m)) + t = 's'; + else + t = '?'; + + char ur = (m & S_IRUSR) ? 'r' : '-'; + char uw = (m & S_IWUSR) ? 'w' : '-'; + char ux = (m & S_IXUSR) ? 'x' : '-'; + char gr = (m & S_IRGRP) ? 'r' : '-'; + char gw = (m & S_IWGRP) ? 'w' : '-'; + char gx = (m & S_IXGRP) ? 'x' : '-'; + char or = (m & S_IROTH) ? 'r' : '-'; + char ow = (m & S_IWOTH) ? 'w' : '-'; + char ox = (m & S_IXOTH) ? 'x' : '-'; + + /* TODO: Fix code to report set-uid/set-gid/sticky bit as 'ls' does. */ + if (m & S_ISUID) ux = 's'; + if (m & S_ISGID) gx = 's'; + if (m & S_ISVTX) ox = 't'; + + printf("%c%c%c%c%c%c%c%c%c%c", t, ur, uw, ux, gr, gw, gx, or, ow, ox); +} + +static void print_uid(uid_t uid) { + struct passwd *pw = getpwuid(uid); + if (pw) + printf(" %10s", pw->pw_name); + else + printf(" %10d", uid); +} + +static void print_gid(gid_t gid) { + struct group *gr = getgrgid(gid); + if (gr) + printf(" %10s", gr->gr_name); + else + printf(" %10d", gid); +} + +static void file_info(int dirfd, const char *name) { + struct stat sb[1]; + + /* TODO: Read file metadata. */ + fstatat(dirfd, name, sb, AT_SYMLINK_NOFOLLOW); + + print_mode(sb->st_mode); + printf("%4ld", sb->st_nlink); + print_uid(sb->st_uid); + print_gid(sb->st_gid); + + /* TODO: For devices: print major/minor pair; for other files: size. */ + if (S_ISCHR(sb->st_mode) || S_ISBLK(sb->st_mode)) { + int mi = minor(sb->st_rdev); + int ma = major(sb->st_rdev); + printf(" %d,\t%d", mi, ma); + } + else { + printf("\t%ld", sb->st_size); + } + + char *now = ctime(&sb->st_mtime); + now[strlen(now) - 1] = '\0'; + printf("%26s", now); + + printf(" %s", name); + + if (S_ISLNK(sb->st_mode)) { + /* TODO: Read where symlink points to and print '-> destination' string. */ + char buf[300]; + size_t len = readlinkat(dirfd, name, buf, sizeof(buf)); + buf[len] = 0; + printf("-> %s", buf); + } + + putchar('\n'); +} + +int main(int argc, char *argv[]) { + if (!argv[1]) + argv[1] = "."; + + int dirfd = Open(argv[1], O_RDONLY | O_DIRECTORY, 0); + char buf[DIRBUFSZ]; + int n; + + while ((n = Getdents(dirfd, (void *)buf, DIRBUFSZ))) { + struct linux_dirent *d; + /* TODO: Iterate over directory entries and call file_info on them. */ + int offset = 0; + while (offset < n) { + d = (struct linux_dirent *)(buf + offset); + offset += d->d_reclen; + file_info(dirfd, d->d_name); + } + } + + Close(dirfd); + return EXIT_SUCCESS; +} diff --git a/semestr-5/so/lista5/so21_lista_5/mergesort.c b/semestr-5/so/lista5/so21_lista_5/mergesort.c new file mode 100644 index 0000000..b5328b6 --- /dev/null +++ b/semestr-5/so/lista5/so21_lista_5/mergesort.c @@ -0,0 +1,141 @@ +#include "csapp.h" + +typedef struct { + int child_fd; + int parent_fd; +} sockpair_t; + +static sockpair_t MakeSocketPair(void) { + int sv[2]; + Socketpair(AF_UNIX, SOCK_STREAM, 0, sv); + return (sockpair_t){.child_fd = sv[0], .parent_fd = sv[1]}; +} + +static bool MaybeReadNum(int fd, int *num_p) { + return Read(fd, num_p, sizeof(int)) == sizeof(int); +} + +static int ReadNum(int fd) { + int num; + if (Read(fd, &num, sizeof(int)) < sizeof(int)) + app_error("ReadNum error"); + return num; +} + +static void WriteNum(int fd, int num) { + if (Write(fd, &num, sizeof(int)) < sizeof(int)) + app_error("WriteNum error"); +} + +static void SendElem(int parent_fd, int child_fd, int nelem) { + WriteNum(child_fd, nelem); + for (int i = 0; i < nelem; i++) + WriteNum(child_fd, ReadNum(parent_fd)); +} + +static void Merge(int left_fd, int right_fd, int parent_fd) { + bool has_left = true; + bool has_right = true; + int left = ReadNum(left_fd); + int right = ReadNum(right_fd); + + do { + if ((has_left && has_right) ? left < right : has_left) { + WriteNum(parent_fd, left); + has_left = MaybeReadNum(left_fd, &left); + } else { + WriteNum(parent_fd, right); + has_right = MaybeReadNum(right_fd, &right); + } + } while (has_left || has_right); +} + +static void Sort(int parent_fd) { + int nelem = ReadNum(parent_fd); + + if (nelem < 2) { + WriteNum(parent_fd, ReadNum(parent_fd)); + Close(parent_fd); + return; + } + + sockpair_t left = MakeSocketPair(); + + int left_fd = left.parent_fd; + int lnelem = nelem/2; + + if (Fork()) { + Close(left.child_fd); + SendElem(parent_fd, left_fd, lnelem); + } + else { + Close(left.parent_fd); + Sort(left.child_fd); + return; + } + + sockpair_t right = MakeSocketPair(); + /* TODO: Spawn right child. */ + int right_fd = right.parent_fd; + int rnelem = nelem - nelem/2; + + if (Fork()) { + Close(right.child_fd); + SendElem(parent_fd, right_fd, rnelem); + } + else { + Close(right.parent_fd); + Sort(right.child_fd); + return; + } + + /* TODO: Send elements to children and merge returned values afterwards. */ + Merge(left_fd, right_fd, parent_fd); + + /* Wait for both children. */ + Wait(NULL); + Wait(NULL); +} + +static int GetNumber(void) { + char buf[20]; + if (fgets(buf, sizeof(buf), stdin) == NULL) + app_error("GetNumber error"); + return strtol(buf, NULL, 10); +} + +int main(void) { + sockpair_t sort = MakeSocketPair(); + + if (Fork()) { + /* parent */ + int nelem = GetNumber(); + if (nelem < 2) + app_error("Number of sorted elements must be at least 2!\n"); + Close(sort.child_fd); + + /* Write unsorted numbers to mergesort */ + WriteNum(sort.parent_fd, nelem); + for (int i = 0; i < nelem; i++) { + WriteNum(sort.parent_fd, GetNumber()); + } + + /* Read sorted numbers from mergesort */ + int prev = INT_MIN; + for (int i = 0; i < nelem; i++) { + int elem = ReadNum(sort.parent_fd); + fprintf(stderr, "%d\n", elem); + assert(prev <= elem); + prev = elem; + } + Close(sort.parent_fd); + + Wait(NULL); + } else { + /* child */ + Close(sort.parent_fd); + Sort(sort.child_fd); + } + + return 0; +} diff --git a/semestr-5/so/lista5/so21_lista_5/prime.c b/semestr-5/so/lista5/so21_lista_5/prime.c new file mode 100644 index 0000000..80ed3c6 --- /dev/null +++ b/semestr-5/so/lista5/so21_lista_5/prime.c @@ -0,0 +1,97 @@ +#include "csapp.h" + +typedef struct { + int read; + int write; +} pipe_t; + +static inline pipe_t MakePipe(void) { + int fds[2]; + Pipe(fds); + return (pipe_t){.read = fds[0], .write = fds[1]}; +} + +static inline void CloseReadEnd(pipe_t p) { + Close(p.read); +} + +static inline void CloseWriteEnd(pipe_t p) { + Close(p.write); +} + +static bool ReadNum(pipe_t p, long *valp) { + return Read(p.read, valp, sizeof(long)) == sizeof(long); +} + +static bool WriteNum(pipe_t p, long val) { + return Write(p.write, &val, sizeof(long)) == sizeof(long); +} + +static noreturn void generator(pipe_t out, long maxprime) { + for (long n = 2; n <= maxprime; n++) + WriteNum(out, n); + exit(EXIT_SUCCESS); +} + +static void filter(pipe_t in, pipe_t out, long prime) { + long num; + while (ReadNum(in, &num)) { + if (num % prime != 0) + WriteNum(out, num); + } +} + +static noreturn void filter_chain(pipe_t in) { + long prime; + + /* TODO: Something is missing here! */ + pipe_t out = MakePipe(); + if (!ReadNum(in, &prime)) { + exit(EXIT_SUCCESS); + } + printf("%ld\n", prime); + if (Fork()) { /* parent */ + close(out.read); + filter(in, out, prime); + close(out.write); + close(in.read); + Wait(NULL); + } else { /* child */ + close(out.write); + close(in.read); + filter_chain(out); + } + + exit(EXIT_SUCCESS); +} + +int main(int argc, char *argv[]) { + if (argc != 2) + app_error("Usage: %s [MAXPRIME]", argv[0]); + + long maxprime = atol(argv[1]); + + if (maxprime < 2 || maxprime > 10000) + app_error("Give maximum prime number in range from 2 to 10000!"); + + /* Spawn generator. */ + pipe_t gen_pipe = MakePipe(); + if (Fork()) { /* parent */ + CloseWriteEnd(gen_pipe); + } else { /* child */ + CloseReadEnd(gen_pipe); + generator(gen_pipe, maxprime); + } + + /* Spawn filter chain. */ + if (Fork()) { /* parent */ + CloseReadEnd(gen_pipe); + } else { /* child */ + filter_chain(gen_pipe); + } + + for (int i = 0; i < 2; i++) + Wait(NULL); + + return 0; +} |