// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you 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 IMPALA_RUNTIME_BUFFERPOOL_FREE_LIST_H
#define IMPALA_RUNTIME_BUFFERPOOL_FREE_LIST_H

#include <algorithm>
#include <cstdint>
#include <vector>

#include <boost/thread/locks.hpp>

#include "common/logging.h"
#include "gutil/macros.h"
#include "runtime/bufferpool/buffer-pool.h"

namespace impala {

using BufferHandle = BufferPool::BufferHandle;

/// A non-threadsafe list of free buffers.
///
/// Buffers are allocated by the caller and can be added to the list for later retrieval
/// with AddFreeBuffer(). If the list is non-empty, calling PopFreeBuffer() will return
/// one of the buffers previously added to the list. FreeList is agnostic about the size
/// or other properties of the buffers added to it.
///
/// Buffers in the list can be freed at any point, e.g. if the list is storing too many
/// free buffers (according to some policy). The caller is responsible for implementing
/// the policy and calling FreeBuffers() or FreeAll() at the appropriate times.
///
/// Address space fragmentation
/// ---------------------------
/// To reduce memory fragmentation, the free list hands out buffers with lower memory
/// addresses first and frees buffers with higher memory address first. If buffers were
/// handed out by a policy that didn't take memory address into account, over time the
/// distribution of free buffers within the address space would become essentially
/// random. If free buffers were then unmapped, there would be many holes in the virtual
/// memory map, which can cause difficulties for the OS in some cases, e.g. exceeding the
/// maximum number of mmapped() regions (vm.max_map_count) in Linux. Using this approach
/// will tend to consolidate free buffers in higher parts of the address space, allowing
/// coalescing of the holes in most cases.
class FreeList {
 public:
  FreeList() {}

  /// Gets a free buffer. If the list is non-empty, returns true and sets 'buffer' to
  /// one of the buffers previously added with AddFreeBuffer(). Otherwise returns false.
  bool PopFreeBuffer(BufferHandle* buffer) {
    if (free_list_.empty()) return false;
    std::pop_heap(free_list_.begin(), free_list_.end(), HeapCompare);
    *buffer = std::move(free_list_.back());
    free_list_.pop_back();
    return true;
  }

  /// Adds a free buffer to the list.
  void AddFreeBuffer(BufferHandle&& buffer) {
    buffer.Poison();
    free_list_.emplace_back(std::move(buffer));
    std::push_heap(free_list_.begin(), free_list_.end(), HeapCompare);
  }

  /// Get the 'num_buffers' buffers with the highest memory address from the list to
  /// free. The average time complexity is n log n, where n is the current size of the
  /// list.
  vector<BufferHandle> GetBuffersToFree(int64_t num_buffers) {
    vector<BufferHandle> buffers;
    DCHECK_LE(num_buffers, free_list_.size());
    // Sort the list so we can free the buffers with higher memory addresses.
    // Note that the sorted list is still a valid min-heap.
    std::sort(free_list_.begin(), free_list_.end(), SortCompare);

    for (int64_t i = 0; i < num_buffers; ++i) {
      buffers.emplace_back(std::move(free_list_.back()));
      free_list_.pop_back();
    }
    return buffers;
  }

  /// Returns the number of buffers currently in the list.
  int64_t Size() const { return free_list_.size(); }

 private:
  friend class FreeListTest;

  DISALLOW_COPY_AND_ASSIGN(FreeList);

  /// Compare function that orders by memory address.
  inline static bool SortCompare(const BufferHandle& b1, const BufferHandle& b2) {
    return b1.data() < b2.data();
  }

  /// Compare function that orders by memory address. Needs to be inverse of SortCompare()
  /// because C++ provides a max-heap.
  inline static bool HeapCompare(const BufferHandle& b1, const BufferHandle& b2) {
    return SortCompare(b2, b1);
  }

  /// List of free memory buffers. Maintained as a min-heap ordered by the memory address
  /// of the buffer.
  std::vector<BufferHandle> free_list_;
};
}

#endif