tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * tdq.c: implement a 'to-do queue', a simple de-duplicating to-do
3 * list mechanism.
4 */
5
6#include <assert.h>
7
8#include "puzzles.h"
9
10/*
11 * Implementation: a tdq consists of a circular buffer of size n
12 * storing the integers currently in the queue, plus an array of n
13 * booleans indicating whether each integer is already there.
14 *
15 * Using a circular buffer of size n to store between 0 and n items
16 * inclusive has an obvious failure mode: if the input and output
17 * pointers are the same, how do you know whether that means the
18 * buffer is full or empty?
19 *
20 * In this application we have a simple way to tell: in the former
21 * case, the flags array is all 1s, and in the latter case it's all
22 * 0s. So we could spot that case and check, say, flags[0].
23 *
24 * However, it's even easier to simply determine whether the queue is
25 * non-empty by testing flags[buffer[op]] - that way we don't even
26 * _have_ to compare ip against op.
27 */
28
29struct tdq {
30 int n;
31 int *queue;
32 int ip, op; /* in pointer, out pointer */
33 bool *flags;
34};
35
36tdq *tdq_new(int n)
37{
38 int i;
39 tdq *tdq = snew(struct tdq);
40 tdq->queue = snewn(n, int);
41 tdq->flags = snewn(n, bool);
42 for (i = 0; i < n; i++) {
43 tdq->queue[i] = 0;
44 tdq->flags[i] = false;
45 }
46 tdq->n = n;
47 tdq->ip = tdq->op = 0;
48 return tdq;
49}
50
51void tdq_free(tdq *tdq)
52{
53 sfree(tdq->queue);
54 sfree(tdq->flags);
55 sfree(tdq);
56}
57
58void tdq_add(tdq *tdq, int k)
59{
60 assert((unsigned)k < (unsigned)tdq->n);
61 if (!tdq->flags[k]) {
62 tdq->queue[tdq->ip] = k;
63 tdq->flags[k] = true;
64 if (++tdq->ip == tdq->n)
65 tdq->ip = 0;
66 }
67}
68
69int tdq_remove(tdq *tdq)
70{
71 int ret = tdq->queue[tdq->op];
72
73 if (!tdq->flags[ret])
74 return -1;
75
76 tdq->flags[ret] = false;
77 if (++tdq->op == tdq->n)
78 tdq->op = 0;
79
80 return ret;
81}
82
83void tdq_fill(tdq *tdq)
84{
85 int i;
86 for (i = 0; i < tdq->n; i++)
87 tdq_add(tdq, i);
88}