[libgee/0.6] PriorityQueue: fix segfault discovered during stress-testing



commit 19d1c24caaf201b689a923015d309141bb746b04
Author: Maciej Piechotka <uzytkownik2 gmail com>
Date:   Sun Nov 25 18:11:56 2012 +0000

    PriorityQueue: fix segfault discovered during stress-testing
    
    If node P is removed then set P to R, as described in paper, instead of
    NULL.

 gee/priorityqueue.vala |   13 +++++++++----
 1 files changed, 9 insertions(+), 4 deletions(-)
---
diff --git a/gee/priorityqueue.vala b/gee/priorityqueue.vala
index e31601c..7727d8f 100644
--- a/gee/priorityqueue.vala
+++ b/gee/priorityqueue.vala
@@ -1,6 +1,7 @@
 /* priorityqueue.vala
  *
  * Copyright (C) 2009  Didier Villevalois
+ * Copyright (C) 2012  Maciej Piechotka
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -233,9 +234,6 @@ public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
 		#endif
 
 		// 4. Adjust(Q, P, P)
-		if (_p == null) {
-			_p = _r;
-		}
 		_adjust (_p, _p);
 
 		// For now we can't have type2 node other than R' (left for reference)
@@ -764,7 +762,7 @@ public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
 
 		// Check whether removed node is P
 		if (node == _p) {
-			_p = null;
+			_p = _r;
 		}
 
 		// Maintain brothers list
@@ -791,6 +789,13 @@ public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
 	private void _updated_degree (Type1Node<G> node, bool child_removed) {
 		int degree = node.degree ();
 
+		// Ensure proper sizes of A and B
+		if (degree >= _a.length) {
+			int old_length = _a.length;
+			_a.resize (degree + 1);
+			_b.resize (degree + 1);
+		}
+
 		// Maintain A and B
 		if (child_removed && _a[degree - 1] == null) {
 			_a[degree - 1] = node;



[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]