summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/ChangeLog8
-rw-r--r--lib/pqueue.c14
-rw-r--r--lib/pqueue.h3
3 files changed, 24 insertions, 1 deletions
diff --git a/lib/ChangeLog b/lib/ChangeLog
index 4573839d..6d1a229e 100644
--- a/lib/ChangeLog
+++ b/lib/ChangeLog
@@ -1,3 +1,11 @@
+2005-02-21 Vincenzo Eramo <eramo at infocom.ing.uniroma1.it>
+
+ * pqueue.[ch]: Introduce "update" function to meet ospf spf needs. It
+ will allow to update node when:
+ i) a node is inserted into the priority queue;
+ ii) a node position is modified in the priority queue;
+ * pqueue.h: Export trickle_down() function.
+
2005-02-19 Paul Jakma <paul.jakma@sun.com>
* stream.c: (stream_new) fix dumb mistake.
diff --git a/lib/pqueue.c b/lib/pqueue.c
index 1e41b092..870f8a7c 100644
--- a/lib/pqueue.c
+++ b/lib/pqueue.c
@@ -56,14 +56,18 @@ trickle_up (int index, struct pqueue *queue)
{
/* actually trickle up */
queue->array[index] = queue->array[PARENT_OF (index)];
+ if (queue->update != NULL)
+ (*queue->update) (queue->array[index], index);
index = PARENT_OF (index);
}
/* Restore the tmp node to appropriate place. */
queue->array[index] = tmp;
+ if (queue->update != NULL)
+ (*queue->update) (tmp, index);
}
-static void
+void
trickle_down (int index, struct pqueue *queue)
{
void *tmp;
@@ -90,11 +94,15 @@ trickle_down (int index, struct pqueue *queue)
/* Actually trickle down the tmp node. */
queue->array[index] = queue->array[which];
+ if (queue->update != NULL)
+ (*queue->update) (queue->array[index], index);
index = which;
}
/* Restore the tmp node to appropriate place. */
queue->array[index] = tmp;
+ if (queue->update != NULL)
+ (*queue->update) (tmp, index);
}
struct pqueue *
@@ -110,6 +118,8 @@ pqueue_create ()
memset (queue->array, 0, DATA_SIZE * PQUEUE_INIT_ARRAYSIZE);
queue->array_size = PQUEUE_INIT_ARRAYSIZE;
+ /* By default we want nothing to happen when a node changes. */
+ queue->update = NULL;
return queue;
}
@@ -146,6 +156,8 @@ pqueue_enqueue (void *data, struct pqueue *queue)
return;
queue->array[queue->size] = data;
+ if (queue->update != NULL)
+ (*queue->update) (data, queue->size);
trickle_up (queue->size, queue);
queue->size ++;
}
diff --git a/lib/pqueue.h b/lib/pqueue.h
index 95f79b8c..d19c46de 100644
--- a/lib/pqueue.h
+++ b/lib/pqueue.h
@@ -28,6 +28,7 @@ struct pqueue
int size;
int (*cmp) (void *, void *);
+ void (*update) (void * node, int actual_position);
};
#define PQUEUE_INIT_ARRAYSIZE 32
@@ -38,4 +39,6 @@ void pqueue_delete (struct pqueue *queue);
void pqueue_enqueue (void *data, struct pqueue *queue);
void *pqueue_dequeue (struct pqueue *queue);
+void trickle_down (int index, struct pqueue *queue);
+
#endif /* _ZEBRA_PQUEUE_H */