Tag: #c

Implement a queue using two stacks, with one stack for the back of the queue and one for the front. Reverse the back stack onto the front stack when dequeuing to maintain the queue order. 2020-01-21

A stack with a min operation that runs in O(1) time. Store the current minimum alongside each element, or use run-length encoding to compress the stack of minimums. 2020-01-19

The head is the front of the queue, allowing efficient dequeue. The tail is the back of the list. To enqueue efficiently, we keep a reference to the tail. 2020-01-18

The head of the list is the top of the stack. 2020-01-17

Find the middle node of the linked list using the “runner” trick. Reverse the first half, then compare the nodes pairwise from the middle outwards. Restore the list to its original state before returning. 2020-01-16

A trick to find the middle of a linked list by using two pointers, slow and fast, where fast moves twice as fast as slow. 2020-01-15

Reverse a linked list by treating it as a stack, popping elements and pushing them onto a new list. An implementation in C without a separate stack. 2020-01-14

A C function to partition a linked list around a value x, running in optimal time and space. 2020-01-13

To delete a node from the middle of a linked list, copy the value and next pointer of the next node to the current node, then free the next node. 2020-01-12

Use the “runner” technique with two pointers - one leading by k nodes - to find the kth last element of a singly linked list without knowing the list length in advance. 2020-01-11

To remove duplicates from an unsorted linked list with no extra memory, use a nested loop to check each node against all others, removing duplicates as you go. Time complexity is O(n^2). 2020-01-10

An in-place algorithm to rotate a square matrix by 90 degrees. The key is to rotate 4 corresponding points using a formula, applying this to all points in the top-left corner. 2020-01-09

Compresses a string by replacing consecutive repeated characters with the character and its count. The solution requires two passes to first calculate the length of the compressed string, then generate it. 2020-01-08

A C function to replacing spaces with "%20" in-place, by iterating from the end, preserving true string length. 2020-01-07

A C function to determine if one string is a permutation of another, using a character distribution representation for optimal time and space complexity. 2020-01-06

An in-place string reversal function in C, starting by swapping the first and last characters, then iterating towards the middle. 2020-01-05

A recursive algorithm to determine if a string has all unique characters, with an analysis of its time complexity. 2020-01-04

The Morris approximate counter is incremented probabilistically. 2018-12-17

An efficient algorithm to round up to the next power of two in C, using bitwise operations and compiler intrinsics for constant-time performance. 2018-03-30

The magic shell string 3>&2 2>&1 1>&3- swaps stdout and stderr. It does with the dup2 system call to swap file descriptors. 2018-02-22

A C program that writes “hello, world!” to the console using inline assembly instead of standard library functions, demonstrating direct system call invocation. 2018-02-20

Replacing printf with write, and finally directly using the syscall function with inline assembly. 2018-02-19

Subnets divide the IP address space hierarchically using bitstring prefixes. We check if an IP address is in a subnet using C. 2018-02-10

nscd, a local DNS resolver within glibc, is non-standard. Instead, use a local DNS server like named or dnscache. 2018-02-05

getaddrinfo ostensibly does DNS lookups. Sounds simple, but it uses more than 100 system calls! Let’s trace the crazy path of address lookup on Linux. 2018-02-03

less uses the terminal’s “alternate screen” feature to clear the screen and display the contents of a file, and then restores the previous screen when exiting. 2017-12-04

extern declares a variable without defining it, allowing the linker to find the definition elsewhere. This is useful when a variable is declared in one file but defined in another. 2017-08-27

#include in C does not import functionality, but rather inserts the preprocessed text of the included file. The actual implementation of the included functions, like fprintf, is provided through linking. 2017-08-21

C’s _Generic is not true generics. It requires manual implementation of concrete type cases, unlike generics that automatically generate code for any type. 2017-08-19

The openssl passwd command hashes passwords using the outdated crypt algorithm, with truncation to 8 characters - a poor choice for secure password hashing. 2017-03-12

Encrypt and decrypt text using the openssl enc command with a password and AES-256 cipher. The encrypted text is base64-encoded. 2017-03-09

Examines Redis’s source code to understand how it tracks subscriptions, handles disconnections, and implements pattern subscriptions, highlighting potential pitfalls and attack vectors. 2017-03-01

Focused on learning C, UNIX, and networking fundamentals. To avoid becoming a neckbeard, I’ll keep my projects grounded in real-world applications. March will be dedicated to Vidrio. 2017-03-01

Install ebe assembler with a one-liner, but be wary of the SourceForge installation script. 2017-03-01

A TCP server that uses pthread to serve multiple clients concurrently, with an “echo” server for each connection. 2017-02-28

The domain and type arguments to socket() describe the protocol family and socket type, respectively. The protocol argument specifies the actual protocol to use, which may be inferred from the domain and type. 2017-02-27

UTF-8 is a character encoding that can represent the entire Unicode character set. It’s variable-length, self-synchronizing, and an extension of ASCII. 2017-02-26

A TCP server that uses the fork system call to create a new child process for each accepted connection, allowing it to handle multiple clients concurrently. 2017-02-25

mode_t is a bitfield type in C that represents file permissions, including read, write, and execute permissions for the owner, group, and other classes. It provides symbolic constants to set and check these permissions. 2017-02-24

A program in C that prints the individual bits of various data types, showing how they are represented in memory. 2017-02-23

ssize_t is a signed version of size_t, used to represent return values from system calls that may need to indicate error with -1. 2017-02-22

A FIFO is a special file that allows inter-process communication. The mkfifo system call creates a FIFO, enabling processes to read from and write to it. 2017-02-21

lsof lists open system resources, including pipes, sockets, and yes, files. It shows their type, owner, and location. 2017-02-20

Generate Intel and AT&T assembly with clang, demonstrating the difference in syntax between the two styles. 2017-02-19

setjmp and longjmp in C bypass normal function call and return flow, allowing a function to return to a previously saved state. setjmp saves the current execution context, and longjmp restores it. 2017-02-18

A C function to create a new process, set up its standard input/output/error pipes, and return a struct containing the process ID and pipe file descriptors. 2017-02-17

To close a file descriptor in C, use the close system call. Multiple descriptors can reference the same underlying file or pipe. The pipe is only closed when all references are closed. 2017-02-16

Use the dup system call to duplicate a file descriptor in C, allowing two references to the same underlying pipe. 2017-02-15

Lamport timestamps measure time and causality in distributed systems. Timestamps are assigned to events, with the property that if event A happened-before event B, then A’s timestamp is less than B’s. 2017-02-12

To call a program from C, use `fork` then `execve`. There is no more direct way! 2017-02-07

fork duplicates the current process. It returns 0 in the child process. In the parent process, it returns the child’s new process id. 2017-02-06

execve replaces the current process with a new one. It takes a path, an argument array, and an environment array. The process never returns unless execve fails. 2017-02-05

C compilation involves 6 stages: preprocessing, parsing, AST generation, LLVM IR production, assembly generation, and linking to produce the final executable or shared library. 2017-02-04

Compiling with the -S flag generates assembly. 2017-02-03

Access environment variables in C by using the global environ variable, which points to an array of string pointers representing the environment. 2017-02-02

All system calls on macOS 10.12, categorized by the functionality they provide, such as process management, file operations, memory management, etc. 2017-01-31

The man command is used to access the UNIX manual pages, which are organized into numbered sections. man searches a predefined path to find the relevant manual page. 2017-01-30

Processes can communicate via files, pipes, signals, sockets, message queues, semaphores, and shared memory. 2017-01-29

To write to a file, open the file, mmap the file descriptor, then write to memory. 2017-01-28

Use mmap to map a file into memory, then read and write the memory directly. 2017-01-27

mmap is a system call in C that allows programs to manipulate underlying hardware resources, such as physical memory or files, using ordinary memory manipulation. 2017-01-26

How to check if a 64-bit word contains a zero byte. A step-by-step example and a proof of correctness. 2017-01-24

Integers in C are int by default, while suffixes like L and U denote long and unsigned types. Floats are double without a suffix. 2017-01-23

Literals are lvalues with addresses, while constants are rvalues without addresses. In C, only string literals are literals; other “literals” like numbers and characters are constants. 2017-01-22

“lvalue” either means “expression which can be placed on the left-hand side of the assignment operator”, or means “expression which has a memory address”. “rvalue” is defined as “all other expressions”. 2017-01-21

The UINT64_C macro appends the ULL suffix to a 64-bit unsigned integer literal, converting it to the appropriate type. 2017-01-20

C signal handlers reuse the same call stack as normal functions, but can optionally use a special signal stack instead. 2017-01-14

sigaction says what to do when a signal is received. signal is a simplified interface to sigaction. 2017-01-13

Executing do_something() N times in C using a while loop and post-decrement operator. 2017-01-12

To unregister a signal handler in C, use signal(signum, SIG_DFL) to reset the disposition to the default, or signal(signum, SIG_IGN) to set the disposition to ignore the signal. 2017-01-11

signal returns the old signal handler pointer for given signal number. 2017-01-10

Signals in C are software interrupts that allow programs to respond to events. The signal.h header provides functions to register signal handlers and send signals. 2017-01-09

Using unique error codes with linkable documentation improves error reporting. Provide a central error page URL with each error message. 2017-01-05

Bitfields in C allow compact bit packing in structs, avoiding manual bitwise operations for greater safety and clarity, at the cost of some language complexity. 2017-01-04

A union in C allows one variable to hold different data types, where the storage is shared. The size of a union is at least the size of its largest member. Fields in a union have the same byte offset. 2017-01-03

Efficient packing of game player data into 16 bits using bitwise operations on a uint16_t type. 2017-01-02

GCC’s ‘statement expressions’ allow inserting statements into expression positions. Behavior is unspecified. 2016-12-30

Redis uses length-prefixed strings with pointers into the middle of the allocation, allowing C-string operations on the string data. 2016-12-28

C allows a single array field of incomplete type (char []) at the end of a struct definition. The size of the struct is determined by the size of the fixed fields, and the dynamic-sized array is allocated separately. 2016-12-27

Use the times() system call in C to measure the CPU time used by a process, distinguishing between time charged to the process itself and time charged to the kernel on its behalf. 2016-12-26

C array literals can use explicit indexes. The array length is determined by the largest explicit index. 2016-12-25

perror in C prints a human-readable description of the last error that occurred, as stored in the global errno variable. 2016-12-24

Useful to show how C represents various data types. 2016-12-22

htons and htonl convert values between host and network byte order, where network order is big-endian. ntohl and ntohs are the inverse functions. 2016-12-21

A C program that creates an HTTP server that responds with “Hello, world!” to every request. 2016-12-20

The syscalls needed for a simple UDP echo server are socket, bind, recvfrom, sendto, and close. 2016-12-19

Kqueue is a more efficient alternative to select for managing multiple TCP connections, providing a publish-subscribe model for tracking events in the kernel. 2016-12-18

fdset in C is a data structure that represents a set of file descriptors. The FD_SET, FD_CLR, FD_ISSET, and FD_ZERO macros are used to manipulate and inspect these sets. 2016-12-17

The select syscall allows a process to sleep and wake up when a file descriptor is ready for reading, writing, or has an exceptional condition. This enables a TCP server to handle multiple clients concurrently. 2016-12-16

File descriptors should be called “resource descriptors”. They represent various system resources, not just regular files. The operations you can perform depend on the specific resource. 2016-12-15

A minimal TCP server in C uses the socket, bind, listen, accept, recv, send, and close syscalls to manage connections. 2016-12-14

errno lets you access error codes from system calls. It’s a global int. 2016-12-13

static functions in C are only callable within the translation unit they are defined in, not across the whole program. 2016-12-12

Use i & (n-1) to compute i % n, when n is a power of two. This avoids the modulo operation. 2016-12-10

Macros in C can define token replacements or function-like replacements. 2016-12-09

Arrays in C can “decay” to pointers, but are not inherently pointers. The size of an array is lost during decay. 2016-12-08

Automatic variables in a Makefile, like $@ for the target and $^ for the dependencies, reduce repetition in rules. 2016-12-07

C strings use null-terminated byte arrays, which cannot represent arbitrary binary data. Binary-safe strings explicitly store the length, allowing them to represent any sequence of bytes. 2016-12-06

Set the C compiler in Makefile using predefined variable $(CC), which defaults to cc and can be redefined. 2016-12-05

A FILE is a C data type that represents an open file. It contains metadata about the file, such as its file descriptor and buffers. 2016-12-04

The restrict keyword in C is a type qualifier that indicates a pointer parameter points to an object not accessed through any other pointer in the function’s scope. This allows the compiler to make optimizations. 2016-12-03

const is a type qualifier in C that makes a variable unassignable, except during initialization. 2016-12-02

C99 introduced the stdbool.h header, providing bool, true, and false for boolean values, building on the _Bool type. 2016-12-01

realloc resizes an allocated memory block, copying contents if necessary. 2016-12-01

C is defined in several places, including “The C Programming Language” by Kernighan and Ritchie, and a series of ISO C standards (C89, C99, C11). 2016-11-30

Computing a pointer to unowned memory invokes undefined behavior, even without dereferencing! 2016-11-30

Use concatenated string literals with newline characters to define multi-line string literals in C. 2016-11-30

C string literals can contain comment-like characters, which are treated as literal text, not as comments. 2016-11-30

C array subscripts are defined as pointer arithmetic, where a[b] means *(a+b). This means a[b] is the same as b[a]! 2016-11-30

To find out which preprocessor your C compiler uses, run the compiler with the -print-prog-name=cpp flag, which shows the path to the preprocessor subprogram it calls. 2016-11-29

size_t is used to represent the size of objects in memory. It is commonly used for array indexing. 2016-11-29

Use uintptr_t to count objects in C, as it can represent the largest possible pointer value. 2016-11-29

static in C can modify variable declarations inside and outside a function body, and function parameters. 2016-11-28

void in a C function parameter list means the function takes no arguments, whereas an empty list allows for an unspecified number of arguments. 2016-11-27

void in C has multiple meanings: as a return type to indicate no return value, as a parameter type to indicate no parameters, and as a pointer type to indicate a pointer to an unknown type. 2016-11-27

The “K&R-style” function definition in C uses an initializer list to declare parameters, unlike the more common parameter type list. This old-style definition has significant semantic differences and should be avoided due to its potential for undefined behavior. 2016-11-27

A convention for expressing complex C types using typedef and a “reverse Polish notation” syntax to improve readability. 2016-11-24

The stack layout in C includes function arguments, return address, and local variables. Addresses decrease as you go through the arguments, and the stack grows downward with each function call. 2016-11-24

Variadic functions in C use the ... syntax to accept an arbitrary number of arguments. The stdarg.h library provides va_start, va_arg, and va_end to access the arguments. 2016-11-23