<commit_before>// ** a non blocking hash map **
//
// author: <NAME> <<EMAIL>>
// version: 2010-04-14
// depends: libatomic-ops
// license: MIT; see license.txt
//
// inspired by Cliff Clicks Java version; I've simplified the state machine and other algorithms
//
// internal state machine; keys map to null if they 1) don't exist in map; or 2) are updated to null (== deleted)
// notice the states must be read (and written) in key, hash, value order (using a true happens-before fashion)
// key, hash, value = <state name> -> ("transition name": <new state>)*
// 0, _, _ = free        -> "claim": partial, "resize empty": sized-free
// k, h, v = value       -> "update": value, "resize value": sized-value
// S, _, _ = sized-free  -> "restart"
// k, h, S = sized-value -> "restart"
// k, 0, _ = partial     -> "wait hash": value
//
// Notice, though it is a _non blocking_ hash map, it does sometimes yield (sleep) the current thread. But only if
// another thread promised to do something, but was unscheduled before (or is still busy) doing it. Since these
// promises will happen in a near future without any blocking, this is ok. Unfortunately we cannot know the identity
// of the promising thread, and we cannot yield only until the promise is fullfilled.
// (A signal-when-memory-written-or-is-not(oldval) ... might be a nice primitive to complement cas; futex?)
//
// Situations where a thread yields:
// * waiting for a hash to appear, after we raced to observe a previously not claimed key slot
// * when the map needs resizing, we yield to the winner of the resize to publish new (uninitialized) map
// * when helping zeroing or copying, we yield to wait until all other helpers are done
// * after resize, we yield until new map is promoted to current map (by the winner of the second case)
//
// One danger! When resizing a map, we delete (and free) keys mapping to null. However another thread using the old
// table might still do equals() on the key we just free'd. The result of this equals doesn't matter (as long as it
// finishes somehow), since it will read a SIZED for the value. But, if the free also unmaps the page the key resides
// on, we will generate a page fault. (Plus the equals function might get passed in a corrupt key, which might not be
// expected and cause trouble on its own.) Maybe something needs to be done about this ...
//
//
// TODO some false sharing might be going on, especially _btodo and _bdone fields
// TODO yield is great on macosx, but on linux it is horrible, but so is any kind of sleep ... unless time ./test lies
// TODO we don't need to volatile read key,hash,value ... think about that (at least key and hash are final)
// TODO a shrinking map might want to resize into something smaller, how and when and why?
// TODO add more public api, iterators and such, and a delete that doesn't own the key ... (pass in free function to _putif?)
// TODO allow null functions for hash/equals/free when: key == hash, equals == value compare, free == nop
// TODO add support for garbage collectors and fixed Values or such... as compile time option/macros maybe?
// TODO refactor _zero_block and _copy_block; they share a lot of code
// TODO handle out of memory ... but we really cannot do anything sensible
// TODO think about how to handle deleted keys that we free, it is not truly safe this way
// TODO on processors where volatile read/writes do not guarentee a fence, we might have to add more memory fences
// TODO for _get, we don't need do a full circle before return null; since _put will never put anything beyond reprobe limit

#define _GNU_SOURCE
#include <unistd.h>
#include <atomic_ops.h>
#include <sys/time.h>
#include <strings.h>
#include <sched.h>

#define HAVE_DEBUG
#define HAVE_STRACE

#include "debug.h"

#undef STRACE
#define STRACE 0

// threading primitives
static void yield() { sched_yield(); }
static void read_barrier() { AO_nop_read(); }
static void write_barrier() { AO_nop_write(); }
static int cas(void *addr, const void *nval, const void *oval) {
    return AO_compare_and_swap(addr, (AO_t)oval, (AO_t)nval);
}


// ** actual implementation **

typedef struct entry entry;
struct entry {
    volatile void *_key;
    volatile void *_val;
    volatile unsigned int _hash;
};

typedef struct header header;
struct header {
    volatile AO_t _btodo;   // unsigned long; _btodo and _bdone are placed apart to prevent false cachline sharing
    unsigned long len;      // final unsigned long
    header *prev;           // a linked list of older maps to free later
    volatile AO_t _bdone;   // unsigned long
    entry kvs[0];           // the actual entries
};


// the map "owns" the keys, but it needs an equals, hash and free function
typedef int (hashmap_key_equals)(void *left, void *right);
typedef unsigned int (hashmap_key_hash)(void *key);
typedef void (hashmap_key_free)(void *key);

typedef struct HashMap HashMap;
struct HashMap {
    volatile AO_t _size;           // unsigned long
    volatile unsigned int changes; // counting all map modifications; but dropping some read/writes is ok
    volatile header *_kvs;         // the main map
    volatile header *_nkvs;        // the new map when a resize is in flight, so other threads can help

    hashmap_key_equals *equals_func;
    hashmap_key_hash   *hash_func;
    hashmap_key_free   *free_func;
};

#define INITIAL_SIZE 4
#define REPROBE_LIMIT 17
#define BLOCK_SIZE (1024 * 8)

#define null 0                        // indicates value is deleted
static void *SIZED   = "__SIZED__";   // marker to indicate map is or has resized
static void *IGNORE  = "__IGNORE__";  // marker to indicate old map value is to be ignored
static void *DELETED = "__DELETED__"; // marker to indicate key is to be deleted (when resizing)


// when racing to resize, the winner must succesfully cas this into map->nkvs
static header * kvs_promise = (header *)1;

static header * header_new(unsigned int len) {
    header *h = malloc(sizeof(header) + sizeof(entry) * len);
    assert(h);
    h->len = len;
    h->_btodo = 0;
    h->_bdone = 0;
    h->prev = 0;<commit_msg>IGNORE must actually be public<commit_after>// ** a lockless high throughput hash map **
//
// author: <NAME> <<EMAIL>>
// version: 2010-04-14
// depends: libatomic-ops
// license: MIT; see license.txt
//
// inspired by Cliff Clicks Java version; I've simplified the state machine and other algorithms
//
// internal state machine; keys map to null if they 1) don't exist in map; or 2) are updated to null (== deleted)
// notice the states must be read (and written) in key, hash, value order (using a true happens-before fashion)
// key, hash, value = <state name> -> ("transition name": <new state>)*
// 0, _, _ = free        -> "claim": partial, "resize empty": sized-free
// k, h, v = value       -> "update": value, "resize value": sized-value
// S, _, _ = sized-free  -> "restart"
// k, h, S = sized-value -> "restart"
// k, 0, _ = partial     -> "wait hash": value
//
// Notice, it is not truly a _non blocking_ hash map, since it does sometimes yield (sleep) the current thread. But only if
// another thread promised to do something, but was unscheduled before (or is still busy) doing it. Since these
// promises will happen in a near future without any blocking, this is ok. Unfortunately we cannot know the identity
// of the promising thread, and we cannot yield only until the promise is fullfilled.
// (A signal-when-memory-written-or-is-not(oldval) ... might be a nice primitive to complement cas; futex?)
//
// Situations where a thread yields:
// * waiting for a hash to appear, after we raced to observe a previously not claimed key slot
// * when the map needs resizing, we yield to the winner of the resize to publish new (uninitialized) map
// * when helping zeroing or copying, we yield to wait until all other helpers are done
// * after resize, we yield until new map is promoted to current map (by the winner of the second case)
//
// One danger! When resizing a map, we delete (and free) keys mapping to null. However another thread using the old
// table might still do equals() on the key we just free'd. The result of this equals doesn't matter (as long as it
// finishes somehow), since it will read a SIZED for the value. But, if the free also unmaps the page the key resides
// on, we will generate a page fault. (Plus the equals function might get passed in a corrupt key, which might not be
// expected and cause trouble on its own.) Maybe something needs to be done about this ...
//
//
// TODO some false sharing might be going on, especially _btodo and _bdone fields
// TODO yield is great on macosx, but on linux it is horrible, but so is any kind of sleep ... unless time ./test lies
// TODO we don't need to volatile read key,hash,value ... think about that (at least key and hash are final)
// TODO a shrinking map might want to resize into something smaller, how and when and why?
// TODO add more public api, iterators and such, and a delete that doesn't own the key ... (pass in free function to _putif?)
// TODO allow null functions for hash/equals/free when: key == hash, equals == value compare, free == nop
// TODO add support for garbage collectors and fixed Values or such... as compile time option/macros maybe?
// TODO refactor _zero_block and _copy_block; they share a lot of code
// TODO handle out of memory ... but we really cannot do anything sensible
// TODO think about how to handle deleted keys that we free, it is not truly safe this way
// TODO on processors where volatile read/writes do not guarentee a fence, we might have to add more memory fences
// TODO for _get, we don't need do a full circle before return null; since _put will never put anything beyond reprobe limit

#define _GNU_SOURCE
#include <unistd.h>
#include <atomic_ops.h>
#include <sys/time.h>
#include <strings.h>
#include <sched.h>

#define HAVE_DEBUG
#define HAVE_STRACE

#include "debug.h"

#undef STRACE
#define STRACE 0

// threading primitives
static void yield() { sched_yield(); }
static void read_barrier() { AO_nop_read(); }
static void write_barrier() { AO_nop_write(); }
static int cas(void *addr, const void *nval, const void *oval) {
    return AO_compare_and_swap(addr, (AO_t)oval, (AO_t)nval);
}


// ** actual implementation **

typedef struct entry entry;
struct entry {
    volatile void *_key;
    volatile void *_val;
    volatile unsigned int _hash;
};

typedef struct header header;
struct header {
    volatile AO_t _btodo;   // unsigned long; _btodo and _bdone are placed apart to prevent false cachline sharing
    unsigned long len;      // final unsigned long
    header *prev;           // a linked list of older maps to free later
    volatile AO_t _bdone;   // unsigned long
    entry kvs[0];           // the actual entries
};


// the map "owns" the keys, but it needs an equals, hash and free function
typedef int (hashmap_key_equals)(void *left, void *right);
typedef unsigned int (hashmap_key_hash)(void *key);
typedef void (hashmap_key_free)(void *key);

typedef struct HashMap HashMap;
struct HashMap {
    volatile AO_t _size;           // unsigned long
    volatile unsigned int changes; // counting all map modifications; but dropping some read/writes is ok
    volatile header *_kvs;         // the main map
    volatile header *_nkvs;        // the new map when a resize is in flight, so other threads can help

    hashmap_key_equals *equals_func;
    hashmap_key_hash   *hash_func;
    hashmap_key_free   *free_func;
};

#define INITIAL_SIZE 4
#define REPROBE_LIMIT 17
#define BLOCK_SIZE (1024 * 8)

#define null 0                        // indicates value is deleted
       void *IGNORE  = "__IGNORE__";  // marker to indicate old map value is to be ignored
static void *SIZED   = "__SIZED__";   // marker to indicate map is or has resized
static void *DELETED = "__DELETED__"; // marker to indicate key is to be deleted (when resizing)


// when racing to resize, the winner must succesfully cas this into map->nkvs
static header * kvs_promise = (header *)1;

static header * header_new(unsigned int len) {
    header *h = malloc(sizeof(header) + sizeof(entry) * len);
    assert(h);
    h->len = len;
    h->_btodo = 0;
    h->_bdone = 0;
    h->prev = 0;
{'fraction_non_alphanumeric': 0.09151822193168818, 'fraction_numerical': 0.004412485700277823, 'mean_word_length': 3.3339235127478752, 'pattern_counts': {'":': 12, '<': 23, '<?xml version=': 0, '>': 45, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, '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': '3159487', 'n_tokens_mistral': 3568, 'n_tokens_neox': 3398, 'n_words': 1739}