mirror of
https://github.com/bsnes-emu/bsnes.git
synced 2025-04-02 10:42:14 -04:00
81f43a4d01
This represents a major code restructuring. The dot-based and scanline-based renderers are now split into two separate core libraries, asnes and bsnes. For now at least, these are -internal- names. I'm not entirely decided on how I'm going to handle releasing these two separate builds. Regardless, the folders need names. asnes has had all of the processor subfolders collapsed back into their parent folders. In other words, ppu's functions were moved into ppu/sppu, and then ppu was deleted, and then ppu/sppu became the new ppu. Repeat this for the cpu, smp and dsp and there you go. asnes/dsp also removed the DSP_STATE_MACHINE option. This was done for the sake of consistency with the rest of the core. asnes' debugger mode is currently extremely broken, but I will be fixing it in time. And for now, bsnes has kept the processor abstraction layer. I may keep it around, not sure yet. It doesn't hurt speed or anything, so I'm not too worried about making a decision right away. I may throw snesfilter, snesreader and supergameboy into this folder, just to have everything in one place. The alternate GUI forks are definitely going in there as dotnet, cocoa and python. Compiled output goes to the out/ folder now, to prevent conflicts with a file and folder named bsnes, for instance.
109 lines
2.9 KiB
C++
109 lines
2.9 KiB
C++
#ifndef NALL_PRIORITYQUEUE_HPP
|
|
#define NALL_PRIORITYQUEUE_HPP
|
|
|
|
#include <limits>
|
|
#include <nall/function.hpp>
|
|
#include <nall/serializer.hpp>
|
|
#include <nall/utility.hpp>
|
|
|
|
namespace nall {
|
|
template<typename type_t> void priority_queue_nocallback(type_t) {}
|
|
|
|
//priority queue implementation using binary min-heap array;
|
|
//does not require normalize() function.
|
|
//O(1) find (tick)
|
|
//O(log n) insert (enqueue)
|
|
//O(log n) remove (dequeue)
|
|
template<typename type_t> class priority_queue {
|
|
public:
|
|
inline void tick(unsigned ticks) {
|
|
basecounter += ticks;
|
|
while(heapsize && gte(basecounter, heap[0].counter)) callback(dequeue());
|
|
}
|
|
|
|
//counter is relative to current time (eg enqueue(64, ...) fires in 64 ticks);
|
|
//counter cannot exceed std::numeric_limits<unsigned>::max() >> 1.
|
|
void enqueue(unsigned counter, type_t event) {
|
|
unsigned child = heapsize++;
|
|
counter += basecounter;
|
|
|
|
while(child) {
|
|
unsigned parent = (child - 1) >> 1;
|
|
if(gte(counter, heap[parent].counter)) break;
|
|
|
|
heap[child].counter = heap[parent].counter;
|
|
heap[child].event = heap[parent].event;
|
|
child = parent;
|
|
}
|
|
|
|
heap[child].counter = counter;
|
|
heap[child].event = event;
|
|
}
|
|
|
|
type_t dequeue() {
|
|
type_t event(heap[0].event);
|
|
unsigned parent = 0;
|
|
unsigned counter = heap[--heapsize].counter;
|
|
|
|
while(true) {
|
|
unsigned child = (parent << 1) + 1;
|
|
if(child >= heapsize) break;
|
|
if(child + 1 < heapsize && gte(heap[child].counter, heap[child + 1].counter)) child++;
|
|
if(gte(heap[child].counter, counter)) break;
|
|
|
|
heap[parent].counter = heap[child].counter;
|
|
heap[parent].event = heap[child].event;
|
|
parent = child;
|
|
}
|
|
|
|
heap[parent].counter = counter;
|
|
heap[parent].event = heap[heapsize].event;
|
|
return event;
|
|
}
|
|
|
|
void reset() {
|
|
basecounter = 0;
|
|
heapsize = 0;
|
|
}
|
|
|
|
void serialize(serializer &s) {
|
|
s.integer(basecounter);
|
|
s.integer(heapsize);
|
|
for(unsigned n = 0; n < heapcapacity; n++) {
|
|
s.integer(heap[n].counter);
|
|
s.integer(heap[n].event);
|
|
}
|
|
}
|
|
|
|
priority_queue(unsigned size, function<void (type_t)> callback_ = &priority_queue_nocallback<type_t>)
|
|
: callback(callback_) {
|
|
heap = new heap_t[size];
|
|
heapcapacity = size;
|
|
reset();
|
|
}
|
|
|
|
~priority_queue() {
|
|
delete[] heap;
|
|
}
|
|
|
|
priority_queue& operator=(const priority_queue&) = delete;
|
|
priority_queue(const priority_queue&) = delete;
|
|
|
|
private:
|
|
function<void (type_t)> callback;
|
|
unsigned basecounter;
|
|
unsigned heapsize;
|
|
unsigned heapcapacity;
|
|
struct heap_t {
|
|
unsigned counter;
|
|
type_t event;
|
|
} *heap;
|
|
|
|
//return true if x is greater than or equal to y
|
|
inline bool gte(unsigned x, unsigned y) {
|
|
return x - y < (std::numeric_limits<unsigned>::max() >> 1);
|
|
}
|
|
};
|
|
}
|
|
|
|
#endif
|