<commit_before>namespace mimosa
{
  template <typename Value, StringRef (*GetKey)(Value value)>
  inline
  Trie<Value, GetKey>::Trie(uint32_t depth)
    : value_(),
      childs_(nullptr),
      depth_(depth),
      size_(0)
  {
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline
  Trie<Value, GetKey>::~Trie()
  {
    clear();
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline void
  Trie<Value, GetKey>::clear()
  {
    if (childs_) {
      for (int i = 0; i < 256; ++i)
        delete childs_[i];
      free(childs_);
      childs_ = nullptr;
    }
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline void
  Trie<Value, GetKey>::allocateChilds()
  {
    assert(!childs_);
    childs_ = (Trie<Value, GetKey>**)calloc(sizeof (*childs_), 256);

    // check if value_ should go to childs_
    if (!value_)
      return;

    StringRef key = GetKey(value_);
    if (key.size() == depth_)
      return;

    insert(key, value_);
    value_ = nullptr;
    --size_;
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline bool
  Trie<Value, GetKey>::insert(const StringRef & key, Value value)
  {
    assert(key.size() >= depth_);

    if (key.size() == depth_) {
      if (!value_) {
        value_ = value;
        ++size_;
        return true;
      }

      if (GetKey(value_).size() > depth_) {
        std::swap(value, value_);
        insert(value);
        return true;
      }

      return false;
    }

    if (!value_ && !childs_) {
      value_ = value;
      ++size_;
      return true;
    }

    if (!childs_)
      allocateChilds();

    if (!childs_[(uint8_t)key[depth_]])
      childs_[(uint8_t)key[depth_]] = new Trie<Value, GetKey>(depth_ + 1);
    if (!childs_[(uint8_t)key[depth_]]->insert(key, value))
      return false;
    ++size_;
    return true;
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline Value
  Trie<Value, GetKey>::find(const StringRef & key) const
  {
    assert(key.size() >= depth_);

    if (key.size() == depth_) {
      if (value_)
        return value_;
      return nullptr;
    }

    if (!childs_ || !childs_[(uint8_t)key[depth_]])
      return nullptr;

    return childs_[(uint8_t)key[depth_]]->find(key);
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline void
  Trie<Value, GetKey>::erase(const StringRef & key)
  {
    if (key.size() == depth_) {
      value_ = nullptr;
      --size_;
      return;
    }

    if (!childs_ || !childs_[(uint8_t)key[depth_]])
      return;

    childs_[(uint8_t)key[depth_]]->erase(key);
    --size_;

    if (childs_[(uint8_t)key[depth_]]->empty()) {
      delete childs_[(uint8_t)key[depth_]];
      childs_[(uint8_t)key[depth_]] = nullptr;
    }
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline void
  Trie<Value, GetKey>::foreach(const std::function<void (Value)> & callback) const
  {
    if (value_)
      callback(value_);<commit_msg>Trie: fix a bug in insert() and remove()<commit_after>namespace mimosa
{
  template <typename Value, StringRef (*GetKey)(Value value)>
  inline
  Trie<Value, GetKey>::Trie(uint32_t depth)
    : value_(),
      childs_(nullptr),
      depth_(depth),
      size_(0)
  {
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline
  Trie<Value, GetKey>::~Trie()
  {
    clear();
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline void
  Trie<Value, GetKey>::clear()
  {
    if (childs_) {
      for (int i = 0; i < 256; ++i)
        delete childs_[i];
      free(childs_);
      childs_ = nullptr;
    }
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline void
  Trie<Value, GetKey>::allocateChilds()
  {
    assert(!childs_);
    childs_ = (Trie<Value, GetKey>**)calloc(sizeof (*childs_), 256);

    // check if value_ should go to childs_
    if (!value_)
      return;

    StringRef key = GetKey(value_);
    if (key.size() == depth_)
      return;

    insert(key, value_);
    value_ = nullptr;
    --size_;
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline bool
  Trie<Value, GetKey>::insert(const StringRef & key, Value value)
  {
    assert(key.size() >= depth_);

    if (key.size() == depth_) {
      if (!value_) {
        value_ = value;
        ++size_;
        return true;
      }

      if (GetKey(value_).size() > depth_) {
        std::swap(value, value_);
        insert(value);
        return true;
      }

      return false;
    }

    if (!value_ && !childs_) {
      value_ = value;
      ++size_;
      return true;
    }

    if (!childs_)
      allocateChilds();

    if (!childs_[(uint8_t)key[depth_]])
      childs_[(uint8_t)key[depth_]] = new Trie<Value, GetKey>(depth_ + 1);
    if (!childs_[(uint8_t)key[depth_]]->insert(key, value))
      return false;
    ++size_;
    return true;
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline Value
  Trie<Value, GetKey>::find(const StringRef & key) const
  {
    assert(key.size() >= depth_);

    if (key.size() == depth_ || size_ == 1) {
      if (value_ && GetKey(value_) == key)
        return value_;
      return nullptr;
    }

    if (!childs_ || !childs_[(uint8_t)key[depth_]])
      return nullptr;

    return childs_[(uint8_t)key[depth_]]->find(key);
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline void
  Trie<Value, GetKey>::erase(const StringRef & key)
  {
    if ((key.size() == depth_ || size_ == 1) &&
        (value_ && GetKey(value_) == key))
    {
      value_ = nullptr;
      --size_;
      return;
    }

    if (!childs_ || !childs_[(uint8_t)key[depth_]])
      return;

    childs_[(uint8_t)key[depth_]]->erase(key);
    --size_;

    if (childs_[(uint8_t)key[depth_]]->empty()) {
      delete childs_[(uint8_t)key[depth_]];
      childs_[(uint8_t)key[depth_]] = nullptr;
    }
  }

  template <typename Value, StringRef (*GetKey)(Value value)>
  inline void
  Trie<Value, GetKey>::foreach(const std::function<void (Value)> & callback) const
  {
    if (value_)
      callback(value_);
{'fraction_non_alphanumeric': 0.15652031989554432, 'fraction_numerical': 0.00718132854578097, 'mean_word_length': 2.792079207920792, 'pattern_counts': {'":': 0, '<': 43, '<?xml version=': 0, '>': 55, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6294388', 'n_tokens_mistral': 2160, 'n_tokens_neox': 2103, 'n_words': 473}