Writing a simple pool allocator in C
I found out about pool allocators some time ago, and I really liked its simplicity and high performance, so I decided to write my own. This article was initially inspired by Dmitry Soshnikov’s article. It’s also worth mentioning that this article was discussed in Hacker News. Similarly to malloc, a pool allocator allows the user to allocate memory at run time. The pool allocator, however, is much
GitHub - orlp/polymur-hash: The PolymurHash universal hash function.
PolymurHash is a 64-bit universal hash function designed for use in hash tables. It has a couple desirable properties: It is mathematically proven to have a statistically low collision rate. When initialized with an independently chosen random seed, for any distinct pair of inputs m and m' of up to n bytes the probability that h(m) = h(m') is at most n * 2^-60.2. This is known as an almost-univers
Leo Robinovitch @ The Leo Zone
I implemented a simple hash table in C when solving a problem in CS Primer. Solving it helped me gain better intuition around hash functions, pointers, and memory segments like the stack and the heap. BasicsYou have probably encountered a hash table in the wild, like a dict in Python, map in Go, or Map in JavaScript. Hash tables associate a key with a value. Setting, looking up, and deleting value
The quick and practical "MSI" hash table
Follow-up: Solving “Two Sum” in C with a tiny hash table I generally prefer C, so I’m accustomed to building whatever I need on the fly, such as heaps, linked lists, and especially hash tables. Few programs use more than a small subset of a data structure’s features, making their implementation smaller, simpler, and more efficient than the general case, which must handle every edge case. A typical
Faster integer formatting - James Anhalt (jeaiii)’s algorithm
This post is about an ingenious algorithm for printing integers into decimal strings. It sounds like an extremely simple problem, but it is in fact quite more complicated than one might imagine. Let us more precisely define what we want to do: we take an integer of specific bit-width and a byte buffer, and convert the input integer into a string consisting of its decimal digits, and then write it
taxicat1.github.io
Reversing an integer hash function This is an integer hash function written by Thomas Wang: uint32_t hash6432shift(uint64_t key) { key = (~key) + (key << 18); key ^= key >> 31; key *= 21; key ^= key >> 11; key += key << 6; key ^= key >> 22; return 0xFFFFFFFF & key; } It hashes down a 64-bit input to a 32-bit output. It has good mixing: basic statistical analysis can show that it has reasonably goo
Implementing Hash Tables in C
NOTE(s): The article is in “draft” status. The content was originally written in 2017. The intended audience for this article is undergrad students or seasoned developers who want to refresh their knowledge on the subject. The reader should already be familiar with C (pointers, pointer functions, macros, memory management) and basic data structures knowledge (e.g., arrays, linked lists, and binary
How to implement a hash table (in C)
March 2021 Summary: An explanation of how to implement a simple hash table data structure using the C programming language. I briefly demonstrate linear and binary search, and then design and implement a hash table. My goal is to show that hash table internals are not scary, but – within certain constraints – are easy enough to build from scratch. Go to: Linear search | Binary search | Hash tables
State machines are wonderful tools
This article was discussed on Hacker News. I love when my current problem can be solved with a state machine. They’re fun to design and implement, and I have high confidence about correctness. They tend to: Present minimal, tidy interfaces Require few, fixed resources Hold no opinions about input and output Have a compact, concise implementation Be easy to reason about State machines are perhaps o
Implementing cosine in C from scratch
Austin Z. Henley Associate Teaching Professor Carnegie Mellon University Implementing cosine in C from scratch 7/19/2020 Update 7/20: See the discussion of this post on Reddit. Update 3/22: See more discussion of this post on Hacker News and Reddit. Update 6/23: See even more discussion of this post on Hacker News. TL;DR: I explored how to implement cosine using a few different approaches. One of
GitHub - scandum/quadsort: Quadsort is a branchless stable adaptive mergesort faster than quicksort.
ロックフリーアルゴリズムによるFIFOバッファ - Qiita
はじめに 私が組み込みプログラミングを始めたころ(まだインターネットもなく組み込みマイコンもAKI-80とかZ80系主流で遊んでいた時代)に大学の先輩に教えてもらったテクニックです。今どきのCPU向けではないですが、私自身が古典的かつ重要な要素が含まれており、組み込みプログラミングに引き込まれたきっかけの一つでもありますので、当時を思い出しつつ記事にしてみます。 「ロックフリーなアルゴリズム」についてはこちらのWikipediaの記事がわかりやすいです。 これらのアルゴリズムは、割り込み禁止やミューテックスなどのロックを用いずに、割り込みハンドラやマルチタスク／マルチスレッドなどの異なる非同期な実行コンテキスト間で情報を渡すことを目的としており、今回はその応用内でのFIFOバッファの構成例となります。 近年ではArduinoなどの組み込みプログラミングも手軽に行える環境が増えています。また
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - nishihatapalmer/HashChain: A very fast online search algorithm
GitHub - clibraries/array-algorithms: Unintrusive algorithms for C arrays OR a C implementation of <algorithm> from C++
GitHub - scandum/fluxsort: A fast branchless stable quicksort / mergesort hybrid that is highly adaptive.
GitHub - scandum/rotate: A collection of array rotation algorithms.
notes/fast-case-conversion at master · apankrat/notes
GitHub - scandum/crumsort: A branchless unstable quicksort / mergesort that is highly adaptive.
GitHub - viega/hatrack: Fast, multi-reader, multi-writer, lockless data structures for parallel programming
GitHub - mkirchner/linked-list-good-taste: Linus Torvalds' linked list argument for good taste, explained
