fsrw question - character insertion
CassLan
Posts: 586
Silly question,
Is it possible to write/overwrite an existing byte of a file, or is appending to the end the only option at this point?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
NYC Area Prop Club
Prop Forum Search (Via Google)
·
Is it possible to write/overwrite an existing byte of a file, or is appending to the end the only option at this point?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
NYC Area Prop Club
Prop Forum Search (Via Google)
·
Comments
They could be added. Doing it correctly, complying with POSIX specs or else adopting a consistent
and workable API would be tricky but certainly doable. But it needs to be designed carefully.
In particular, the "+" modes interact with seek in a nontrivial way.
In the 24 version, is the seek still only usable on small files?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
NYC Area Prop Club
Prop Forum Search (Via Google)
·
Maybe you missed my virtual memory thread:
http://forums.parallax.com/forums/default.aspx?f=25&m=401244&g=401357#m401357
I have been Prop AWAL for a couple of months. I did miss this post. I will investigate.
Its really a grand idea : )
Rick
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
NYC Area Prop Club
Prop Forum Search (Via Google)
·
Originally, I was pretty close, that being a design where the entire original file in taken in by a buffer that would reside on the prop, but of course that is not large, and with my·goal of being able to edit spin programs on the prop itself, it became clear that there was simply not enough space unless it was going to be a hobbled 5k limit of a file.
So, the next step was to use the SD card as a means to make up for that...this took me in many directions...from creating a changelog file which would be applied to the original file only upon saving.. while showing a "mockup" of the file with changes made onscreen....to trying to edit the original file in real time character by character...lol.· Needless to say its been a hard nut for me to crack.
I have taken a break and I'm back with renewed vigor
What I would like to do is treat the Virual Memory as a large buffer (3mb?) that I can move blocks of data, as well as bytes.
I will have a good look at it now, I haven't had the chance yet.
Rick
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
NYC Area Prop Club
Prop Forum Search (Via Google)
·
Adding seek for writes shouldn't be too problematic.
I did get the 80 column, color, 8x8 driver done. I'll get a 1.0 release done here in the very near future.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness!
Chat in real time with other Propellerheads on IRC #propeller @ freenode.net
Safety Tip: Life is as good as YOU think it is!
I have a swap.sys which is 256MB ... no problem.
Here are some ideas:
Virtual memory is sector driven. You can't copy data into virtual memory or out of memory when you cross the 512 byte boundary. You have to take care of that by yourself, otherwise the virtual memory would be slower. I do not like the idea to make it idiot-safe on cost of performance. So, the ideas for your editor would be to store the file in vMem line by line having a fixed maximum line length of 128-1 bytes (-1 for line-end or better line length). So you can have 4 lines per sector max. BUT .. during initial load of a text file to vMem·you'd only put 2 lines into one sector. That easyly allows to insert lines by rearranging this one sector only.
Inserting/deleting characters in a line is easy this way as your buffer is always big enought to hold the 127 characters without moving the following lines.
What would be helpful for you is having 2 independent virtual memories. So, one could be your working buffer, The other one is for reading bigger portions and for reading when doing copy-jobs.
When a sector is full you need a routine to split it. Therefore it would be helpful to have a linked list of sectors that give you the sector numbers in the order of the linenumbers. This way it's easier to insert lines without affecting the whole buffer after that line. Say you insert 2 lines to an initialy read file like described above (2 lines per sector). No problem so far. Now you insert another one. Instead of copying maybe a huge amount of bytes one line down, you simply take the first free sektor at the end and change the links in the linked list.
Hope I wrote down my thoughts clear enough. Otherwise ask.
Post Edited (MagIO2) : 12/2/2009 9:51:06 PM GMT
I'm sure your ideas are clear, and I *kind-of* understand what your saying..but I'm not too clear on what sector behaviour would be..umm I think a sector is a larger chunk break down of the way a hard drive/SD card is mapped out?
Could you perhaps suggest an arcticle or something that explains sectors a bit better for this type of application?
potatohead:
I'm not giving up man, its going to be a reality [noparse]:)[/noparse]
OBC contributed a Prop DIP for this thing [noparse]:)[/noparse]
80 Columns!! If there is a thread about this already I missed it can you point it out? maybe a screen shot?
rokicki:
Hmmm, I was under the impression that once you left the sector cluster (there it is again
Rick
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
NYC Area Prop Club
Prop Forum Search (Via Google)
·
One SD card sector has 512 bytes. That's it!
So, one sector has an adress range from $000 to $1ff. The virtual memory adress·has 2 parts. First part are the 9 least significant bits which is the adress inside of a loaded sector. All bits above are so to say the sector number shifted to the left by 9 bits.
So, let's say you want to copy a string to virtual adress 500 it should not be longer than 11 bytes otherwise the copy will overwrite memory that no longer is part of the buffer where the sector is kept. But when one line is limited to 128 bytes, then you will never have this problem. As the start adresses are fixed to be $00, $80, $100, $180 inside of a sector. (128 divides 512 without rest). So, if you copy a full line (128 bytes) to $180 you won't cross the boundary.
Additional suggestions:
A limit to 5000 line is by far more than we need ... maybe 2000 or 1000 ... hmmm ... this is what I would keep in HUB-RAM as an array of words. 1000 lines loaded into vMem like described above (2 lines per sector) means that we need 500 sectors. So you can live with 256kB swap-file. ... hmmm ... sounds like you can support multiple files open at the same time easyly.
What you need first are some functions to maintain the line adress list. DeleteLine, InsertLine.
Then you need functions to maintain the line buffers in vMem. DeleteLine, UpdateLine, InsertLine, CopyLine, PasteLine AND SplitSector.
If your program is in line 10 of the file and you want to delete the line, it looks up in the line adress list at which vMem-adress this line can be found. Then it deletes the 128 bytes from this adress and deletes the entry of that line in the line adress list.
If you update a line it's only a lookup and copy the new content.
Insert at the end of the file is easy as that. Get the adress of the last line. Is it already occupied by 2 lines go to the next free sector. Copy the line to the vMem and add it's adress in the line adress list.
Moving lines means to update the line adress buffer only.
Most difficult case is the insert in the middle. First you can use the not used lines in a sector - still easy. With the 3rd insert it starts to get interesting as the sector is already full. That's what the SplitSector function is needed for. It gets the next free sector and copies some lines from the old sector into the new one plus the one that has to be inserted (and of course maintains the adresses of all touched lines in the list).
Post Edited (MagIO2) : 12/2/2009 10:49:44 PM GMT
The new version works great for any size, no restrictions, you can seek and read anywhere.
Read my message in your original thread about the holey buffer; it's a very neat trick and very elegant,
and made just for editors. It handles insert, delete, and arbitrary motions very nicely.
The key thing is we keep the big ends of the buffer on disk, one file for the beginning and the other for the
end (and the end in stored in reverse-sector-order) along with pointers indicating how many bytes of each
file are valid. This plus the in-memory contents means that we can do seek throughout, do random inserts
and deletes, and everything goes very fast, and it's a *very* simple data structure, so very little code.
I threatened to prototype this code before; maybe I'll do it soon.
Simplest implementation is something along the lines of splitting the file as follows:
A = [noparse][[/noparse]In prefix file, always a multiple of 512 bytes]
B = [noparse][[/noparse]In memory at start of gap buffer]
[noparse][[/noparse]cursor]
C = [noparse][[/noparse]gap]
D = [noparse][[/noparse]In memory at end of gap buffer]
E = [noparse][[/noparse]In suffix file, in reverse order; always a multiple of 512 bytes]
The total size of the file is always A+B+D+E. The total size of the memory buffer is always
B+C+D. As you insert a single character, B grows by one and C shrinks by one. If your
gap gets to be zero, you flush data from B to A or from D to E. If the user moves the cursor,
data moves from D to B or B to D (the gap moves). If the user moves the cursor out of the
memory buffer, say in the forward direction, text flows from B to A and then from E to D.
The fact that A and E are always full sectors means maintaining sector "alignment" is trivial.
You can make the in-memory buffer as large or practically as small as you want. If you have
a maximum line size, and you maintain B and D greater than that line size, you are always
guaranteed to have a full line in B and D. Etc.
Nice huh? Took long enough though. No worries on the editor, you had this as an excuse for the whole time!
Need to add stuff to my signature.
http://forums.parallax.com/showthread.php?p=840574
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness!
Chat in real time with other Propellerheads on IRC #propeller @ freenode.net
Safety Tip: Life is as good as YOU think it is!
Thank you both very much for those detailed answers, I understand what both of you are saying.
Will try to put some of these ideas to use.
Rick
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
NYC Area Prop Club
Prop Forum Search (Via Google)
·
Nice to see you active in the forums again. (and the Prop!) I had hoped we hadn't
scared you off with impossible requests! [noparse]:)[/noparse]
Your work on the PrEditor is appreciated!
OBC
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
New to the Propeller?
Visit the: The Propeller Pages @ Warranty Void.
Pretty much says what rokicki said.
http://en.wikipedia.org/wiki/Gap_buffer
And this is a book all about how to make a text editor and various ways to do it:
http://www.finseth.com/craft/index.php
Jeff, its good to be back [noparse]:)[/noparse]
Rick
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
NYC Area Prop Club
Prop Forum Search (Via Google)
·
The gap buffer idea sounds perfect, and is essentially what we were hashing out with Chip that evening. No pressure here, BTW. If it happens, it happens!
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness!
Chat in real time with other Propellerheads on IRC #propeller @ freenode.net
Safety Tip: Life is as good as YOU think it is!
I'm wrting some code that will take a text file, and a given point value (cursor location within file) split the file into A,B,C,D,E as you posted earlier.
Where A and E are temp files on SD, BCD are byte arrays on the prop.
then I will write some code to put all those pieces back together, hopefully the end result will be·an exact match of the original file [noparse]:)[/noparse]
I'm not really sure what would be in C....
As I see it, since the cursor is always inbewteen B and D, and those are easily maniplulated, no real reason for C, unless its meant not as another array, but a way to visualize the setup.
Thanks,
Rick
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
NYC Area Prop Club
Prop Forum Search (Via Google)
·