diff options
Diffstat (limited to 'semestr-5/so/lista1')
| -rw-r--r-- | semestr-5/so/lista1/rozwiazania/ex2a.c | 25 | ||||
| -rw-r--r-- | semestr-5/so/lista1/rozwiazania/ex2b.c | 21 | ||||
| -rw-r--r-- | semestr-5/so/lista1/rozwiazania/lista1.md | 87 | ||||
| -rw-r--r-- | semestr-5/so/lista1/so21_lista_1.pdf | bin | 0 -> 146523 bytes | |||
| -rw-r--r-- | semestr-5/so/lista1/so21_lista_1.tar.gz | bin | 0 -> 43799 bytes | |||
| -rw-r--r-- | semestr-5/so/lista1/so21_lista_1/Makefile.include | 103 | ||||
| -rw-r--r-- | semestr-5/so/lista1/so21_lista_1/fileref.c | 50 | ||||
| -rw-r--r-- | semestr-5/so/lista1/so21_lista_1/het.c | 71 | ||||
| -rw-r--r-- | semestr-5/so/lista1/so21_lista_1/include/bitstring.h | 138 | ||||
| -rw-r--r-- | semestr-5/so/lista1/so21_lista_1/include/csapp.h | 238 | ||||
| -rw-r--r-- | semestr-5/so/lista1/so21_lista_1/include/queue.h | 587 | ||||
| -rw-r--r-- | semestr-5/so/lista1/so21_lista_1/include/rio.h | 27 | ||||
| -rw-r--r-- | semestr-5/so/lista1/so21_lista_1/include/terminal.h | 27 | ||||
| -rw-r--r-- | semestr-5/so/lista1/so21_lista_1/include/tree.h | 735 | ||||
| -rw-r--r-- | semestr-5/so/lista1/so21_lista_1/test.txt | 3 |
15 files changed, 2112 insertions, 0 deletions
diff --git a/semestr-5/so/lista1/rozwiazania/ex2a.c b/semestr-5/so/lista1/rozwiazania/ex2a.c new file mode 100644 index 0000000..63b26db --- /dev/null +++ b/semestr-5/so/lista1/rozwiazania/ex2a.c @@ -0,0 +1,25 @@ +#include <unistd.h> +#include <stdio.h> +#include <stdlib.h> + +int main() { + printf("[%d] Ex2, parent pid: %d\n", getpid(), getppid()); + + int pid = fork(); + if (pid < 0) { + printf("Fork error\n"); + exit(1); + } + if (pid == 0) { + for (int i = 0; i < 10; i++) { + printf("[%d] Child process, parent pid: %d\n", getpid(), getppid()); + sleep(1); + } + } + else { + printf("[%d] Sleeping for a second.\n", getpid()); + sleep(1); + printf("[%d] Exit.\n", getpid()); + exit(0); + } +}
\ No newline at end of file diff --git a/semestr-5/so/lista1/rozwiazania/ex2b.c b/semestr-5/so/lista1/rozwiazania/ex2b.c new file mode 100644 index 0000000..af4a986 --- /dev/null +++ b/semestr-5/so/lista1/rozwiazania/ex2b.c @@ -0,0 +1,21 @@ +#include <stdlib.h> +#include <stdio.h> +#include <unistd.h> + +int main() { + int pid = fork(); + if (pid < 0) { + printf("Fork error\n"); + exit(1); + } + if (pid == 0) { + printf("[%d], Child process, returning.\n", getpid()); + exit(0); + } + else { + while (1) { + printf("[%d] Parent process, sleeping.\n", getpid()); + sleep(1); + } + } +}
\ No newline at end of file diff --git a/semestr-5/so/lista1/rozwiazania/lista1.md b/semestr-5/so/lista1/rozwiazania/lista1.md new file mode 100644 index 0000000..9b20a4a --- /dev/null +++ b/semestr-5/so/lista1/rozwiazania/lista1.md @@ -0,0 +1,87 @@ +# Lista 1 +###### tags: `so-rozw` + +## Zadanie 1 + +<!-- ::: --> +> W systemach uniksowych wszystkie procesy są związane relacją **rodzic-dziecko**. Uruchom polecenie `ps -eo user,pid,ppid,pgid,tid,pri,stat,wchan,cmd`. Na wydruku zidentyfikuj **identyfikator procesu**, **identyfikator grupy procesów**, **identyfikator rodzica** oraz **właściciela** procesu. Kto jest rodzicem procesu $\texttt{init}$? Wskaż, które z wyświetlonych zadań są **wątkami jądra**. Jakie jest znaczenie poszczególnych znaków w kolumnie STAT? Wyświetl drzewiastą reprezentację **hierarchii procesów** poleceniem pstree – które z zadań są wątkami? +<!-- ::: --> + +### Definicje + +**Relacja rodzic-dziecko** - Jeżeli proces używje wywołania systemowego `fork`, to jądro systemu operacyjnego tworzy identyczną kopię tego procesu. Tę kopię nazywamy *dzieckiem*, a proces wołający `fork` nazywamy *rodzicem*. Jeśli proces rodzica umrze, a proces dziecka nie, to rodzicem dziecka staje się rodzic jego rodzica (*reparenting*). + +**Identyfikator procesu (PID)** - unikalny numer, który jądro przypisuje danemu procesowi w momencie jego powstawania. + +**Identyfikator grupy procesów** - #TODO + +**Identyikator rodzica (PPID)** - (w kontekście jakiegoś konkretnego procesu) PID rodzica procesu. + +**Wątki jądra** - #TODO + +**Hierarchia procesów** - Graf skierowany, którego wierzchołkami są procesy, a krawędzie są dane przez relację rodzic-dziecko. + +> Kto jest rodzicem procesu $\texttt{init}$? + + +> Jakie jest znaczenie poszczególnych znaków w kolumnie STAT? +``` +PROCESS STATE CODES + Here are the different values that the s, stat and state output specifiers (header "STAT" or "S") will display to describe the state of a process: + + D uninterruptible sleep (usually IO) + I Idle kernel thread + R running or runnable (on run queue) + S interruptible sleep (waiting for an event to complete) + T stopped by job control signal + t stopped by debugger during the tracing + W paging (not valid since the 2.6.xx kernel) + X dead (should never be seen) + Z defunct ("zombie") process, terminated but not reaped by its parent + + For BSD formats and when the stat keyword is used, additional characters may be displayed: + + < high-priority (not nice to other users) + N low-priority (nice to other users) + L has pages locked into memory (for real-time and custom IO) + s is a session leader + l is multi-threaded (using CLONE_THREAD, like NPTL pthreads do) + + is in the foreground process group +``` + + +## Zadanie 2 +> Jak jądro systemu reaguje na sytuację kiedy proces staje się **sierotą**? W jaki sposób pogrzebać proces, który wszedł w stan **zombie**? Czemu proces nie może sam siebie pogrzebać? Zauważ, że proces może, przy pomocy `waitpid(2)`, czekać na zmianę **stanu** wyłącznie swoich dzieci. Co złego mogłoby się stać, gdyby znieść to ograniczenie? Rozważ scenariusze (a) dziecko może czekać na zmianę stanu swojego rodzica (b) wiele procesów oczekuje na zmianę stanu jednego procesu. + +> Jak jądro systemu reaguje na sytuację kiedy proces staje się **sierotą**? + +**Sierotą** nazywamy proces, którego proces rodzica został zakończony. Takie procesy są podpinane jako dzieci procesu 1 `init` (reparenting). + +> W jaki sposób pogrzebać proces, który wszedł w stan **zombie**? + +**Zombie** to określenie procesu, który zakończył swoje działanie, ale nie został "pogrzebany" przez swojego rodzica. Grzebania można dokonać przy pomocy wywołania systemowego `wait`. Czemu procesy przechodzą w stan zombie, zamiast po prostu umrzeć? Np. dlatego, żeby proces rodzica mógł dostać status wyjścia tego zmarłego procesu. + +Z `man wait`: +> A child that terminates, but has not been waited for becomes a "zom‐ + bie". The kernel maintains a minimal set of information about the + zombie process (PID, termination status, resource usage information) + in order to allow the parent to later perform a wait to obtain in‐ + formation about the child. As long as a zombie is not removed from + the system via a wait, it will consume a slot in the kernel process + table, and if this table fills, it will not be possible to create + further processes. If a parent process terminates, then its "zom‐ + bie" children (if any) are adopted by init(1), (or by the nearest + "subreaper" process as defined through the use of the prctl(2) + PR_SET_CHILD_SUBREAPER operation); init(1) automatically performs a + wait to remove the zombies. + +> Czemu proces nie może sam siebie pogrzebać? + +Skoro proces zakończył działanie, to nie dokonuje już żadnych operacji. Poza tym, to byłoby bezcelowe, powód dlaczego w ogóle chcemy grzebać opisałem wyżej. + + + +## Zadanie 8 +Rozwiązanie w katalogu niżej, het.c + +Diagram procesów: # TODO
\ No newline at end of file diff --git a/semestr-5/so/lista1/so21_lista_1.pdf b/semestr-5/so/lista1/so21_lista_1.pdf Binary files differnew file mode 100644 index 0000000..9db0903 --- /dev/null +++ b/semestr-5/so/lista1/so21_lista_1.pdf diff --git a/semestr-5/so/lista1/so21_lista_1.tar.gz b/semestr-5/so/lista1/so21_lista_1.tar.gz Binary files differnew file mode 100644 index 0000000..cfff741 --- /dev/null +++ b/semestr-5/so/lista1/so21_lista_1.tar.gz diff --git a/semestr-5/so/lista1/so21_lista_1/Makefile.include b/semestr-5/so/lista1/so21_lista_1/Makefile.include new file mode 100644 index 0000000..71fe82e --- /dev/null +++ b/semestr-5/so/lista1/so21_lista_1/Makefile.include @@ -0,0 +1,103 @@ +CC = gcc -g +CFLAGS = -Og -Wall -Werror -Wstrict-prototypes +AS = as -g +ASFLAGS = +CPPFLAGS = -Iinclude +LDLIBS = -Llibcsapp -lcsapp + +# Recognize operating system +ifeq ($(shell uname -s), Darwin) +CPPFLAGS += -DMACOS +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/lista1/so21_lista_1/fileref.c b/semestr-5/so/lista1/so21_lista_1/fileref.c new file mode 100644 index 0000000..b5d6f9f --- /dev/null +++ b/semestr-5/so/lista1/so21_lista_1/fileref.c @@ -0,0 +1,50 @@ +#include "csapp.h" + +static char buf[256]; + +#define LINE1 49 +#define LINE2 33 +#define LINE3 78 + +static void do_read(int fd) { + /* TODO: Spawn a child. Read from the file descriptor in both parent and + * child. Check how file cursor value has changed in both processes. */ + int pid = fork(); + pid = getpid(); + int offset = lseek(fd, 0, SEEK_CUR); + printf("[%d] Offset: %d\n", pid, offset); + + int aux = read(fd, buf, LINE1); + offset = lseek(fd, 0, SEEK_CUR); + printf("[%d] Offset: %d\n", pid, offset); + + aux = read(fd, buf, LINE2); + offset = lseek(fd, 0, SEEK_CUR); + printf("[%d] Offset: %d\n", pid, offset); + + aux = read(fd, buf, LINE3); + offset = lseek(fd, 0, SEEK_CUR); + printf("[%d] Offset: %d\n", pid, offset); + printf("%d\n", aux); + exit(0); +} + +static void do_close(int fd) { + /* TODO: In the child close file descriptor, in the parent wait for child to + * die and check if the file descriptor is still accessible. */ + + exit(0); +} + +int main(int argc, char **argv) { + if (argc != 2) + app_error("Usage: %s [read|close]", argv[0]); + + int fd = Open("test.txt", O_RDONLY, 0); + + if (!strcmp(argv[1], "read")) + do_read(fd); + if (!strcmp(argv[1], "close")) + do_close(fd); + app_error("Unknown variant '%s'", argv[1]); +} diff --git a/semestr-5/so/lista1/so21_lista_1/het.c b/semestr-5/so/lista1/so21_lista_1/het.c new file mode 100644 index 0000000..579abe4 --- /dev/null +++ b/semestr-5/so/lista1/so21_lista_1/het.c @@ -0,0 +1,71 @@ +#include "csapp.h" + +#define CONFLICT 0 +#define NO_CONFLICT 1 + +static int ndselect(int n) { + for (int column = 0; column < n; column++) { + int pid = fork(); + if (pid == 0) { + return column; + } + waitpid(pid, NULL, 0); + } + /* TODO: A loop is missing here that spawns processes and waits for them! */ + exit(0); +} + +static int conflict(int x1, int y1, int x2, int y2) { + return x1 == x2 + || y1 == y2 + || x1 + y1 == x2 + y2 + || x1 - y1 == x2 - y2; +} + +static bool check_conflict(int size, int board[size], int column) { + for (int i = 0; i < column; i++) { + if (conflict(board[i], i, board[column], column) == 1) return CONFLICT; + } + return NO_CONFLICT; +} + +static void print_line_sep(int size) { + for (int i = 0; i < size; ++i) + printf("+---"); + printf("+\n"); +} + +static void print_board(int size, int board[size]) { + for (int i = 0; i < size; ++i) { + print_line_sep(size); + for (int j = 0; j < size; ++j) + printf("|%s", board[i] == j ? " ♕ " : " "); + printf("|\n"); + } + print_line_sep(size); + printf("\n"); +} + +int main(int argc, char **argv) { + if (argc != 2) + app_error("Usage: %s [SIZE]", argv[0]); + + int size = atoi(argv[1]); + + if (size < 3 || size > 9) + app_error("Give board size in range from 4 to 9!"); + + int board[size]; + + /* TODO: A loop is missing here that initializes recursive algorithm. */ + for (int row = 0; row < size; row++) { + int column = ndselect(size); + board[row] = column; + if (check_conflict(size, board, row) == CONFLICT) + exit(0); + } + + print_board(size, board); + + return 0; +} diff --git a/semestr-5/so/lista1/so21_lista_1/include/bitstring.h b/semestr-5/so/lista1/so21_lista_1/include/bitstring.h new file mode 100644 index 0000000..66503f0 --- /dev/null +++ b/semestr-5/so/lista1/so21_lista_1/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/lista1/so21_lista_1/include/csapp.h b/semestr-5/so/lista1/so21_lista_1/include/csapp.h new file mode 100644 index 0000000..6ab9435 --- /dev/null +++ b/semestr-5/so/lista1/so21_lista_1/include/csapp.h @@ -0,0 +1,238 @@ +#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 + +#define __unused __attribute__((unused)) + +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/lista1/so21_lista_1/include/queue.h b/semestr-5/so/lista1/so21_lista_1/include/queue.h new file mode 100644 index 0000000..de4ddc9 --- /dev/null +++ b/semestr-5/so/lista1/so21_lista_1/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/lista1/so21_lista_1/include/rio.h b/semestr-5/so/lista1/so21_lista_1/include/rio.h new file mode 100644 index 0000000..bd62723 --- /dev/null +++ b/semestr-5/so/lista1/so21_lista_1/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/lista1/so21_lista_1/include/terminal.h b/semestr-5/so/lista1/so21_lista_1/include/terminal.h new file mode 100644 index 0000000..832358e --- /dev/null +++ b/semestr-5/so/lista1/so21_lista_1/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#Terminal_output_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/lista1/so21_lista_1/include/tree.h b/semestr-5/so/lista1/so21_lista_1/include/tree.h new file mode 100644 index 0000000..3355bad --- /dev/null +++ b/semestr-5/so/lista1/so21_lista_1/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/lista1/so21_lista_1/test.txt b/semestr-5/so/lista1/so21_lista_1/test.txt new file mode 100644 index 0000000..ab153f4 --- /dev/null +++ b/semestr-5/so/lista1/so21_lista_1/test.txt @@ -0,0 +1,3 @@ +Write programs that do one thing and do it well. +Write programs to work together. +Write programs to handle text streams, because that is a universal interface. |