<commit_before>Wheel-of-Fortune Memory Allocator
=================================

A little while ago, the [Wireshark Project](https://www.wireshark.org/) was in
need of a new memory management framework to replace its aging 'emem' framework.
Nothing available seemed to suit, so I (mostly) wrote one from scratch, called
[wmem](https://anonsvn.wireshark.org/viewvc/trunk/doc/README.wmem?view=markup).

The majority of wmem was bog-standard memory-pool code, but there was one
component that ended up turning into a *very* interesting exercise in
algorithms and data structures. Within wmem it is simply known as the "block"
allocator, but it was interesting enough that I extracted it from Wireshark,
and made it available stand-alone here. The wheel-of-fortune name will become
obvious once you understand how the recycler structure works.

It is one C source file that uses nothing but bare-bones standard C90, so it
should compile on basically any platform in existence.

Behaviour
---------

For a proper understanding of how the allocator works, read the rest of this
README. In brief though, `wof_alloc` is constant-time unless it needs to grab a
new block from the OS, the cost of which can be amortized. `wof_free` is always
constant-time. `wof_realloc` is constant-time if it doesn't have to move the<commit_msg>Update wireshark README link<commit_after>Wheel-of-Fortune Memory Allocator
=================================

A little while ago, the [Wireshark Project](https://www.wireshark.org/) was in
need of a new memory management framework to replace its aging 'emem' framework.
Nothing available seemed to suit, so I (mostly) wrote one from scratch, called
[wmem](https://code.wireshark.org/review/gitweb?p=wireshark.git;a=blob;f=doc/README.wmem).

The majority of wmem was bog-standard memory-pool code, but there was one
component that ended up turning into a *very* interesting exercise in
algorithms and data structures. Within wmem it is simply known as the "block"
allocator, but it was interesting enough that I extracted it from Wireshark,
and made it available stand-alone here. The wheel-of-fortune name will become
obvious once you understand how the recycler structure works.

It is one C source file that uses nothing but bare-bones standard C90, so it
should compile on basically any platform in existence.

Behaviour
---------

For a proper understanding of how the allocator works, read the rest of this
README. In brief though, `wof_alloc` is constant-time unless it needs to grab a
new block from the OS, the cost of which can be amortized. `wof_free` is always
constant-time. `wof_realloc` is constant-time if it doesn't have to move the
{'fraction_non_alphanumeric': 0.08832335329341318, 'fraction_numerical': 0.0014970059880239522, 'mean_word_length': 4.687234042553191, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 4, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2289030', 'n_tokens_mistral': 735, 'n_tokens_neox': 723, 'n_words': 370}