러스트로 트리맵 구현하기 겁나 어려움

ㅋㅋㅋ

1. unsafe 써서 편한 길을 가자니 러스트 사용하는 장점이 소멸되고

2. 안전한 길을 가지니 겁나 어렵고

ㅋㅋㅋ

러스트로 개발하면 개발에 흥미 읽고

결국 5년 이내에 99%가 개발 포기하게 됩니다.

ㅋㅋㅋ

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

/*

 * c-tree-map.c

 * Copyright (C) 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>

*/

#include "c-tree-map.h"

#include "c-mem.h"

#include <stdlib.h>

#include <assert.h>

#define _RANK(node) ((node) ? (node)->rank : -1)

#ifdef NDEBUG

#undef NDEBUG

#endif

CTreeMap* c_tree_map_new (CCompareFunc key_compare_func,

                          CFreeFunc key_free_func,

                          CFreeFunc value_free_func)

{

  CTreeMap* map         = c_malloc (sizeof (CTreeMap));

  map->root             = nullptr;

  map->key_compare_func = key_compare_func;

  map->key_free_func    = key_free_func;

  map->value_free_func  = value_free_func;

  map->size             = 0;

  return map;

}

static void _free_node (CTreeMap* map, CTreeNode* node)

{

  if (!node)

    return;

  _free_node (map, node->left);

  _free_node (map, node->right);

  if (map->key_free_func)

    map->key_free_func (node->key);

  if (map->value_free_func)

    map->value_free_func (node->value);

  free (node);

}

void c_tree_map_free (CTreeMap* map)

{

  _free_node (map, map->root);

  free (map);

}

static void _update_rank (CTreeNode* h)

{

  h->rank = C_MAX (_RANK (h->left), _RANK (h->right)) + 1;

}

static CTreeNode* _node_new (void* key, void* value)

{

  CTreeNode* node = c_malloc (sizeof (CTreeNode));

  node->left   = nullptr;

  node->right  = nullptr;

  node->key    = key;

  node->value  = value;

  node->rank   = 0;

  return node;

}

CTreeNode* _rotate_left (CTreeNode* h)

{

  assert (h->left != nullptr);

  CTreeNode* x = h->left;

  h->left = x->right;

  x->right = h;

  _update_rank (h);

  _update_rank (x);

  return x;

}

CTreeNode* _rotate_right (CTreeNode* h)

{

  assert (h->right != nullptr);

  CTreeNode* x = h->right;

  h->right = x->left;

  x->left = h;

  _update_rank (h);

  _update_rank (x);

  return x;

}

static CTreeNode* _balance (CTreeNode* h)

{

  if ((_RANK(h->left) - _RANK(h->right) > 1))

  {

    if (_RANK(h->left->right) > _RANK(h->left->left))

      h->left = _rotate_right (h->left);

    h = _rotate_left (h);

  }

  else

  {

    if ((_RANK(h->right) - _RANK(h->left) > 1))

    {

      if (_RANK(h->right->left) > _RANK(h->right->right))

        h->right = _rotate_left (h->right);

      h = _rotate_right (h);

    }

  }

  _update_rank (h);

  return h;

}

static CTreeNode* _insert (CTreeMap* map, CTreeNode* h, void* key, void* value)

{

  if (h == nullptr)

  {

    map->size++;

    return _node_new (key, value);

  }

  int retval = map->key_compare_func (key, h->key);

  if (retval < 0)

  {

    h->left = _insert (map, h->left, key, value);

  }

  else if (retval > 0)

  {

    h->right = _insert (map, h->right, key, value);

  }

  else // replace

  {

    if (map->key_free_func)

      map->key_free_func (h->key);

    if (map->value_free_func)

      map->value_free_func (h->value);

    h->key   = key;

    h->value = value;

    return h;

  }

  return _balance (h);

}

static void _verify (CTreeNode* node, int* count)

{

  if (!node)

    return;

  _verify (node->left, count);

  _verify (node->right, count);

  (*count)++;

  // All leaf nodes have rank 0.

  if (!node->left && !node->right)

    assert (node->rank == 0);

  if (node->left && node->right && // An internal node

      !node->left->left && !node->left->right &&

      !node->right->left && !node->right->right) //  with two leaf nodes

    assert (node->rank == 1);  // has rank 1.

  // The rank difference from the parent node is 1 or 2.

  int diff;

  diff = abs (_RANK(node) - _RANK(node->left));

  assert (diff == 1 || diff == 2);

  diff = abs (_RANK(node) - _RANK(node->right));

  assert (diff == 1 || diff == 2);

  (void) diff;

}

void c_tree_map_varify (CTreeMap* map)

{

  int count = 0;

  _verify (map->root, &count);

  assert (map->size == count);

}

void c_tree_map_insert (CTreeMap* map, void* key, void* value)

{

  map->root = _insert (map, map->root, key, value);

  c_tree_map_varify (map);

}

int c_tree_map_size (CTreeMap* map)

{

  return map->size;

}

bool c_tree_map_lookup (CTreeMap* map, const void* key, void** value)

{

  CTreeNode* node = map->root;

  while (node)

  {

    int retval = map->key_compare_func (key, node->key);

    if (retval < 0)

    {

      node = node->left;

    }

    else if (retval > 0)

    {

      node = node->right;

    }

    else

    {

      if (value)

        *value = node->value;

      return true;

    }

  }

  return false;

}

CTreeNode* _real_remove (CTreeMap* map, CTreeNode* h)

{

  if (h->left && h->right)

  {

    if (h->left->rank > h->right->rank)

    {

      h = _rotate_left (h);

      h->right = _real_remove (map, h->right);

    }

    else

    {

      h = _rotate_right (h);

      h->left = _real_remove (map, h->left);

    }

  }

  else

  {

    CTreeNode* _next = nullptr;

    if (h->left)

      _next = h->left;

    else

      _next = h->right;

    if (map->key_free_func)

      map->key_free_func (h->key);

    if (map->value_free_func)

      map->value_free_func (h->value);

    free (h);

    return _next;

  }

  return _balance (h);

}

CTreeNode* _remove (CTreeMap* map, CTreeNode* h, void* key)

{

  if (!h)

    return nullptr;

  int retval = map->key_compare_func (key, h->key);

  if (retval < 0)

  {

    h->left = _remove (map, h->left, key);

  }

  else if (retval > 0)

  {

    h->right = _remove (map, h->right, key);

  }

  else

  {

    map->size--;

    return _real_remove (map, h);

  }

  return _balance (h);

}

void c_tree_map_remove (CTreeMap* map, void* key)

{

  map->root = _remove (map, map->root, key);

  c_tree_map_varify (map);

}

static void _foreach (CTreeNode* node,

                      CTreeMapOrder order,

                      CTreeMapForEachFunc func,

                      void* user_data)

{

  if (!node)

    return;

  if (order == C_TREE_MAP_PRE_ORDER)

    func (node->key, node->value, user_data);

  _foreach (node->left, order, func, user_data);

  if (order == C_TREE_MAP_IN_ORDER)

    func (node->key, node->value, user_data);

  _foreach (node->right, order, func, user_data);

  if (order == C_TREE_MAP_POST_ORDER)

    func (node->key, node->value, user_data);

}

void c_tree_map_foreach (CTreeMap* map,

                         CTreeMapOrder order,

                         CTreeMapForEachFunc func,

                         void* user_data)

{

  _foreach (map->root, order, func, user_data);

}