FilesExpand file tree

 diagnosticsOrganization

/

stringTable.ts

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

159 lines (128 loc) · 6.46 KB

 diagnosticsOrganization

/

stringTable.ts

Copy path

Top

File metadata and controls

• Code
• Blame

159 lines (128 loc) · 6.46 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

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

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

///<reference path='references.ts' />

module TypeScript.Collections {

export var DefaultStringTableCapacity = 256;

class StringTableEntry {

constructor(public Text: string,

public HashCode: number,

public Next: StringTableEntry) {

}

}

// A table of interned strings. Faster and better than an arbitrary hashtable for the needs of the

// scanner. Specifically, the scanner operates over a sliding window of characters, with a start

// and end pointer for the current lexeme. The scanner then wants to get the *interned* string

// represented by that subsection.

//

// Importantly, if the string is already interned, then it wants ask "is the string represented by

// this section of a char array contained within the table" in a non-allocating fashion. i.e. if

// you have "[' ', 'p', 'u', 'b', 'l', 'i', 'c', ' ']" and you ask to get the string represented by

// range [1, 7), then this table will return "public" without any allocations if that value was

// already in the table.

//

// Of course, if the value is not in the table then there will be an initial cost to allocate the

// string and the bucket for the table. However, that is only incurred the first time each unique

// string is added.

export class StringTable {

// TODO: uncomment this once typecheck bug is fixed.

private entries: StringTableEntry[];

private count: number = 0;

constructor(capacity: number) {

var size = Hash.getPrime(capacity);

this.entries = ArrayUtilities.createArray<StringTableEntry>(size, null);

}

public addCharArray(key: number[], start: number, len: number): string {

// Compute the hash for this key. Also ensure that it fits within 31 bits (so that it

// stays a non-heap integer, and so we can index into the array safely).

var hashCode = Hash.computeSimple31BitCharArrayHashCode(key, start, len) & 0x7FFFFFFF;

// Debug.assert(hashCode > 0);

// First see if we already have the string represented by "key[start, start + len)" already

// present in this table. If we do, just return that string. Do this without any

// allocations

var entry = this.findCharArrayEntry(key, start, len, hashCode);

if (entry !== null) {

return entry.Text;

}

// We don't have an entry for that string in our table. Convert that

var slice: number[] = key.slice(start, start + len);

return this.addEntry(StringUtilities.fromCharCodeArray(slice), hashCode);

}

private findCharArrayEntry(key: number[], start: number, len: number, hashCode: number) {

for (var e = this.entries[hashCode % this.entries.length]; e !== null; e = e.Next) {

if (e.HashCode === hashCode && StringTable.textCharArrayEquals(e.Text, key, start, len)) {

return e;

}

}

return null;

}

private addEntry(text: string, hashCode: number): string {

var index = hashCode % this.entries.length;

var e = new StringTableEntry(text, hashCode, this.entries[index]);

this.entries[index] = e;

// We grow when our load factor equals 1. I tried different load factors (like .75 and

// .5), however they seemed to have no effect on running time. With a load factor of 1

// we seem to get about 80% slot fill rate with an average of around 1.25 table entries

// per slot.

if (this.count === this.entries.length) {

this.grow();

}

this.count++;

return e.Text;

}

//private dumpStats() {

// var standardOut = Environment.standardOut;

// standardOut.WriteLine("----------------------")

// standardOut.WriteLine("String table stats");

// standardOut.WriteLine("Count : " + this.count);

// standardOut.WriteLine("Entries Length : " + this.entries.length);

// var longestSlot = 0;

// var occupiedSlots = 0;

// for (var i = 0; i < this.entries.length; i++) {

// if (this.entries[i] !== null) {

// occupiedSlots++;

// var current = this.entries[i];

// var slotCount = 0;

// while (current !== null) {

// slotCount++;

// current = current.Next;

// }

// longestSlot = MathPrototype.max(longestSlot, slotCount);

// }

// }

// standardOut.WriteLine("Occupied slots : " + occupiedSlots);

// standardOut.WriteLine("Longest slot : " + longestSlot);

// standardOut.WriteLine("Avg Length/Slot : " + (this.count / occupiedSlots));

// standardOut.WriteLine("----------------------");

//}

private grow(): void {

// this.dumpStats();

var newSize = Hash.expandPrime(this.entries.length);

var oldEntries = this.entries;

var newEntries: StringTableEntry[] = ArrayUtilities.createArray<StringTableEntry>(newSize, null);

this.entries = newEntries;

for (var i = 0; i < oldEntries.length; i++) {

var e = oldEntries[i];

while (e !== null) {

var newIndex = e.HashCode % newSize;

var tmp = e.Next;

e.Next = newEntries[newIndex];

newEntries[newIndex] = e;

e = tmp;

}

}

// this.dumpStats();

}

private static textCharArrayEquals(text: string, array: number[], start: number, length: number): boolean {

if (text.length !== length) {

return false;

}

var s = start;

for (var i = 0; i < length; i++) {

if (text.charCodeAt(i) !== array[s]) {

return false;

}

s++;

}

return true;

}

}

export var DefaultStringTable = new StringTable(DefaultStringTableCapacity);

}