>[!NOTE] Unmaintained Since 2018 > These types of libraries do not necessarily need to be constantly updated unless there are security issues. The primary developer was a company that was acquired by [[Microsoft]]. ACF is a [[Apache v2]] licensed collection of data structures and algorithms written in [[3. Reference/Software/Programming Languages/C|C]]. - [Source](https://github.com/appnexus/acf) > This C library contains core components on which other higher level libraries and applications can build. # Notability Non-block data structures and algorithms may be interesting to learn from. Contains another alternative integer to string function `an_itoa`. Worth comparing against [[Strings - itoa_for_linux]]. # Philosophy > Our goal with this initial code dump is to share read-optimised data structures implemented in C. The implementation is usually not all we dreamed of, and the dependency graph is sometimes unreasonable. However, the code has proved its mettle in production, builds to our real needs, and is known to not be overly bug-prone for users. We don't doubt that others have similar solutions to similar problems, and we hope that we can all learn from each other, even if we can't always immediately use one another's code. # OS Support # Features ### Data structures and non-blocking algorithms - `an_array`: more utility functions over the `an_array` already in acf. - `an_average`: racy exponential moving average. - `an_dict`, `an_dict_common`: type-safe, less bug-prone, wrappers for ConcurrencyKit's `ck_hs` SPMC hash set. - `an_hook`: fast dynamic feature flags via self-modifying (cross-modifying) code. - `an_hrlock`: hashed "big reader" reader-writer lock. - `an_hrw`: rendezvous hashing to pick elements from `an_dict` sets. - `an_interpolation_table`: a practical implementation of Demaine's, Jones's, and Patrascu's static interpolation search (Interpolation Search for Non-Independent Data, SODA 2004) - `an_interval`: a practical implementation of Chazelle's filtering search for stabbing queries over machine integers (Filtering search: a new approach to query answering, SIAM Journal on Computing 1986) - `an_itoa`: a faster integer to decimal string conversion. It seems everyone makes the mistake of initially using human-readable strings for systems that eventually become bottlenecked on `itoa`. This file was our stopgap while transitioning to a binary format. Yes, it is reliably faster than the branchy Facebook code. - `an_map`: another type-safe, easier to use, wrapper for ConcurrencyKit, this time `ck_ht`, the SPMC hash map. - `an_qsort.inc`: just some trivial changes to the FreeBSD quicksort to specialise it at compile-time. `AN_QSORT_ENABLE_INSERTION_SORT_HEURISTIC` is useful to turn off an optimisation that sometimes goes quadratic. - `an_rand`: convenient wrapper around xorshift128+. - `an_ring`: two-phase enqueue/dequeue for ConcurrencyKit's `ck_ring`. Useful for ring buffers of large, partially used, items. - `an_sampling`: windowed uniform sampling. - `an_sparse_bitmap`: stabbing queries for disjoint intervals of machine integers. - `an_sstm`: single-writer multi-version object-level transactional memory. - `an_streaming_quantile`: concurrent streaming quantile estimation. - `an_swlock`: compact single-writer multi-reader lock. - `an_zorder`: Morton/Z-ordering utilities. - `btree`: sorted flat container. - `int_set`: specialised btree for machine integers. - `log_linear_bin`: jemalloc-style log-linear binning, or, equivalently, high dynamic range histogram buckets. - `tsearch.inc`: unrolled ternary search for sorted arrays. ### [](https://github.com/appnexus/acf#generic-support-code) ### Generic support code - `an_buf`: It's a constant battle to keep the number of buffer types under control, especially as we depend on new libraries. `an_buf` is our attempt at a compatibility layer while we actually delete and merge buffer types. - `an_cc`: Compile-time trickery. - `an_malloc`: Multi-threaded tracked allocations, _and_ a bump pointer allocator for overlapping transaction lifetimes, in one huge file. - `an_md`, `x86_64`: Hardware timestamp counter code. - `an_poison`: That's our list of functions we definitely do not want to use. - `an_server`: Asynchronous HTTP server with some congestion control. - `an_smr`: A wrapper for safe-memory reclamation that we find easier to use for the AppNexus context, where it's more important that data update code be easy to maintain than for it to be fast. - `an_syslog`: Our old syslog sometimes deadlocks. Some may enjoy this hack to centralise syslog production and to throttle identical messages. - `an_table_hash`: We used to have a lot of different hash functions. We now only use murmurhash. - `memory`: Some memory management primitives. - `rtbr`: SMR driven by real time (i.e., the timestamp counter) instead of quiescence points or discrete epochs. ### [](https://github.com/appnexus/acf#necessary-evil-code) ### Necessary evil code - `an_string`: Clones of standard string manipulation functions that track allocations in `an_malloc`. - `an_thread`: We ported many concepts directly from OS code, with one worker per core. Doing so means we need per-thread blocks (to replace per-cpu storage), and these blocks of data must be safe to read from other threads. `an_thread` is our monolithic per-thread storage block. If we were to do it again, we'd probably avoid baking in the assumption of a pre-allocated set of per-thread data blocks; even the bounded (at most 32) set of workers is becoming an issue. - `an_time`: Various time manipulation utility functions. - `net/protocol/http-parser`: Vendored code for Joyent's HTTP parser. - `util`: Grab bag of who-knows-what. Despite everyone's best intentions, this sort of file seems to always happen. # Tips # References