러스트로는 이런거 못 짠다.

ㅋㅋㅋ

/* -*- Mode: C; indent-tabs-mode: nil; c-basic-offset: 2; tab-width: 2 -*- */

/*

  c-hash-map.c

  Copyright (C) 2021-2024 Hodong Kim, All rights reserved.

  Unauthorized copying of this software, via any medium is strictly prohibited.

  Proprietary and confidential.

  Written by Hodong Kim <hodong@nimfsoft.art>

 */

#if defined(__FreeBSD__) || defined(__OpenBSD__)

  #include <sys/endian.h>

#else

  #define _DEFAULT_SOURCE

  #include <endian.h>

  #include <sys/random.h>

#endif

#include "c-hash-map.h"

#include <stdlib.h>

#include <string.h>

#include "c-array.h"

#include "c-mem.h"

#include "c-list.h"

/*****************************************************************************/

typedef struct _CEntry CEntry;

struct _CEntry {

  CEntry* next;

  CEntry* prev;

  void*   key;

  void*   value;

};

static CEntry* c_entry_new (void* key, void* value)

{

  CEntry* entry = c_malloc (sizeof (CEntry));

  entry->key    = key;

  entry->value  = value;

  return entry;

}

static void c_entry_free (CEntry*   entry,

                          CFreeFunc key_free_func,

                          CFreeFunc value_free_func)

{

  if (key_free_func)

    key_free_func (entry->key);

  if (value_free_func)

    value_free_func (entry->value);

  free (entry);

}

/*****************************************************************************/

uint32_t c_murmur3_32 (const uint8_t* key, size_t len, uint32_t seed)

{

  uint32_t h = seed;

  uint32_t k;

  for (size_t i = len >> 2; i; i--)

  {

    k = htole32 (*(uint32_t*) key);

    key += sizeof (uint32_t);

    k *= 0xcc9e2d51;

    k = (k << 15) | (k >> 17);

    k *= 0x1b873593;

    h ^= k;

    h = (h << 13) | (h >> 19);

    h = h * 5 + 0xe6546b64;

  }

  k = 0;

  for (size_t i = len & 3; i; i--)

  {

    k <<= 8;

    k |= key[i - 1];

  }

  k *= 0xcc9e2d51;

  k = (k << 15) | (k >> 17);

  k *= 0x1b873593;

  h ^= k;

  h ^= len;

  h ^= h >> 16;

  h *= 0x85ebca6b;

  h ^= h >> 13;

  h *= 0xc2b2ae35;

  h ^= h >> 16;

  return h;

}

uintptr_t c_str_hash (const void* str, uint32_t seed)

{

  return c_murmur3_32 (str, strlen (str), seed);

}

/*****************************************************************************/

// RAND_MAX:      0x7fffffffU  This is a prime number

// UINT32_MAX:    0xffffffffU

#if defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__linux__)

  #define PRIME     0xfffffffbU /* for arc4random_uniform() or getrandom() */

#else

  #define PRIME     0x7fffffffU /* for rand() */

#endif

typedef struct _CBucket CBucket;

struct _CBucket {

  unsigned random;      // 1 <= k <= prime - 1

  unsigned entries_len; // entries_len = 2 * m * (m - 1)

  unsigned m;           // entries_len = 2 * m * (m - 1)

  unsigned b;           // rehash: b = lists[i]->len, insert: b = b + 1

  CEntry** entries;

};

// constant

#define DYNFECT_C  1 // m = (1 + c) * C_MAX (count, 4) in rehash()

#define DYNFECT_S  1 // buckets_len = S(M) = DYNFECT_S * dynfect->m

typedef struct _CDynfect CDynfect;

struct _CDynfect {

  unsigned   random;      /* 1 <= k <= prime - 1 */

  unsigned   buckets_len; /* buckets_len = S(M) = DYNFECT_S * dynfect->m */

  CHashFunc  key_hash_func;

  CEqualFunc key_equal_func;

  CFreeFunc  key_free_func;

  CFreeFunc  value_free_func;

  CList*     list;

  CBucket*   buckets;

  unsigned   op_count; /* count++ when add, remove */

  unsigned   m;        /* m = (1 + c) * C_MAX (count, 4) in rehash() */

};

static unsigned c_dynfect_gen_random ()

{

#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__linux__)

  #if RAND_MAX != 0x7fffffffU

    #error "Debug this source code"

  #endif

  static unsigned seed;

  if (!seed)

  {

    /* This is insecure */

    seed = time (NULL);

    srand (seed);

  }

#endif

  /* h(x) = (kx mod p) mod s; 1 <= k <= prime - 1 */

#if defined(__FreeBSD__) || defined(__OpenBSD__)

  return arc4random_uniform (PRIME - 1) + 1; /* uint32_t */

#elif defined __linux__

  uint32_t buf;

  if (getrandom (&buf, sizeof (uint32_t), 0) != -1)

    return buf % (PRIME - 1) + 1;

  else

    return rand() % (PRIME - 1) + 1; /* int */

#else

  return rand() % (PRIME - 1) + 1; /* int */

#endif

}

uintptr_t c_ptr_hash (const void* p, uint32_t seed)

{

  return (seed * (uintptr_t) p) % PRIME;

}

bool c_ptr_equal (const void* a, const void* b)

{

  return a == b;

}

static bool c_dynfect_condition (CDynfect* dynfect)

{

  unsigned sum = 0;

  // 32 * M * M / S(M) + 4 * M

  // S(M) is buckets_len

  // buckets_len is DYNFECT_S * dynfect->m

  unsigned bound = 32 * dynfect->m / DYNFECT_S + 4 * dynfect->m;

  for (unsigned i = 0; i < dynfect->buckets_len; i++)

  {

    sum = sum + dynfect->buckets[i].m;

    if (sum > bound)

      return false;

  }

  return true;

}

static bool c_dynfect_inject (CDynfect* dynfect, CArray* list, CBucket* bucket)

{

  bucket->random = c_dynfect_gen_random ();

  for (unsigned i = 0; i < list->len; i++)

  {

    CEntry*  entry = list->data[i];

    unsigned index = dynfect->key_hash_func (entry->key, bucket->random) %

                     (unsigned long) bucket->entries_len;

    if (bucket->entries[index])

      return false;

    bucket->entries[index] = entry;

  }

  return true;

}

static bool c_dynfect_contains (CDynfect* dynfect, const void* key)

{

  unsigned i = dynfect->key_hash_func (key, dynfect->random) % (unsigned long) dynfect->buckets_len;

  CBucket* bucket = &dynfect->buckets[i];

  if (bucket->entries_len > 0)

  {

    int pos = dynfect->key_hash_func (key, bucket->random) % (unsigned long) bucket->entries_len;

    CEntry* entry = bucket->entries[pos];

    if (entry && dynfect->key_equal_func (entry->key, key))

      return true;

  }

  return false;

}

static void c_dynfect_rehash (CDynfect* dynfect, CEntry* new_entry)

{

  CArray*  list;

  CArray** lists;

  list = c_array_new (NULL, true);

  for (unsigned i = 0; i < dynfect->buckets_len; i++)

  {

    CBucket* bucket = &dynfect->buckets[i];

    for (unsigned j = 0; j < bucket->entries_len; j++)

      if (bucket->entries[j])

        c_array_add (list, bucket->entries[j]);

    free (bucket->entries);

  }

  if (new_entry)

    c_array_add (list, new_entry);

  dynfect->op_count = list->len;

  dynfect->m = (1 + DYNFECT_C) * C_MAX (dynfect->op_count, 4);

  dynfect->buckets_len = DYNFECT_S * dynfect->m;

  dynfect->buckets = c_realloc (dynfect->buckets,

                                dynfect->buckets_len * sizeof (CBucket));

  memset (dynfect->buckets, 0, dynfect->buckets_len * sizeof (CBucket));

  lists = c_calloc (dynfect->buckets_len, sizeof (CArray*));

  do {

    dynfect->random = c_dynfect_gen_random ();

    for (unsigned i = 0; i < dynfect->buckets_len; i++)

      if (lists[i] && lists[i]->len)

        c_array_clear (lists[i]);

    for (unsigned i = 0; i < list->len; i++)

    {

      CEntry* entry = list->data[i];

      unsigned pos = dynfect->key_hash_func (entry->key, dynfect->random) % (unsigned long) dynfect->buckets_len;

      if (!lists[pos])

        lists[pos] = c_array_new (NULL, true);

      c_array_add (lists[pos], entry);

    }

    for (unsigned i = 0; i < dynfect->buckets_len; i++)

    {

      CBucket* bucket = &dynfect->buckets[i];

      memset (bucket, 0, sizeof (CBucket));

      bucket->b = lists[i] ? lists[i]->len : 0;

      bucket->m = 2 * bucket->b;

      bucket->entries_len = 2 * bucket->m * (bucket->m - 1);

    }

  } while (!c_dynfect_condition (dynfect));

  c_array_free (list);

  for (unsigned i = 0; i < dynfect->buckets_len; i++)

  {

    CBucket* bucket = &dynfect->buckets[i];

    if (lists[i] && (lists[i]->len > 0))

    {

      bucket->entries = c_calloc (bucket->entries_len, sizeof (CEntry*));

      do {

        memset (bucket->entries, 0, bucket->entries_len * sizeof (CEntry*));

      } while (!c_dynfect_inject (dynfect, lists[i], bucket));

    }

    if (lists[i])

      c_array_free (lists[i]);

  }

  free (lists);

}

static CDynfect* c_dynfect_new (CHashFunc  key_hash_func,

                                CEqualFunc key_equal_func,

                                CFreeFunc  key_free_func,

                                CFreeFunc  value_free_func,

                                CList*     list)

{

  CDynfect* dynfect = c_malloc (sizeof (CDynfect));

  dynfect->key_hash_func   = key_hash_func;

  dynfect->key_equal_func  = key_equal_func;

  dynfect->key_free_func   = key_free_func;

  dynfect->value_free_func = value_free_func;

  dynfect->list            = list;

  dynfect->op_count        = 0;

  dynfect->buckets_len     = 0;

  dynfect->buckets         = NULL;

  dynfect->m               = 0;

  c_dynfect_rehash (dynfect, NULL);

  return dynfect;

}

static bool

c_dynfect_insert (CDynfect* dynfect, void* key, void* value, CEntry* new_entry)

{

  if (new_entry)

    key = new_entry->key;

  unsigned index  = dynfect->key_hash_func (key, dynfect->random) %

                    (unsigned long) dynfect->buckets_len;

  CBucket* bucket = &dynfect->buckets[index];

  unsigned pos    = 0; // avoid maybe-uninitialized

  if (bucket->entries_len > 0)

  {

    pos = dynfect->key_hash_func (key, bucket->random) %

          (unsigned long) bucket->entries_len;

    CEntry* entry = bucket->entries[pos];

    if (entry)

    {

      if (dynfect->key_equal_func (entry->key, key))

      {

        if (dynfect->key_free_func)

          dynfect->key_free_func (entry->key);

        if (dynfect->value_free_func)

          dynfect->value_free_func (entry->value);

        entry->key   = key;

        entry->value = value;

        return false;

      }

    }

  }

  if (!new_entry)

  {

    new_entry = c_entry_new (key, value);

    c_list_insert_end (dynfect->list, (CNode*) new_entry);

  }

  dynfect->op_count++;

  if (dynfect->op_count > dynfect->m)

  {

    c_dynfect_rehash (dynfect, new_entry);

    return true;

  }

  bucket->b++;

  if (bucket->b <= bucket->m)

  {

    /* bucket->entries_len > 0 is true, so 'pos' NOT maybe-uninitialized */

    if (!bucket->entries[pos])

    {

      bucket->entries[pos] = new_entry;

    }

    else

    {

      CArray* list;

      list = c_array_new (NULL, true);

      for (unsigned i = 0; i < bucket->entries_len; i++)

        if (bucket->entries[i])

          c_array_add (list, bucket->entries[i]);

      c_array_add (list, new_entry);

      do {

        if (bucket->entries == NULL)

          bucket->entries = c_calloc (bucket->entries_len, sizeof (CEntry*));

        else

          memset (bucket->entries,

                  0, bucket->entries_len * sizeof (CEntry*));

      } while (!c_dynfect_inject (dynfect, list, bucket));

      c_array_free (list);

    }

  }

  else

  {

    if (c_dynfect_condition (dynfect))

    {

      CArray* list;

      list = c_array_new (NULL, true);

      if (bucket->entries)

        for (unsigned j = 0; j < bucket->entries_len; j++)

          if (bucket->entries[j])

            c_array_add (list, bucket->entries[j]);

      c_array_add (list, new_entry);

      bucket->m = 2 * C_MAX (bucket->m, 1);

      bucket->entries_len = 2 * (bucket->m) * (bucket->m - 1);

      bucket->entries = c_realloc (bucket->entries,

                                   bucket->entries_len * sizeof (CEntry*));

      do {

        memset (bucket->entries, 0, bucket->entries_len * sizeof (CEntry*));

      } while (!c_dynfect_inject (dynfect, list, bucket));

      c_array_free (list);

    }

    else

    {

      c_dynfect_rehash (dynfect, new_entry);

    }

  }

  return true;

}

static bool c_dynfect_remove (CDynfect* dynfect, const void* key)

{

  dynfect->op_count++;

  unsigned i = dynfect->key_hash_func (key, dynfect->random) %

                                       (unsigned long) dynfect->buckets_len;

  CBucket* bucket = &dynfect->buckets[i];

  if (bucket->entries_len < 1)

    return false;

  int pos = dynfect->key_hash_func (key, bucket->random) %

                                    (unsigned long) bucket->entries_len;

  CEntry* entry = bucket->entries[pos];

  if (entry == NULL)

    return false;

  c_list_remove_link (dynfect->list, (CNode*) entry);

  bucket->entries[pos] = NULL;

  if (dynfect->op_count >= dynfect->m)

    c_dynfect_rehash (dynfect, NULL);

  c_entry_free (entry, dynfect->key_free_func, dynfect->value_free_func);

  return true;

}

static void* c_dynfect_lookup (CDynfect* dynfect, const void* key)

{

  unsigned i = dynfect->key_hash_func (key, dynfect->random) % (unsigned long) dynfect->buckets_len;

  CBucket* bucket = &dynfect->buckets[i];

  if (bucket->entries_len > 0)

  {

    int pos = dynfect->key_hash_func (key, bucket->random) % (unsigned long) bucket->entries_len;

    CEntry* entry = bucket->entries[pos];

    if (entry && dynfect->key_equal_func (entry->key, key))

      return entry->value;

  }

  return NULL;

}

static void c_dynfect_free (CDynfect* dynfect)

{

  for (unsigned i = 0; i < dynfect->buckets_len; i++)

  {

    CBucket* bucket = &dynfect->buckets[i];

    free (bucket->entries);

  }

  free (dynfect->buckets);

  free (dynfect);

}