runtime/vm/port_set.h

// Copyright (c) 2020, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

#ifndef RUNTIME_VM_PORT_SET_H_
#define RUNTIME_VM_PORT_SET_H_

#include "include/dart_api.h"

#include "platform/allocation.h"
#include "platform/globals.h"
#include "platform/utils.h"

namespace dart {

template <typename T /* :public PortSet<T>::Entry */>
class PortSet {
 public:
  static constexpr Dart_Port kFreePort = static_cast<Dart_Port>(0);
  static constexpr Dart_Port kDeletedPort = static_cast<Dart_Port>(3);

  struct Entry : public MallocAllocated {
    Entry() : port(kFreePort) {}
    explicit Entry(Dart_Port port) : port(port) {}

    // Free entries have set this to 0.
    Dart_Port port;
  };

  class Iterator {
   public:
    Iterator(PortSet<T>* ports, intptr_t index) : ports_(ports), index_(index) {
#if defined(DEBUG)
      dirty_counter_ = ports_->dirty_counter_;
#endif
    }

    DART_FORCE_INLINE T& operator->() const {
      ASSERT(index_ >= 0 && index_ < ports_->capacity_);
      DEBUG_ASSERT(!WasModified());
      return ports_->map_[index_];
    }
    DART_FORCE_INLINE T& operator*() const {
      ASSERT(index_ >= 0 && index_ < ports_->capacity_);
      DEBUG_ASSERT(!WasModified());
      return ports_->map_[index_];
    }

    DART_FORCE_INLINE bool operator==(const Iterator& other) const {
      DEBUG_ASSERT(!WasModified());
      return ports_ == other.ports_ && index_ == other.index_;
    }

    DART_FORCE_INLINE bool operator!=(const Iterator& other) const {
      DEBUG_ASSERT(!WasModified());
      return !(*this == other);
    }

    DART_FORCE_INLINE Iterator& operator++() {
      DEBUG_ASSERT(!WasModified());
      index_++;
      while (index_ < ports_->capacity_) {
        const Dart_Port port = ports_->map_[index_].port;
        if (port == kFreePort || port == kDeletedPort) {
          index_++;
          continue;
        } else {
          break;
        }
      }
      return *this;
    }

    // The caller must ensure to call [PortSet::Rebalance] once the iterator is
    // not used anymore.
    DART_FORCE_INLINE void Delete() {
      DEBUG_ASSERT(!WasModified());
      ports_->map_[index_] = T();
      ports_->map_[index_].port = kDeletedPort;
      ports_->used_--;
      ports_->deleted_++;
    }

   private:
    friend class PortSet;

#if defined(DEBUG)
    // Whether the underlying [PortSet] was modified in a way that would render
    // the iterator unusable.
    bool WasModified() const {
      return dirty_counter_ != ports_->dirty_counter_;
    }
#endif

    PortSet<T>* ports_;
    intptr_t index_ = 0;
#if defined(DEBUG)
    intptr_t dirty_counter_ = 0;
#endif
  };

  PortSet() {
    const intptr_t kInitialCapacity = 8;
    ASSERT(Utils::IsPowerOfTwo(kInitialCapacity));
    map_ = new T[kInitialCapacity];
    capacity_ = kInitialCapacity;
  }
  ~PortSet() {
    delete[] map_;
    map_ = nullptr;
  }

  bool IsEmpty() const { return used_ == 0; }

  DART_FORCE_INLINE Iterator begin() {
    for (intptr_t i = 0; i < capacity_; ++i) {
      auto& entry = map_[i];
      if (entry.port != kFreePort && entry.port != kDeletedPort) {
        return Iterator(this, i);
      }
    }
    return end();
  }

  DART_FORCE_INLINE Iterator end() { return Iterator(this, capacity_); }

  void Insert(const T& entry) {
    // Search for the first unused slot. Make use of the knowledge that here is
    // currently no port with this id in the port map.
    ASSERT(FindIndexOfPort(entry.port) < 0);
    intptr_t index = entry.port % capacity_;
    T cur = map_[index];

    // Stop the search at the first found unused (free or deleted) slot.
    while (cur.port != kFreePort && cur.port != kDeletedPort) {
      index = (index + 1) % capacity_;
      cur = map_[index];
    }

    // Insert the newly created port at the index.
    ASSERT(map_[index].port == kFreePort || map_[index].port == kDeletedPort);
    if (map_[index].port == kDeletedPort) {
      deleted_--;
    }
    map_[index] = entry;
    ASSERT(FindIndexOfPort(entry.port) >= 0);

    // Increment number of used slots and grow if necessary.
    used_++;
    MaintainInvariants();

#if defined(DEBUG)
    dirty_counter_++;
#endif
  }

  Iterator TryLookup(Dart_Port port) {
    const intptr_t index = FindIndexOfPort(port);
    if (index >= 0) return Iterator(this, index);
    return Iterator(this, capacity_);
  }

  bool Contains(Dart_Port port) { return FindIndexOfPort(port) >= 0; }

  // To be called if an iterator was used to delete an entry.
  void Rebalance() { MaintainInvariants(); }

 private:
  intptr_t FindIndexOfPort(Dart_Port port) {
    // ILLEGAL_PORT (0) is used as a sentinel value in Entry.port. The loop
    // below could return the index to a deleted port when we are searching for
    // port id ILLEGAL_PORT. Return -1 immediately to indicate the port
    // does not exist.
    if (port == ILLEGAL_PORT) {
      return -1;
    }
    ASSERT(port != ILLEGAL_PORT);
    intptr_t index = port % capacity_;
    intptr_t start_index = index;
    T entry = map_[index];
    while (entry.port != kFreePort) {
      if (entry.port == port) {
        return index;
      }
      index = (index + 1) % capacity_;
      // Prevent endless loops.
      ASSERT(index != start_index);
      entry = map_[index];
    }
    return -1;
  }

  void MaintainInvariants() {
    const intptr_t empty = capacity_ - used_ - deleted_;
    if (used_ > ((capacity_ / 4) * 3)) {
      // Grow the port map.
      Rehash(capacity_ * 2);
    } else if (empty < deleted_) {
      // Rehash without growing the table to flush the deleted slots out of the
      // map.
      Rehash(capacity_);
    }
  }

  void Rehash(intptr_t new_capacity) {
    T* new_ports = new T[new_capacity];

    for (auto entry : *this) {
      intptr_t new_index = entry.port % new_capacity;
      while (new_ports[new_index].port != 0) {
        new_index = (new_index + 1) % new_capacity;
      }
      new_ports[new_index] = entry;
    }
    delete[] map_;
    map_ = new_ports;
    capacity_ = new_capacity;
    deleted_ = 0;

#if defined(DEBUG)
    dirty_counter_++;
#endif
  }

  T* map_ = nullptr;
  intptr_t capacity_ = 0;
  intptr_t used_ = 0;
  intptr_t deleted_ = 0;

#if defined(DEBUG)
  intptr_t dirty_counter_ = 0;
#endif
};

}  // namespace dart

#endif  // RUNTIME_VM_PORT_SET_H_