XVFS
Check-in [37d00c3cfb]
Login
HomeTimelineFilesBranchesTagsTicketsWiki
Overview
Comment:Support using a hash table unless a really small input is used (may change in the future?)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 37d00c3cfb7a3c585d67153b63259f7031a1ae75c050d3191cd0cf3f52b39a6a
User & Date: rkeene on 2019-11-04 21:09:26
Other Links: manifest | tags
Context
2019-11-04
21:16
Minor hash table optimization check-in: 3c8c52a9f8 user: rkeene tags: trunk
21:09
Support using a hash table unless a really small input is used (may change in the future?) check-in: 37d00c3cfb user: rkeene tags: trunk
2019-10-10
00:40
Improved and parameterized perfect hash function generator check-in: f615eecc64 user: rkeene tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Modified lib/xvfs/xvfs.c.rvt from [6833d26c3e] to [ced159acac].

︙︙
55
56
57
58
59
60
61












62
63
64
65
66
67
68
69
70



71
72
73
74
75
76
77
78
79
80



81

82
83
84
85
86
87
88

<?
	package require xvfs

	xvfs::main $::xvfs::argv

?>
static long xvfs_<?= $::xvfs::fsName ?>_nameToIndex(const char *path) {












	long pathIndex;
	ssize_t pathLen;

	if (path == NULL) {
		return(XVFS_NAME_LOOKUP_ERROR);
	}

	pathLen = strlen(path);




	pathIndex = <?= [::xvfs::generatePerfectHashFunctionCall "path" pathLen XVFS_NAME_LOOKUP_ERROR $::xvfs::outputFiles] ?>;
	if (pathIndex < 0 || pathIndex >= <?= [llength $::xvfs::outputFiles] ?>) {
		pathIndex = XVFS_NAME_LOOKUP_ERROR;
	}

	if (pathIndex != XVFS_NAME_LOOKUP_ERROR) {
		if (strcmp(path, xvfs_<?= $::xvfs::fsName ?>_data[pathIndex].name) == 0) {
			return(pathIndex);
		}
	}



	

	return(XVFS_NAME_LOOKUP_ERROR);
}

static const char **xvfs_<?= $::xvfs::fsName ?>_getChildren(const char *path, Tcl_WideInt *count) {
	const struct xvfs_file_data *fileInfo;
	long inode;









>
>
>
>
>
>
>
>
>
>
>
>
|








>
>
>










>
>
>
|
>








55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

<?
	package require xvfs

	xvfs::main $::xvfs::argv

?>
static long xvfs_<?= $::xvfs::fsName ?>_nameToIndex(const char *path) {
<?
		if {[llength $::xvfs::outputFiles] < 3} {
			set hashMode perfectHashFunction
		} else {
			set hashMode hashTable
		}

		if {$hashMode eq "hashTable"} {
			set hashTable [::xvfs::generateHashTable pathIndex path pathLen XVFS_NAME_LOOKUP_ERROR $::xvfs::outputFiles prefix "\t" hashTableSize 30 validate "strcmp(path, xvfs_${::xvfs::fsName}_data\[pathIndex\].name) == 0" onValidated "return(pathIndex);"]
			set hashTableHeader [dict get $hashTable header]
			puts $hashTableHeader
		}
?>	long pathIndex;
	ssize_t pathLen;

	if (path == NULL) {
		return(XVFS_NAME_LOOKUP_ERROR);
	}

	pathLen = strlen(path);

<?
		if {$hashMode eq "perfectHashFunction"} {
?>
	pathIndex = <?= [::xvfs::generatePerfectHashFunctionCall "path" pathLen XVFS_NAME_LOOKUP_ERROR $::xvfs::outputFiles] ?>;
	if (pathIndex < 0 || pathIndex >= <?= [llength $::xvfs::outputFiles] ?>) {
		pathIndex = XVFS_NAME_LOOKUP_ERROR;
	}

	if (pathIndex != XVFS_NAME_LOOKUP_ERROR) {
		if (strcmp(path, xvfs_<?= $::xvfs::fsName ?>_data[pathIndex].name) == 0) {
			return(pathIndex);
		}
	}
<?
		} else {
			puts [dict get $hashTable body]
		}
?>
	return(XVFS_NAME_LOOKUP_ERROR);
}

static const char **xvfs_<?= $::xvfs::fsName ?>_getChildren(const char *path, Tcl_WideInt *count) {
	const struct xvfs_file_data *fileInfo;
	long inode;
︙︙

Modified lib/xvfs/xvfs.tcl from [1ce5b335aa] to [74213d3431].

︙︙
306
307
308
309
310
311
312
313























































314


315

316
317
318
319
320

321

322
323
324
325
326
327
328
329
330

331
332
333

334
335
336
337
338
339

340
341



342
343

344
345
346
347
348

349

350

351
352
353
354
355
356
357
358


359
360
361
362
363
364
365
366
367
368
369
370


371

372
373
374
375
376
377
378
379
380
381
382
383


384




385
386
387
388


389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406







407
408
409



410







411
412
413
414
415
416



417
418
419
420
421


422
423
424
425
426
427

428
429
430
431




















































































432

}

proc ::xvfs::staticIncludeHeader {pathToHeaderFile} {
	set fd [open $pathToHeaderFile]
	::xvfs::staticIncludeHeaderData [read $fd]
	close $fd
}
























































proc ::xvfs::generatePerfectHashFunctionCall {cVarName cVarLength invalidValue nameList args} {


	array set config {

		preferMinimalHashSize   8
		switchToNonMinimalHash  1048576
		triesAtHashSize         1024
		maxIntermediateMultiple 8
	}



	foreach {configKey configVal} $args {
		if {![info exists config($configKey)]} {
			error "Invalid option: $configKey"
		}
	}
	array set config $args

	set minVal 0
	set maxVal [llength $nameList]

	set testExpr(0) {([zlib adler32 $nameItem $alpha] + $beta) % $gamma}
	set testExpr(1) {([zlib crc32 $nameItem $alpha] + $beta) % $gamma}
	set testExpr(2) {([zlib adler32 $nameItem [zlib crc32 $nameItem $alpha]] + $beta) % $gamma}

	set testExprC(0) {((Tcl_ZlibAdler32(${alpha}LU, (unsigned char *) $cVarName, $cVarLength) + ${beta}LU) % ${gamma}LU)}
	set testExprC(1) {((Tcl_ZlibCRC32(${alpha}LU, (unsigned char *) $cVarName, $cVarLength) + ${beta}LU) % ${gamma}LU)}
	set testExprC(2) {((Tcl_ZlibAdler32(Tcl_ZlibCRC32(${alpha}LU, (unsigned char *) $cVarName, $cVarLength), (unsigned char *) $cVarName, $cVarLength) + ${beta}LU) % ${gamma}LU)}

	set minimal false
	if {$maxVal < $config(preferMinimalHashSize)} {

		set minimal true
	}




	set round -1


	set gammaRoundMod [expr {$maxVal * ($config(maxIntermediateMultiple) - 1)}]

	while true {
		if {$minimal && $round > $config(switchToNonMinimalHash)} {

			set minimal false

			set round -1

		}
		incr round

		if {$minimal} {
			set gamma [expr {$maxVal + ($round % ($maxVal * 4))}]
		} else {
			set gamma [expr {$maxVal + ($round % $gammaRoundMod)}]
		}



		for {set try 0} {$try < $config(triesAtHashSize)} {incr try} {
			set alpha [expr {entier(rand() * (2**31))}]
			set beta  [expr {entier(rand() * (2**31))}]

			foreach {testExprID testExprContents} [array get testExpr] {
				set idx -1
				set seenIndexes [list]
				set failed false
				foreach nameItem $nameList {

					set testExprVal [expr $testExprContents]




					if {$minimal} {
						incr idx

						if {$testExprVal != $idx} {
							set failed true
							break
						}
					} else {
						if {$testExprVal in $seenIndexes} {
							set failed true
							break
						}







						lappend seenIndexes $testExprVal
					}
				}



				if {!$failed} {
					break
				}
			}

			if {!$failed} {
				break
			}
		}

		if {!$failed} {
			break
		}
	}

	if {$minimal} {
		set phfCall [subst $testExprC($testExprID)]
	} else {







		unset -nocomplain mapArray
		for {set idx 0} {$idx < $gamma} {incr idx} {
			set mapArray($idx) $invalidValue



		}








		set idx -1
		foreach nameItem $nameList {
			incr idx

			set mapArray([expr $testExpr($testExprID)]) $idx



		}

		set map "(long\[\])\{"
		for {set idx 0} {$idx < $gamma} {incr idx} {
			append map "$mapArray($idx), "


		}
		set map [string range $map 0 end-2]
		append map "\}\[[subst $testExprC($testExprID)]\]"

		set phfCall $map
	}


	return $phfCall
}





















































































package provide xvfs 1









>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

>
>

>
|
<
|
<

>

>







|
|
>
|
<
|
>
|
|
<

|
|
>
|
|
>
>
>
|
|
>
|
<

<
<
>
|
>
|
>

<
|
<
<
<
<
|
>
>
|
<
<
<
|
|
<
<
<
|
|
|
>
>

>
|
|
|
|
|
<
|
<
<
|
|
|
>
>

>
>
>
>
|
|
|
|
>
>
|
<
<










|
|
|
|
|
>
>
>
>
>
>
>
|
|
<
>
>
>
|
>
>
>
>
>
>
>
|
|
|
<
|
|
>
>
>
|
|
|
<
<
>
>

<
<
|
<
|
>




>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>


306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374

375

376
377
378
379
380
381
382
383
384
385
386
387
388
389
390

391
392
393
394

395
396
397
398
399
400
401
402
403
404
405
406
407

408


409
410
411
412
413
414

415




416
417
418
419



420
421



422
423
424
425
426
427
428
429
430
431
432
433

434


435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451


452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475

476
477
478
479
480
481
482
483
484
485
486
487
488
489

490
491
492
493
494
495
496
497


498
499
500


501

502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592

}

proc ::xvfs::staticIncludeHeader {pathToHeaderFile} {
	set fd [open $pathToHeaderFile]
	::xvfs::staticIncludeHeaderData [read $fd]
	close $fd
}

proc ::xvfs::_tryFit {list} {
	set idx -1
	set lastItem -100000
	foreach item $list {
		incr idx

		if {$item <= $lastItem} {
			return ""
		}

		set difference [expr {$item - $idx}]
		if {$idx != 0} {
			set divisor [expr {$item / $idx}]
		} else {
			set divisor 1
		}
		lappend differences $difference
		lappend divisors $divisor

		set lastItem $item
	}

	foreach divisor [lrange $divisors 1 end] {
		incr divisorCount
		incr divisorValue $divisor
	}
	set divisor [expr {$divisorValue / $divisorCount}]

	for {set i 0} {$i < [llength $list]} {incr i} {
		lappend outList $i
	}

	set mapFunc " - ${difference}"

	set newList [lmap v $list { expr "\$v${mapFunc}" }]
	if {$newList eq $outList} {
		return $mapFunc
	}

	if {$divisor != 1} {
		set mapFunc " / ${divisor}"
		set newList [lmap v $list { expr "\$v${mapFunc}" }]
		if {$newList eq $outList} {
			return $mapFunc
		}

		set subMapFunc [_tryFit $newList]
		if {$subMapFunc != ""} {
			return " / ${divisor}${subMapFunc}"
		}
	}

	return ""
}

proc ::xvfs::generatePerfectHashFunctionCall {cVarName cVarLength invalidValue nameList args} {
	# Manage config
	## Default config
	array set config {
		useCacheFirst  false
		cacheValue     true

		enableCache    false

	}
	set config(cacheFile) [file join [file normalize ~/.cache] xvfs phf-cache.db]

	## User config
	foreach {configKey configVal} $args {
		if {![info exists config($configKey)]} {
			error "Invalid option: $configKey"
		}
	}
	array set config $args

	if {$config(enableCache)} {
		package require sqlite3
	}


	# Adjustment for computing the expense of a function call by its length
	# Calls that take longer should be made longer, so make CRC32 longer
	# than Adler32
	set lengthAdjustment [list Tcl_ZlibCRC32 Tcl_CRCxxx32]


	# Check for a cached entry
	if {$config(enableCache) && $config(useCacheFirst)} {
		catch {
			set hashKey $nameList

			sqlite3 ::xvfs::phfCache $config(cacheFile)
			::xvfs::phfCache eval {CREATE TABLE IF NOT EXISTS cache(hashKey PRIMARY KEY, function BLOB);}
			::xvfs::phfCache eval {SELECT function FROM cache WHERE hashKey = $hashKey LIMIT 1;} cacheRow {}
		}
		catch {
			::xvfs::phfCache close
		}




		if {[info exists cacheRow(function)]} {
			set phfCall $cacheRow(function)
			set phfCall [string map [list @@CVARNAME@@ $cVarName @@CVARLENGTH@@ $cVarLength @@INVALIDVALUE@@ $invalidValue] $phfCall]

			return $phfCall
		}

	}





	set minVal 0
	set maxVal [llength $nameList]
	set testExpr_(0) {[zlib adler32 $nameItem $alpha] % $gamma}



	set testExpr(1) {[zlib crc32 $nameItem $alpha] % $gamma}
	set testExpr_(2) {[zlib adler32 $nameItem [zlib crc32 $nameItem $alpha]] % $gamma}



	set testExpr_(3) {[zlib crc32 $nameItem [zlib adler32 $nameItem $alpha]] % $gamma}
	set testExprC(0) {((Tcl_ZlibAdler32(${alpha}LU, (unsigned char *) @@CVARNAME@@, @@CVARLENGTH@@) % ${gamma}LU)${fitMod})}
	set testExprC(1) {((Tcl_ZlibCRC32(${alpha}LU, (unsigned char *) @@CVARNAME@@, @@CVARLENGTH@@) % ${gamma}LU)${fitMod})}
	set testExprC(2) {((Tcl_ZlibAdler32(Tcl_ZlibCRC32(${alpha}LU, (unsigned char *) @@CVARNAME@@, @@CVARLENGTH@@), (unsigned char *) @@CVARNAME@@, @@CVARLENGTH@@) % ${gamma}LU)${fitMod})}
	set testExprC(3) {((Tcl_ZlibCRC32(Tcl_ZlibAdler32(${alpha}LU, (unsigned char *) @@CVARNAME@@, @@CVARLENGTH@@), (unsigned char *) @@CVARNAME@@, @@CVARLENGTH@@) % ${gamma}LU)${fitMod})}

	# Short-circuit for known cases
	if {$maxVal == 1} {
		return 0
	}

	set round -1




	while true {
		incr round

		set gamma [expr {$maxVal + ($round % ($maxVal * 128))}]
		set alpha [expr {$round / 6}]

		foreach {testExprID testExprContents} [array get testExpr] {
			set unFitList [list]
			foreach nameItem $nameList {
				set testExprVal [expr $testExprContents]
				lappend unFitList $testExprVal
			}

			set failed false
			set fitMod [_tryFit $unFitList]
			if {$fitMod eq ""} {
				set failed true


			}

			if {!$failed} {
				break
			}
		}

		if {!$failed} {
			break
		}

	}

	set phfCall [string map [list { - 0LU} ""] [subst $testExprC($testExprID)]]

	# Check cache for a better answer
	if {$config(enableCache)} {
		catch {
			set hashKey $nameList
			set cacheDir [file dirname $config(cacheFile)]
			file mkdir $cacheDir

			unset -nocomplain cacheRow


			sqlite3 ::xvfs::phfCache $config(cacheFile)
			::xvfs::phfCache eval {CREATE TABLE IF NOT EXISTS cache(hashKey PRIMARY KEY, function BLOB);}
			::xvfs::phfCache eval {SELECT function FROM cache WHERE hashKey = $hashKey LIMIT 1;} cacheRow {}

			set updateCache false
			if {[info exists cacheRow(function)]} {
				if {[string length [string map $lengthAdjustment $cacheRow(function)]] <= [string length [string map $lengthAdjustment $phfCall]]} {
					# Use the cached value since it is better
					set phfCall $cacheRow(function)
				} else {
					set updateCache true
				}
			} else {
				set updateCache true

			}

			if {$updateCache && $config(cacheValue)} {
				# Save to cache
				::xvfs::phfCache eval {INSERT OR REPLACE INTO cache (hashKey, function) VALUES ($hashKey, $phfCall);}
			}
		}



		catch {
			::xvfs::phfCache close
		}


	}


	set phfCall [string map [list @@CVARNAME@@ $cVarName @@CVARLENGTH@@ $cVarLength @@INVALIDVALUE@@ $invalidValue] $phfCall]

	return $phfCall
}

proc ::xvfs::generateHashTable {outCVarName cVarName cVarLength invalidValue nameList args} {
	# Manage config
	## Default config
	array set config {
		prefix        ""
		hashTableSize 10
		validate      0
		onValidated   "break;"
	}

	## User config
	foreach {configKey configVal} $args {
		if {![info exists config($configKey)]} {
			error "Invalid option: $configKey"
		}
	}
	array set config $args

	if {[llength $nameList] < $config(hashTableSize)} {
		set config(hashTableSize) [llength $nameList]
	}

	set maxLength 0
	set index -1
	foreach name $nameList {
		incr index
		set length [string length $name]
		set hash [expr {[zlib adler32 $name 0] % $config(hashTableSize)}]

		lappend indexesAtLength($length) $index
		lappend indexesAtHash($hash) $index

		if {$length > $maxLength} {
			set maxLength $length
		}
	}

	set maxIndexes 0
	foreach {hash indexes} [array get indexesAtHash] {
		set indexesCount [llength $indexes]

		if {$indexesCount > $maxIndexes} {
			set maxIndexes $indexesCount
		}
	}

	lappend outputHeader "${config(prefix)}long ${outCVarName}_idx;"
	lappend outputHeader "${config(prefix)}int ${outCVarName}_hash;"

	for {set hash 0} {$hash < $config(hashTableSize)} {incr hash} {
		if {[info exists indexesAtHash($hash)]} {
			set indexes $indexesAtHash($hash)
		} else {
			set indexes [list]
		}

		lappend indexes $invalidValue
		lappend outputHeader "${config(prefix)}static const long ${outCVarName}_hashTable_${hash}\[\] = \{"
		lappend outputHeader "${config(prefix)}\t[join $indexes {, }]"
		lappend outputHeader "${config(prefix)}\};"
	}

	lappend outputHeader "${config(prefix)}static const long * const ${outCVarName}_hashTable\[${config(hashTableSize)}\] = \{"

	for {set hash 0} {$hash < $config(hashTableSize)} {incr hash} {
		lappend outputHeader "${config(prefix)}\t${outCVarName}_hashTable_${hash},"
	}

	lappend outputHeader "${config(prefix)}\};"
	lappend outputBody "${config(prefix)}${outCVarName}_hash = Tcl_ZlibAdler32(0, (unsigned char *) ${cVarName}, ${cVarLength}) % ${config(hashTableSize)};"
	lappend outputBody "${config(prefix)}for (${outCVarName}_idx = 0; ${outCVarName}_idx <= ${maxIndexes}; ${outCVarName}_idx++) \{"
	lappend outputBody "${config(prefix)}\t${outCVarName} = ${outCVarName}_hashTable\[${outCVarName}_hash\]\[${outCVarName}_idx\];"
	lappend outputBody "${config(prefix)}\tif (${outCVarName} == $invalidValue) \{"
	lappend outputBody "${config(prefix)}\t\tbreak;"
	lappend outputBody "${config(prefix)}\t\}"
	lappend outputBody ""
	lappend outputBody "${config(prefix)}\tif (${config(validate)}) \{"
	lappend outputBody "${config(prefix)}\t\t${config(onValidated)}"
	lappend outputBody "${config(prefix)}\t\}"
	lappend outputBody "${config(prefix)}\}"

	return [dict create header [join $outputHeader "\n"] body [join $outputBody "\n"]]
}

package provide xvfs 1

Powered by Fossil · RSS