arma3 / DokanPbo

Mount PBO files as drives or folders in the file system
GNU Lesser General Public License v3.0
23 stars 5 forks source link

New storage for fileTree #7

Closed dedmen closed 6 years ago

dedmen commented 6 years ago
Unordered map (buckets. key is path)
    Lookup is pathhash + vector lookup. Almost constant. O(1)
    Insert might need to rehash. That's cheap.
    Storage requires whole path for each file. 90% redundant data.

Map (binary tree. key is path)
    Lookup needs to walk whole tree. O(log fileCount)
    Inserts equal to lookup
    Storage requires whole path for each file. 90% redundant data.

Trie (custom implemented tree with each path element as node)
    Lookup needs to walk whole tree. More expensive the deeper the path is. O(pathDepth)
    Inserts equal to lookup
    Storage requires each path element's name once.

Ordered vector (key is filepath)
    Lookup binary search. O(log fileCount)
    Insert is O(log fileCount)+moving entries after the insert place to make space
    Storage requires whole path for each file. 90% redundant data.

Additional Idea. HashSet (Unordered Map, without value. key is pointer to file)
    Pointer to file is unique. file has pointer to parent so you can walk up the whole path.
    GetHashCode() function generates path by walking to parent and taking the names of the nodes.
    Lookup needs to generate hash for file to be found by splitting the path string by delimiter.
    Insert is equal to lookup
    Storage requirement is one reference for each file. Might additionally want to cache the hash inside the file to make GetHashCode() faster.
    https://stackoverflow.com/a/8952026 says it internally stores the hashcode. So we don't have to cache it.

Wrote this. And implemented the last one

dedmen commented 6 years ago

built on top of #6.

For my small test setup ACE,ACEX,CBA Memory usage before: 28.4MB Memory usage after: 27.0MB Need to re-test with a bigger setup.

jonpas commented 6 years ago

Recursive folder creation confirmed fixed.

dedmen commented 6 years ago

Rekursivordnererstellungsfehlerbehebungsbestätigung.