commit 2a52a277ff15c390d69e6f61974425ac98e1a88c
parent 66046d1bf1b0b4c2f421389510bed001e142993a
Author: Remy Noulin <loader2x@gmail.com>
Date: Fri, 19 Aug 2022 09:40:49 -0400
add rate limiter and reasonable limits
rateLimiter/hashfunctions.c | 47 ++
rateLimiter/hashfunctions.h | 6 +
rateLimiter/hashtable.c | 20 +
rateLimiter/hashtable.h | 1310 +++++++++++++++++++++++++++++++++++++
rateLimiter/main.c | 30 +
rateLimiter/rateLimiter.c | 257 ++++++++
rateLimiter/rateLimiter.h | 107 +++
rateLimiter/rateLimiterInternal.h | 6 +
serverPackage.sh | 1 +
serverPackage.yml | 2 +-
sserver.c | 24 +-
11 files changed, 1807 insertions(+), 3 deletions(-)
Diffstat:
11 files changed, 1807 insertions(+), 3 deletions(-)
diff --git a/rateLimiter/hashfunctions.c b/rateLimiter/hashfunctions.c
@@ -0,0 +1,47 @@
+
+#include "libsheepyObject.h"
+#include "hashfunctions.h"
+
+/**
+ * FNV 1-a string hash.
+ */
+u32 strHashFNV1A(char *k) {
+ u32 hash = 2166136261U;
+ for (const u8* ptr = (u8*)k; *ptr; ptr++) {
+ hash = (hash ^ *ptr) * 16777619U;
+ }
+ return hash;
+}
+
+/**
+ * Integer reversible hash function for 32 bits.
+ * Implementation of the Robert Jenkins "4-byte Integer Hashing",
+ * from http://burtleburtle.net/bob/hash/integer.html
+ */
+u32 u32Hash(u32 k) {
+ k -= k << 6;
+ k ^= k >> 17;
+ k -= k << 9;
+ k ^= k << 4;
+ k -= k << 3;
+ k ^= k << 10;
+ k ^= k >> 15;
+ return k;
+}
+
+/**
+ * Integer reversible hash function for 64 bits.
+ * Implementation of the Thomas Wang "Integer Hash Function",
+ * from http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm
+ */
+u64 u64Hash(u64 k) {
+ k = ~k + (k << 21);
+ k = k ^ (k >> 24);
+ k = k + (k << 3) + (k << 8);
+ k = k ^ (k >> 14);
+ k = k + (k << 2) + (k << 4);
+ k = k ^ (k >> 28);
+ k = k + (k << 31);
+ return k;
+}
+
diff --git a/rateLimiter/hashfunctions.h b/rateLimiter/hashfunctions.h
@@ -0,0 +1,6 @@
+#pragma once
+#include "libsheepyObject.h"
+
+u32 strHashFNV1A(char *k);
+u32 u32Hash(u32 k);
+u64 u64Hash(u64 k);
diff --git a/rateLimiter/hashtable.c b/rateLimiter/hashtable.c
@@ -0,0 +1,20 @@
+
+#include "libsheepyObject.h"
+
+u32 ilog2Hashtable(u32 value);
+
+u32 ilog2Hashtable(u32 value) {
+ //u32 n = (__builtin_clz(value) ^ 31) + 1;
+ if (!value) return 4;
+ // compute log2 of value
+ u32 n;
+ asm ("bsrl %1, %0" : "=r" (n) : "r" (value));
+ n++;
+ // keep size at 16 for values under 17
+ if (n <= 4) n = 4;
+ // if value is a power of 2, keep the size down
+ else if ((value & (value-1)) == 0) n--;
+ /*else if (value == (1<<(n-1))) n--;*/
+ return n;
+}
+
diff --git a/rateLimiter/hashtable.h b/rateLimiter/hashtable.h
@@ -0,0 +1,1310 @@
+#pragma once
+
+/**
+ * \file
+ *
+ * Chained hash table
+ *
+ * NOTE: The macros in this file are for creating hash table functions wrapping the macros.
+ * I don't advise using these directly because of the risk of memory leaks and
+ * wrong computations.
+ * The leaks and wrong computations happen because the parameters to the macros
+ * are evaluated multiple times.
+ * Example:
+ * hashTbAdd(ahashtable, strdup("akey"), value) causes a leak because strdup is
+ * evaluted twice.
+ *
+ * NOTE: This package doesn't provide the hash functions, install the hashfunctions package to
+ * get some hash functions.
+ *
+ * This hash table has 2 single linked lists in each bucket,
+ * the performance is still good with a load factor of 2.
+ *
+ * The maximum number of buckets is 2^32 and and the maximum number (key, value) nodes 2^32 ( > 40 GB RAM)
+ *
+ * The size (bucket count) increases in power of 2.
+ *
+ * The status of the macros is saved (hashtableVar).res and is set to true when the operation is success and
+ * false when the operation is failure.
+ *
+ * Use hashmap when there are more than 50 elements in the dictionary
+ *
+ * Hash table memory usage (for key type char* and value type u32):
+ * Empty hashmap size: 2744 bytes
+ * Size depending on element count (with load factor 2): 184 + 42 * count
+ *
+ * It takes in average 4 times more memory than smallDict
+ * hashmap = 4 * smallDict RAM
+ *
+ * Lookup time:
+ * fnv hash get: 440ns (300 000 000 keys in hash table - kaby lake CPU)
+ *
+ * This hash table has better performance than smallDict with 50 elements
+ *
+ *
+ * The types handled by the hash table (key, value and hash types)
+ * are defined with hashTbT or hashNodeT and hashtableT.
+ *
+ * The hashTb* are short and convenient macros for the hashtable* macros.
+ * With hashTb* macros there is no need to specify the hash, cmp and free functions.
+ *
+ * Before using the hashTb* macros, define HASHFUNC CMPFUNC and FREEFUNC.
+ *
+ * *Node Macros:
+ * The *Node macros handle the nodes in hash table and save time by not running the hash function.
+ * These macros are useful when the hash function is expensive (like siphash).
+ *
+ * The hash table has to be defined with hashNodeT and hashtableT to be able to use the *Node macros.
+ * The *Node macros use the context type defined by hashNodeT, the context type is named:
+ *
+ * context_typeName
+ *
+ * The key and value in the node is accessed with:
+ * node.key
+ * node.value
+ *
+ * HASHFUNC is a function with prototype:
+ * hashType hashFunc(keyType key);
+ *
+ * CMPFUNC compares keys and is a function with prototype:
+ * int compare(keyType k1, keyType k2);
+ * Return 0 when the keys are equal, 1 otherwise
+ *
+ * FREEFUNC frees key and value is a function with prototype:
+ * void freeKV(keyType* key, valueType* value);
+ * NOTE: the free function gets a pointer to the key and value which is useful when iterating on the nodes
+ * (for example, when keyType is int, set key to -1, iterate on the aHashnode dArray and ignore the node
+ * when the key is -1)
+ *
+ * See the 'node macros' section below for details on usage scenarios of the *Node macros.
+ *
+ * Example:
+ * hashTbT(hasht, char*, u32, u32);
+ *
+ * #define HASHFUNC strHashFNV1A
+ * #define CMPFUNC strcmp
+ * #define FREEFUNC freeNode
+ *
+ * void freeNode(char **key, u32* UNUSED value) {
+ * //logI("free key %x\n", key);
+ * free(key);
+ * }
+ *
+ * hasht h;
+ * hashtableInit(h, 128, 2, 1);
+ *
+ * hashTbAdd(h, "a key", 12);
+ *
+ * u32 result = 0;
+ * hashTbGet(h, "a key", result);
+ *
+ * hashTbDel(h, "a key");
+ *
+ * hashTbFree(h);
+ */
+
+
+#include "libsheepyObject.h"
+
+/**
+ * function declarations for tailored hash table
+ *
+ * - define hash table types
+ * - declare prototypes
+ *
+ * this macro is placed most of the time in a header file
+ *
+ * the Hash table type is defined as:
+ * 'typeName't
+ *
+ * the node in the hash table is defined as:
+ * 'typeName'Nodet
+ *
+ * the node context is defined as:
+ * context_'typeName'Nodet
+ *
+ * the function names are:
+ * function'suffix'
+ *
+ * the scope parameter is the function scope and can be 'empty' for global functions, 'static' for local functions, ...
+ *
+ * the declared functions are:
+ * init, empty, free, add, addOrFind, find, get, getKey, del, seed, addOrFindNode
+ * setKeyNode, getNode, updateNodeContext, unlink, freeUnlinked, delNode
+ *
+ *
+ * RETURN VALUES:
+ * add, setKeyNode, updateNodeContext: true success, false failure
+ * addOrFind, addOrFindNode: non NULL success, NULL failure.
+ * *isnew is set to true when the returned value pointer is in a new node.
+ * find, getNode, unlink: non NULL success, NULL failure
+ *
+ * the ctx pointer parameters must be allocated before the function calls
+ * the isnew pointer must point to an existing bool variable
+ *
+ *
+ * Example:
+ * hashTbDef(, m3232, M32, u32, u32, u32); // declare hash table type m3232t with u32 keys, u32 values and u32 hash
+ *
+ * m3232Nodet *node;
+ * context_m3232Nodet ctx;
+ * bool isnew;
+ *
+ * m3232t h; // declares a hash table
+ *
+ */
+#define hashTbDef(scope, typeName, suffix, keyType, valueType, hashType) \
+ hashNodeT(typeName##Nodet, keyType, valueType, hashType);\
+ hashtableT(typeName##t, typeName##Nodet);\
+ scope void init##suffix(typeName##t *map);\
+ scope void empty##suffix(typeName##t *map);\
+ scope void free##suffix(typeName##t *map);\
+ scope bool add##suffix(typeName##t *map, keyType key, valueType value);\
+ scope valueType* addOrFind##suffix(typeName##t *map, keyType key, bool *isnew);\
+ scope valueType* find##suffix(typeName##t *map, keyType key);\
+ scope valueType get##suffix(typeName##t *map, keyType key);\
+ scope keyType getKey##suffix(typeName##t *map, keyType key);\
+ scope void del##suffix(typeName##t *map, keyType key);\
+ scope u8* seed##suffix(typeName##t *map);\
+ scope typeName##Nodet* addOrFindNode##suffix(typeName##t *map, keyType key, bool *isnew, context_##typeName##Nodet *ctx);\
+ scope bool setKeyNode##suffix(typeName##t *map, context_##typeName##Nodet *ctx);\
+ scope typeName##Nodet *getNode##suffix(typeName##t *map, keyType key, context_##typeName##Nodet *ctx);\
+ scope bool updateNodeContext##suffix(typeName##t *map, context_##typeName##Nodet *ctx);\
+ scope typeName##Nodet* unlink##suffix(typeName##t *map, keyType key);\
+ scope void freeUnlinked##suffix(typeName##t *map, typeName##Nodet *node);\
+ scope void delNode##suffix(typeName##t *map, context_##typeName##Nodet *ctx)
+
+/**
+ * function implementations
+ *
+ * this macros implements the hash table functions:
+ * init, empty, free, add, addOrFind, find, get, getKey, del, seed, addOrFindNode
+ * setKeyNode, getNode, updateNodeContext, unlink, freeUnlinked, delNode
+ *
+ * this macro is placed most of the time in a source file
+ *
+ * the hash function, compare function and free function must be implemented before this macro
+ * HASHFUNC, CMPFUNC and FREEFUNC must be defined before this macro
+ *
+ * Example:
+ * hashTbDef(, m3232, M32, u32, u32, u32); // declare hash table type m3232t with u32 keys, u32 values and u32 hash
+ *
+ * int cmp(u32 k1, u32 k2) {
+ * return k1 == k2 ? 0 : 1;
+ * }
+ *
+ * void freeM(u32* k, u32* v) {
+ * }
+ *
+ * #define HASHFUNC u32Hash // hash function from the hashfunctions spm package
+ * #define CMPFUNC cmp
+ * #define FREEFUNC freeM
+ *
+ * hashTbFunctions(, m3232, M32, u32, u32); // implements global scope m3232t functions: *M32()
+ *
+ * #undef HASHFUNC
+ * #undef CMPFUNC
+ * #undef FREEFUNC
+ *
+ * m3232t h; // declares a hash table
+ *
+ * initM32(&h);
+ * addM32(&h, 1, 1);
+ *
+ */
+#define hashTbFunctions(scope, typeName, suffix, keyType, valueType)\
+ scope void init##suffix(typeName##t *map) {\
+ hashTbInit(*map, 64, 2, 1);\
+ }\
+ scope void empty##suffix(typeName##t *map) {\
+ hashTbEmpty(*map);\
+ }\
+ scope void free##suffix(typeName##t *map) {\
+ hashTbFree(*map);\
+ }\
+ scope bool add##suffix(typeName##t *map, keyType key, valueType value) {\
+ hashTbAdd(*map, key, value);\
+ return map->res;\
+ }\
+ scope valueType* addOrFind##suffix(typeName##t *map, keyType key, bool *isnew) {\
+ valueType* r = NULL;\
+ hashTbAddOrFind(*map, key, r, *isnew);\
+ return r;\
+ }\
+ scope valueType* find##suffix(typeName##t *map, keyType key) {\
+ valueType *r = NULL;\
+ hashTbFind(*map, key, r);\
+ return r;\
+ }\
+ scope valueType get##suffix(typeName##t *map, keyType key) {\
+ valueType r;\
+ hashTbGet(*map, key, r);\
+ return r;\
+ }\
+ scope keyType getKey##suffix(typeName##t *map, keyType key) {\
+ keyType r;\
+ hashTbGetKey(*map, key, r);\
+ return r;\
+ }\
+ scope void del##suffix(typeName##t *map, keyType key) {\
+ hashTbDel(*map, key);\
+ }\
+ scope u8* seed##suffix(typeName##t *map) {\
+ u8 *r = hashTbSeed(*map);\
+ return r;\
+ }\
+ scope typeName##Nodet* addOrFindNode##suffix(typeName##t *map, keyType key, bool *isnew, context_##typeName##Nodet *ctx) {\
+ typeName##Nodet* r;\
+ hashTbAddOrFindNode(*map, key, r, *ctx, *isnew);\
+ return r;\
+ }\
+ scope bool setKeyNode##suffix(typeName##t *map, context_##typeName##Nodet *ctx) {\
+ hashTbSetKeyNode(*map, *ctx);\
+ return map->res;\
+ }\
+ scope typeName##Nodet *getNode##suffix(typeName##t *map, keyType key, context_##typeName##Nodet *ctx) {\
+ typeName##Nodet *r = NULL;\
+ hashTbGetNode(*map , key, r, *ctx);\
+ return r;\
+ }\
+ scope bool updateNodeContext##suffix(typeName##t *map, context_##typeName##Nodet *ctx) {\
+ hashTbUpdateNodeContext(*map, *ctx);\
+ return map->res;\
+ }\
+ scope typeName##Nodet* unlink##suffix(typeName##t *map, keyType key) {\
+ typeName##Nodet *r = NULL;\
+ hashTbUnlinkNode(*map, key, r);\
+ return r;\
+ }\
+ scope void freeUnlinked##suffix(typeName##t *map, typeName##Nodet *node) {\
+ hashTbFreeUnlinkedNode(*map, node);\
+ }\
+ scope void delNode##suffix(typeName##t *map, context_##typeName##Nodet *ctx) {\
+ hashTbDelNode(*map, *ctx);\
+ }
+
+
+/** initialize hash table */
+#define hashTbInit(HT, SIZE, NUMERATOR, DENOMINATOR) hashtableInit(HT, SIZE, NUMERATOR, DENOMINATOR)
+
+/** remove all key,value pairs in hash table */
+#define hashTbEmpty(HT) hashtableEmpty(HT, FREEFUNC)
+
+/** free hash table */
+#define hashTbFree(HT) hashtableFree(HT, FREEFUNC)
+
+/** insert new (key,value), fail when the key already exists */
+#define hashTbAdd(HT, K, V) hashtableAdd(HT, K, V, HASHFUNC, CMPFUNC)
+
+/** insert/find key, return value address in VPOINTER and ISNEW */
+#define hashTbAddOrFind(HT, K, VPOINTER, ISNEW) hashtableAddOrFind(HT, K, VPOINTER, ISNEW, HASHFUNC, CMPFUNC)
+
+/** find key, return value address in VPOINTER */
+#define hashTbFind(HT, K, VPOINTER) hashtableFind(HT, K, VPOINTER, HASHFUNC, CMPFUNC)
+
+/** get value */
+#define hashTbGet(HT, K, R) hashtableGet(HT, K, R, HASHFUNC, CMPFUNC)
+
+/** get key */
+#define hashTbGetKey(HT, K, R) hashtableGetKey(HT, K, R, HASHFUNC, CMPFUNC)
+
+/** remove key, value */
+#define hashTbDel(HT, K) hashtableDel(HT, K, HASHFUNC, CMPFUNC, FREEFUNC)
+
+/** get random seed address */
+#define hashTbSeed(HT) hashtableSeed(HT)
+
+/** create or reuse an exists node, return NODEPOINTER, NODECONTEXT and ISNEW */
+#define hashTbAddOrFindNode(HT, K, NODEPOINTER, NODECONTEXT, ISNEW) hashtableAddOrFindNode(HT, K, NODEPOINTER, NODECONTEXT, ISNEW, HASHFUNC, CMPFUNC)
+
+/** change the key in a node */
+#define hashTbSetKeyNode(HT, NODECONTEXT) hashtableSetKeyNode(HT, NODECONTEXT, HASHFUNC, CMPFUNC)
+
+/** get a node, return NODE and NODECONTEXT */
+#define hashTbGetNode(HT, K, NODE, NODECONTEXT) hashtableGetNode(HT, K, NODE, NODECONTEXT, HASHFUNC, CMPFUNC)
+
+/** key in node */
+#define hashTbNodeKey(NODE) (NODE).key
+
+/** value in node */
+#define hashTbNodeValue(NODE) (NODE).value
+
+/** update node context after a rehash, return NODECONTEXT */
+#define hashTbUpdateNodeContext(HT, NODECONTEXT) hashtableUpdateNodeContext(HT, NODECONTEXT, HASHFUNC, CMPFUNC)
+
+/** return a node and remove it from the hashtable, return NODE */
+#define hashTbUnlinkNode(HT, K, NODE) hashtableUnlinkNode(HT, K, NODE, HASHFUNC, CMPFUNC)
+
+/** free an unlinked node */
+#define hashTbFreeUnlinkedNode(HT, NODE) hashtableFreeUnlinkedNode(HT, NODE, FREEFUNC)
+
+/** delete a node */
+#define hashTbDelNode(HT, NODECONTEXT) hashtableDelNode(HT, NODECONTEXT, FREEFUNC)
+
+/**
+ * node definition for bucket single linked lists
+ *
+ * keyType, valueType and hashType can any valid type.
+ *
+ * context_typeName is defined and is needed for *Node macros
+ *
+ * In general, hashType is an uint between 32bits and 256bits
+ */
+#define hashNodeT(typeName, keyType, valueType, hashType)\
+ typedef struct typeName typeName;\
+ struct typeName {\
+ keyType key;\
+ typeName *next;\
+ hashType hash;\
+ u32 index;\
+ valueType value;\
+ };\
+ typedef struct {\
+ typeName *node;\
+ typeName *prev;\
+ u32 mhash;\
+ u8 moreOrLess;\
+ u32 size;\
+ } TOKENPASTE(context_, typeName) /* concatenate strings with preprocessor */
+
+/**
+ * hash table definition
+ * typeName is the type of hash table defined.
+ *
+ * hashNodeT(nodeType) has to defined before this macro.
+ *
+ * Example:
+ * hashNodeT(hashSipNodet, char*, u32, u64);
+ * hashtableT(hashsipt, hashSipNodet);
+ *
+ * context_hashSipNodet is the node context type.
+ */
+#define hashtableT(typeName, nodeType)\
+ dArrayT(UNIQVAR(aHashnodet), nodeType);\
+ dArrayT(UNIQVAR(HNFreet), u32);\
+ typedef struct {\
+ nodeType* (*list)[][2]; /* buckets, 2 single linked lists */\
+ nodeType node;\
+ size_t count; /* node count */\
+ u32 size; /* bucket count */\
+ u32 szMask; /* mask for bucket indexing */\
+ UNIQVAR(aHashnodet) aHashnode; /* node dynamic array */\
+ UNIQVAR(HNFreet) HNFree; /* list of free nodes in aHashnode */\
+ u8 hashseed[16]; /* random seed for siphash */\
+ u32 loadfactor_numerator;\
+ u32 loadfactor_denominator;\
+ bool res; /* return value for macros */\
+ bool newNodeInDArray; /* add, addOrFind and addOrFindNode set this flag: true an new node is pushed in aHashnode, false an existing array element is recycled */\
+ } typeName
+
+/**
+ * hash table and hash node definition
+ * typeName is the type of hash table defined.
+ *
+ * keyType, valueType and hashType can any valid type.
+ *
+ * In general, hashType is an uint between 32bits and 256bits
+ */
+#define hashTbT(typeName, keyType, valueType, hashType)\
+ hashNodeT(UNIQVAR(hashnodet), keyType, valueType, hashType);\
+ hashtableT(typeName, UNIQVAR(hashnodet))
+
+/**
+ * fast log2 function for computing the bucket list size and mask
+ */
+u32 ilog2Hashtable(u32 value);
+
+/**
+ * initialize the hash table 'name'
+ *
+ * sz is the initial size
+ * numerator and denominator are the load factor
+ *
+ * the random hash seed is generated
+ *
+ * this macro must be called before using the hash table
+ *
+ * \return
+ * (name).res true success, false failed
+ */
+#define hashtableInit(name, sz, numerator, denominator) do{\
+ (name).size = sz;\
+ if (sz <= 0) { (name).res = false; break;}\
+ (name).loadfactor_numerator = numerator;\
+ (name).loadfactor_denominator = denominator;\
+ dArrayInit(&(name).aHashnode);\
+ dArrayInit(&(name).HNFree);\
+ setSoftwareRandom();\
+ range(UNIQVAR(i),16) {\
+ (name).hashseed[UNIQVAR(i)] = randomChoice(256);\
+ }\
+ (name).size = (1<<ilog2Hashtable(sz));\
+ (name).szMask = (name).size - 1;\
+ (name).list = malloc((name).size * 2 * sizeof(typeof((name).node)*));\
+ if (!(name).list) /* alloc failed */ { (name).size = 0; (name).res = false; break;}\
+ memset((name).list, 0, (name).size * 2 * sizeof(typeof((name).node)*));\
+ (name).count = 0;\
+ (name).res = true;\
+ } while(0)
+
+/** Internal - for testing the hash table
+ * show the content of the buckets
+ */
+#define hashtableTest(name) do{\
+ range(UNIQVAR(i), (name).size) {\
+ /* free first linked list */\
+ typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(i)][0];\
+ while (UNIQVAR(node)) {\
+ logI("bucket %3d list 0 key %s", UNIQVAR(i), UNIQVAR(node)->key);\
+ typeof((name).node) *UNIQVAR(next) = UNIQVAR(node)->next;\
+ UNIQVAR(node) = UNIQVAR(next);\
+ }\
+ /* free second linked list */\
+ UNIQVAR(node) = (*(name).list)[UNIQVAR(i)][1];\
+ while (UNIQVAR(node)) {\
+ logI("bucket %3d list 1 key %s", UNIQVAR(i), UNIQVAR(node)->key);\
+ typeof((name).node) *UNIQVAR(next) = UNIQVAR(node)->next;\
+ UNIQVAR(node) = UNIQVAR(next);\
+ }\
+ }\
+ } while(0);
+
+/**
+ * remove all key,value pairs in hash table
+ */
+#define hashtableEmpty(name, freeNodeFunc) do{\
+ range(UNIQVAR(i), (name).size) {\
+ /* free first linked list */\
+ typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(i)][0];\
+ while (UNIQVAR(node)) {\
+ typeof((name).node) *UNIQVAR(next) = UNIQVAR(node)->next;\
+ freeNodeFunc(&UNIQVAR(node)->key, &UNIQVAR(node)->value);\
+ UNIQVAR(node) = UNIQVAR(next);\
+ }\
+ /* free second linked list */\
+ UNIQVAR(node) = (*(name).list)[UNIQVAR(i)][1];\
+ while (UNIQVAR(node)) {\
+ typeof((name).node) *UNIQVAR(next) = UNIQVAR(node)->next;\
+ freeNodeFunc(&UNIQVAR(node)->key, &UNIQVAR(node)->value);\
+ UNIQVAR(node) = UNIQVAR(next);\
+ }\
+ (*(name).list)[UNIQVAR(i)][0] = NULL;\
+ (*(name).list)[UNIQVAR(i)][1] = NULL;\
+ }\
+ (name).count = 0;\
+ } while(0);
+
+/**
+ * empty hash table and free all buffers
+ *
+ * \return
+ * (name).res true success, false failed
+ */
+#define hashtableFree(name, freeNodeFunc) do{\
+ (name).res = false;\
+ if (!(name).size) /* size=0 invalid */ break;\
+ hashtableEmpty(name, freeNodeFunc);\
+ free((name).list);\
+ dArrayFree(&(name).aHashnode);\
+ dArrayFree(&(name).HNFree);\
+ (name).list = NULL;\
+ (name).count = 0;\
+ (name).size = 0;\
+ (name).res = true;\
+ } while(0)
+
+/**
+ * resize the hash table
+ *
+ * \return
+ * (name).res true success, false failed
+ */
+#define hashtableResize(name, sz) do{\
+ u32 UNIQVAR(new_size) = (1<<ilog2Hashtable(sz));\
+ (name).szMask = (name).size - 1;\
+ if ((name).size == UNIQVAR(new_size)) goto UNIQVAR(msuccess);\
+ typeof((name).node) *(*UNIQVAR(list))[][2] = malloc(UNIQVAR(new_size) * 2 * sizeof(typeof((name).node)*));\
+ if (!UNIQVAR(list)) {(name).res = false; break;}\
+ memset(UNIQVAR(list), 0, UNIQVAR(new_size) * 2 * sizeof(typeof((name).node)*));\
+ range(UNIQVAR(i), (name).size) {\
+ range(UNIQVAR(moreLessIdx), 2) {\
+ for (typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(i)][UNIQVAR(moreLessIdx)]; UNIQVAR(node);) {\
+ typeof((name).node) *UNIQVAR(next) = UNIQVAR(node)->next;\
+ u32 UNIQVAR(mhash) = UNIQVAR(node)->hash & (name).szMask;\
+ typeof((name).node) *UNIQVAR(search) = (*UNIQVAR(list))[UNIQVAR(mhash)][0];\
+ typeof((name).node) *UNIQVAR(prev) = NULL;\
+ u8 UNIQVAR(moreOrLess) = 0;\
+ if (UNIQVAR(search)) {\
+ if (UNIQVAR(node)->hash >= UNIQVAR(search)->hash) {\
+ UNIQVAR(moreOrLess) = 0;\
+ while (UNIQVAR(search) && UNIQVAR(node)->hash >= UNIQVAR(search)->hash) {\
+ UNIQVAR(prev) = UNIQVAR(search);\
+ UNIQVAR(search) = UNIQVAR(search)->next;\
+ }\
+ }\
+ else {\
+ UNIQVAR(moreOrLess) = 1;\
+ UNIQVAR(search) = (*UNIQVAR(list))[UNIQVAR(mhash)][1];\
+ while (UNIQVAR(search) && UNIQVAR(node)->hash <= UNIQVAR(search)->hash) {\
+ UNIQVAR(prev) = UNIQVAR(search);\
+ UNIQVAR(search) = UNIQVAR(search)->next;\
+ }\
+ }\
+ }\
+ UNIQVAR(node)->next = UNIQVAR(search);\
+ if (UNIQVAR(prev)) {\
+ UNIQVAR(prev)->next = UNIQVAR(node);\
+ }\
+ else {\
+ (*UNIQVAR(list))[UNIQVAR(mhash)][UNIQVAR(moreOrLess)] = UNIQVAR(node);\
+ }\
+ UNIQVAR(node) = UNIQVAR(next);\
+ }\
+ }\
+ }\
+ free((name).list);\
+ (name).list = UNIQVAR(list);\
+ (name).size = UNIQVAR(new_size);\
+ UNIQVAR(msuccess):\
+ (name).res = true;\
+ } while(0)
+
+/**
+ * insert key, value
+ *
+ * fails when the key already exists
+ *
+ * \return
+ * (name).res true success, false failed
+ */
+#define hashtableAdd(name, k, v, hashFunc, cmpFunc) do{\
+ if ((name).loadfactor_denominator * (name).count >= (name).loadfactor_numerator * (name).size) {\
+ /* load factor too high */\
+ hashtableResize(name, (name).count*2);\
+ /*if (!(name).res) break; else (name).res = false;*/\
+ }\
+ const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
+ const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
+ typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][0];\
+ typeof((name).node) *UNIQVAR(prev) = NULL;\
+ typeof((name).node) *UNIQVAR(add);\
+ u8 UNIQVAR(moreOrLess) = 0;\
+ if (UNIQVAR(node)) {\
+ if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ UNIQVAR(moreOrLess) = 0;\
+ while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ (name).newNodeInDArray = false;\
+ (name).res = false; goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ else {\
+ UNIQVAR(moreOrLess) = 1;\
+ UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
+ while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ (name).newNodeInDArray = false;\
+ (name).res = false; goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ }\
+ if (dArrayIsEmpty(&(name).HNFree)) {\
+ dArrayPush(&(name).aHashnode);\
+ UNIQVAR(add) = dArrayLastPtr(&(name).aHashnode);\
+ UNIQVAR(add)->index = dArrayLastIndex(&(name).aHashnode);\
+ (name).newNodeInDArray = true;\
+ }\
+ else {\
+ u32 UNIQVAR(idx) = dArrayLast(&(name).HNFree);\
+ dArrayDelLast(&(name).HNFree);\
+ UNIQVAR(add) = dArrayPtr(&(name).aHashnode, UNIQVAR(idx));\
+ (name).newNodeInDArray = false;\
+ }\
+ UNIQVAR(add)->key = k;\
+ UNIQVAR(add)->value = v;\
+ UNIQVAR(add)->hash = UNIQVAR(hash);\
+ if (UNIQVAR(prev)) UNIQVAR(prev)->next = UNIQVAR(add);\
+ else (*(name).list)[UNIQVAR(mhash)][UNIQVAR(moreOrLess)] = UNIQVAR(add);\
+ UNIQVAR(add)->next = UNIQVAR(node);\
+ (name).count++;\
+ (name).res = true;\
+ UNIQVAR(mreturn):;\
+ } while(0)
+
+/**
+ * add or find key, get value pointer
+ *
+ * vPointer must be of type:
+ * valueType *
+ *
+ * isNew must be of type:
+ * bool
+ *
+ * \return
+ * vPointer address to value associated the key k
+ * isNew true when the node is new, false when the node already existed
+ * (name).res true success, false failed
+ */
+#define hashtableAddOrFind(name, k, vPointer, isNew, hashFunc, cmpFunc) do{\
+ if ((name).loadfactor_denominator * (name).count >= (name).loadfactor_numerator * (name).size) {\
+ /* load factor too high */\
+ hashtableResize(name, (name).count*2);\
+ /*if (!(name).res) break; else (name).res = false;*/\
+ }\
+ const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
+ const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
+ typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][0];\
+ typeof((name).node) *UNIQVAR(prev) = NULL;\
+ typeof((name).node) *UNIQVAR(add);\
+ u8 UNIQVAR(moreOrLess) = 0;\
+ if (UNIQVAR(node)) {\
+ if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ UNIQVAR(moreOrLess) = 0;\
+ while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ vPointer = &(UNIQVAR(node)->value);\
+ isNew = false;\
+ (name).newNodeInDArray = false;\
+ (name).res = true; goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ else {\
+ UNIQVAR(moreOrLess) = 1;\
+ UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
+ while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ vPointer = &(UNIQVAR(node)->value);\
+ isNew = false;\
+ (name).newNodeInDArray = false;\
+ (name).res = true; goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ }\
+ isNew = true;\
+ if (dArrayIsEmpty(&(name).HNFree)) {\
+ dArrayPush(&(name).aHashnode);\
+ UNIQVAR(add) = dArrayLastPtr(&(name).aHashnode);\
+ UNIQVAR(add)->index = dArrayLastIndex(&(name).aHashnode);\
+ (name).newNodeInDArray = true;\
+ }\
+ else {\
+ u32 UNIQVAR(idx) = dArrayLast(&(name).HNFree);\
+ dArrayDelLast(&(name).HNFree);\
+ UNIQVAR(add) = dArrayPtr(&(name).aHashnode, UNIQVAR(idx));\
+ (name).newNodeInDArray = false;\
+ }\
+ UNIQVAR(add)->key = k;\
+ vPointer = &(UNIQVAR(add)->value);\
+ UNIQVAR(add)->hash = UNIQVAR(hash);\
+ if (UNIQVAR(prev)) UNIQVAR(prev)->next = UNIQVAR(add);\
+ else (*(name).list)[UNIQVAR(mhash)][UNIQVAR(moreOrLess)] = UNIQVAR(add);\
+ UNIQVAR(add)->next = UNIQVAR(node);\
+ (name).count++;\
+ (name).res = true;\
+ UNIQVAR(mreturn):;\
+ } while(0)
+
+/**
+ * find key, get value pointer
+ *
+ * vPointer must be of type:
+ * valueType *
+ *
+ * \return
+ * vPointer address to value associated the key k
+ * (name).res true success, false failed
+ */
+#define hashtableFind(name, k, vPointer, hashFunc, cmpFunc) do{\
+ const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
+ const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
+ typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(hash) & (name).szMask][0];\
+ if (UNIQVAR(node)) {\
+ if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ vPointer = &UNIQVAR(node)->value;\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ else {\
+ UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
+ while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ vPointer = &UNIQVAR(node)->value;\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ }\
+ (name).res = false;\
+ UNIQVAR(mreturn):;\
+ } while(0)
+
+/**
+ * get value
+ *
+ * \return
+ * (name).res true success, false failed
+ */
+#define hashtableGet(name, k, result, hashFunc, cmpFunc) do{\
+ const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
+ const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
+ typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(hash) & (name).szMask][0];\
+ if (UNIQVAR(node)) {\
+ if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ result = UNIQVAR(node)->value;\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ else {\
+ UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
+ while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ result = UNIQVAR(node)->value;\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ }\
+ (name).res = false;\
+ UNIQVAR(mreturn):;\
+ } while(0)
+
+/**
+ * get key
+ *
+ * \return
+ * (name).res true success, false failed
+ */
+#define hashtableGetKey(name, k, result, hashFunc, cmpFunc) do{\
+ const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
+ const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
+ typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(hash) & (name).szMask][0];\
+ if (UNIQVAR(node)) {\
+ if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ result = UNIQVAR(node)->key;\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ else {\
+ UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
+ while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ result = UNIQVAR(node)->key;\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ }\
+ (name).res = false;\
+ UNIQVAR(mreturn):;\
+ } while(0)
+
+/**
+ * remove key, value
+ *
+ * \return
+ * (name).res true success, false failed
+ */
+#define hashtableDel(name, k, hashFunc, cmpFunc, freeNodeFunc) do{\
+ const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
+ u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
+ typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][0];\
+ typeof((name).node) *UNIQVAR(prev) = NULL;\
+ if (UNIQVAR(node)) {\
+ if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ freeNodeFunc(&UNIQVAR(node)->key, &UNIQVAR(node)->value);\
+ hashtableInternalDelNode(name, UNIQVAR(node), UNIQVAR(mhash), UNIQVAR(prev), 0);\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ else {\
+ UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
+ while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ freeNodeFunc(&UNIQVAR(node)->key, &UNIQVAR(node)->value);\
+ hashtableInternalDelNode(name, UNIQVAR(node), UNIQVAR(mhash), UNIQVAR(prev), 1);\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ }\
+ (name).res = false;\
+ UNIQVAR(mreturn):;\
+ } while(0)
+
+// Internal macro
+#define hashtableInternalDelNode(name, node, mhash, prev, moreOrLess) do{\
+ hashtableInternalUnlink(name, node, mhash, prev, moreOrLess);\
+ dArrayAppend(&(name).HNFree, node->index);\
+ (name).count--;\
+ } while(0)
+
+/**
+ * get hash seed address for siphash
+ */
+#define hashtableSeed(name) ((name).hashseed)
+
+
+
+/***************************************
+ * node macros
+ *
+ * Usage scenarios:
+ *
+ * The getNode allow processing node data before reinsert or delete and running the hash function
+ * only once.
+ *
+ * Example:
+ * getNode
+ * use node data, change key
+ * setKeyNode
+ *
+ * same as
+ * get
+ * use node data, change key
+ * del original key
+ * add new key, value
+ *
+ * The unlink macro allow using data in a node before deleting it.
+ * The same operation can be done with Get and Del, using unlink runs the hash function only once.
+ *
+ * Example:
+ * unlinkNode
+ * use node data
+ * freeUnlinkedNode
+ *
+ * same as
+ * get
+ * use value
+ * del
+ *
+ ***************************************/
+
+/**
+ * add or find node
+ *
+ * nodePointer must be a pointer to hash node type
+ * hashNode *result;
+ *
+ * nodeContext must be a struct of type
+ * context_hashNode ctx;
+ *
+ * \return
+ * (name).res true success, false failed
+ */
+#define hashtableAddOrFindNode(name, k, nodePointer, nodeContext, isNew, hashFunc, cmpFunc) do{\
+ if ((name).loadfactor_denominator * (name).count >= (name).loadfactor_numerator * (name).size) {\
+ /* load factor too high */\
+ hashtableResize(name, (name).count*2);\
+ /*if (!(name).res) break; else (name).res = false;*/\
+ }\
+ const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
+ const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
+ (nodeContext).node->hash = UNIQVAR(hash);\
+ typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][0];\
+ typeof((name).node) *UNIQVAR(prev) = NULL;\
+ u8 UNIQVAR(moreOrLess) = 0;\
+ if (UNIQVAR(node)) {\
+ if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ UNIQVAR(moreOrLess) = 0;\
+ while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ nodePointer = UNIQVAR(node);\
+ (nodeContext).node = nodePointer;\
+ (nodeContext).prev = UNIQVAR(prev);\
+ (nodeContext).mhash = UNIQVAR(mhash);\
+ (nodeContext).moreOrLess = UNIQVAR(moreOrLess);\
+ (nodeContext).size = (name).size;\
+ isNew = false;\
+ (name).newNodeInDArray = false;\
+ (name).res = true; goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ else {\
+ UNIQVAR(moreOrLess) = 1;\
+ UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
+ while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ nodePointer = UNIQVAR(node);\
+ (nodeContext).node = nodePointer;\
+ (nodeContext).prev = UNIQVAR(prev);\
+ (nodeContext).mhash = UNIQVAR(mhash);\
+ (nodeContext).moreOrLess = UNIQVAR(moreOrLess);\
+ (nodeContext).size = (name).size;\
+ isNew = false;\
+ (name).newNodeInDArray = false;\
+ (name).res = true; goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ }\
+ isNew = true;\
+ if (dArrayIsEmpty(&(name).HNFree)) {\
+ dArrayPush(&(name).aHashnode);\
+ nodePointer = dArrayLastPtr(&(name).aHashnode);\
+ nodePointer->index = dArrayLastIndex(&(name).aHashnode);\
+ (name).newNodeInDArray = true;\
+ }\
+ else {\
+ u32 UNIQVAR(idx) = dArrayLast(&(name).HNFree);\
+ dArrayDelLast(&(name).HNFree);\
+ nodePointer = dArrayPtr(&(name).aHashnode, UNIQVAR(idx));\
+ (name).newNodeInDArray = false;\
+ }\
+ nodePointer->key = k;\
+ if (UNIQVAR(prev)) UNIQVAR(prev)->next = nodePointer;\
+ else (*(name).list)[UNIQVAR(mhash)][UNIQVAR(moreOrLess)] = nodePointer;\
+ nodePointer->next = UNIQVAR(node);\
+ (name).count++;\
+ /* set context */\
+ (nodeContext).node = nodePointer;\
+ (nodeContext).prev = UNIQVAR(prev);\
+ (nodeContext).mhash = UNIQVAR(mhash);\
+ (nodeContext).moreOrLess = UNIQVAR(moreOrLess);\
+ (nodeContext).size = (name).size;\
+ (name).res = true;\
+ UNIQVAR(mreturn):;\
+ } while(0)
+
+/**
+ * set node to be used when the key is updated
+ * unlink the node then
+ * insert it in another bucket
+ *
+ * nodeContext must be a struct of type
+ * context_hashNode ctx;
+ *
+ * The node context is updated and remains valid after this macro (no need to run updateNodeContext)
+ *
+ * When key,value pairs are added after getNode and the table is rehashed (the size changed), the node context should be updated with getNode before calling this macro
+ *
+ * The node is unlinked, so in case of failure, the node should be added with AddOrFindNode or the node should be freed with freeUnlinkedNode
+ *
+ * \return
+ * (name).res true success, false failed
+ */
+#define hashtableSetKeyNode(name, nodeContext, hashFunc, cmpFunc) do{\
+ /* no need to resize because the node is unlinked and the key is rehashed */\
+ const typeof((name).node.hash) UNIQVAR(hash) = hashFunc((nodeContext).node->key);\
+ if (UNIQVAR(hash) == (nodeContext).node->hash) /* the hash is identical to the previous one, we are done */{\
+ (name).res = true; goto UNIQVAR(mreturn);\
+ }\
+ hashtableInternalUnlinkNode(name, nodeContext);\
+ if (!(name).res) /* the table has been rehashed, the context is invalid */ goto UNIQVAR(mreturn);\
+ const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
+ (nodeContext).node->hash = UNIQVAR(hash);\
+ typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][0];\
+ typeof((name).node) *UNIQVAR(prev) = NULL;\
+ u8 UNIQVAR(moreOrLess) = 0;\
+ if (UNIQVAR(node)) {\
+ if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ UNIQVAR(moreOrLess) = 0;\
+ while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && (((nodeContext).node->key == UNIQVAR(node)->key) || (cmpFunc((nodeContext).node->key, UNIQVAR(node)->key) == 0))) {\
+ (name).res = false; goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ else {\
+ UNIQVAR(moreOrLess) = 1;\
+ UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
+ while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && (((nodeContext).node->key == UNIQVAR(node)->key) || (cmpFunc((nodeContext).node->key, UNIQVAR(node)->key) == 0))) {\
+ (name).res = false; goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ }\
+ if (UNIQVAR(prev)) UNIQVAR(prev)->next = (nodeContext).node;\
+ else (*(name).list)[UNIQVAR(mhash)][UNIQVAR(moreOrLess)] = (nodeContext).node;\
+ (nodeContext).node->next = UNIQVAR(node);\
+ /* update context */\
+ (nodeContext).prev = UNIQVAR(prev);\
+ (nodeContext).mhash = UNIQVAR(mhash);\
+ (nodeContext).moreOrLess = UNIQVAR(moreOrLess);\
+ (nodeContext).size = (name).size;\
+ (name).res = true;\
+ UNIQVAR(mreturn):;\
+ } while(0)
+
+// Internal macro, like Internal DelNode without free the node
+// the node is removed from the bucket
+#define hashtableInternalUnlinkNode(name, nodeContext) do{\
+ if ((nodeContext).size != (name).size) {\
+ /* the table has been rehashed since the nodeContext was filled in */\
+ /* update the context, run updateNodeContext with the original key */\
+ /* the original is not available in the context, since the key is probably updated */\
+ (name).res = false;\
+ break;\
+ }\
+ if ((nodeContext).prev) (nodeContext).prev->next = (nodeContext).node->next;\
+ else (*(name).list)[(nodeContext).mhash][(nodeContext).moreOrLess] = (nodeContext).node->next;\
+ if (((nodeContext).moreOrLess == 0) && !(*(name).list)[(nodeContext).mhash][0] && (*(name).list)[(nodeContext).mhash][1]) {\
+ /* the first linked list is empty, take the first element from the second linked list */\
+ (*(name).list)[(nodeContext).mhash][0] = (*(name).list)[(nodeContext).mhash][1];\
+ (*(name).list)[(nodeContext).mhash][1] = (*(name).list)[(nodeContext).mhash][1]->next;\
+ (*(name).list)[(nodeContext).mhash][0]->next = NULL;\
+ }\
+ (name).res = true;\
+ } while(0)
+
+
+/**
+ * get node
+ *
+ * result must be a pointer to hash node type
+ * hashNode *result;
+ *
+ * nodeContext must be a struct of type
+ * context_hashNode ctx;
+ *
+ * \return
+ * (name).res true success, false failed
+ */
+#define hashtableGetNode(name, k, result, nodeContext, hashFunc, cmpFunc) do{\
+ const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
+ const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
+ typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(hash) & (name).szMask][0];\
+ typeof((name).node) *UNIQVAR(prev) = NULL;\
+ if (UNIQVAR(node)) {\
+ if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ result = UNIQVAR(node);\
+ (nodeContext).node = UNIQVAR(node);\
+ (nodeContext).prev = UNIQVAR(prev);\
+ (nodeContext).mhash = UNIQVAR(mhash);\
+ (nodeContext).moreOrLess = 0;\
+ (nodeContext).size = (name).size;\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ else {\
+ UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
+ while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ result = UNIQVAR(node);\
+ (nodeContext).node = UNIQVAR(node);\
+ (nodeContext).prev = UNIQVAR(prev);\
+ (nodeContext).mhash = UNIQVAR(mhash);\
+ (nodeContext).moreOrLess = 1;\
+ (nodeContext).size = (name).size;\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ }\
+ (name).res = false;\
+ UNIQVAR(mreturn):;\
+ } while(0)
+
+/**
+ * update node context
+ *
+ * the node context must have been initialized with getNode or setKeyNode
+ *
+ * call this macro when the table has been rehashed after getNode or setKeyNode
+ *
+ * nodeContext must be a struct of type
+ * context_hashNode ctx;
+ *
+ * \return
+ * (name).res true success, false failed
+ */
+#define hashtableUpdateNodeContext(name, nodeContext, hashFunc, cmpFunc) do{\
+ const typeof((name).node.hash) UNIQVAR(hash) = (nodeContext).node->hash;\
+ const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
+ typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(hash) & (name).szMask][0];\
+ typeof((name).node) *UNIQVAR(prev) = NULL;\
+ if (UNIQVAR(node)) {\
+ if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && (((nodeContext).node->key == UNIQVAR(node)->key) || (cmpFunc((nodeContext).node->key, UNIQVAR(node)->key) == 0))) {\
+ (nodeContext).prev = UNIQVAR(prev);\
+ (nodeContext).mhash = UNIQVAR(mhash);\
+ (nodeContext).moreOrLess = 0;\
+ (nodeContext).size = (name).size;\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ else {\
+ UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
+ while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && (((nodeContext).node->key == UNIQVAR(node)->key) || (cmpFunc((nodeContext).node->key, UNIQVAR(node)->key) == 0))) {\
+ (nodeContext).prev = UNIQVAR(prev);\
+ (nodeContext).mhash = UNIQVAR(mhash);\
+ (nodeContext).moreOrLess = 1;\
+ (nodeContext).size = (name).size;\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ }\
+ (name).res = false;\
+ UNIQVAR(mreturn):;\
+ } while(0)
+
+/**
+ * unlink node
+ *
+ * result must be a pointer to hash node type
+ * hashNode *result;
+ *
+ * result must be freed with freeUnlinkNode
+ *
+ * This macro allow using data in a node before deleting it.
+ * The same operation can be done with Get and Del, using unlink runs the hash function only once.
+ *
+ * Example:
+ * unlinkNode
+ * use node data
+ * freeUnlinkedNode
+ *
+ * same as
+ * get
+ * use value
+ * del
+ *
+ * \return
+ * result unlinked node
+ * (name).res true success, false failed
+ */
+#define hashtableUnlinkNode(name, k, result, hashFunc, cmpFunc) do{\
+ const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
+ const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
+ typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(hash) & (name).szMask][0];\
+ typeof((name).node) *UNIQVAR(prev) = NULL;\
+ if (UNIQVAR(node)) {\
+ if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ hashtableInternalUnlink(name, UNIQVAR(node), UNIQVAR(mhash), UNIQVAR(prev), 0);\
+ result = UNIQVAR(node);\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ else {\
+ UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
+ while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
+ if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
+ hashtableInternalUnlink(name, UNIQVAR(node), UNIQVAR(mhash), UNIQVAR(prev), 1);\
+ result = UNIQVAR(node);\
+ (name).res = true;\
+ goto UNIQVAR(mreturn);\
+ }\
+ UNIQVAR(prev) = UNIQVAR(node);\
+ UNIQVAR(node) = UNIQVAR(node)->next;\
+ }\
+ }\
+ }\
+ (name).res = false;\
+ UNIQVAR(mreturn):;\
+ } while(0)
+
+// Internal macro
+#define hashtableInternalUnlink(name, node, mhash, prev, moreOrLess) do{\
+ if (prev) prev->next = node->next;\
+ else (*(name).list)[mhash][moreOrLess] = node->next;\
+ if ((moreOrLess == 0) && !(*(name).list)[mhash][0] && (*(name).list)[mhash][1]) {\
+ /* the first linked list is empty, take the first element from the second linked list */\
+ (*(name).list)[mhash][0] = (*(name).list)[mhash][1];\
+ (*(name).list)[mhash][1] = (*(name).list)[mhash][1]->next;\
+ (*(name).list)[mhash][0]->next = NULL;\
+ }\
+ } while(0)
+
+/**
+ * free an unlinked node
+ *
+ * node must be a pointer to hash node type
+ * hashNode *node;
+ *
+ * the node has to be first unlinked with the unlinkNode macro
+ */
+#define hashtableFreeUnlinkedNode(name, node, freeNodeFunc) do{\
+ freeNodeFunc(&(node)->key, &(node)->value);\
+ dArrayAppend(&(name).HNFree, (node)->index);\
+ (name).count--;\
+ } while(0)
+
+/**
+ * delete/remove node
+ *
+ * the node context must be already initialized with the other *Node macros
+ *
+ * if the node context is changed due to rehash, updateNodeContext has to be called before this macro
+ */
+// no status
+#define hashtableDelNode(name, nodeContext, freeNodeFunc) do{\
+ freeNodeFunc(&(nodeContext).node->key, &(nodeContext).node->value);\
+ hashtableInternalDelNode(name, (nodeContext).node, (nodeContext).mhash, (nodeContext).prev, (nodeContext).moreOrLess);\
+ } while(0)
+
diff --git a/rateLimiter/main.c b/rateLimiter/main.c
@@ -0,0 +1,30 @@
+#! /usr/bin/env sheepy
+/* or direct path to sheepy: #! /usr/local/bin/sheepy */
+
+#include "libsheepyObject.h"
+#include "rateLimiter.h"
+
+int main(int ARGC, char** ARGV) {
+
+ initLibsheepy(ARGV[0]);
+
+ createRateLimiter(rateLim);
+
+ setupG(&rateLim, 1 /* max clients */, 1000 /* window */, 1 /* max access count */);
+
+ logVarG(incomingG(&rateLim, 1));
+ logVarG(incomingG(&rateLim, 1));
+ logVarG(incomingG(&rateLim, 1));
+ logVarG(incomingG(&rateLim, 1));
+ logVarG(incomingG(&rateLim, 1));
+ logVarG(incomingG(&rateLim, 1));
+ /* incomingG(&rateLim, 2); */
+ /* incomingG(&rateLim, 1); */
+ /* incomingG(&rateLim, 2); */
+ /* incomingG(&rateLim, 1); */
+ /* incomingG(&rateLim, 2); */
+ /* logVarG(clientCountG(&rateLim)); */
+ /* logVarG(clientCountG(&rateLim)); */
+
+ freeO(&rateLim);
+}
diff --git a/rateLimiter/rateLimiter.c b/rateLimiter/rateLimiter.c
@@ -0,0 +1,257 @@
+
+
+/* Add class methods and modify the base functions (free, duplicate, ...) where there are the TODOs (TODO)*/
+
+#include "libsheepyObject.h"
+#include "rateLimiter.h"
+#include "rateLimiterInternal.h"
+
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+void initiateRateLimiter(rateLimitert *self);
+void registerMethodsRateLimiter(rateLimiterFunctionst *f);
+void initiateAllocateRateLimiter(rateLimitert **self);
+void finalizeRateLimiter(void);
+rateLimitert* allocRateLimiter(void);
+internal void freeRateLimiter(rateLimitert *self);
+internal void terminateRateLimiter(rateLimitert **self);
+internal char* toStringRateLimiter(rateLimitert *self);
+internal rateLimitert* duplicateRateLimiter(rateLimitert *self);
+internal void smashRateLimiter(rateLimitert **self);
+internal void finishRateLimiter(rateLimitert **self);
+internal bool setupRateLimiter(rateLimitert *self, u32 maxClients, u64 window, u32 maxAccessCount);
+internal size_t countRateLimiter(rateLimitert *self);
+internal bool incomingRateLimiter(rateLimitert *self, u32 ip);
+internal bool hasRateLimiter(rateLimitert *self, u32 ip);
+internal time_t getTime(void);
+internal void prune(rateLimitert *self);
+internal int cmprateL(u32 k1, u32 k2);
+internal void freerateLKV(u32* k, u32* v);
+/* TODO add prototypes */
+
+/* enable/disable logging */
+#undef pLog
+#define pLog(...)
+
+#define RATELIMA self->rateLimiterA
+#define RATELIMIX self->rateLimiterIx
+#define RATELIMH self->rateLimiterH
+
+#define RATELIM(index) RATELIMA[indexerRef(RATELIMIX, index)]
+#define RATELIMFirst RATELIMA[indexerFirst(RATELIMIX)]
+#define RATELIMLast RATELIMA[indexerLast(RATELIMIX)]
+
+internal int cmprateL(u32 k1, u32 k2) {
+ return k1 == k2 ? 0 : 1;
+}
+
+internal void freerateLKV(u32* k, u32* v) {
+ // nothing to free, the data is stored in rateLimiterA
+}
+
+#define HASHFUNC u32Hash // hash function from the hashfunctions spm package
+#define CMPFUNC cmprateL
+#define FREEFUNC freerateLKV
+
+hashTbFunctions(, rateL, rateL, u32, u32);
+
+#undef HASHFUNC
+#undef CMPFUNC
+#undef FREEFUNC
+
+void initiateRateLimiter(rateLimitert *self) {
+
+ self->type = "rateLimiter";
+ if (!rateLimiterF) {
+ rateLimiterF = malloc(sizeof(rateLimiterFunctionst));
+ registerMethodsRateLimiter(rateLimiterF);
+ pErrorNot0(atexit(finalizeRateLimiter));
+ }
+ self->f = rateLimiterF;
+
+ RATELIMA = NULL;
+ initrateL(&RATELIMH);
+ /* TODO Initialize object data */
+}
+
+void registerMethodsRateLimiter(rateLimiterFunctionst *f) {
+
+ f->free = freeRateLimiter;
+ f->terminate = terminateRateLimiter;
+ f->toString = toStringRateLimiter;
+ f->duplicate = duplicateRateLimiter;
+ f->smash = smashRateLimiter;
+ f->finish = finishRateLimiter;
+ f->setup = setupRateLimiter;
+ f->count = countRateLimiter;
+ f->incoming = incomingRateLimiter;
+ f->has = hasRateLimiter;
+ /* TODO add class functions */
+}
+
+void initiateAllocateRateLimiter(rateLimitert **self) {
+
+ if (self) {
+ (*self) = malloc(sizeof(rateLimitert));
+ if (*self) {
+ initiateRateLimiter(*self);
+ }
+ }
+}
+
+void finalizeRateLimiter(void) {
+
+ if (rateLimiterF) {
+ free(rateLimiterF);
+ rateLimiterF = NULL;
+ }
+}
+
+rateLimitert* allocRateLimiter(void) {
+ rateLimitert *r = NULL;
+
+ initiateAllocateRateLimiter(&r);
+ /* TODO copy data given in parameter to the object */
+ return(r);
+}
+
+
+internal void freeRateLimiter(rateLimitert *self) {
+
+ free(RATELIMA);
+ freerateL(&RATELIMH);
+ /* TODO free internal data (not the structure holding the function pointers) */
+ return;
+}
+
+internal void terminateRateLimiter(rateLimitert **self) {
+
+ freeRateLimiter(*self);
+ free(*self);
+ *self = NULL;
+}
+
+
+internal char* toStringRateLimiter(rateLimitert *self) {
+
+ /* TODO convert object data to string */
+ return(strdup("TODO - rateLimiter"));
+}
+
+internal rateLimitert* duplicateRateLimiter(rateLimitert *self) {
+
+ createAllocateRateLimiter(dup);
+ /* TODO COPY data */
+ return(dup);
+}
+
+internal void smashRateLimiter(rateLimitert **self) {
+
+ finishRateLimiter(self);
+}
+
+internal void finishRateLimiter(rateLimitert **self) {
+
+ free(*self);
+ *self = NULL;
+}
+
+
+internal bool setupRateLimiter(rateLimitert *self, u32 maxClients, u64 window, u32 maxAccessCount) {
+
+ if (RATELIMA) free(RATELIMA);
+ emptyrateL(&RATELIMH);
+
+ RATELIMA = malloc(sizeof(rateLimterE) * maxClients);
+ if (!RATELIMA) return false;
+
+ indexerInit(RATELIMIX, maxClients);
+
+ self->window = window;
+ self->maxAccessCount = maxAccessCount;
+ return true;
+}
+
+internal time_t getTime(void) {
+ return getCurrentUnixTime();
+ /* static time_t tim = 0; */
+ /* return tim++; */
+}
+
+internal void prune(rateLimitert *self) {
+ time_t now = getTime();
+
+ range (p, indexerCount(RATELIMIX)) {
+ if ((u64)(now - RATELIMFirst.time) < self->window)
+ break;
+ delrateL(&RATELIMH, RATELIMFirst.ip);
+ logI("removed %x", RATELIMFirst.ip);
+ indexerDequeue(RATELIMIX);
+ }
+}
+
+internal size_t countRateLimiter(rateLimitert *self) {
+ prune(self);
+ return indexerCount(RATELIMIX);
+}
+
+internal bool incomingRateLimiter(rateLimitert *self, u32 ip) {
+ time_t now = getTime();
+ logVarG(now);
+
+ u32 *value;
+ if ((value = findrateL(&RATELIMH, ip))) { // assign value and test NULL
+ u32 i = *value;
+ RATELIM(i).count++;
+ logI("found ip in rateLimiterA %x i %d, count %d time %d", ip, i, RATELIM(i).count, RATELIM(i).time);
+
+ if ((u64)(now - RATELIM(i).time) < self->window) {
+ //if ((now - RATELIM(i).time) < self->window) {
+ if (RATELIM(i).count < self->maxAccessCount) {
+ // limit not yet reached
+ return true;
+ }
+ else {
+ logI("too many connections from ip %x", ip);
+ return false;
+ }
+ }
+ else {
+ // remove connections older than self->window
+ prune(self);
+ size_t cnt = indexerCount(RATELIMIX);
+ logVarG(cnt);
+ return true;
+ }
+ }
+ else {
+ if (indexerIsFull(RATELIMIX)) {
+ if ((u64)(now - RATELIMFirst.time) >= self->window) {
+ // free first slot since it is older than self->window
+ delrateL(&RATELIMH, RATELIMFirst.ip);
+ indexerDequeue(RATELIMIX);
+ }
+ else {
+ logI("too many connections");
+ return false;
+ }
+ }
+
+ indexerPush(RATELIMIX);
+ /* u32 i = indexerLast(RATELIMIX); */
+ /* logI("new ip %x, i %d", ip, i); */
+ addrateL(&RATELIMH, ip, indexerLast(RATELIMIX));
+ RATELIMLast.ip = ip;
+ RATELIMLast.count = 1;
+ RATELIMLast.time = now;
+ return true;
+ }
+}
+
+internal bool hasRateLimiter(rateLimitert *self, u32 ip) {
+ prune(self);
+ ret findrateL(&RATELIMH, ip) ? true : false;
+}
+/* TODO add method implementations */
diff --git a/rateLimiter/rateLimiter.h b/rateLimiter/rateLimiter.h
@@ -0,0 +1,107 @@
+#pragma once
+
+/* Add class methods and class data where there are the TODOs (TODO)*/
+
+#include "libsheepyObject.h"
+#include "hashfunctions.h"
+#include "hashtable.h"
+
+#define setupG(obj, maxClients, window, maxAccessCount) (obj)->f->setup(obj, maxClients, window, maxAccessCount)
+#define clientCountG(obj) (obj)->f->count(obj)
+#define incomingG(obj, ip) (obj)->f->incoming(obj, ip)
+
+/* TODO add generics: #define amethodG(obj) (obj)->f->amethod(obj) */
+
+/* Class rateLimiter */
+typ struct rateLimiter rateLimitert;
+
+/* for object inheriting rateLimiter, cast to rateLimiter to be able to use this class functions and generics*/
+#define cRateLimiter(self) ( (rateLimitert*) self )
+
+typ struct {
+ u32 ip;
+ u32 count;
+ time_t time;
+} rateLimterE;
+
+hashTbDef(, rateL, rateL, u32, u32, u32);
+
+typ void (*freeRateLimiterFt) (rateLimitert *self);
+typ void (*terminateRateLimiterFt) (rateLimitert **self);
+typ char* (*toStringRateLimiterFt) (rateLimitert *self);
+typ rateLimitert* (*duplicateRateLimiterFt) (rateLimitert *self);
+typ void (*smashRateLimiterFt) (rateLimitert **self);
+
+/**
+ * free rateLimiter
+ */
+typ void (*finishRateLimiterFt) (rateLimitert **self);
+
+typ bool (*setupRateLimiterFt) (rateLimitert *self, u32 maxClients, u64 window, u32 maxAccessCount);
+typ size_t (*countRateLimiterFt) (rateLimitert *self);
+typ bool (*incomingRateLimiterFt) (rateLimitert *self, u32 ip);
+typ bool (*hasRateLimiterFt) (rateLimitert *self, u32 ip);
+/* TODO add function typ with pattern: functionNameClassTempleFt */
+
+/**
+ * class functions
+ * allocated once for all objects
+ *
+ * freed with finalizeRateLimiter
+ */
+
+/**
+ * use this define in child classes and add the new function after this class functions
+ *
+ * in this define, add the methods after <finishRateLimiterFt finish;>
+ *
+ * Example:
+ * #define RINGFUNCTIONST \n * RATELIMITERFUNCTIONST; \n * setSizeRingFt setSize
+ */
+#define RATELIMITERFUNCTIONST \
+ setupRateLimiterFt setup;\
+ countRateLimiterFt count;\
+ incomingRateLimiterFt incoming;\
+ hasRateLimiterFt has
+ /* TODO ADD METHODS AFTER <finishRateLimiterFt finish;> HERE */
+
+typ struct {
+ freeRateLimiterFt free;
+ terminateRateLimiterFt terminate;
+ toStringRateLimiterFt toString;
+ duplicateRateLimiterFt duplicate;
+ smashRateLimiterFt smash;
+ finishRateLimiterFt finish;
+ RATELIMITERFUNCTIONST;
+} rateLimiterFunctionst;
+
+/**
+ * class
+ */
+struct rateLimiter {
+ const char *type;
+ rateLimiterFunctionst *f;
+
+ rateLimterE *rateLimiterA;
+ indexer rateLimiterIx;
+ u64 window;
+ u32 maxAccessCount;
+ rateLt rateLimiterH;
+ /* TODO add class data */
+};
+
+/* rateLimiter */
+
+#define createRateLimiter(obj) rateLimitert obj; initiateRateLimiter(&obj)
+#define createAllocateRateLimiter(obj) rateLimitert *obj; initiateAllocateRateLimiter(&obj)
+
+void initiateRateLimiter(rateLimitert *self);
+void initiateAllocateRateLimiter(rateLimitert **self);
+void finalizeRateLimiter(void);
+
+/* initialize class methods, call registerMethodsRateLimiter from classes inheriting this class */
+void registerMethodsRateLimiter(rateLimiterFunctionst *f);
+
+rateLimitert* allocRateLimiter(void/*TODO INIT DATA */);
+
+/* end class rateLimiter*/
diff --git a/rateLimiter/rateLimiterInternal.h b/rateLimiter/rateLimiterInternal.h
@@ -0,0 +1,6 @@
+#pragma once
+
+static rateLimiterFunctionst *rateLimiterF = NULL;
+
+/* TODO declare structs for private data and add a void pointer to the private data in the class declaration */
+
diff --git a/serverPackage.sh b/serverPackage.sh
@@ -7,6 +7,7 @@ cp netFrame.h tuyauServer/
cp netFrameInternal.h tuyauServer/
cp serverPackage.yml tuyauServer/package.yml
cp sserver.c tuyauServer/tuyauServer.c
+cp -R rateLimiter tuyauServer/
cp -R shpPackages tuyauServer/
cd tuyauServer
diff --git a/serverPackage.yml b/serverPackage.yml
@@ -1,6 +1,6 @@
---
name: tuyauServer
- version: 0.0.3
+ version: 0.0.4
description: "Server for copying files with tuyau"
bin: ./tuyauServer.c
#cflags: -DA -g3 -std=gnu11 -fPIC -pipe
diff --git a/sserver.c b/sserver.c
@@ -32,6 +32,8 @@
#include "shpPackages/short/short.h"
#include "makeHeader.h"
+#include "rateLimiter/rateLimiter.h"
+
#define CONFIG "~/.tuyau/serverConfig.yml"
int packetCount = 0;
@@ -40,8 +42,10 @@ u64 transferSz = 0;
// client socket
int mysock = 0;
SSL *ssl;
+rateLimitert *rateLim = null;
+u32 clientIp = 0;
-smallJsont *tokens = null;
+smallJsont *tokens = null;
/* enable/disable logging */
/* #undef pLog */
@@ -78,6 +82,10 @@ int main(int ARGC, char** ARGV) {
initLibsheepy(ARGV[0]);
setLogMode(LOG_FUNC);
+ // block ips for 10mn when token is wrong
+ initiateAllocateRateLimiter(&rateLim);
+ setupG(rateLim, 1000000 /* max clients */, 600 /* window 10mn */, 0 /* max access count */);
+
SSL_CTX *ctx;
ctx = SSL_CTX_new(TLS_server_method());
int r = SSL_CTX_set_min_proto_version(ctx, TLS1_3_VERSION);
@@ -156,6 +164,12 @@ int main(int ARGC, char** ARGV) {
perror("accept failed");
else {
logI("Connection: %s:%d",inet_ntoa(addr.sin_addr), ntohs(addr.sin_port));
+ clientIp = addr.sin_addr.s_addr;
+ if (o(rateLim,has, clientIp)) {
+ logI("Ip %s is blocked.", inet_ntoa(addr.sin_addr));
+ close(mysock);
+ continue;
+ }
// get new SSL state with context
ssl = SSL_new(ctx);
// set connection socket to SSL state
@@ -170,12 +184,13 @@ int main(int ARGC, char** ARGV) {
}
// release SSL state
SSL_free(ssl);
+ close(mysock);
}
}
SSL_CTX_free(ctx);
-
terminateG(tokens);
+ terminateO(rateLim);
}
void saveReceivedData(void *receiveB, size_t sz) {
@@ -189,6 +204,7 @@ void saveReceivedData(void *receiveB, size_t sz) {
memcpy(tk, token, 8);
if (not hasG(tokens, tk)) {
+ incomingG(rateLim, clientIp);
logE("token not found");
ret;
}
@@ -199,6 +215,7 @@ void saveReceivedData(void *receiveB, size_t sz) {
// receive file
u16 *filenameLength = (u16*)(receiveB + 9);
+ if (*filenameLength > 4096) ret;
// receiveB + 11 = filename
cleanCharP(filename) = malloc(*filenameLength + 1);
filename[*filenameLength] = 0;
@@ -207,6 +224,7 @@ void saveReceivedData(void *receiveB, size_t sz) {
u16 *filemode = (u16*)(receiveB + bufi);
bufi += 2;
u16 *pathLength = (u16*)(receiveB + bufi);
+ if (*pathLength > 4096) ret;
bufi += 2;
cleanCharP(destPath) = null;
if (*pathLength) {
@@ -279,6 +297,7 @@ void saveReceivedData(void *receiveB, size_t sz) {
// mkdir
u16 *filemode = (u16*)(receiveB + 9);
u16 *pathLength = (u16*)(receiveB + 11);
+ if (*pathLength > 4096) ret;
cleanCharP(destPath) = malloc(*pathLength + 1);
memcpy(destPath, receiveB + 13, *pathLength);
destPath[*pathLength] = 0;
@@ -293,6 +312,7 @@ void saveReceivedData(void *receiveB, size_t sz) {
elif (*command == 2) {
logD("send files to client");
u16 *sendFileLength = (u16*)(receiveB + 9);
+ if (*sendFileLength > 4096) ret;
cleanCharP(sendFile) = malloc(*sendFileLength + 1);
memcpy(sendFile, receiveB + 11, *sendFileLength);
sendFile[*sendFileLength] = 0;
