src/tac-pipe.c

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