diff options
author | Franklin Wei <frankhwei536@gmail.com> | 2016-11-20 15:16:41 -0500 |
---|---|---|
committer | Franklin Wei <me@fwei.tk> | 2016-12-18 18:13:22 +0100 |
commit | 1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99 (patch) | |
tree | 8e7f2d6b0cbdb5d15c13457b2c3e1de69f598440 /apps/plugins/puzzles/tdq.c | |
parent | 3ee79724f6fb033d50e26ef37b33d3f8cedf0c5b (diff) | |
download | rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.tar.gz rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.zip |
Port of Simon Tatham's Puzzle Collection
Original revision: 5123b1bf68777ffa86e651f178046b26a87cf2d9
MIT Licensed. Some games still crash and others are unplayable due to
issues with controls. Still need a "real" polygon filling algorithm.
Currently builds one plugin per puzzle (about 40 in total, around 100K
each on ARM), but can easily be made to build a single monolithic
overlay (800K or so on ARM).
The following games are at least partially broken for various reasons,
and have been disabled on this commit:
Cube: failed assertion with "Icosahedron" setting
Keen: input issues
Mines: weird stuff happens on target
Palisade: input issues
Solo: input issues, occasional crash on target
Towers: input issues
Undead: input issues
Unequal: input and drawing issues (concave polys)
Untangle: input issues
Features left to do:
- In-game help system
- Figure out the weird bugs
Change-Id: I7c69b6860ab115f973c8d76799502e9bb3d52368
Diffstat (limited to 'apps/plugins/puzzles/tdq.c')
-rw-r--r-- | apps/plugins/puzzles/tdq.c | 88 |
1 files changed, 88 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/tdq.c b/apps/plugins/puzzles/tdq.c new file mode 100644 index 0000000000..43c9c35de5 --- /dev/null +++ b/apps/plugins/puzzles/tdq.c | |||
@@ -0,0 +1,88 @@ | |||
1 | /* | ||
2 | * tdq.c: implement a 'to-do queue', a simple de-duplicating to-do | ||
3 | * list mechanism. | ||
4 | */ | ||
5 | |||
6 | #include "rbassert.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 | |||
29 | struct tdq { | ||
30 | int n; | ||
31 | int *queue; | ||
32 | int ip, op; /* in pointer, out pointer */ | ||
33 | char *flags; | ||
34 | }; | ||
35 | |||
36 | tdq *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, char); | ||
42 | for (i = 0; i < n; i++) { | ||
43 | tdq->queue[i] = 0; | ||
44 | tdq->flags[i] = 0; | ||
45 | } | ||
46 | tdq->n = n; | ||
47 | tdq->ip = tdq->op = 0; | ||
48 | return tdq; | ||
49 | } | ||
50 | |||
51 | void tdq_free(tdq *tdq) | ||
52 | { | ||
53 | sfree(tdq->queue); | ||
54 | sfree(tdq->flags); | ||
55 | sfree(tdq); | ||
56 | } | ||
57 | |||
58 | void 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] = 1; | ||
64 | if (++tdq->ip == tdq->n) | ||
65 | tdq->ip = 0; | ||
66 | } | ||
67 | } | ||
68 | |||
69 | int 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] = 0; | ||
77 | if (++tdq->op == tdq->n) | ||
78 | tdq->op = 0; | ||
79 | |||
80 | return ret; | ||
81 | } | ||
82 | |||
83 | void tdq_fill(tdq *tdq) | ||
84 | { | ||
85 | int i; | ||
86 | for (i = 0; i < tdq->n; i++) | ||
87 | tdq_add(tdq, i); | ||
88 | } | ||