525 lines
17 KiB
MQL5
525 lines
17 KiB
MQL5
//+------------------------------------------------------------------+
|
|
//| Main.mqh |
|
|
//| Copyright 2026, Niquel Mendoza. |
|
|
//| https://www.mql5.com/ |
|
|
//+------------------------------------------------------------------+
|
|
#property copyright "Copyright 2026, Niquel Mendoza."
|
|
#property link "https://www.mql5.com/"
|
|
#property strict
|
|
|
|
#ifndef FASTCOLLECTIONSBYLEO_COLHASH_HASHBASES_MAIN_MQH
|
|
#define FASTCOLLECTIONSBYLEO_COLHASH_HASHBASES_MAIN_MQH
|
|
|
|
//+------------------------------------------------------------------+
|
|
//| |
|
|
//+------------------------------------------------------------------+
|
|
#include "Def.mqh"
|
|
|
|
//+------------------------------------------------------------------+
|
|
//| TPar requiere al menos: TKey key; ulong hash; |
|
|
//+------------------------------------------------------------------+
|
|
namespace TSN
|
|
{
|
|
//+------------------------------------------------------------------+
|
|
//| |
|
|
//+------------------------------------------------------------------+
|
|
template <typename TPar, typename TKey, typename TBase>
|
|
class CFastHashTableBase
|
|
{
|
|
public:
|
|
TPar m_table[];
|
|
//int m_table_capacity;
|
|
ulong m_meta[];
|
|
int m_num_groups;
|
|
uint m_last_created_pos;
|
|
|
|
protected:
|
|
int m_count;
|
|
int m_next_resize;
|
|
|
|
private:
|
|
int CalcNumGroups(int min_slots) const;
|
|
|
|
public:
|
|
CFastHashTableBase(void) {}
|
|
~CFastHashTableBase(void) {}
|
|
|
|
//---
|
|
bool Remove(const TKey& key);
|
|
void Remove(uint i, int bit_pos);
|
|
|
|
//---
|
|
int GetKeys(TKey& keys[]) const;
|
|
|
|
//---
|
|
__forceinline int Count() const { return m_count; }
|
|
__forceinline bool Contains(const TKey& key) const { return Find(key) != -1; }
|
|
|
|
//---
|
|
void Clear();
|
|
void Reserve(int reserve_elements);
|
|
void Init(int new_el_size);
|
|
|
|
//---
|
|
bool Find(const TKey& key, uint& i, int& bit_pos) const;
|
|
int Find(const TKey& key) const;
|
|
int Find(const ulong hash) const;
|
|
|
|
//---
|
|
bool Add(const TKey& key);
|
|
};
|
|
|
|
//+------------------------------------------------------------------+
|
|
//| |
|
|
//+------------------------------------------------------------------+
|
|
template <typename TPar, typename TKey, typename TBase>
|
|
bool CFastHashTableBase::Add(const TKey& key)
|
|
{
|
|
//---
|
|
if(m_count > m_next_resize)
|
|
{
|
|
Reserve((m_num_groups << 3) << 1); // primero convetirmos a "slots".. y a eso lo duplicmos..
|
|
// si teniamos en total 128 slots... lo doubplcas a 256
|
|
}
|
|
|
|
//---
|
|
const ulong hash = TBase::Hash(key);
|
|
const uint group_f = m_num_groups - 1;
|
|
uint i = uint(hash & group_f); // inicio
|
|
const uchar h2 = uchar(hash >> 57);
|
|
const ulong mask_hashes_finals = h2 * 0x0101010101010101; // mascara
|
|
|
|
//--- Iteracion circular
|
|
int final_pos = -1;
|
|
for(int it = 0; it < m_num_groups; it++)
|
|
{
|
|
//--- Verfiicar si coincide aqui..
|
|
const ulong has_mask_hash = m_meta[i] ^ mask_hashes_finals;
|
|
ulong mask_hash = TSNTABLES_SWAR_HAS(has_mask_hash);
|
|
while(mask_hash != 0)
|
|
{
|
|
const ulong flag = TSNTABLES_SWAR_64_DEJAR_SOLO_MINUS_SIG_BYTE(mask_hash);
|
|
const int pos = TSNTABLES_SWAR_64_GET_BYTE(flag); // nota usamos byte.. posicion exacta
|
|
#ifndef TSN_MQLARTICLES_USE_KEY
|
|
if(m_table[(i << 3) + pos].hash == hash)
|
|
{
|
|
// Ya existe
|
|
return false;
|
|
}
|
|
#else // TSN_MQLARTICLES_USE_KEY
|
|
if(TBase::Eq(m_table[(i << 3) + pos].key, key))
|
|
{
|
|
// Ya existe
|
|
return false;
|
|
}
|
|
#endif // TSN_MQLARTICLES_USE_KEY
|
|
|
|
mask_hash &= (mask_hash - 1);
|
|
}
|
|
// No existe ahi..
|
|
//---
|
|
const ulong has_mask_emptry = m_meta[i] ^ MQLARTICLES_HASHMAP_MASK_EMPTY;
|
|
const ulong mask_hash_empty = TSNTABLES_SWAR_HAS(has_mask_emptry);
|
|
if(mask_hash_empty != 0)
|
|
{
|
|
const ulong flag = TSNTABLES_SWAR_64_DEJAR_SOLO_MINUS_SIG_BYTE(mask_hash_empty);
|
|
final_pos = TSNTABLES_SWAR_64_GET_BIT(flag); // bit posicion
|
|
break;
|
|
}
|
|
|
|
//---
|
|
i = (i + 1) & group_f;
|
|
}
|
|
|
|
//---
|
|
if(final_pos == -1)
|
|
return false;
|
|
|
|
// 0 1 2 3 4 5 6 7
|
|
final_pos -= 7;
|
|
|
|
//---
|
|
// final pos en rango de [0-63]
|
|
const ulong clear_mask = ~(255ULL << final_pos);
|
|
m_meta[i] = (m_meta[i] & clear_mask) | (ulong(h2) << final_pos);
|
|
|
|
//---
|
|
m_last_created_pos = (i << 3) + (final_pos >> 3); // le añadimos la posicion exacta...
|
|
m_table[m_last_created_pos].key = key;
|
|
m_table[m_last_created_pos].hash = hash;
|
|
m_count++;
|
|
return true;
|
|
}
|
|
|
|
//+------------------------------------------------------------------+
|
|
//| |
|
|
//+------------------------------------------------------------------+
|
|
template <typename TPar, typename TKey, typename TBase>
|
|
int CFastHashTableBase::CalcNumGroups(int min_slots) const
|
|
{
|
|
// Cuántos grupos de 8 necesito como mínimo para cubrir min_slots
|
|
int min_groups = (min_slots + 7) >> 3; // redondeo hacia arriba, división por 8
|
|
if(min_groups < 1)
|
|
min_groups = 1;
|
|
|
|
// Redondear hacia arriba a la potencia de 2 más cercana
|
|
int groups = 1;
|
|
while(groups < min_groups)
|
|
groups <<= 1;
|
|
|
|
return groups;
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| |
|
|
//+------------------------------------------------------------------+
|
|
template <typename TPar, typename TKey, typename TBase>
|
|
void CFastHashTableBase::Init(int new_el_size)
|
|
{
|
|
//---
|
|
m_num_groups = CalcNumGroups(new_el_size);
|
|
const int total_slots = m_num_groups << 3;
|
|
ArrayResize(m_meta, m_num_groups);
|
|
ArrayResize(m_table, total_slots);
|
|
|
|
//---
|
|
for(int g = 0; g < m_num_groups; g++)
|
|
m_meta[g] = MQLARTICLES_HASHMAP_MASK_EMPTY;
|
|
|
|
//---
|
|
m_count = 0;
|
|
m_next_resize = (total_slots * 7) >> 3;
|
|
}
|
|
|
|
//+------------------------------------------------------------------+
|
|
//| |
|
|
//+------------------------------------------------------------------+
|
|
template <typename TPar, typename TKey, typename TBase>
|
|
void CFastHashTableBase::Clear(void)
|
|
{
|
|
//---
|
|
for(int g = 0; g < m_num_groups; g++)
|
|
m_meta[g] = MQLARTICLES_HASHMAP_MASK_EMPTY;
|
|
|
|
m_count = 0;
|
|
}
|
|
|
|
//+------------------------------------------------------------------+
|
|
//| |
|
|
//+------------------------------------------------------------------+
|
|
template <typename TPar, typename TKey, typename TBase>
|
|
void CFastHashTableBase::Reserve(int reserve_elements)
|
|
{
|
|
//---
|
|
// Si la tabla está vacía, es exactamente Init
|
|
if(m_count == 0)
|
|
{
|
|
Init(reserve_elements);
|
|
return;
|
|
}
|
|
|
|
//--- Si ya hay datos, guardamos referencia a la tabla vieja (completa)
|
|
TPar old_table[];
|
|
ulong old_meta[];
|
|
const int old_num_groups = m_num_groups;
|
|
const int prev_table_size = old_num_groups << 3;
|
|
|
|
//--- copy
|
|
ArrayResize(old_table, prev_table_size);
|
|
for(int i = 0; i < prev_table_size; i++)
|
|
old_table[i] = m_table[i];
|
|
|
|
ArrayCopy(old_meta, m_meta);
|
|
|
|
//--- Iniciamos mas grande... tamaño actual + nuevos elementos
|
|
Init(prev_table_size + reserve_elements);
|
|
|
|
//--- Reinsertamos cada elemento válido de la tabla vieja, sin recalcular el hash
|
|
//--- y sin pasar por Add (nunca hay duplicados, ya vienen de una tabla válida)
|
|
const uint group_f = uint(m_num_groups - 1);
|
|
|
|
for(int g = 0; g < old_num_groups; g++)
|
|
{
|
|
ulong occupied_mask = (old_meta[g] & MQLARTICLES_HASHMAP_MASK_HIGH_BIT) ^ MQLARTICLES_HASHMAP_MASK_HIGH_BIT;
|
|
while(occupied_mask != 0)
|
|
{
|
|
const ulong flag = TSNTABLES_SWAR_64_DEJAR_SOLO_MINUS_SIG_BYTE(occupied_mask);
|
|
const int slot = (g << 3) + TSNTABLES_SWAR_64_GET_BYTE(flag);
|
|
const ulong hash = old_table[slot].hash;
|
|
const uchar h2 = uchar(hash >> 57);
|
|
uint i = uint(hash & group_f);
|
|
|
|
//--- buscamos el primer slot vacío
|
|
int final_pos = -1;
|
|
for(int it = 0; it < m_num_groups; it++)
|
|
{
|
|
const ulong has_mask_empty = m_meta[i] ^ MQLARTICLES_HASHMAP_MASK_EMPTY;
|
|
const ulong mask_hash_empty = TSNTABLES_SWAR_HAS(has_mask_empty);
|
|
if(mask_hash_empty != 0)
|
|
{
|
|
const ulong f = TSNTABLES_SWAR_64_DEJAR_SOLO_MINUS_SIG_BYTE(mask_hash_empty);
|
|
final_pos = TSNTABLES_SWAR_64_GET_BIT(f);
|
|
break;
|
|
}
|
|
i = (i + 1) & group_f;
|
|
}
|
|
|
|
//---
|
|
final_pos -= 7;
|
|
const ulong clear_mask = ~(255ULL << final_pos);
|
|
m_meta[i] = (m_meta[i] & clear_mask) | (ulong(h2) << final_pos);
|
|
|
|
const uint fpos = (i << 3) + (final_pos >> 3);
|
|
m_table[fpos] = old_table[slot];
|
|
m_count++;
|
|
|
|
occupied_mask &= (occupied_mask - 1);
|
|
}
|
|
}
|
|
}
|
|
|
|
//+------------------------------------------------------------------+
|
|
//| |
|
|
//+------------------------------------------------------------------+
|
|
template <typename TPar, typename TKey, typename TBase>
|
|
int CFastHashTableBase::GetKeys(TKey& keys[]) const
|
|
{
|
|
ArrayResize(keys, m_count);
|
|
int out_idx = 0;
|
|
|
|
for(int group = 0; group < m_num_groups; group++)
|
|
{
|
|
//---
|
|
ulong occupied_mask = (m_meta[group] & MQLARTICLES_HASHMAP_MASK_HIGH_BIT) ^ MQLARTICLES_HASHMAP_MASK_HIGH_BIT;
|
|
|
|
//---
|
|
while(occupied_mask != 0)
|
|
{
|
|
const ulong flag = TSNTABLES_SWAR_64_DEJAR_SOLO_MINUS_SIG_BYTE(occupied_mask);
|
|
const int slot = (group << 3) + TSNTABLES_SWAR_64_GET_BYTE(flag);
|
|
keys[out_idx] = m_table[slot].key;
|
|
out_idx++;
|
|
occupied_mask &= (occupied_mask - 1);
|
|
}
|
|
}
|
|
|
|
//---
|
|
return out_idx; // debería ser == m_count al final
|
|
}
|
|
|
|
//+------------------------------------------------------------------+
|
|
//| |
|
|
//+------------------------------------------------------------------+
|
|
template <typename TPar, typename TKey, typename TBase>
|
|
bool CFastHashTableBase::Remove(const TKey& key)
|
|
{
|
|
//---
|
|
uint i; // grupo exacto
|
|
int bit_pos; // 0-63
|
|
if(!Find(key, i, bit_pos))
|
|
return false;
|
|
|
|
//---
|
|
bit_pos -= 7;
|
|
|
|
const ulong clear_mask = ~(255ULL << bit_pos);
|
|
m_meta[i] = (m_meta[i] & clear_mask) | (MQLARTICLES_HASHMAP_MDEL << bit_pos); // 0xFE = kDeleted
|
|
|
|
//---
|
|
m_count--;
|
|
return true;
|
|
}
|
|
|
|
//+------------------------------------------------------------------+
|
|
#define TSN_FASTHASHMAP_INDEX(i, bit_pos) ((i << 3) + (bit_pos >> 3))
|
|
template <typename TPar, typename TKey, typename TBase>
|
|
void CFastHashTableBase::Remove(uint i, int bit_pos)
|
|
{
|
|
//---
|
|
bit_pos -= 7;
|
|
const ulong clear_mask = ~(255ULL << bit_pos);
|
|
m_meta[i] = (m_meta[i] & clear_mask) | (MQLARTICLES_HASHMAP_MDEL << bit_pos); // 0xFE = kDeleted
|
|
|
|
//---
|
|
m_count--;
|
|
}
|
|
|
|
|
|
//+------------------------------------------------------------------+
|
|
//| Find |
|
|
//+------------------------------------------------------------------+
|
|
template <typename TPar, typename TKey, typename TBase>
|
|
bool CFastHashTableBase::Find(const TKey& key, uint& i, int& bit_pos) const
|
|
{
|
|
//---
|
|
const ulong hash = TBase::Hash(key);
|
|
const uint group_f = m_num_groups - 1;
|
|
i = uint(hash & group_f); // inicio
|
|
const uchar h2 = uchar(hash >> 57);
|
|
const ulong mask_hashes_finals = h2 * 0x0101010101010101; // mascara
|
|
|
|
//---
|
|
for(int it = 0; it < m_num_groups; it++)
|
|
{
|
|
//--- Verfiicar si coincide aqui..
|
|
const ulong has_mask_hash = m_meta[i] ^ mask_hashes_finals;
|
|
ulong mask_hash = TSNTABLES_SWAR_HAS(has_mask_hash);
|
|
while(mask_hash != 0)
|
|
{
|
|
const ulong flag = TSNTABLES_SWAR_64_DEJAR_SOLO_MINUS_SIG_BYTE(mask_hash);
|
|
bit_pos = TSNTABLES_SWAR_64_GET_BIT(flag); // nota usamos byte.. posicion exacta
|
|
#ifndef TSN_MQLARTICLES_USE_KEY
|
|
if(m_table[(i << 3) + (bit_pos >> 3)].hash == hash)
|
|
return true;
|
|
#else // TSN_MQLARTICLES_USE_KEY
|
|
if(TBase::Eq(m_table[(i << 3) + (bit_pos >> 3)].key, key))
|
|
return true;
|
|
#endif // TSN_MQLARTICLES_USE_KEY
|
|
|
|
mask_hash &= (mask_hash - 1);
|
|
}
|
|
|
|
//---
|
|
const ulong has_mask_emptry = m_meta[i] ^ MQLARTICLES_HASHMAP_MASK_EMPTY;
|
|
const ulong mask_hash_empty = TSNTABLES_SWAR_HAS(has_mask_emptry);
|
|
if(mask_hash_empty != 0)
|
|
return false; // Empty aqui...
|
|
|
|
//---
|
|
i = (i + 1) & group_f;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
//+------------------------------------------------------------------+
|
|
#define TSN_FASTHASHMAP_MACRO_U_S \
|
|
const uint group_f = m_num_groups - 1;\
|
|
uint i = uint(hash & group_f); \
|
|
const uchar h2 = uchar(hash >> 57);\
|
|
const ulong mask_hashes_finals = h2 * 0x0101010101010101; \
|
|
for(int it = 0; it < m_num_groups; it++) \
|
|
{ \
|
|
const ulong has_mask_hash = m_meta[i] ^ mask_hashes_finals; \
|
|
ulong mask_hash = TSNTABLES_SWAR_HAS(has_mask_hash); \
|
|
while(mask_hash != 0) \
|
|
{ \
|
|
const ulong flag = TSNTABLES_SWAR_64_DEJAR_SOLO_MINUS_SIG_BYTE(mask_hash); \
|
|
const int slot = int(i << 3) + (TSNTABLES_SWAR_64_GET_BIT(flag) >> 3);
|
|
|
|
//+------------------------------------------------------------------+
|
|
#define TSN_FASTHASHMAP_MACRO_U_E \
|
|
mask_hash &= (mask_hash - 1); \
|
|
} \
|
|
const ulong has_mask_emptry = m_meta[i] ^ MQLARTICLES_HASHMAP_MASK_EMPTY; \
|
|
const ulong mask_hash_empty = TSNTABLES_SWAR_HAS(has_mask_emptry); \
|
|
if(mask_hash_empty != 0) \
|
|
return -1; \
|
|
i = (i + 1) & group_f; \
|
|
}
|
|
|
|
|
|
//+------------------------------------------------------------------+
|
|
template <typename TPar, typename TKey, typename TBase>
|
|
int CFastHashTableBase::Find(const ulong hash) const
|
|
{
|
|
//---
|
|
TSN_FASTHASHMAP_MACRO_U_S
|
|
#ifndef TSN_MQLARTICLES_USE_KEY
|
|
if(m_table[slot].hash == hash)
|
|
return slot;
|
|
#else
|
|
if(TBase::Eq(m_table[slot].key, key))
|
|
return slot;
|
|
#endif
|
|
TSN_FASTHASHMAP_MACRO_U_E
|
|
|
|
//---
|
|
return -1;
|
|
}
|
|
|
|
|
|
//+------------------------------------------------------------------+
|
|
template <typename TPar, typename TKey, typename TBase>
|
|
int CFastHashTableBase::Find(const TKey& key) const
|
|
{
|
|
//---
|
|
const ulong hash = TBase::Hash(key);
|
|
|
|
//---
|
|
TSN_FASTHASHMAP_MACRO_U_S
|
|
#ifndef TSN_MQLARTICLES_USE_KEY
|
|
if(m_table[slot].hash == hash)
|
|
return slot;
|
|
#else
|
|
if(TBase::Eq(m_table[slot].key, key))
|
|
return slot;
|
|
#endif
|
|
TSN_FASTHASHMAP_MACRO_U_E
|
|
|
|
//---
|
|
return -1;
|
|
}
|
|
|
|
|
|
//+------------------------------------------------------------------+
|
|
//| |
|
|
//+------------------------------------------------------------------+
|
|
template <typename TCtx, typename TKey>
|
|
struct CFastHashTableIteratorBase
|
|
{
|
|
TCtx* m_ctx;
|
|
ulong m_current_mask;
|
|
int m_num_groups;
|
|
int m_group_index;
|
|
int m_current_slot;
|
|
|
|
|
|
CFastHashTableIteratorBase(TCtx* ptr)
|
|
: m_ctx(ptr), m_current_mask(0), m_num_groups(ptr.m_num_groups), m_group_index(-1), m_current_slot(0)
|
|
{
|
|
Next();
|
|
}
|
|
CFastHashTableIteratorBase()
|
|
: m_ctx(NULL), m_current_mask(0), m_num_groups(0), m_group_index(-1), m_current_slot(0)
|
|
{
|
|
}
|
|
|
|
//---
|
|
__forceinline bool IsValid() const { return m_group_index < m_num_groups; }
|
|
void Kill() { m_group_index = m_num_groups; }
|
|
void Next();
|
|
|
|
//---
|
|
__forceinline ulong Hash() const { return m_ctx.m_table[m_current_slot].hash; }
|
|
__forceinline TKey Key() const { return m_ctx.m_table[m_current_slot].key; }
|
|
__forceinline int KeyLen() const { return StringLen(m_ctx.m_table[m_current_slot].key); }
|
|
};
|
|
|
|
//+------------------------------------------------------------------+
|
|
//| |
|
|
//+------------------------------------------------------------------+
|
|
template <typename TCtx, typename TKey>
|
|
void CFastHashTableIteratorBase::Next()
|
|
{
|
|
//--- Solo si esta vacia...
|
|
while(true)
|
|
{
|
|
if(m_current_mask != 0)
|
|
{
|
|
const ulong flag = TSNTABLES_SWAR_64_DEJAR_SOLO_MINUS_SIG_BYTE(m_current_mask);
|
|
m_current_slot = (m_group_index << 3) + TSNTABLES_SWAR_64_GET_BYTE(flag);
|
|
m_current_mask &= (m_current_mask - 1);
|
|
return;
|
|
}
|
|
|
|
//---
|
|
m_group_index++;
|
|
if(m_group_index >= m_num_groups)
|
|
return;
|
|
|
|
//---
|
|
m_current_mask = (m_ctx.m_meta[m_group_index] & MQLARTICLES_HASHMAP_MASK_HIGH_BIT) ^ MQLARTICLES_HASHMAP_MASK_HIGH_BIT;
|
|
}
|
|
}
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
#endif // FASTCOLLECTIONSBYLEO_COLHASH_HASHBASES_MAIN_MQH
|