Thread: Reiventing the wheel (again)

  1. #1
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654

    Reiventing the wheel (again)

    OK, so I'm back trying to reinvent the wheel again, because it's fun
    Now, I just thought I'd ask. Here's the deal. This is some kind of linked list, you might suppose, that's to be written to a file (or two).
    So, I have a data file that contains data and a linked list structure saved as an index.
    To make things easier, I decided to store the index structures in a separate file, so seeking and re-writing index wouldn't be necessary as the data file expands.
    However, the thing is that the index structure is of variable length due to a string inside it. So either I make it static length by pre-allocating say, 255 chars for the length (which I find bad since it limits the length of the name and [often] wastes a lot of space for nothing) or I can do another linked list approach to write the length of the index.
    So you read the length of the index, seek that amount of bytes and you'll be at the start of the next index.
    Or, I could make a small table at the beginning of the file with offsets to all the indexes. These are in the case the index is variable length.
    Another thing I might try is to write the string to the data file and keep track of its offset in the index.

    So, my question would be, what do you think?
    Either:
    - Make index static length (fixed amount of width for string).
    - Write string to data file and make index static length.
    - Make index variable length with a linked-list approach to save the amount of bytes the index takes at the start of the each index so you can travel from index to index.
    - Make index variable length and save a table at the beginning of the index file with positions of each index.
    - Some other solution you might think is a good thing.

    For the curious, here's what the current draft of the index structure looks like:
    Code:
    	class CIndex
    	{
    		friend class CRegistry;
    
    	private:
    		UINT64 nIndexLength;
    		CString strName;
    		UINT64 nOffset;
    		DWORD dwSize;
    		DWORD dwType;
    		DWORD dwElements;
    		DWORD dwTreeLevel;
    		CIndex* pParent;
    		CIndex* pNextSibling;
    		CIndex* pPrevSibling;
    		CIndex* pChild;
    		CIndex** pEnd;
    		DWORD dwParentID;
    		DWORD dwNextSiblingID;
    		DWORD dwPrevSiblingID;
    		DWORD dwChildID;
    		UINT64 dwId;
    
    		ERROR1 Save(CRegistry::CKey& Key);
    		ERROR1 Load(CRegistry::CKey& Key);
    		DWORD GetIndexDataSize() { return strName.GetLength() + 4; }
    
    	public:
    		bool operator == (const CIndex& rCompare) { return (dwId == rCompare.dwId); }
    		bool operator != (const CIndex& rCompare) { return (dwId != rCompare.dwId); }
    
    		#define REGTYPE_FREE 0
    		#define REGTYPE_KEY 1
    	};
    What is the code? It's a reinvent of the registry, of course
    Comments have been stripped to reduce the size of the code block.

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Here's another storage option for you to ponder: make the actual index format fixed-size. Put all the variable-sized strings at the end of the index file. Put the offset to the string and its length in the index node.
    Eh, not a very good method (because you have to go back and edit all the entries after you've written all the nodes), but creative.

    Seriously, though, I think you need to give more thought to what the usage pattern of this index is, and what data structure is therefore suitable for it.
    There's also CDB, which might interest you - for ideas if nothing else.
    http://cr.yp.to/cdb.html
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    The pattern should be simple. Since it's a registry, you store all entries under a name and a key. So the idea is to store the data into a data file and use an index to keep track of the data and all of its contents.
    So, we keep track of the name the data is identified by, the offset where the data is stored in the data file, the size of the data in the data files, in bytes, what type of data it is (does it contain a block of saved data or is the block free?), number of elements in the data (if an array), the level in the tree this data (and index) belongs to, pointers to the parent item in the tree, the next sibling, the previous sibling, the child and a pointer to the last item in the entire list (these pointers are used to walk the tree) and lastly we have an ID to identify the data and index.
    I'm leaning more towards saving the strings in the data file to avoid complications.

  4. #4
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Screw XML. Besides, this is written to be time critical, as fast as possible, preferably as fast as or close to Window's registry (it's close, but I suppose I can't get all the speed since the registry is implemented in Kernel, and this in User).
    Another reason is that I find XML wasteful. Lots of lots of crappy text and wasted space. And when I write a file, I don't intend the user to change it.

  5. #5
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    What if you store your Registry entries as both files AND directories?
    You could look at the left side of the Windows Registry editor as a directory structure, and the right side as the contents of a file with Keys & Values.
    You'd probably run into some file & directory fragmentation if you're doing a lot of insert & delete operations, but you wouldn't need to move around as much data for each insert...

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Erm, that's exactly what I'm doing. The question is how to save the registry data into files.
    And besides that, I won't move around data at all. I will use free space for insert. Yes, it will get fragmented, but that's the price to pay for speed.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Reinventing the Wheel
    By manofsteel972 in forum A Brief History of Cprogramming.com
    Replies: 37
    Last Post: 07-11-2007, 11:38 AM
  2. my mouse wheel
    By DavidP in forum Tech Board
    Replies: 0
    Last Post: 11-06-2006, 09:58 AM
  3. Problems with mouse wheel...
    By xkrja in forum Windows Programming
    Replies: 1
    Last Post: 09-12-2006, 02:22 PM
  4. Logitech MOMO wheel broke, fixed manually
    By Xei in forum Tech Board
    Replies: 2
    Last Post: 07-25-2003, 02:29 AM
  5. Mouse Wheel In Console
    By GaPe in forum C Programming
    Replies: 0
    Last Post: 09-07-2002, 02:05 AM