https://github.com/cran/gstat
Tip revision: 6452e9e00339be4420cd3b01a58628e55e5d40bd authored by Edzer Pebesma on 26 September 2019, 13:00:02 UTC
version 2.0-3
version 2.0-3
Tip revision: 6452e9e
pqueue.c
/*
* priority queue, Jan-Apr 1998
*
* I did a net search one day, and found so many implementations of
* priority queues that I decided to write my own. For the fun of it.
*
* This one has no limits and needs a generic (qsort-like) comparison
* function for element comparison at initialisation. To enqueue an
* unordered array of elements, elements are sorted with qsort(), before
* they are merged into the ordered queue. Only pointers to the next
* element are stored (so it's basically an ordered single linked list).
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "defs.h"
#include "userio.h"
#include "data.h"
#include "utils.h"
#include "nsearch.h"
#include "pqueue.h"
static void enlarge_queue(QUEUE *q);
static void enlarge_queue(QUEUE *q) {
/*
* don't use realloc() on `empty': all pointers to the
* first element would have to be moved along with itself.
*/
int i;
Q_ELEMENT *block;
block = (Q_ELEMENT *) emalloc(Q_BUFFER_SIZE * sizeof(Q_ELEMENT));
for (i = 0; i < Q_BUFFER_SIZE - 1; i++)
block[i].next = &(block[i+1]);
block[Q_BUFFER_SIZE - 1].next = NULL;
if (q->empty == NULL)
q->empty = block;
else
q->empty->next = block;
q->max_length += Q_BUFFER_SIZE;
/* register block to free later on... */
q->blocks += 1;
q->block = (Q_ELEMENT **) erealloc(q->block, q->blocks * sizeof(Q_ELEMENT *));
q->block[q->blocks - 1] = block;
}
QUEUE *init_queue(QUEUE *q, int (CDECL *cmp)(const QUEUE_NODE *a,
const QUEUE_NODE *b)) {
int i, j;
if (q == NULL) {
q = (QUEUE *) emalloc(sizeof(QUEUE));
q->max_length = q->blocks = 0;
q->empty = NULL;
q->block = NULL;
q->cmp = cmp;
enlarge_queue(q);
} else {
q->empty = q->block[0];
for (i = 0; i < q->blocks; i++) {
for (j = 0; j < Q_BUFFER_SIZE - 1; j++) /* connect elements: */
q->block[i][j].next = &(q->block[i][j+1]);
if (i < q->blocks - 1) /* connect elements between blocks: */
q->block[i][Q_BUFFER_SIZE - 1].next = &(q->block[i+1][0]);
}
q->block[q->blocks - 1][Q_BUFFER_SIZE - 1].next = NULL;
}
q->length = 0;
q->head = NULL;
return q;
}
void free_queue(QUEUE *q) {
int i;
if (q != NULL) {
for (i = 0; i < q->blocks; i++)
efree(q->block[i]); /* queue buffers */
if (q->block != NULL)
efree(q->block);
efree(q);
}
}
static Q_ELEMENT *get_free(QUEUE *q) {
Q_ELEMENT *e;
if (q->empty->next == NULL)
enlarge_queue(q);
e = q->empty;
q->empty = q->empty->next;
return e;
}
void enqueue(QUEUE *q, QUEUE_NODE *el, int n) {
/*
* insert n elements in array el into the priority queue q
*/
Q_ELEMENT *e, *where, *next;
int i = 0, p;
if (q == NULL || el == NULL || n <= 0)
ErrMsg(ER_NULL, "enqueue");
/*
* first sort array el
*/
qsort(el, (size_t) n, sizeof(QUEUE_NODE),
(int CDECL (*)(const void *,const void *)) q->cmp);
/*
* and then merge them with the priority queue q
*/
/*
* find p, the number of elements in el[] that are smaller than
* the first element in the queue, if any.
* (Yes, we expect at least some of them to be closer than q->head)
*/
for (p = n; q->head != NULL && p > 0; p--)
if (q->cmp(&(el[p-1]), &(q->head->el)) <= 0)
break; /* out of this for loop */
/*
* put these p elements in order at the queue head:
*/
for (i = p; i > 0; i--) {
e = get_free(q);
e->el = el[i-1];
e->next = q->head;
q->head = e;
}
q->length += p;
n -= p;
/*
* We might be done by now (n zero).
* Process the remaining elements:
*/
where = q->head; /* starting point for insertion: */
next = where->next; /* the next element */
el += p; /* start of the remaining elements */
for (i = 0; i < n; i++) {
e = get_free(q); /* get a free queue element */
e->el = el[i]; /* copy contents: */
/*
* unless where is the last element, shift a position in the queue
* when the element is larger than the insertion element e:
*/
while (next != NULL && q->cmp(&(e->el), &(next->el)) > 0) {
where = next;
next = where->next;
}
/*
* now next points either to NULL or to the first element smaller
* than or equal to e. So, insert e after where and before next:
*/
e->next = next;
where->next = e;
/*
* the next element in el[] will should follow after e,
* so shift where one position to start looking after e:
*/
where = e;
}
q->length += n;
return;
}
QUEUE_NODE dequeue(QUEUE *q) {
Q_ELEMENT *e;
if (q->length == 0)
ErrMsg(ER_NULL, "cannot dequeue empty queue");
e = q->head; /* get first queue element */
q->head = q->head->next; /* reset first to next */
e->next = q->empty; /* put the dequeued element in the empty queue */
q->empty = e;
q->length--;
return e->el;
}