   [C++] Reading a Text File line by line, but backwards
  I am writing a Tool on Windows to analyze my logs.I need to iterate on the log Lines starting from the end (most recent) to the top (oldest). The files are huge, so creating an array of Lines in memory and read it in reverse order is out of question.Does STL provide any utility to do this for me, or do I have to write my own low level code using _lseek()?   
Quote:Original post by hiigaraI need to iterate on the log Lines starting from the end (most recent) to the top (oldest).This implies all lines must be read. Storing everything in memory is likely the best option (8 bytes per file offset for 64-bit/infinite sized files). 2GB of memory will handle 250 million lines. Once the file is parsed entirely, use the offsets to read the lines.Quote:Does STL provide any utility to do this for me, or do I have to write my own low level code using _lseek()?If above doesn't work, forward scan can still work with auxiliary storage, still 8 bytes per offset, can be text or binary.Otherwise, use pages. Read 1, 4, 512, 2000 MB, search lines backward, repeat as needed, handle the overlap as needed. Special case where individual line is bigger than buffer must be handled. std::string version will require copying of individual lines, char * can be used as zero alloc version, if line ends are replaced with \0.   ;  If you can't keep it all in memory at once, you'll probably have to write your own code since reading files backwards is atypical and not natively supported (AFAIK).  Memory-mapped I/O, or reading in small chunks/pages, might make the process of scanning backwards for newlines less painful.EDIT:  A double-pass as Antheus suggests would also work :)   ;Quote:Original post by ZipsterEDIT:  A double-pass as Antheus suggests would also work :)It can be tweaked by storing only line lengths, so then one needs much less memory (16 or 32-bit per line). The downside is obviously each line needs to be read twice, and disk is the bottleneck. Plus the huge up-front time, it can be 30+ minutes for first pass.That is assuming the files really are huge aka bigger than directly addressable memory.   ;  You could read backwards by progressively scanning in reverse, looking for line endings (1024 bytes at a time or so). It's a bit of nuisance but would work and with caching you shouldn't see much of a disk access overhead.   ;Quote:Original post by GodBeastXYou could read backwards by progressively scanning in reverse, looking for line endings (1024 bytes at a time or so). It's a bit of nuisance but would work and with caching you shouldn't see much of a disk access overhead.I am gonna go with that. A single pass scanning a block at a time in reverse.I forgot to mention that I don't necessarily need to read all the lines until I reach the beginning. I read the lines as the user steps the frames back in time using a button or a slider. The user will be more likely interested in the bottom of the file rather than the beginning, and therefore a pass just to build an index is unnecessary overhead.   ;  FWIW, text editors commonly read the entire file (try opening a huge file in, say, gVim) at the start even though they only have to display a window's worth at a time.   ;Quote:Original post by Antheusstd::string version will require copying of individual lines, char * can be used as zero alloc version, if line ends are replaced with \0.Can you elaborate on this. I don't follow.I am thinking of reading from the buffer into a string by inserting the pieces of the line in the beginning of the string. So if the line spans several buffers the string will grow as much as necessary.