103 lines
1.4 KiB
C
103 lines
1.4 KiB
C
/* SPDX-License-Identifier: 0BSD */
|
|
|
|
#include <assert.h>
|
|
#include <stdlib.h>
|
|
|
|
#include "reconque.h"
|
|
|
|
struct reconque {
|
|
struct reconque *old; /* queue we're in the process of replacing */
|
|
size_t slots; /* total number of slots in `data[]` */
|
|
size_t used; /* number of used slots in `data[]` */
|
|
size_t head; /* where `rcq_pop` reads */
|
|
size_t tail; /* where `rcq_push` writes */
|
|
void *data[];
|
|
};
|
|
|
|
struct reconque *
|
|
rcq_alloc(size_t slots)
|
|
{
|
|
assert(slots > 0);
|
|
|
|
struct reconque *q = RCQ_MALLOC(sizeof(*q) + slots * sizeof(*q->data));
|
|
if (!q) {
|
|
return NULL;
|
|
}
|
|
|
|
q->old = NULL;
|
|
q->slots = slots;
|
|
q->used = q->head = q->tail = 0;
|
|
|
|
return q;
|
|
}
|
|
|
|
struct reconque *
|
|
rcq_recon(size_t slots, struct reconque *old)
|
|
{
|
|
assert(slots > 0);
|
|
assert(old);
|
|
|
|
struct reconque *q = rcq_alloc(slots);
|
|
if (!q) {
|
|
return NULL;
|
|
}
|
|
|
|
q->old = old;
|
|
|
|
return q;
|
|
}
|
|
|
|
void
|
|
rcq_free(struct reconque *q)
|
|
{
|
|
assert(q);
|
|
|
|
if (q->old) {
|
|
rcq_free(q->old);
|
|
}
|
|
|
|
RCQ_FREE(q);
|
|
}
|
|
|
|
int
|
|
rcq_push(struct reconque *q, void *item)
|
|
{
|
|
assert(q);
|
|
|
|
if (q->used >= q->slots) {
|
|
return -1; /* full */
|
|
}
|
|
|
|
q->data[q->tail] = item;
|
|
q->tail = (q->tail + 1) % q->slots;
|
|
q->used++;
|
|
|
|
return 0;
|
|
}
|
|
|
|
void *
|
|
rcq_pop(struct reconque *q)
|
|
{
|
|
assert(q);
|
|
|
|
if (q->old) {
|
|
void *item = rcq_pop(q->old);
|
|
if (item) {
|
|
return item;
|
|
}
|
|
|
|
rcq_free(q->old);
|
|
q->old = NULL;
|
|
}
|
|
|
|
if (q->used == 0) {
|
|
return NULL;
|
|
}
|
|
|
|
void *item = q->data[q->head];
|
|
q->head = (q->head + 1) % q->slots;
|
|
q->used--;
|
|
|
|
return item;
|
|
}
|