marvin at rectangular
Sep 18, 2008, 8:35 PM
Views: 2287
Permalink
|
|
r3880 - trunk/c_src/KinoSearch/Util
|
|
Author: creamyg
Date: 2008-09-18 20:35:26 -0700 (Thu, 18 Sep 2008)
New Revision: 3880
Modified:
trunk/c_src/KinoSearch/Util/PriorityQueue.bp
trunk/c_src/KinoSearch/Util/PriorityQueue.c
Log:
Add PriQ_Jostle().
Modified: trunk/c_src/KinoSearch/Util/PriorityQueue.bp
===================================================================
--- trunk/c_src/KinoSearch/Util/PriorityQueue.bp 2008-09-18 03:03:04 UTC (rev 3879)
+++ trunk/c_src/KinoSearch/Util/PriorityQueue.bp 2008-09-19 03:35:26 UTC (rev 3880)
@@ -37,6 +37,13 @@
bool_t
Insert(PriorityQueue *self, Obj *element);
+ /** Equivalent to Insert(), except for the return value. If the Queue has
+ * room, the element is inserted and Jostle() returns NULL. If not, then
+ * the item which falls out of the bottom of the Queue is returned.
+ */
+ incremented Obj*
+ Jostle(PriorityQueue *self, Obj *element);
+
/** Pop the *least* item off of the priority queue.
*/
incremented Obj*
Modified: trunk/c_src/KinoSearch/Util/PriorityQueue.c
===================================================================
--- trunk/c_src/KinoSearch/Util/PriorityQueue.c 2008-09-18 03:03:04 UTC (rev 3879)
+++ trunk/c_src/KinoSearch/Util/PriorityQueue.c 2008-09-19 03:35:26 UTC (rev 3880)
@@ -74,24 +74,37 @@
bool_t
PriQ_insert(PriorityQueue *self, Obj *element)
{
+ Obj *least = PriQ_Jostle(self, element);
+ REFCOUNT_DEC(least);
+ if (element == least) return false;
+ else return true;
+}
+
+Obj*
+PriQ_jostle(PriorityQueue *self, Obj *element)
+{
/* Absorb element if there's a vacancy. */
if (self->size < self->max_size) {
put(self, element);
- return true;
+ return NULL;
}
/* Otherwise, compete for the slot. */
- else if (self->size > 0) {
+ else if (self->size == 0) {
+ return REFCOUNT_INC(element);
+ }
+ else {
Obj *scratch = PriQ_Peek(self);
if ( !PriQ_Less_Than(self, element, scratch) ) {
/* If the new element belongs in the queue, replace something. */
- REFCOUNT_DEC( self->heap[1] );
+ Obj *retval = self->heap[1];
self->heap[1] = REFCOUNT_INC(element);
down_heap(self);
- return true;
+ return retval;
}
+ else {
+ return REFCOUNT_INC(element);
+ }
}
-
- return false;
}
Obj*
_______________________________________________
kinosearch-commits mailing list
kinosearch-commits [at] rectangular
http://www.rectangular.com/mailman/listinfo/kinosearch-commits
|
r3880 - trunk/c_src/KinoSearch/Util