4 files changed, 289 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..4e8c820
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,6 @@
+CC?=gcc
+CFLAGS=-Os
+LDFLAGS=-s
+
+el: el.c mystdlib.c mystdlib.h
+        $(CC) -o el el.c mystdlib.c $(CFLAGS) $(LDFLAGS)
diff --git a/el.c b/el.c
new file mode 100644
index 0000000..a1994b6
--- /dev/null
+++ b/el.c
@@ -0,0 +1,195 @@
+/* Extract Lines
+   Usage: echo -x 10 2 7 100 | el data.txt
+   extracts lines 16, 2, 7, 256 from the file data.txt
+*/
+
+#include <stdlib.h>
+#include "mystdlib.h"
+#include <unistd.h>
+
+// Our index into the already scanned lines.
+// memory buffer is estimated to 1/32th of the
+// indexed file's size, meaning each line
+// containing approx 31 letters. If it hits the
+// top, we increase in 1/32th steps
+static unsigned char **index = NULL;
+
+// this denotes the number of fields, NOT the
+// memory occupied (would be a size_t, then!!!)
+static long indexsize = 0;
+
+// this specifies, how many lines have been indexed
+// already, scanning always only happens to the
+// last reqeusted line
+static long indexfilled = 1;
+
+// If set, the stream of linenums specified calls
+// the first line number 0... *shiver*
+static int zerobased = 0;
+
+// This tells us, whether we need to scan for hex
+// line numbers
+static char *g_scanfmodifier = "%i";
+
+// scans the text file for the requested line
+// returns NULL, if line exceeds file's end
+// Note: we will not extend the index too early
+// to prevent huge numbers from stdin to steal our
+// memory
+
+static unsigned char * scanforline( MAP file, const long lineno, long *size ) {
+  unsigned char *scanline, *const e_o_f = file->addr + file->size;
+  static int alllinesscanned = 0;
+  *size = 0;
+
+  // lines start at 1
+  if( lineno < 1 ) return NULL;
+
+  // lines we already found can simply be returned
+  if( lineno < indexfilled ) {
+    *size = index[lineno] - index[lineno-1];
+    return index[lineno-1];
+  }
+
+  // if alllines were scanned, were either on
+  // or behind last line
+  if( alllinesscanned ) {
+    if( lineno == indexfilled ) {
+      *size = e_o_f - index[lineno-1];
+      return index[lineno-1];
+      }
+    return NULL;
+  }
+
+  // exploring undiscovered land...
+  scanline = index[indexfilled-1];
+
+  while( indexfilled <= lineno ) {
+    // scan for next line
+    while( ( scanline < e_o_f ) && ( *scanline++ != '\n' ));
+
+    // store pointer
+    if( scanline == e_o_f ) {
+      alllinesscanned = 1;
+      if( indexfilled == lineno ) {
+        *size = e_o_f - index[lineno-1];
+        return index[lineno-1];
+      } else
+        return NULL;
+    }
+
+    index[indexfilled++] = scanline;
+
+    // reallocate some memory
+    if( indexfilled == indexsize ) {
+      unsigned char ** newblock = (unsigned char**) realloc( index, sizeof(char *) * ( indexsize + file->size / 32 ) );
+      if( !newblock ) {
+        fputs( "Could not allocate memory, exiting.\n", stderr);
+        // unmap file and zero pointer
+        unmap_file( &file );
+        exit ( 1 );
+      }
+      indexsize += file->size / 32;
+      index = newblock;
+    }
+  
+  }
+
+  *size = index[lineno] - index[lineno-1];
+  return index[lineno-1];
+}
+
+// Reads all characters up to the next white space
+// from stdin, eof is treated as a white space
+// If more than 13 characters without white space
+// occur, we assume a too large line number and return
+// 0 which is an invalid line (these start at 1) and will
+// result in an empty line being printed
+
+// Rationale:
+// Since we wont support linenos greater 2^31 and this
+// is 12 characters + leading 0 in octal, we stop parsing
+// after 13 characters (technically, 001 is 01, but
+// constructing such strings to annoy parser writers must
+// be punished
+
+static int acquire_lineno( int c ) {
+  char input[15];
+  int inputindex = 0, lineno;
+
+  while ( (c != EOF) && !isspace(c)) {
+    if( inputindex < 14 )
+      input[inputindex++] = (char)c;
+    c = getchar();
+  }
+
+  if( inputindex == 14 )
+    return 0;
+
+  input[inputindex] = 0;
+
+  // Try to read 
+  if( sscanf( input, g_scanfmodifier, &lineno ) != 1 )
+    return 0;
+
+  return lineno + zerobased;
+}
+
+static void usage() {
+  fputs( "Usage: el [-0xh] filename < filenums\n", stderr);
+}
+
+int main( int argc, char **argv ) {
+  // Our handle to the mapped text file
+  MAP textfile = NULL;
+  int c;
+
+  while ((c = getopt(argc, argv, ":0x")) != -1) {
+    switch (c) {
+      case '0':
+        zerobased = 1;
+        break;
+      case 'x':
+        g_scanfmodifier = "%x";
+        break;
+      case 'h':
+      case '?':
+      default:
+        usage();
+        exit(1);
+    }
+  }
+  argc -= optind;
+  argv += optind;
+
+  if( argc != 1 ) { usage(); exit(1); }
+
+  // Map text file read only
+  if( (textfile = map_file( argv[0], 1 )) == NULL ) exit(1);
+
+  indexsize = textfile->size < 32 ? 32 : textfile->size / 32;
+  if( (index = malloc( sizeof(char *) * indexsize )) == NULL ) {
+    fputs( "Could not allocate memory, exiting.\n", stderr);
+    // unmap file and zero pointer
+    unmap_file( &textfile );
+    exit ( 1 );
+ }
+
+  // First line starts at begin of file.
+  index[0] = textfile->addr;
+
+  while( (c = getchar()) != EOF ) {
+    //         get linenumber, pass on eof test char
+    long slen, lineno = acquire_lineno(c);
+    unsigned char *line = scanforline( textfile, lineno, &slen );
+
+    if( line && slen )
+      fwrite( line, slen, 1, stdout );
+    else
+      putchar('\n');
+  }
+
+  // unmap file and zero pointer
+  unmap_file( &textfile );
+  return 0;
+}
diff --git a/mystdlib.c b/mystdlib.c
new file mode 100644
index 0000000..b53beca
--- /dev/null
+++ b/mystdlib.c
@@ -0,0 +1,56 @@
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/mman.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "mystdlib.h"
+
+MAP map_file( char *filename, int readonly )
+{
+  struct stat fstatus;
+  MAP    map = (MAP)malloc( sizeof( *map ));
+
+  if( map )
+  {
+    memset( map, 0, sizeof( *map ));
+
+    if( ( map->fh = open( filename, readonly ? O_RDONLY : O_RDWR ) ) >= 0 )
+    {
+      fstat( map->fh, &fstatus );
+      if( ( map->addr = mmap( NULL, map->size = (size_t)fstatus.st_size,
+         PROT_READ | ( readonly ? 0 : PROT_WRITE), (readonly ? 0 : MAP_SHARED), map->fh, 0) ) == MAP_FAILED )
+      {
+        fprintf( stderr, "Mapping file '%s' failed\n", filename );
+        close( map->fh ); free( map ); map = NULL;
+      }
+    } else {
+      fprintf( stderr, "Couldn't open file: '%s'\n", filename );
+      free( map ); map = NULL;
+    }
+  } else {
+    fputs( "Couldn't allocate memory", stderr );
+  }
+
+  return map;
+}
+
+void unmap_file ( MAP *pMap )
+{
+  if( !pMap || !*pMap ) return;
+  munmap( (*pMap)->addr, (*pMap)->size);
+  close( (*pMap)->fh);
+  free( *pMap ); *pMap = NULL;
+}
+
+int getfilesize( int fd, unsigned long *size)
+{
+  struct stat sb;
+  int ret;
+  if( fstat( fd, &sb )) return -1;
+  *size = sb.st_size;
+  return 0;
+}
diff --git a/mystdlib.h b/mystdlib.h
new file mode 100644
index 0000000..2e9499f
--- /dev/null
+++ b/mystdlib.h
@@ -0,0 +1,32 @@
+#include <sys/types.h>
+#include <stdio.h>
+
+typedef struct { int fh; unsigned char *addr; size_t size; } *MAP;
+
+/* Mapps a file into memory
+   returns pointer to the mapping struct,
+   containing the file's size, the mapped
+   address and its file handle.
+
+   If readonly is true, the file will be
+   opened and mapped read only. File is
+   opened and mapped writable, if false.
+
+   Returns NULL if memory could not be
+   allocated, file could not be opened or
+   mapped. Gives out an diagnostic message
+   on stderr
+*/
+MAP map_file( char *filename, int readonly );
+
+/* Unmapps a file from memory. NULL pointer
+   checks are being done, so this is safe
+   to be called from cleanup without knowing
+   whether there actually is a map.
+*/
+void unmap_file ( MAP *pMap );
+
+/* Gets file size of open file
+   returns != 0 in case of error */
+inline int getfilesize( int fd, unsigned long *size );
+