Skip to content

Instantly share code, notes, and snippets.

View justinmeiners's full-sized avatar

Justin Meiners justinmeiners

View GitHub Profile
justinmeiners /
Last active January 31, 2024 17:54
Why is std::map typically implemented as a red-black tree?

Why is std::map typically implemented as a red-black tree?

Why not a hash table?

A type only requires < operator (comparison) to be used as a key in a tree. However, hash tables require that each key type has a hash function defined. Keeping type requirements to a minimum is very important for generic programming so you can use it with a wide variety of types and algorithms.

Designing a good hash table requires intimate knowledge of the context it which it will be used. Should it use open addressing, or linked chaining? What levels of load should it accept before resizing? Should it use an expensive hash that avoids collisions, or one that is rough and fast?

Since the STL can't anticipate which is the best choice for your application, the default needs to be more flexible. Trees "just work" and scale nicely.

justinmeiners /
Last active February 9, 2023 17:17
A simple caching HTTP proxy in Python 3.
# A simple HTTP proxy which does caching of requests.
# Inspired by:
# but updated for Python 3 and some additional sanity improvements:
# - shutil is used to serve files in a streaming manner, so the entire data is not loaded into memory.
# - the http request is written to a temp file and renamed on success
# - forward headers
import http.server
import socketserver
import urllib.request
Standard recursive descent parsers are LL(1) parsers, yes (the 1 means that you only look at the very next token to decide which rule to apply). Because of the whole recursive descent thing, LL parsers are top-down parsers (whereas LR parsers are bottom-up).
Their big downside, in parsing programming languages, is in parsing infix operator expressions. For example, suppose you want to have a simple grammar that matches a language in which you can add and multiply binary digits (ignoring operator precedence for now):
Expr <- Expr "*" Digit
| Expr "+" Digit
| Digit
Digit <- "0"
justinmeiners / grid_neighbors.cpp
Last active October 27, 2022 19:36
How to iterate neighbors of a grid efficiently and concisely.
#include <algorithm>
template <typename I>
void rotate_2d(I& a, I& b) {
std::swap(a, b);
b = -b;
int main() {
// Suppose we want to iterate over the neighbors of a cell in a 2D grid:
justinmeiners / read_entire_file.c
Last active October 25, 2022 20:43
Read an entire file into a buffer (without race conditions or seeking).
void* fread_all(FILE* file, size_t* out_size) {
const size_t BLOCK_SIZE = 32 * 1024;
const size_t MEDIUM_SIZE = 10 * 1024 * 1024;
*out_size = 0;
size_t cap = 0;
char* data = NULL;
while (1) {
justinmeiners /
Created August 22, 2022 21:04 — forked from BB9z/
Reveal the Latest Simulator Application’s Data Container in Finder.
cd ~/Library/Developer/CoreSimulator/Devices/
isVaildDeviceDir () {
# echo $1
# $1 is not directory or empty
if ! [[ -d $1 ]] || ! [[ -n $1 ]] ; then
return 1
// gcc -I/usr/X11/include -L/usr/X11/lib -lX11 xlib_image.c
// bsd: gcc -I/usr/X11R6/include -L/usr/X11R6/lib -lX11 xlib_image.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <X11/Xlib.h>
#include <X11/Xutil.h>
void draw(char *rgb_out, int w, int h)