The Disk

This is alot to swallow... so only you users who want to know how objects are stored internally read on, otherwise skip the post. Screens needs a place to store its objects. Each object has properties like its name, type, size and so on and its data, however I need a place to store them and I cannot just write them down one after each other in a file. Screens has a stream it creates from a database 'ScrMain.pdb' with the type 'DISK'. This stream is interfaced through the Disk component. The Disk component gives me a file interface to read/write to the database. Why not just use the standard PalmOS functions? Because Screens is designed to have as little as possible dependency points on PalmOS. By using the Disk component which can use any underlying way to store the stream, Screens gets maximum flexability if it is ported to another platform. So the Disk component gives me a stream of bytes which I can read/write to. But its just a stream, how do I store objects on them? Well... If we think about it, each object has a header and data. Because its better to store them in seperate places because the object header is fixed and therefore indexable while the data is sizable and therefore needs some allocation/deallocation method. Screens devides the Disk into fixed Areas. The Area API allows to deal with these fixed areas. Currently Screens splits the Disk stream into two areas: the Object area and the Data area. Each Object header is stored in the Object Area and each data is stored in the Data Area. Lets focus on the Object header at the moment. The object area is stored from the end of the disk stream and backwards. It stores the object headers in a backward fashion (the actual header is forward but indexes backwards) so the first object is aligned to the end of the disk with the second object behind it. The start of the last object header is the end of the object area. The advantage of the area API is that it can store areas forward or backward. Each object header holds various object properties such as its Name and Type which are 128bit identifiers, the data offset (in the data area) and its flags (such as read-only). The size is stored with the actual data. The object header also holds a previous index, next index and depth value. I want to talk about those three values. You all know about node trees where each item in the tree holds its parent pointer, first child pointer, previous sibling and next sibling pointer and the advantage is that the items can be not in order (so new items are added at the end of the list and you can remove items from the middle) and still be fast at enumarating them. However one of the biggest problems with node trees is recursion. If I want to delete an item, I want it to delete all its children and its childrens children and so on, but then I need to use a recursive function (a function which calls itself) to go through and remove each item only after I have removed its children. So I need to dig up/down removing items with no children untill all children are removed. PalmOS has a limited stack, so it cannot handle such recursion. This is one of the reasons there is no VFS function to remove a folder with all its sub folders and files because it would require recursion which PalmOS is just not good at. Which is why I think they did not include a file system design in the first place. Screens solves this by using a hybrid node+depth design. A depth design holds a depth per item so it knows by its depth value who is a parent (the first item before it that has a -1 depth), its children (if the item has children they follow directly with a +1 depth) and its siblings which it can look up/down for items with the same depth (as long as the depth is not lower but can be higher). This solves the recursion since it puts the recursion in the storage design. If you want to remove an item, just delete the item and all following items untill you find an item with the same depth as the item you wanted to remove. So it puts recursion in a single while/for loop. The problem with the depth design is that it relies on the indexes, so if you want to add an item you have to add it at a specific index which means you have to shift everything else downwards. Screens solves this by using a hybrid design so instead of using index+depth, it stores a previous and next pointer (like in a linked list) and a depth. This gives you the advantage of recursion in a single for/while loop and you can insert items freely since they can be added pysically at the end but can insert themselves in the linked list to appear at a certain index. So, we now have all the object headers stored in the object area in the disk in a backward fashion. Now I want to talk about the data area: The data area stores the data of each object which has a 32bit size value so it does not have the PalmOS 64K limit. It stores data one after each other in a linked list fashion. So each data has a data header which holds the size of the data, and its next data header (the previous header is not needed to know). You remove data by just removing its header out of the linked list. When you reach the end of the disk area, it tries to resize the area to cover more of the unused disk area. If it cannot expand because it will overwrite the item area it aligns the data. Aligning data starts from the first data and makes sure it is aligned to the end of the disk header. It then takes the next data and aligns it to the end of the first data and so on untill all data has been aligned. Then it can add new data since all the free space of the data area is at the end. If there is no more free space, Screens can ask the user if it can resize the entire database to a bigger amount. This moves the entire object header to the end of the new resized stream since the object area is always aligned to the end of the disk stream. There you have it. My disk design.