-
Notifications
You must be signed in to change notification settings - Fork 14
/
hashtable1.h
48 lines (40 loc) · 1.29 KB
/
hashtable1.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#ifndef __COMMON_HASHTABLE1_H__
#define __COMMON_HASHTABLE1_H__
#include <mintomic/mintomic.h>
//----------------------------------------------
// The World's Simplest Lock-Free HashTable
//
// Maps 32-bit integers to 32-bit integers.
// Uses open addressing with linear probing.
// You can call SetItem and GetItem from several threads simultaneously.
// GetItem is wait-free.
// SetItem is lock-free.
// You can't assign any value to key = 0.
// In the m_cells array, key = 0 is reserved to indicate an unused cell.
// You can't assign value = 0 to any key.
// value = 0 means the key is unused.
// The hash table never grows in size.
// You can't delete individual items from the hash table.
// You can Clear the hash table, but only at a time when there are no other calls being made from other threads.
//----------------------------------------------
class HashTable1
{
public:
struct Entry
{
mint_atomic32_t key;
mint_atomic32_t value;
};
private:
Entry* m_entries;
uint32_t m_arraySize;
public:
HashTable1(uint32_t arraySize);
~HashTable1();
// Basic operations
void SetItem(uint32_t key, uint32_t value);
uint32_t GetItem(uint32_t key);
uint32_t GetItemCount();
void Clear();
};
#endif // __COMMON_HASHTABLE1_H__