home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / editors / 2031 < prev    next >
Encoding:
Text File  |  1992-08-19  |  3.4 KB  |  67 lines

  1. Newsgroups: comp.editors
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!mips!darwin.sura.net!zaphod.mps.ohio-state.edu!think.com!news.bbn.com!noc.near.net!wpi.WPI.EDU!rcarter
  3. From: rcarter@wpi.WPI.EDU (Randolph Carter <Joseph H. Allen>)
  4. Subject: Re: Q: Line # addressing using buffer gap.
  5. Message-ID: <Bt8o8E.A5q@wpi.WPI.EDU>
  6. Keywords: Finseth, Craft, Of, Text, Editing, buffer, gap
  7. Sender: news@wpi.WPI.EDU (USENET News System)
  8. Nntp-Posting-Host: wpi.wpi.edu
  9. Organization: Worcester Polytechnic Institute
  10. References: <1992Aug18.132755.25619@mks.com>
  11. Date: Wed, 19 Aug 1992 16:24:14 GMT
  12. Lines: 53
  13.  
  14. ant@mks.com (Anthony Howe) writes:
  15. >
  16. >Is there a reasonably fast technique, given a Buffer Gap structure,
  17. >for finding line number X.  Currently, AE, just performs linear scans
  18. >for <newline> marks when performing cursor motion, since the
  19. >assumption is that the majority of movement is localized.
  20.  
  21. Here's a cute idea: change the LFs to CR-LF sequences.  Then you only need
  22. to look at each other character to find the line ends and the search is
  23. twice as fast. 
  24.  
  25. Or change the lines to <length><chars> sequences.  Perhaps make <length>
  26. variable length so it doesn't waste so much space.  The search is then, say,
  27. 30 times as fast.
  28.  
  29. >Being able to find the start of a line quickly would help in
  30. >implementing a Goto-Line command and possibly a better screen update
  31. >manager.
  32.  
  33. I've found that the linear search is not so bad for the Goto-Line command,
  34. but maybe if your going to add the full set of vi commands it will become
  35. more important.
  36.  
  37. I don't know how your screen update/generation algorithm works, but you can
  38. probably eliminate having to do a full screen generation on the simplest,
  39. but most often used commands.  For example, prevent a full screen generation
  40. when you type in characters and when you backspace.  When I added this to
  41. joe, it changed the amount of CPU time it used from being close to that for
  42. emacs to close to that for vi (and emacs does this optimization as well).
  43. Also a hint with curses: if you make a one character change on one place on
  44. the screen then curses does almost no work.  But if you make a one character
  45. change on two places then curses checks all the characters between those two
  46. places.
  47.  
  48. >I think I read somewhere about the idea of keeping a table of buffer
  49. >indexes that correspond to each line.  Then as you insert or delete
  50. >characters in a given line, all the indexes above line X would need to
  51. >be updated.  This idea strikes me as being very ugly since the time to
  52. >update the indexes is dependant on which line you are currently at.
  53. >If you were at the end of the file, this would be very quick, but if
  54. >you were at the beginning of the file, this time maybe unacceptable
  55. >for large files.
  56.  
  57. Don't store the line addresses, store the line lengths in the buffer.  This
  58. way you don't have to update anything (but you still have to read through
  59. the buffer sequencially to accumulate the line address).  Actually you could
  60. store the line lengths in a buffer gap and maintain both at the same time,
  61. I.E., to eliminate copying in the table when you insert or delete a line.  
  62. -- 
  63. /*  rcarter@wpi.wpi.edu */      /* Amazing */             /* Joseph H. Allen */
  64. int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
  65. +r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
  66. ]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}
  67.