1 /* Invisible Vector Library
2 * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
3 * Understanding is not required. Only obedience.
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, version 3 of the License ONLY.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 module iv
.vfs
.arc
.internal
/*is aliced*/;
20 //version = iv_vfs_arcs_debug_hash;
21 version = iv_vfs_arcs_nomodulo
;
24 // ////////////////////////////////////////////////////////////////////////// //
25 package mixin template VFSSimpleArchiveDriverMixin() {
27 static struct HashTableEntry
{
28 uint hash
; // name hash; name is lowercased
29 uint prev
=uint.max
; // previous name with the same reduced hash position
30 uint didx
=uint.max
; // dir index
33 // returns lowercased string bytes, suitable for hash calculation
34 static struct LoStringRange
{
37 pure nothrow @trusted @nogc:
38 this (const(char)[] as
) { pragma(inline
, true); s
= as
; pos
= 0; }
39 @property bool empty () const { pragma(inline
, true); return (pos
>= s
.length
); }
40 @property ubyte front () const {
45 return cast(ubyte)koi8tolowerTable
.ptr
[cast(ubyte)koi8from1251Table
[s
.ptr
[pos
]]];
47 return cast(ubyte)koi8tolowerTable
.ptr
[cast(ubyte)s
.ptr
[pos
]];
52 return (pos
< s
.length ?
cast(ubyte)s
.ptr
[pos
] : 0);
54 void popFront () { pragma(inline
, true); if (pos
< s
.length
) ++pos
; }
57 static uint hashStr (const(char)[] s
) {
58 //pragma(inline, true);
59 if (auto res
= mur3HashOf(LoStringRange(s
))) return res
; else return 1; // so we can use 0 as sentinel
60 //return mur3HashOf(LoStringRange(s));
66 HashTableEntry
[] htable
; // for names, in reverse order; so name lookups will be faster
68 // htable[hashStr(name)%htable.length]: check if hash is ok, and name is ok
69 // if not ok, jump to htable[curht.prev], repeat
72 // call this after you done building `dir`; never modify `dir` after that (or call `buildNameHashTable()` again)
73 final void buildNameHashTable () @trusted {
74 import core
.memory
: GC
;
75 if (dir
.length
== 0 || dir
.length
>= uint.max
-8) { delete htable
; return; } // just in case
76 if (htable
.length
) htable
.assumeSafeAppend
;
77 htable
.length
= dir
.length
;
78 if (htable
.ptr
is GC
.addrOf(htable
.ptr
)) GC
.setAttr(htable
.ptr
, GC
.BlkAttr
.NO_INTERIOR
);
79 htable
[] = HashTableEntry
.init
;
80 version(iv_vfs_arcs_debug_hash
) {
84 foreach_reverse (immutable idx
, const ref FileInfo fi
; dir
) {
85 uint nhash
= hashStr(fi
.name
); // never zero
86 version(iv_vfs_arcs_nomodulo
) {
87 uint hidx
= cast(uint)((cast(ulong)nhash
*cast(ulong)htable
.length
)>>32);
88 assert(hidx
< htable
.length
);
90 uint hidx
= nhash
%cast(uint)htable
.length
;
92 if (htable
.ptr
[hidx
].didx
== uint.max
) {
94 htable
.ptr
[hidx
].hash
= nhash
;
95 htable
.ptr
[hidx
].didx
= cast(uint)idx
;
96 assert(htable
.ptr
[hidx
].prev
== uint.max
);
97 //version(iv_vfs_arcs_debug_hash) { import core.stdc.stdio; printf("H1: [%.*s] nhash=0x%08x; hidx=%u\n", cast(uint)fi.name.length, fi.name.ptr, nhash, hidx); }
99 version(iv_vfs_arcs_debug_hash
) {
104 while (htable
.ptr
[hidx
].prev
!= uint.max
) {
105 version(iv_vfs_arcs_debug_hash
) ++chainlen
;
106 hidx
= htable
.ptr
[hidx
].prev
;
108 version(iv_vfs_arcs_debug_hash
) if (chainlen
> maxchainlen
) maxchainlen
= chainlen
;
110 uint freeslot
= hidx
;
111 foreach (immutable uint count
; 0..cast(uint)dir
.length
) {
112 freeslot
= (freeslot
+1)%cast(uint)htable
.length
;
113 if (htable
.ptr
[freeslot
].hash
== 0) break; // i found her!
115 if (htable
.ptr
[freeslot
].hash
!= 0) assert(0, "wtf?!");
116 htable
.ptr
[hidx
].prev
= freeslot
;
117 htable
.ptr
[freeslot
].hash
= nhash
;
118 htable
.ptr
[freeslot
].didx
= cast(uint)idx
;
119 assert(htable
.ptr
[freeslot
].prev
== uint.max
);
122 version(iv_vfs_arcs_debug_hash
) { import core
.stdc
.stdio
; printf("chaincount=%u; maxchainlen=%u; count=%u\n", chaincount
, maxchainlen
, cast(uint)htable
.length
); }
126 this (VFile fl
, const(char)[] prefixpath
) {
127 open(fl
, prefixpath
);
131 override VFile
tryOpen (const(char)[] fname
, bool ignoreCase
) {
132 static bool xequ (const(char)[] s0
, const(char)[] s1
, bool icase
) {
135 if (s0
.length
!= s1
.length
) return false;
136 foreach (immutable idx
, char c0
; s0
) {
137 char c1
= koi8from1251Table
[s1
.ptr
[idx
]];
139 c0
= koi8tolowerTable
.ptr
[cast(ubyte)c0
];
140 c1
= koi8tolowerTable
.ptr
[cast(ubyte)c1
];
142 if (c0
!= c1
) return false;
146 import iv
.vfs
.koi8
: koi8StrCaseEqu
;
147 return (icase ?
koi8StrCaseEqu(s0
, s1
) : (s0
== s1
));
151 if (fname
.length
== 0 || dir
.length
== 0) return VFile
.init
;
152 // try hashtable first
153 if (htable
.length
== dir
.length
) {
154 uint nhash
= hashStr(fname
);
155 version(iv_vfs_arcs_debug_hash
) { import core
.stdc
.stdio
; printf("HL: [%.*s] nhash=0x%08x\n", cast(uint)fname
.length
, fname
.ptr
, nhash
); }
156 version(iv_vfs_arcs_nomodulo
) {
157 uint hidx
= cast(uint)((cast(ulong)nhash
*cast(ulong)htable
.length
)>>32);
159 uint hidx
= nhash
%cast(uint)htable
.length
;
161 while (hidx
!= uint.max
&& htable
.ptr
[hidx
].hash
!= 0) {
162 if (htable
.ptr
[hidx
].hash
== nhash
) {
163 uint didx
= htable
.ptr
[hidx
].didx
;
164 FileInfo
* fi
= dir
.ptr
+didx
;
165 if (xequ(fi
.name
, fname
, ignoreCase
)) {
166 version(iv_vfs_arcs_debug_hash
) { import core
.stdc
.stdio
; printf("HH: [%.*s] nhash=0x%08x; hthash=0x%08x; hidx=%u\n", cast(uint)fi
.name
.length
, fi
.name
.ptr
, nhash
, htable
.ptr
[hidx
].hash
, hidx
); }
170 version(iv_vfs_arcs_debug_hash
) { import core
.stdc
.stdio
; printf("HS: [%.*s] nhash=0x%08x; hthash=0x%08x; hidx=%u\n", cast(uint)dir
.ptr
[htable
.ptr
[hidx
].didx
].name
.length
, dir
.ptr
[htable
.ptr
[hidx
].didx
].name
.ptr
, nhash
, htable
.ptr
[hidx
].hash
, hidx
); }
171 hidx
= htable
.ptr
[hidx
].prev
;
173 // alas, and it is guaranteed that we have no such file here
176 // fallback to linear search
177 foreach_reverse (immutable idx
, ref fi
; dir
) {
178 if (xequ(fi
.name
, fname
, ignoreCase
)) return wrap(idx
);
183 override @property usize
dirLength () { return dir
.length
; }
184 override DirEntry
dirEntry (usize idx
) { return (idx
< dir
.length ?
DirEntry(cast(uint)idx
, dir
.ptr
[idx
].name
, dir
.ptr
[idx
].size
) : DirEntry
.init
); }
188 // ////////////////////////////////////////////////////////////////////////// //
189 package enum VFSSimpleArchiveDetectorMixin(string drvname
, string mode
="normal") =
190 "shared static this () { vfsRegisterDetector!"~mode
.stringof
~"(new "~drvname
~"Detector()); }\n"~
191 "private final class "~drvname
~"Detector : VFSDriverDetector {\n"~
192 " override VFSDriver tryOpen (VFile fl, const(char)[] prefixpath) {\n"~
194 " return new VFSDriver"~drvname
~"(fl, prefixpath);\n"~
195 " } catch (Exception) {}\n"~