For some tests, I wrote this small code for implementing a priority
queue... However I found an issue in the unary pre-increment operator.
In fact, look at the PriorityQueue.insert() function, if I do:
QueueItem qi = new QueueItem(v, priority);
priority_queue[size++] = qi;
print("Added value with Prioirity
%d\n".printf(priority_queue[size].prio));
The code segfaults when doing the print, due to the fact that the size
value is not correctly incremented.
Otherwise, doing:
QueueItem qi = new QueueItem(v, priority);
size++;
priority_queue[size] = qi;
print("Added value with Prioirity
%d\n".printf(priority_queue[size].prio));
Everything works as expected.
Now, looking at the differencies in the generated C code, you can see
that _tmp1_ is set to self->priv->_size, but when size is incremented,
_tmp1_ is not, that's why there's a segfault when reading from an
un-initialized array location.
--- /tmp/priority-queue-invalid.c 2011-01-21 02:44:21.724660008 +0100
+++ /tmp/priority-queue-valid.c 2011-01-21 02:43:08.094660003 +0100
@@ -239,12 +239,12 @@
qi = _tmp0_;
_tmp1_ = self->priv->_size;
priority_queue_set_size (self, _tmp1_ + 1);
_tmp2_ = _priority_queue_queue_item_ref0 (qi);
_tmp3_ = _tmp2_;
- _priority_queue_queue_item_unref0 (self->priv->priority_queue[_tmp1_]);
- self->priv->priority_queue[_tmp1_] = _tmp3_;
+ _priority_queue_queue_item_unref0
(self->priv->priority_queue[self->priv->_size]);
+ self->priv->priority_queue[self->priv->_size] = _tmp3_;
_priority_queue_queue_item_unref0 (qi);
}
static void main(string[] args) {
var pq = new PriorityQueue<int>(5);
print("Testing Priority Queue\n");
print("Inserting 1 (2)\n"); pq.insert(1, 2);
print("Inserting 2 (4)\n"); pq.insert(2, 4);
print("Inserting 3 (1)\n"); pq.insert(3, 1);
print("Inserting 4 (3)\n"); pq.insert(4, 3);
print(@"$(pq.remove())\n");
print(@"$(pq.remove())\n");
print(@"$(pq.remove())\n");
print(@"$(pq.remove())\n");
}
class PriorityQueue<T> {
class QueueItem {
internal QueueItem(void* v, int p) {
value = v;
prio = p;
}
internal void* value;
internal int prio;
}
QueueItem[] priority_queue;
int size {public get; private set; }
public PriorityQueue(int n) {
priority_queue = new QueueItem[n];
size = 0;
}
public void insert(T v, int priority = 1) {
if (size >= priority_queue.length-2) {
print("Overflow!\n");
return;
}
QueueItem qi = new QueueItem((void*)v, priority);
size++;
priority_queue[size/*++ <- this would cause a sefault */] = qi;
print("Added value with Prioirity %d\n".printf(priority_queue[size].prio));
}
public T remove() {
if (size <= 0) {
print("Underflow!\n");
return null;
}
int max = 1;
for (int i = 2; i < size; i++) {
if (priority_queue[i].prio > priority_queue[max].prio)
max = i;
}
var qi = priority_queue[max];
priority_queue[max] = priority_queue[size];
priority_queue[size] = null;
size--;
return (T) qi.value;
}
}
_______________________________________________
vala-list mailing list
[email protected]
http://mail.gnome.org/mailman/listinfo/vala-list
