1 /* tac from a pipe.
2
3 Copyright (C) 1997-2023 Free Software Foundation, Inc.
4
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 /* FIXME */
19 #include "assure.h"
20
21 /* FIXME: this is small for testing */
22 #define BUFFER_SIZE (8)
23
24 #define LEN(X, I) ((X)->p[(I)].one_past_end - (X)->p[(I)].start)
25 #define EMPTY(X) ((X)->n_bufs == 1 && LEN (X, 0) == 0)
26
27 #define ONE_PAST_END(X, I) ((X)->p[(I)].one_past_end)
28
29 struct Line_ptr
30 {
31 size_t i;
32 char *ptr;
33 };
34 typedef struct Line_ptr Line_ptr;
35
36 struct B_pair
37 {
38 char *start;
39 char *one_past_end;
40 };
41
42 struct Buf
43 {
44 size_t n_bufs;
45 struct obstack obs;
46 struct B_pair *p;
47 };
48 typedef struct Buf Buf;
49
50 static bool
51 buf_init_from_stdin (Buf *x, char eol_byte)
52 {
53 bool last_byte_is_eol_byte = true;
54 bool ok = true;
55
56 #define OBS (&(x->obs))
57 obstack_init (OBS);
58
59 while (true)
60 {
61 char *buf = (char *) malloc (BUFFER_SIZE);
62 size_t bytes_read;
63
64 if (buf == nullptr)
65 {
66 /* Fall back on the code that relies on a temporary file.
67 Write all buffers to that file and free them. */
68 /* FIXME */
69 ok = false;
70 break;
71 }
72 bytes_read = full_read (STDIN_FILENO, buf, BUFFER_SIZE);
73 if (bytes_read != buffer_size && errno != 0)
74 error (EXIT_FAILURE, errno, _("read error"));
75
76 {
77 struct B_pair bp;
78 bp.start = buf;
79 bp.one_past_end = buf + bytes_read;
80 obstack_grow (OBS, &bp, sizeof (bp));
81 }
82
83 if (bytes_read != 0)
84 last_byte_is_eol_byte = (buf[bytes_read - 1] == eol_byte);
85
86 if (bytes_read < BUFFER_SIZE)
87 break;
88 }
89
90 if (ok)
91 {
92 /* If the file was non-empty and lacked an EOL_BYTE at its end,
93 then add a buffer containing just that one byte. */
94 if (!last_byte_is_eol_byte)
95 {
96 char *buf = malloc (1);
97 if (buf == nullptr)
98 {
99 /* FIXME: just like above */
100 ok = false;
101 }
102 else
103 {
104 struct B_pair bp;
105 *buf = eol_byte;
106 bp.start = buf;
107 bp.one_past_end = buf + 1;
108 obstack_grow (OBS, &bp, sizeof (bp));
109 }
110 }
111 }
112
113 x->n_bufs = obstack_object_size (OBS) / sizeof (x->p[0]);
114 x->p = (struct B_pair *) obstack_finish (OBS);
115
116 /* If there are two or more buffers and the last buffer is empty,
117 then free the last one and decrement the buffer count. */
118 if (x->n_bufs >= 2
119 && x->p[x->n_bufs - 1].start == x->p[x->n_bufs - 1].one_past_end)
120 free (x->p[--(x->n_bufs)].start);
121
122 return ok;
123 }
124
125 static void
126 buf_free (Buf *x)
127 {
128 for (size_t i = 0; i < x->n_bufs; i++)
129 free (x->p[i].start);
130 obstack_free (OBS, nullptr);
131 }
132
133 Line_ptr
134 line_ptr_decrement (const Buf *x, const Line_ptr *lp)
135 {
136 Line_ptr lp_new;
137
138 if (lp->ptr > x->p[lp->i].start)
139 {
140 lp_new.i = lp->i;
141 lp_new.ptr = lp->ptr - 1;
142 }
143 else
144 {
145 affirm (lp->i > 0);
146 lp_new.i = lp->i - 1;
147 lp_new.ptr = ONE_PAST_END (x, lp->i - 1) - 1;
148 }
149 return lp_new;
150 }
151
152 Line_ptr
153 line_ptr_increment (const Buf *x, const Line_ptr *lp)
154 {
155 Line_ptr lp_new;
156
157 affirm (lp->ptr <= ONE_PAST_END (x, lp->i) - 1);
158 if (lp->ptr < ONE_PAST_END (x, lp->i) - 1)
159 {
160 lp_new.i = lp->i;
161 lp_new.ptr = lp->ptr + 1;
162 }
163 else
164 {
165 affirm (lp->i < x->n_bufs - 1);
166 lp_new.i = lp->i + 1;
167 lp_new.ptr = x->p[lp->i + 1].start;
168 }
169 return lp_new;
170 }
171
172 static bool
173 find_bol (const Buf *x,
174 const Line_ptr *last_bol, Line_ptr *new_bol, char eol_byte)
175 {
176 size_t i;
177 Line_ptr tmp;
178 char *last_bol_ptr;
179
180 if (last_bol->ptr == x->p[0].start)
181 return false;
182
183 tmp = line_ptr_decrement (x, last_bol);
184 last_bol_ptr = tmp.ptr;
185 i = tmp.i;
186 while (true)
187 {
188 char *nl = memrchr (x->p[i].start, last_bol_ptr, eol_byte);
189 if (nl)
190 {
191 Line_ptr nl_pos;
192 nl_pos.i = i;
193 nl_pos.ptr = nl;
194 *new_bol = line_ptr_increment (x, &nl_pos);
195 return true;
196 }
197
198 if (i == 0)
199 break;
200
201 --i;
202 last_bol_ptr = ONE_PAST_END (x, i);
203 }
204
205 /* If last_bol->ptr didn't point at the first byte of X, then reaching
206 this point means that we're about to return the line that is at the
207 beginning of X. */
208 if (last_bol->ptr != x->p[0].start)
209 {
210 new_bol->i = 0;
211 new_bol->ptr = x->p[0].start;
212 return true;
213 }
214
215 return false;
216 }
217
218 static void
219 print_line (FILE *out_stream, const Buf *x,
220 const Line_ptr *bol, const Line_ptr *bol_next)
221 {
222 for (size_t i = bol->i; i <= bol_next->i; i++)
223 {
224 char *a = (i == bol->i ? bol->ptr : x->p[i].start);
225 char *b = (i == bol_next->i ? bol_next->ptr : ONE_PAST_END (x, i));
226 fwrite (a, 1, b - a, out_stream);
227 }
228 }
229
230 static bool
231 tac_mem ()
232 {
233 Buf x;
234 Line_ptr bol;
235 char eol_byte = '\n';
236
237 if (! buf_init_from_stdin (&x, eol_byte))
238 {
239 buf_free (&x);
240 return false;
241 }
242
243 /* Special case the empty file. */
244 if (EMPTY (&x))
245 return true;
246
247 /* Initially, point at one past the last byte of the file. */
248 bol.i = x.n_bufs - 1;
249 bol.ptr = ONE_PAST_END (&x, bol.i);
250
251 while (true)
252 {
253 Line_ptr new_bol;
254 if (! find_bol (&x, &bol, &new_bol, eol_byte))
255 break;
256 print_line (stdout, &x, &new_bol, &bol);
257 bol = new_bol;
258 }
259 return true;
260 }