Program Listing for File hash_map.hpp

            

            
/*
* SPDX-FileCopyrightText: Copyright (c) 2025 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
* SPDX-License-Identifier: Apache-2.0
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef HOLOSCAN_POSE_TREE_HASH_MAP_HPP
#define HOLOSCAN_POSE_TREE_HASH_MAP_HPP

#include <memory>
#include <shared_mutex>
#include <utility>

#include "holoscan/core/expected.hpp"
#include "holoscan/pose_tree/math/pose3.hpp"

namespace holoscan::pose_tree {

template <typename Key, typename Value>
class HashMap {
 public:
  enum class Error {
    kInvalidArgument,
    kOutOfMemory,
    kHashMapFull,
    kKeyNotFound,
    kKeyAlreadyExists
  };

  template <typename T>
  using expected_t = expected<T, Error>;
  using unexpected_t = unexpected<Error>;

  using hash_t = uint64_t;

  HashMap() = default;

  expected_t<void> reserve(int32_t size, int32_t capacity) {
    if (size <= 0) { return unexpected_t(Error::kInvalidArgument); }
    if (capacity < size) { return unexpected_t(Error::kInvalidArgument); }
    entries_.reset(new Entry[capacity]);
    for (int32_t i = 0; i < capacity; ++i) { entries_[i].is_occupied = false; }
    max_size_ = size;
    capacity_ = capacity;
    return {};
  }

  bool has(const Key& key) const {
    hash_t hash = std::hash<Key>{}(key);
    int32_t index = hash % capacity_;
    while (entries_[index].is_occupied) {
      if (entries_[index].hash == hash && entries_[index].key == key) { return true; }
      ++index;
      if (index == capacity_) { index = 0; }
    }
    return false;
  }

  expected_t<Value> get(const Key& key) const {
    hash_t hash = std::hash<Key>{}(key);
    int32_t index = hash % capacity_;
    while (entries_[index].is_occupied) {
      if (entries_[index].hash == hash && entries_[index].key == key) {
        return entries_[index].value;
      }
      ++index;
      if (index == capacity_) { index = 0; }
    }
    return unexpected_t(Error::kKeyNotFound);
  }

  expected_t<void> insert(const Key& key, Value value) {
    if (size_ >= max_size_) { return unexpected_t(Error::kHashMapFull); }
    hash_t hash = std::hash<Key>{}(key);
    int32_t index = hash % capacity_;
    while (entries_[index].is_occupied) {
      if (entries_[index].hash == hash && entries_[index].key == key) {
        return unexpected_t(Error::kKeyAlreadyExists);
      }
      ++index;
      if (index == capacity_) { index = 0; }
    }
    entries_[index].hash = hash;
    entries_[index].key = key;
    entries_[index].value = std::move(value);
    entries_[index].is_occupied = true;
    ++size_;
    return {};
  }

  expected_t<void> erase(const Key& key) {
    hash_t hash = std::hash<Key>{}(key);
    int32_t index = hash % capacity_;
    while (entries_[index].is_occupied) {
      if (entries_[index].hash == hash && entries_[index].key == key) {
        entries_[index].is_occupied = false;
        --size_;
        fill_holes(index);
        return {};
      }
      ++index;
      if (index == capacity_) { index = 0; }
    }
    return unexpected_t(Error::kKeyNotFound);
  }

  int32_t size() const { return size_; }

 private:
  struct Entry {
    hash_t hash;
    Key key;
    bool is_occupied;
    Value value;
  };

  void fill_holes(int index) {
    while (true) {
      int32_t start_index = index;
      int32_t swap_index = index;
      while (true) {
        ++index;
        if (index == capacity_) {
          index = 0;
          start_index -= capacity_;
        }
        if (!entries_[index].is_occupied) { return; }
        int32_t target_index = entries_[index].hash % capacity_;
        if (target_index > index) { target_index -= capacity_; }
        if (target_index <= start_index) {
          std::swap(entries_[index], entries_[swap_index]);
          break;
        }
      }
    }
  }

  std::unique_ptr<Entry[]> entries_;
  int32_t size_ = 0;
  int32_t max_size_ = 0;
  int32_t capacity_ = 0;
};

}  // namespace holoscan::pose_tree

#endif// HOLOSCAN_POSE_TREE_HASH_MAP_HPP