1 #include "targetqueue.h"
2 #include "ml_macros.h"
3 #include <gc/gc.h>
4 #include <string.h>
5
6 target_t **QueueHeap = 0;
7 target_t *PriorityAdjustQueue = 0;
8 int QueueSize = 0;
9 int QueueTop = 0;
10
targetqueue_init()11 void targetqueue_init() {
12 QueueSize = 32;
13 QueueHeap = anew(target_t *, QueueSize);
14 }
15
16 static void target_priority_compute(target_t *Target);
17
targetqueue_priority_fn(target_t * Target,int * Total)18 static int targetqueue_priority_fn(target_t *Target, int *Total) {
19 if (Target->QueuePriority == PRIORITY_INVALID) target_priority_compute(Target);
20 *Total += Target->QueuePriority;
21 return 0;
22 }
23
target_priority_compute(target_t * Target)24 static void target_priority_compute(target_t *Target) {
25 Target->QueuePriority = 1;
26 targetset_foreach(Target->Affects, &Target->QueuePriority, (void *)targetqueue_priority_fn);
27 }
28
targetqueue_insert(target_t * Target)29 void targetqueue_insert(target_t *Target) {
30 if (Target->QueuePriority == PRIORITY_INVALID) target_priority_compute(Target);
31 if (QueueTop == QueueSize) {
32 int NewHeapSize = QueueSize * 2;
33 target_t **NewHeap = anew(target_t *, NewHeapSize);
34 memcpy(NewHeap, QueueHeap, QueueSize * sizeof(target_t *));
35 QueueHeap = NewHeap;
36 QueueSize = NewHeapSize;
37 }
38 int Index = QueueTop++;
39 QueueHeap[Index] = Target;
40 while (Index > 0) {
41 int ParentIndex = (Index - 1) / 2;
42 target_t *Parent = QueueHeap[ParentIndex];
43 if (Parent->QueuePriority >= Target->QueuePriority) {
44 Target->QueueIndex = Index;
45 return;
46 }
47 Parent->QueueIndex = Index;
48 QueueHeap[Index] = Parent;
49 QueueHeap[ParentIndex] = Target;
50 Index = ParentIndex;
51 }
52 }
53
target_priority_invalidate(target_t * Target)54 void target_priority_invalidate(target_t *Target) {
55 if ((Target->QueueIndex >= 0) && (Target->QueuePriority > PRIORITY_INVALID)) {
56 Target->QueuePriority = PRIORITY_INVALID;
57 Target->PriorityAdjustNext = PriorityAdjustQueue;
58 PriorityAdjustQueue = Target;
59 }
60 }
61
targetqueue_adjust_queue()62 static inline void targetqueue_adjust_queue() {
63 target_t *Target = PriorityAdjustQueue;
64 PriorityAdjustQueue = 0;
65 while (Target) {
66 if (Target->QueuePriority == PRIORITY_INVALID) {
67 target_priority_compute(Target);
68 int Index = Target->QueueIndex;
69 while (Index > 0) {
70 int ParentIndex = (Index - 1) / 2;
71 target_t *Parent = QueueHeap[ParentIndex];
72 if (Parent->QueuePriority >= Target->QueuePriority) {
73 Target->QueueIndex = Index;
74 return;
75 }
76 Parent->QueueIndex = Index;
77 QueueHeap[Index] = Parent;
78 QueueHeap[ParentIndex] = Target;
79 Index = ParentIndex;
80 }
81 }
82 Target = Target->PriorityAdjustNext;
83 }
84 }
85
targetqueue_next()86 target_t *targetqueue_next() {
87 targetqueue_adjust_queue();
88 //printf("Queue state:\n");
89 //for (int Index = 0; Index < QueueTop; ++Index) printf("\t%d -> %d -> %s\n", Index, QueueHeap[Index]->QueuePriority, QueueHeap[Index]->Id);
90 target_t *Next = QueueHeap[0];
91 if (!Next) return 0;
92 Next->QueueIndex = -2;
93 int Index = 0;
94 target_t *Target = QueueHeap[--QueueTop];
95 QueueHeap[QueueTop] = 0;
96 if (!QueueTop) return Next;
97 for (;;) {
98 int Left = 2 * Index + 1;
99 int Right = 2 * Index + 2;
100 int Largest = Index;
101 QueueHeap[Index] = Target;
102 if (Left < QueueTop && QueueHeap[Left] && QueueHeap[Left]->QueuePriority > QueueHeap[Largest]->QueuePriority) {
103 Largest = Left;
104 }
105 if (Right < QueueTop && QueueHeap[Right] && QueueHeap[Right]->QueuePriority > QueueHeap[Largest]->QueuePriority) {
106 Largest = Right;
107 }
108 if (Largest != Index) {
109 target_t *Parent = QueueHeap[Largest];
110 QueueHeap[Index] = Parent;
111 Parent->QueueIndex = Index;
112 Index = Largest;
113 } else {
114 Target->QueueIndex = Index;
115 return Next;
116 }
117 }
118 }
119