1 /** @file lumpindex.cpp Index of lumps.
2 *
3 * @authors Copyright © 2003-2017 Jaakko Keränen <jaakko.keranen@iki.fi>
4 * @authors Copyright © 2006-2014 Daniel Swanson <danij@dengine.net>
5 * @authors Copyright © 2006 Jamie Jones <jamie_jones_au@yahoo.com.au>
6 * @authors Copyright © 1999-2006 by Colin Phipps, Florian Schulze, Neil Stevens, Andrey Budko (PrBoom 2.2.6)
7 * @authors Copyright © 1999-2001 by Jess Haas, Nicolas Kalkhof (PrBoom 2.2.6)
8 * @authors Copyright © 1999 Chi Hoang, Lee Killough, Jim Flynn, Rand Phares, Ty Halderman (PrBoom 2.2.6)
9 * @authors Copyright © 1993-1996 by id Software, Inc.
10 *
11 * @par License
12 * GPL: http://www.gnu.org/licenses/gpl.html
13 *
14 * <small>This program is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU General Public License as published by the
16 * Free Software Foundation; either version 2 of the License, or (at your
17 * option) any later version. This program is distributed in the hope that it
18 * will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty
19 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
20 * Public License for more details. You should have received a copy of the GNU
21 * General Public License along with this program; if not, write to the Free
22 * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
23 * 02110-1301 USA</small>
24 */
25
26 #include "doomsday/filesys/lumpindex.h"
27 #include <QBitArray>
28 #include <QHash>
29 #include <QVector>
30 #include <de/LogBuffer>
31
32 namespace de {
33 namespace internal
34 {
35 struct LumpSortInfo
36 {
37 File1 const *lump;
38 String path;
39 int origIndex;
40 };
41
lumpSorter(void const * a,void const * b)42 static int lumpSorter(void const *a, void const *b)
43 {
44 LumpSortInfo const *infoA = (LumpSortInfo const *)a;
45 LumpSortInfo const *infoB = (LumpSortInfo const *)b;
46
47 if (int delta = infoA->path.compare(infoB->path, Qt::CaseInsensitive))
48 return delta;
49
50 // Still matched; try the file load order indexes.
51 if (int delta = (infoA->lump->container().loadOrderIndex() -
52 infoB->lump->container().loadOrderIndex()))
53 return delta;
54
55 // Still matched (i.e., present in the same package); use the original indexes.
56 return (infoB->origIndex - infoA->origIndex);
57 }
58
59 } // namespace internal
60
61 using namespace internal;
62
DENG2_PIMPL_NOREF(LumpIndex::Id1MapRecognizer)63 DENG2_PIMPL_NOREF(LumpIndex::Id1MapRecognizer)
64 {
65 lumpnum_t lastLump = -1;
66 Lumps lumps;
67 String id;
68 Format format = UnknownFormat;
69 };
70
Id1MapRecognizer(LumpIndex const & lumpIndex,lumpnum_t lumpIndexOffset)71 LumpIndex::Id1MapRecognizer::Id1MapRecognizer(LumpIndex const &lumpIndex, lumpnum_t lumpIndexOffset)
72 : d(new Impl)
73 {
74 LOG_AS("LumpIndex::Id1MapRecognizer");
75 LOG_RES_XVERBOSE("Locating data lumps...", "");
76
77 // Keep checking lumps to see if its a map data lump.
78 dint const numLumps = lumpIndex.size();
79 String sourceFile;
80 for (d->lastLump = de::max(lumpIndexOffset, 0); d->lastLump < numLumps; ++d->lastLump)
81 {
82 // Lump name determines whether this lump is a candidate.
83 File1 &lump = lumpIndex[d->lastLump];
84 DataType dataType = typeForLumpName(lump.name());
85
86 if (d->lumps.isEmpty())
87 {
88 // No sequence has yet begun. Continue the scan?
89 if (dataType == UnknownData) continue;
90
91 // Missing a header?
92 if (d->lastLump == 0) return;
93
94 if (dataType == UDMFTextmapData)
95 {
96 // This must be UDMF.
97 d->format = UniversalFormat;
98 }
99
100 // The id of the map is the name of the lump which precedes the first
101 // recognized data lump (which should be the header). Note that some
102 // ports include MAPINFO-like data in the header.
103 d->id = lumpIndex[d->lastLump - 1].name().fileNameAndPathWithoutExtension();
104 sourceFile = lump.container().composePath();
105 }
106 else
107 {
108 if (d->format == UniversalFormat)
109 {
110 // Found the UDMF end marker.
111 if (dataType == UDMFEndmapData) break;
112 }
113 else
114 {
115 // The first unrecognized lump ends the sequence.
116 if (dataType == UnknownData) break;
117 }
118
119 // A lump from another source file also ends the sequence.
120 if (sourceFile.compareWithoutCase(lump.container().composePath()))
121 break;
122 }
123
124 // A recognized map data lump; record it in the collection (replacing any
125 // existing record of the same type).
126 d->lumps.insert(dataType, &lump);
127 }
128
129 if (d->lumps.isEmpty()) return;
130
131 // At this point we know we've found something that could be map data.
132 if (d->format == UnknownFormat)
133 {
134 // Some data lumps are specific to a particular map format and thus their
135 // presence unambiguously identifies the format.
136 if (d->lumps.contains(BehaviorData))
137 {
138 d->format = HexenFormat;
139 }
140 else if (d->lumps.contains(MacroData) ||
141 d->lumps.contains(TintColorData) ||
142 d->lumps.contains(LeafData))
143 {
144 d->format = Doom64Format;
145 }
146 else
147 {
148 d->format = DoomFormat;
149 }
150
151 // Determine whether each data lump is of the expected size.
152 duint numVertexes = 0, numThings = 0, numLines = 0, numSides = 0, numSectors = 0, numLights = 0;
153 DENG2_FOR_EACH_CONST(Lumps, i, d->lumps)
154 {
155 DataType const dataType = i.key();
156 File1 const &lump = *i.value();
157
158 // Determine the number of map data objects of each data type.
159 duint *elemCountAddr = 0;
160 dsize const elemSize = elementSizeForDataType(d->format, dataType);
161
162 switch (dataType)
163 {
164 default: break;
165
166 case VertexData: elemCountAddr = &numVertexes; break;
167 case ThingData: elemCountAddr = &numThings; break;
168 case LineDefData: elemCountAddr = &numLines; break;
169 case SideDefData: elemCountAddr = &numSides; break;
170 case SectorDefData: elemCountAddr = &numSectors; break;
171 case TintColorData: elemCountAddr = &numLights; break;
172 }
173
174 if (elemCountAddr)
175 {
176 if (lump.size() % elemSize != 0)
177 {
178 // What *is* this??
179 d->format = UnknownFormat;
180 d->id.clear();
181 return;
182 }
183
184 *elemCountAddr += lump.size() / elemSize;
185 }
186 }
187
188 // A valid map contains at least one of each of these element types.
189 /// @todo Support loading "empty" maps.
190 if (!numVertexes || !numLines || !numSides || !numSectors)
191 {
192 d->format = UnknownFormat;
193 d->id.clear();
194 return;
195 }
196 }
197
198 LOG_RES_VERBOSE("Recognized %s format map") << formatName(d->format);
199 }
200
id() const201 String const &LumpIndex::Id1MapRecognizer::id() const
202 {
203 return d->id;
204 }
205
format() const206 LumpIndex::Id1MapRecognizer::Format LumpIndex::Id1MapRecognizer::format() const
207 {
208 return d->format;
209 }
210
lumps() const211 LumpIndex::Id1MapRecognizer::Lumps const &LumpIndex::Id1MapRecognizer::lumps() const
212 {
213 return d->lumps;
214 }
215
sourceFile() const216 File1 *LumpIndex::Id1MapRecognizer::sourceFile() const
217 {
218 if (d->lumps.isEmpty()) return nullptr;
219 return &lumps().first()->container();
220 }
221
lastLump() const222 lumpnum_t LumpIndex::Id1MapRecognizer::lastLump() const
223 {
224 return d->lastLump;
225 }
226
formatName(Format id)227 String const &LumpIndex::Id1MapRecognizer::formatName(Format id) // static
228 {
229 static String const names[1 + KnownFormatCount] = {
230 "Unknown",
231 "id Tech 1 (Doom)",
232 "id Tech 1 (Hexen)",
233 "id Tech 1 (Doom64)",
234 "id Tech 1 (UDMF)"
235 };
236 if (id >= DoomFormat && id < KnownFormatCount)
237 {
238 return names[1 + id];
239 }
240 return names[0];
241 }
242
typeForLumpName(String name)243 LumpIndex::Id1MapRecognizer::DataType LumpIndex::Id1MapRecognizer::typeForLumpName(String name) // static
244 {
245 static QHash<String, DataType> const lumpTypeInfo
246 {
247 std::make_pair(String("THINGS"), ThingData ),
248 std::make_pair(String("LINEDEFS"), LineDefData ),
249 std::make_pair(String("SIDEDEFS"), SideDefData ),
250 std::make_pair(String("VERTEXES"), VertexData ),
251 std::make_pair(String("SEGS"), SegData ),
252 std::make_pair(String("SSECTORS"), SubsectorData ),
253 std::make_pair(String("NODES"), NodeData ),
254 std::make_pair(String("SECTORS"), SectorDefData ),
255 std::make_pair(String("REJECT"), RejectData ),
256 std::make_pair(String("BLOCKMAP"), BlockmapData ),
257 std::make_pair(String("BEHAVIOR"), BehaviorData ),
258 std::make_pair(String("SCRIPTS"), ScriptData ),
259 std::make_pair(String("LIGHTS"), TintColorData ),
260 std::make_pair(String("MACROS"), MacroData ),
261 std::make_pair(String("LEAFS"), LeafData ),
262 std::make_pair(String("GL_VERT"), GLVertexData ),
263 std::make_pair(String("GL_SEGS"), GLSegData ),
264 std::make_pair(String("GL_SSECT"), GLSubsectorData),
265 std::make_pair(String("GL_NODES"), GLNodeData ),
266 std::make_pair(String("GL_PVS"), GLPVSData ),
267 std::make_pair(String("TEXTMAP"), UDMFTextmapData),
268 std::make_pair(String("ENDMAP"), UDMFEndmapData ),
269 };
270
271 // Ignore the file extension if present.
272 auto found = lumpTypeInfo.constFind(name.fileNameWithoutExtension().toUpper());
273 if (found != lumpTypeInfo.constEnd())
274 {
275 return found.value();
276 }
277 return UnknownData;
278 }
279
elementSizeForDataType(Format mapFormat,DataType dataType)280 dsize LumpIndex::Id1MapRecognizer::elementSizeForDataType(Format mapFormat, DataType dataType) // static
281 {
282 dsize const SIZEOF_64VERTEX = (4 * 2);
283 dsize const SIZEOF_VERTEX = (2 * 2);
284 dsize const SIZEOF_SIDEDEF = (2 * 3 + 8 * 3);
285 dsize const SIZEOF_64SIDEDEF = (2 * 6);
286 dsize const SIZEOF_LINEDEF = (2 * 7);
287 dsize const SIZEOF_64LINEDEF = (2 * 6 + 1 * 4);
288 dsize const SIZEOF_XLINEDEF = (2 * 5 + 1 * 6);
289 dsize const SIZEOF_SECTOR = (2 * 5 + 8 * 2);
290 dsize const SIZEOF_64SECTOR = (2 * 12);
291 dsize const SIZEOF_THING = (2 * 5);
292 dsize const SIZEOF_64THING = (2 * 7);
293 dsize const SIZEOF_XTHING = (2 * 7 + 1 * 6);
294 dsize const SIZEOF_LIGHT = (1 * 6);
295
296 switch (dataType)
297 {
298 default: return 0;
299
300 case VertexData:
301 return (mapFormat == Doom64Format? SIZEOF_64VERTEX : SIZEOF_VERTEX);
302
303 case LineDefData:
304 return (mapFormat == Doom64Format? SIZEOF_64LINEDEF :
305 mapFormat == HexenFormat ? SIZEOF_XLINEDEF : SIZEOF_LINEDEF);
306
307 case SideDefData:
308 return (mapFormat == Doom64Format? SIZEOF_64SIDEDEF : SIZEOF_SIDEDEF);
309
310 case SectorDefData:
311 return (mapFormat == Doom64Format? SIZEOF_64SECTOR : SIZEOF_SECTOR);
312
313 case ThingData:
314 return (mapFormat == Doom64Format? SIZEOF_64THING :
315 mapFormat == HexenFormat ? SIZEOF_XTHING : SIZEOF_THING);
316
317 case TintColorData: return SIZEOF_LIGHT;
318 }
319 }
320
DENG2_PIMPL(LumpIndex)321 DENG2_PIMPL(LumpIndex)
322 {
323 bool pathsAreUnique;
324
325 Lumps lumps;
326 bool needPruneDuplicateLumps;
327
328 /// Stores indexes into records forming a chain of PathTree::Node fragment
329 /// hashes. For ultra-fast lookup by path.
330 struct PathHashRecord
331 {
332 lumpnum_t head, nextInLoadOrder;
333 };
334 typedef QVector<PathHashRecord> PathHash;
335 QScopedPointer<PathHash> lumpsByPath;
336
337 Impl(Public *i)
338 : Base(i)
339 , pathsAreUnique (false)
340 , needPruneDuplicateLumps(false)
341 {}
342
343 ~Impl() { self().clear(); }
344
345 void buildLumpsByPathIfNeeded()
346 {
347 if (!lumpsByPath.isNull()) return;
348
349 int const numElements = lumps.size();
350 lumpsByPath.reset(new PathHash(numElements));
351
352 // Clear the chains.
353 DENG2_FOR_EACH(PathHash, i, *lumpsByPath)
354 {
355 i->head = -1;
356 }
357
358 // Prepend nodes to each chain, in first-to-last load order, so that
359 // the last lump with a given name appears first in the chain.
360 for (int i = 0; i < numElements; ++i)
361 {
362 File1 const &lump = *(lumps[i]);
363 PathTree::Node const &node = lump.directoryNode();
364 ushort k = node.hash() % (unsigned)numElements;
365
366 (*lumpsByPath)[i].nextInLoadOrder = (*lumpsByPath)[k].head;
367 (*lumpsByPath)[k].head = i;
368 }
369
370 LOG_RES_XVERBOSE("Rebuilt hashMap for LumpIndex %p", thisPublic);
371 }
372
373 /**
374 * @param pruneFlags Passed by reference to avoid deep copy on value-write.
375 * @param file Flag only those lumps contained by this file.
376 *
377 * @return Number of lumps newly flagged during this op.
378 */
379 int flagContainedLumps(QBitArray &pruneFlags, File1 &file)
380 {
381 DENG2_ASSERT(pruneFlags.size() == lumps.size());
382
383 int const numRecords = lumps.size();
384 int numFlagged = 0;
385 for (int i = 0; i < numRecords; ++i)
386 {
387 File1 *lump = lumps[i];
388 if (pruneFlags.testBit(i)) continue;
389 if (!lump->isContained() || &lump->container() != &file) continue;
390 pruneFlags.setBit(i, true);
391 numFlagged += 1;
392 }
393 return numFlagged;
394 }
395
396 /**
397 * @param pruneFlags Passed by reference to avoid deep copy on value-write.
398 * @return Number of lumps newly flagged during this op.
399 */
400 int flagDuplicateLumps(QBitArray &pruneFlags)
401 {
402 DENG2_ASSERT(pruneFlags.size() == lumps.size());
403
404 // Any work to do?
405 if (!pathsAreUnique) return 0;
406 if (!needPruneDuplicateLumps) return 0;
407
408 int const numRecords = lumps.size();
409 if (numRecords <= 1) return 0;
410
411 // Sort in descending load order for pruning.
412 LumpSortInfo *sortInfos = new LumpSortInfo[numRecords];
413 for (int i = 0; i < numRecords; ++i)
414 {
415 LumpSortInfo &sortInfo = sortInfos[i];
416 File1 const *lump = lumps[i];
417
418 sortInfo.lump = lump;
419 sortInfo.path = lump->composePath();
420 sortInfo.origIndex = i;
421 }
422 qsort(sortInfos, numRecords, sizeof(*sortInfos), lumpSorter);
423
424 // Flag the lumps we'll be pruning.
425 int numFlagged = 0;
426 for (int i = 1; i < numRecords; ++i)
427 {
428 if (pruneFlags.testBit(i)) continue;
429 if (sortInfos[i - 1].path.compare(sortInfos[i].path, Qt::CaseInsensitive)) continue;
430 pruneFlags.setBit(sortInfos[i].origIndex, true);
431 numFlagged += 1;
432 }
433
434 // We're done with the sort info.
435 delete[] sortInfos;
436
437 return numFlagged;
438 }
439
440 /// @return Number of pruned lumps.
441 int pruneFlaggedLumps(QBitArray flaggedLumps)
442 {
443 DENG2_ASSERT(flaggedLumps.size() == lumps.size());
444
445 // Have we lumps to prune?
446 int const numFlaggedForPrune = flaggedLumps.count(true);
447 if (numFlaggedForPrune)
448 {
449 // We'll need to rebuild the hash after this.
450 lumpsByPath.reset();
451
452 int numRecords = lumps.size();
453 if (numRecords == numFlaggedForPrune)
454 {
455 lumps.clear();
456 }
457 else
458 {
459 // Do this one lump at a time, respecting the possibly-sorted order.
460 for (int i = 0, newIdx = 0; i < numRecords; ++i)
461 {
462 if (!flaggedLumps.testBit(i))
463 {
464 ++newIdx;
465 continue;
466 }
467
468 // Move the info for the lump to be pruned to the end.
469 lumps.move(newIdx, lumps.size() - 1);
470 }
471
472 // Erase the pruned lumps from the end of the list.
473 int firstPruned = lumps.size() - numFlaggedForPrune;
474 lumps.erase(lumps.begin() + firstPruned, lumps.end());
475 }
476 }
477 return numFlaggedForPrune;
478 }
479
480 void pruneDuplicatesIfNeeded()
481 {
482 if (!needPruneDuplicateLumps) return;
483 needPruneDuplicateLumps = false;
484
485 int const numRecords = lumps.size();
486 if (numRecords <= 1) return;
487
488 QBitArray pruneFlags(numRecords);
489 flagDuplicateLumps(pruneFlags);
490 pruneFlaggedLumps(pruneFlags);
491 }
492 };
493
LumpIndex(bool pathsAreUnique)494 LumpIndex::LumpIndex(bool pathsAreUnique) : d(new Impl(this))
495 {
496 d->pathsAreUnique = pathsAreUnique;
497 }
498
~LumpIndex()499 LumpIndex::~LumpIndex()
500 {}
501
hasLump(lumpnum_t lumpNum) const502 bool LumpIndex::hasLump(lumpnum_t lumpNum) const
503 {
504 d->pruneDuplicatesIfNeeded();
505 return (lumpNum >= 0 && lumpNum < d->lumps.size());
506 }
507
LumpIndex_invalidIndexMessage(int invalidIdx,int lastValidIdx)508 static String LumpIndex_invalidIndexMessage(int invalidIdx, int lastValidIdx)
509 {
510 String msg = String("Invalid lump index %1").arg(invalidIdx);
511 if (lastValidIdx < 0) msg += " (file is empty)";
512 else msg += String(", valid range: [0..%2)").arg(lastValidIdx);
513 return msg;
514 }
515
lump(lumpnum_t lumpNum) const516 File1 &LumpIndex::lump(lumpnum_t lumpNum) const
517 {
518 if (!hasLump(lumpNum)) throw NotFoundError("LumpIndex::lump", LumpIndex_invalidIndexMessage(lumpNum, size() - 1));
519 return *d->lumps[lumpNum];
520 }
521
allLumps() const522 LumpIndex::Lumps const &LumpIndex::allLumps() const
523 {
524 d->pruneDuplicatesIfNeeded();
525 return d->lumps;
526 }
527
size() const528 int LumpIndex::size() const
529 {
530 d->pruneDuplicatesIfNeeded();
531 return d->lumps.size();
532 }
533
lastIndex() const534 int LumpIndex::lastIndex() const
535 {
536 return d->lumps.size() - 1;
537 }
538
pruneByFile(File1 & file)539 int LumpIndex::pruneByFile(File1 &file)
540 {
541 if (d->lumps.empty()) return 0;
542
543 int const numRecords = d->lumps.size();
544 QBitArray pruneFlags(numRecords);
545
546 // We may need to prune path-duplicate lumps. We'll fold those into this
547 // op as pruning may result in reallocations.
548 d->flagDuplicateLumps(pruneFlags);
549
550 // Flag the lumps we'll be pruning.
551 int numFlaggedForFile = d->flagContainedLumps(pruneFlags, file);
552
553 // Perform the prune.
554 d->pruneFlaggedLumps(pruneFlags);
555
556 d->needPruneDuplicateLumps = false;
557
558 return numFlaggedForFile;
559 }
560
pruneLump(File1 & lump)561 bool LumpIndex::pruneLump(File1 &lump)
562 {
563 if (d->lumps.empty()) return 0;
564
565 d->pruneDuplicatesIfNeeded();
566
567 // Prune this lump.
568 if (!d->lumps.removeOne(&lump)) return false;
569
570 // We'll need to rebuild the path hash chains.
571 d->lumpsByPath.reset();
572
573 return true;
574 }
575
catalogLump(File1 & lump)576 void LumpIndex::catalogLump(File1 &lump)
577 {
578 d->lumps.push_back(&lump);
579 d->lumpsByPath.reset(); // We'll need to rebuild the path hash chains.
580
581 if (d->pathsAreUnique)
582 {
583 // We may need to prune duplicate paths.
584 d->needPruneDuplicateLumps = true;
585 }
586 }
587
clear()588 void LumpIndex::clear()
589 {
590 d->lumps.clear();
591 d->lumpsByPath.reset();
592 d->needPruneDuplicateLumps = false;
593 }
594
catalogues(File1 & file)595 bool LumpIndex::catalogues(File1 &file)
596 {
597 d->pruneDuplicatesIfNeeded();
598
599 DENG2_FOR_EACH(Lumps, i, d->lumps)
600 {
601 File1 const &lump = **i;
602 if (&lump.container() == &file)
603 return true;
604 }
605
606 return false;
607 }
608
contains(Path const & path) const609 bool LumpIndex::contains(Path const &path) const
610 {
611 return findFirst(path) >= 0;
612 }
613
findAll(Path const & path,FoundIndices & found) const614 int LumpIndex::findAll(Path const &path, FoundIndices &found) const
615 {
616 LOG_AS("LumpIndex::findAll");
617
618 found.clear();
619
620 if (path.isEmpty() || d->lumps.empty()) return 0;
621
622 d->pruneDuplicatesIfNeeded();
623 d->buildLumpsByPathIfNeeded();
624
625 // Perform the search.
626 DENG2_ASSERT(!d->lumpsByPath.isNull());
627 ushort hash = path.lastSegment().hash() % d->lumpsByPath->size();
628 for (int idx = (*d->lumpsByPath)[hash].head; idx != -1;
629 idx = (*d->lumpsByPath)[idx].nextInLoadOrder)
630 {
631 File1 const &lump = *d->lumps[idx];
632 PathTree::Node const &node = lump.directoryNode();
633
634 if (!node.comparePath(path, 0))
635 {
636 found.push_front(idx);
637 }
638 }
639
640 return int(found.size());
641 }
642
findLast(Path const & path) const643 lumpnum_t LumpIndex::findLast(Path const &path) const
644 {
645 if (path.isEmpty() || d->lumps.empty()) return -1;
646
647 d->pruneDuplicatesIfNeeded();
648 d->buildLumpsByPathIfNeeded();
649
650 // Perform the search.
651 DENG2_ASSERT(!d->lumpsByPath.isNull());
652 ushort hash = path.lastSegment().hash() % d->lumpsByPath->size();
653 for (int idx = (*d->lumpsByPath)[hash].head; idx != -1;
654 idx = (*d->lumpsByPath)[idx].nextInLoadOrder)
655 {
656 File1 const &lump = *d->lumps[idx];
657 PathTree::Node const &node = lump.directoryNode();
658
659 if (!node.comparePath(path, 0))
660 {
661 return idx; // This is the lump we are looking for.
662 }
663 }
664
665 return -1; // Not found.
666 }
667
findFirst(Path const & path) const668 lumpnum_t LumpIndex::findFirst(Path const &path) const
669 {
670 if (path.isEmpty() || d->lumps.empty()) return -1;
671
672 d->pruneDuplicatesIfNeeded();
673 d->buildLumpsByPathIfNeeded();
674
675 lumpnum_t earliest = -1; // Not found.
676
677 // Perform the search.
678 DENG2_ASSERT(!d->lumpsByPath.isNull());
679 ushort hash = path.lastSegment().hash() % d->lumpsByPath->size();
680 for (int idx = (*d->lumpsByPath)[hash].head; idx != -1;
681 idx = (*d->lumpsByPath)[idx].nextInLoadOrder)
682 {
683 File1 const &lump = *d->lumps[idx];
684 PathTree::Node const &node = lump.directoryNode();
685
686 if (!node.comparePath(path, 0))
687 {
688 earliest = idx; // This is now the first lump loaded.
689 }
690 }
691
692 return earliest;
693 }
694
composeResourceUrn(lumpnum_t lumpNum)695 Uri LumpIndex::composeResourceUrn(lumpnum_t lumpNum) // static
696 {
697 return Uri("LumpIndex", Path(String("%1").arg(lumpNum)));
698 }
699
700 } // namespace de
701