diff options
| -rw-r--r-- | lib/ChangeLog | 8 | ||||
| -rw-r--r-- | lib/pqueue.c | 14 | ||||
| -rw-r--r-- | lib/pqueue.h | 3 |
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 */ |