43d241c28d
- Add arena allocator for zero-allocation hot paths - Add thread pool for parallel operations - Add mmap utilities for memory-mapped I/O - Implement queue_index with heap-based priority queue - Implement dataset_hash with SIMD support (SHA-NI, ARMv8) - Add runtime SIMD detection for cross-platform correctness - Add comprehensive tests and benchmarks
54 lines
1.6 KiB
C++
54 lines
1.6 KiB
C++
#pragma once
|
|
#include <stddef.h>
|
|
#include <stdint.h>
|
|
#include <vector>
|
|
#include <functional>
|
|
|
|
// Task priority comparator
|
|
// Higher priority first, then earlier created_at
|
|
template<typename T>
|
|
struct PriorityComparator {
|
|
std::function<int64_t(const T&)> get_priority;
|
|
std::function<int64_t(const T&)> get_created_at;
|
|
|
|
bool operator()(size_t a, size_t b, const std::vector<T>& items) const {
|
|
int64_t pa = get_priority(items[a]);
|
|
int64_t pb = get_priority(items[b]);
|
|
if (pa != pb) {
|
|
return pa < pb; // Max-heap: higher priority first
|
|
}
|
|
return get_created_at(items[a]) > get_created_at(items[b]); // Earlier first
|
|
}
|
|
};
|
|
|
|
// Binary heap for priority queue
|
|
// Uses indices into external storage for indirection
|
|
template<typename T, typename Comparator>
|
|
class BinaryHeap {
|
|
std::vector<size_t> heap_; // Indices into items_
|
|
const std::vector<T>& items_;
|
|
Comparator comp_;
|
|
|
|
void sift_up(size_t idx);
|
|
void sift_down(size_t idx);
|
|
|
|
public:
|
|
BinaryHeap(const std::vector<T>& items, Comparator comp);
|
|
|
|
// Build heap from unsorted indices
|
|
void build(const std::vector<size_t>& indices);
|
|
|
|
// Pop highest priority item
|
|
size_t pop();
|
|
|
|
// Peek at highest priority item without removing
|
|
size_t peek() const { return heap_.empty() ? SIZE_MAX : heap_.front(); }
|
|
|
|
// Get all items as sorted vector (highest priority first)
|
|
std::vector<size_t> sorted() const;
|
|
|
|
bool empty() const { return heap_.empty(); }
|
|
size_t size() const { return heap_.size(); }
|
|
|
|
void clear() { heap_.clear(); }
|
|
};
|