Im working on a custom edit control now. Its surprisingly less work then first expected, however, i want to move off my 'Crutch' (a fixed memory buffer for text), and implement a more dynamic memory arangement for the edit control's text.

My first guess it to use Heap memory as it is so versitile, and can be expanded (HeapReAlloc). Even though i have never tired to do so. Im actually a little confused on the MSDN explaination of this API. It seems like it wants me to create separate new heap, and use HeapReAlloc to *copy* the old heap over. This to me is not reallocating heap size.. :confused:

Anyways, i thought i would put it forward and ask you professionals what you think is the best solution to store text that is dynamically changing in size and content?
    [*]Heap / HeapReAlloc
    [*]Global/Local Alloc (??)
    [*]Virtual Alloc (??)
    [*]File Mapping (??)
    [*]Combination of the above (??)


    The (??) means i have no clue how it would be effective. :grin:

    Anyways thanks for any/suggestions help you can provide!
    :alright:
    NaN
Posted on 2002-04-29 02:23:59 by NaN
I think it's better to cut the memory into pieces and link them together.
If you use one big memory block, and remove one character, everything behind it (possibly several MBs) have to be shifted..
If you allocate pieces of memory of say 4KB, and you do some simple editting, you only need to change the 4KB memory block, and possibly insert another one before the next one. If you select a big block of text and delete it, you need to figure out which blocks to delete completely, and which partly (2 at most).

However if you will be working with large files displayed in the edit control it may not be a good idea to load the complete file into 4KB blocks :). Maybe you can make a combination by adding special blocks that refer to parts of the file while they are untouched, and as soon as you start editting them, cut out a 4KB piece, put it in a memory block and split the previous special block into 2 parts.

Thomas
Posted on 2002-04-29 02:54:40 by Thomas
Hi NaN

Are you making a RichEdit replacement (text only). That would be great. I would be the first one to give up that buggy richedit.

KetilO
Posted on 2002-04-29 03:41:28 by KetilO
What about OLE string memory? As far as I know, there are no disadvantages using it :confused:
Posted on 2002-04-29 03:51:30 by bazik
Thanks Bazik, this is an interesting idea... i will have to look into it!


More suggestion are still welcome, cause i still dont have a "game plan" laid out yet :rolleyes: , Im looking into Thomas' sugestion at the moment.

Anyways, i have to draw the line and get some sleep.
I've been working on the control for about 7 hours, and developed about 300 lines of code in the control.

Here is where im currently at. Please check it out and report its success on your box's. I'm using no new API's so I dont think there will be any problems.

And ya, back to the point, there is only 512 bytes of "type" to enter, after this you'll get a GPF. So dont get type happy :)

Laslty, i know the Curret doesnt follow with word wrap's, and ther still needs to have scroll bars installed. But its at least on its feet :)

Attachment removed (outdated)

:alright:
NaN
Posted on 2002-04-29 04:06:31 by NaN
Global/LocalAlloc resolve to the exact same location in
kernel32, so it doesn't matter which one you use. Also,
it ends up calling HeapAlloc... so you might as well use
HeapAlloc (you can always write a wrapper if you don't
like the additional parms you need to pass). None of the
resize strategies in HeapRealloc is your problem, it's
handled on levels that make it 100% transparent to you.

VirtualAlloc is not good when you need to realloc, it's
good for large "one-time" block allocations.

I wouldn't use filemapping for generic memory allocation,
it's coupled very tightly with the pagefault handler, the
paging file, and is better for allocating shared memory.

Now, your memory allocation strategy will all depend on
what you are doing. If it's a replacement for the standard
edit control, anything but HeapAlloc would be overkill.
If you're doing an edit control for, say, source editing,
you will have other demands... there's a lot of factors to
consider before planning your memory allocation code.
Posted on 2002-04-29 04:52:28 by f0dder
Originally posted by f0dder ... None of the
resize strategies in HeapRealloc is your problem, it's
handled on levels that make it 100% transparent to you.

Im puzzled. If im understanding you correctly, The heap size will coninously grow if i write outside the current range?? I dont think this is true, cause the current buffer is in the heap and static at 512 bytes. If you write beyond this (i have no check code) you *can* write there, but a GPF ends up when you close. Can you elaborate a bit more on this for me, thanx.

Now, your memory allocation strategy will all depend on
what you are doing. If it's a replacement for the standard
edit control, anything but HeapAlloc would be overkill.
If you're doing an edit control for, say, source editing,
you will have other demands... there's a lot of factors to
consider before planning your memory allocation code.

Well, Its first purpose is a rich edit replacement as KeltIO had assumed. But i will be adding alot of feature i like about Ultra Edit as well, so yes it will be very complex. Idealy i would like to be able to have one pointer to 'flat' bank of memory in the heap, but incertain if this is possible (but your above statements sound promising). I dont care if pages get swapped to the HD either, its to be expected for large files, i just dont want to have to make a 'temp' file in the temp dir untill you save (this will a later feature for backup reasons, not operating reasons).

( ( And i thought the GDI would be the rough stuff :P ) )

Thanx for you advice f0dder ;)
:alright:
NaN
Posted on 2002-04-29 12:40:15 by NaN

If you write beyond this (i have no check code) you *can* write
there, but a GPF ends up when you close. Can you elaborate a bit
more on this for me, thanx.

What I meant was, there's not a great deal of trickery involved
from your side - you can HeapRealloc, get a new pointer, and that's
it. If the block can grow, it grows. If it has to move, it moves.


Idealy i would like to be able to have one pointer to 'flat' bank
of memory in the heap

And have the whole file as one big block? Eeek. Sure, this would make
use of BM scanning or whatever very fast, but that's about the only
use a "one big chunk" memory scheme has. Buffer reallocs will be hell
and fragment the heap insanely, deleting one char from the middle means
moving possibly massive amounts of data around, etc.

Allocation strategies will also depend on what you wanna do. Mainly
view large files? Or edit "typical sourcecode"? Unless you want to
operate on huge files, relatively simple memory allocation can be done.
A linked list of lines has worked pretty well for me, and allows for
quick copy/paste of multiple lines. On first lineedit, I allocate a
buffer a bit longer than required, the typical "delta allocation" (but
no need to do that when loading in the file, as typically not all lines
in a file will be edited). This approach seems to work pretty well for
"normal" textfiles (largest file being the bible, around 4 megs. And yeah,
I only have that lying around for test purposes.)
Posted on 2002-04-29 12:57:44 by f0dder
I dont think this is true, cause the current buffer is in the heap and static at 512 bytes. If you write beyond this (i have no check code) you *can* write there, but a GPF ends up when you close


If you call HeapReAlloc on the buffer and you chose as size bigger then the heap then the heap will be adjusted.
Posted on 2002-04-29 12:58:49 by Kudos
Here's the graphical representation of what I had in mind. I would use blocks of 4KB, linked together (a buffer for one line would do too but I think this is more efficient), then don't use all the bytes in the buffer, leaving some padding so it can be editted..
To limit the memory usage, add references to the original file. As long as part of the text in the control matches a piece of the file, leave it in the file until the users starts editting it.

Thomas
Posted on 2002-04-29 13:39:36 by Thomas
Im puzzled again.

I thought i would spy on the API called that Ultra edit makes for inspiration, and found out that with *every* key stroke, there is two HeapFree calls. However, there is NO HeapAlloc, CreateHeap, HeapReAlloc's being called.

To be honest i find this wierd.. :confused:
Posted on 2002-04-29 13:41:22 by NaN
Wow Thomas, Thats pretty!! :grin: (thanx)

I dont think 4KB blocks would be the best allocations. If I change the a letter 'a' -> 'o' , to correct say spelling, and then continue with out saving, i have 4Kb being reserved for one byte.

Correct 20 spelling mistakes and you can have up to 80kB in reserved page memory :(

I like the line buffer tho, say 256 a line, with a check algo to see if your editing beyond this (where realloc would kick in and give it another 256 block.

So far with f0dders thoughts, and your advice, i think this is the best game plan so far.

However, I do want to do this right, so i will hold a bit for anyone elses thoughts before i get coding happy tonight. :)

Thanx everyone so far!
:alright:
NaN
Posted on 2002-04-29 13:43:08 by NaN
The way I would do it is have each line buffer start with a struct wich contains the address of the previous and next lines and the line length. Each time the user tries to edit a line is it first copied to a temp buffer say 4k and then when the user moves to a different line the origonal buffer is deleted and a new one of the new size is allocated and it's address is added to it's previous and next line's structs to add it to the linked list, this way you don't over allocate.
Posted on 2002-04-29 14:05:16 by Kudos
I dont think 4KB blocks would be the best allocations. If I change the a letter 'a' -> 'o' , to correct say spelling, and then continue with out saving, i have 4Kb being reserved for one byte.


That's not what I meant. When you change the a to o, it will allocate a block of 4KB filled (party, so you have some free space to use for editing) with the data from the file at the editting point. You can edit (modify+adding new chars) this piece without allocating new blocks until you've used up all the padding in the block as well.

Here's a sample scenario, I hope you can follow it. Because it's an example, I used 128 byte data blocks instead of 4096.



In file:
--------------------------------------
This is the first line of text
This is the second line of text
Another line of text (number 3)
4. line
and finally the 5th line of text
--------------------------------------

- Load the file
blocks:
1. [reference to the full file]

- User starts editting the first line.
blocks:
1. [128 byte data block filled with line 1 & 2, padded with zeroes]
"This is the first line of textCRLFThis is the second line of text000000....."
2. [reference to the rest of the file starting at line 3]

- User keeps editing the first line
This can still be done in the first block, as only ~63 bytes are
filled and 128 can be stored. Now the user has exceeded the 128 bytes,
a new block is needed. Spread the existing bytes over the original and
the new block so you still have some padding:
blocks:
1. [128 byte data block filled with 64 bytes]
"This is the first line of teblaadssadsadsadsssasdasdasdsadsadasd" + 64 zero bytes
2. [128 byte data block filled with 64 bytes]
"dsadasdjasdjasdasfefefefefefef||This is the second line of text." + 64 zero bytes
(|| is CRLF)
3. [reference to the rest of the file starting at line 3]

- User edits line 4.
new block organization:
1. [128 byte data block filled with 64 bytes] (unchanged)
2. [128 byte data block filled with 64 bytes] (unchanged)
3. [reference to file, line 3 only]
4. [128 byte data block filled with line 4 + padding]
5. [reference to file, line 5 only]


Thomas
Posted on 2002-04-29 14:14:09 by Thomas
Well i got a linked list going now. And works good.

VKim's debug is a god-send! I wouldnt have gotting it up so fast with out it :)

My strategy is more based on Kudos' thoughts. However, i wrote it such that file mapping that Thomas suggest can be added later. (Which will have to come Somehow when time to load and save memory ~ Still unclear *how* yet).

They system is each line gets a link. And there is a "BUFFER LINE" which is static and never destroyed (until exit), is allocated 4Kb.

If you hit 4K on one line, you deserve the warning message box i give you :)

I prefer line linked lists as it will be more flexible to some other ideas I want to implement as an edit :grin:

So:
    [*]- Cursor is *always* in the line buffer
    [*]- Lines are a linked list (not including the Buffer). Always starts with line #1, Position 0.
    [*]- All Text input goes directly into the buffer
    [*]- Cursor movements (and enter), adjust which link the Buffer will stradle overtop. It modifies temporarily the list to the buffer for display purposes. THis means the link it stradles over is actually cut out. If changes are made, the previous link is destroyed. When the line changes, a new allocation for the edited line is created specifically to the line size and buffer is copied into it, then the buffer is cleared or loaded with the next link. etc. etc. etc.


    Well this is what im doing. Any potential griefs with this?? Feel free to critisize. :)

    This layout it to hopefully balance memory used, and at the same time limit fragmentation. Each line is sized to a min of 64 bytes, but can be any length up to 4Kb. (this includes the 16 byte header for each line).

    Thanx all for your help, thoughts, suggestions. They are appreciated!
    :alright:
    NaN
Posted on 2002-04-29 18:28:57 by NaN
I don't know if this is the most efficient way, but this is how I would try it:

1) Use 256 byte segments to store data, saving the last byte as a length byte. 0 length means the segment is free
2) Allocate blocks from VirtualAlloc in 4 kb blocks giving you 16 segments 256 bytes in length. From what I understand, you could reserve a certain size (say 16MB) without actually grabbing physical pages. This would ensure you could grow the blocks in one continuous "heap"
3) Keep a separate table (through HeapAlloc) of words that track what order the segments go together to make up your file. The table needn't be too big at first, but if the file gets too large, use HeapRealloc to make it bigger.

When you go to edit at a certain position, find the segment that contains that position. Then split it into 2 segments, the first being the text *before* the cursor and the second being the text *after* the cursor. Basically, I would grab a free segment (one with a length byte of 0) and copy the text after the edit position to the new segment and set the length byte. With the original segment, just shorten the length byte appropriately.
When typing, just work with the 256 byte segment that is the bytes before the cursor. I doubt this would lead to too much memory thrashing. And if the user types more than will fit in one segment, just grab another one.
If you find that the a little bit of time goes by without typing you could "defrag" it.

--Chorus
Posted on 2002-04-30 00:23:45 by chorus
Thanx alot chorus, i will think about it as well. If i find the current plan has problems down the road (and not seen at the moment). I might need to scrap what i have :)

As well, here is my two day product. Again im posting it cause i *really* would like to know if it runs ok on NT box's. I had some *issues* with resizing and setting the scroll bars tonight. So i want to make sure they are now sized alright, and the 'dc's on NT machines wont get grumpy. :)


I have to say tho, im quite impressed with the project so far. Its as good a basic edit at the moment (single line). The .obj is curretly 6Kb. Which could easily be reduced when optomized. Im writting *big* to keep the logic more understood. When it all works, i plan to squeeze the air out. :)

Thanx alot.
:alright:
NaN

: Attachment Removed to save space. See further for next update.
Posted on 2002-04-30 04:33:13 by NaN
win2000

I bet you already know that enter/tab/scrolling does not work. It would be easier to test with Ctr-v.



Notice the space, that is what happened when
resizing the window.
Posted on 2002-04-30 05:09:27 by bdjames
It's looking great! :alright:


The .obj is curretly 6Kb...

Don't forget that an object file contains a lot more than just code so the real code size will probably be much less.

Thomas
Posted on 2002-04-30 05:18:11 by Thomas
NaN,
i'm gonna jump in here with a suggestion. If i was you, i would create a private heap for the control to use. The reason for this? As a control, this will often be included into other projects, and those projects may or may not be running inside an IDE and/or debugger. I have experienced lots of GPFs because the IDE i was working with was screwing with the heap of the process, which was making my asm component/dll fall over. As soon as i created a private heap and started using it, the problems disappeared. And nobody will want to use your component if it falls over all the time while debugging :) I thought i would mention this because it is not a problem you are likely to see immediately, as most asm programmers use very basic editor/debugger setups.
Posted on 2002-04-30 06:23:04 by sluggy