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
|
#
#
# Nim's Runtime Library
# (c) Copyright 2015 Andreas Rumpf
#
# See the file "copying.txt", included in this
# distribution, for details about the copyright.
#
## Shared string support for Nim.
const ArrayDummySize = when defined(cpu16): 10_000 else: 100_000_000
type
UncheckedCharArray {.unchecked.} = array[0..ArrayDummySize, char]
type
Buffer = ptr object
refcount: int
capacity, realLen: int
data: UncheckedCharArray
SharedString* = object ## A string that can be shared. Slicing is O(1).
buffer: Buffer
first, len: int
proc decRef(b: Buffer) {.inline.} =
if atomicDec(b.refcount) <= 0:
deallocShared(b)
proc incRef(b: Buffer) {.inline.} =
atomicInc(b.refcount)
{.experimental.}
proc `=destroy`*(s: SharedString) =
#echo "destroyed"
if not s.buffer.isNil:
decRef(s.buffer)
when false:
proc `=`*(dest: var SharedString; src: SharedString) =
incRef(src.buffer)
if not dest.buffer.isNil:
decRef(dest.buffer)
dest.buffer = src.buffer
dest.first = src.first
dest.len = src.len
proc len*(s: SharedString): int = s.len
proc `[]`*(s: SharedString; i: Natural): char =
if i < s.len: result = s.buffer.data[i+s.first]
else: raise newException(IndexError, "index out of bounds")
proc `[]=`*(s: var SharedString; i: Natural; value: char) =
if i < s.len: s.buffer.data[i+s.first] = value
else: raise newException(IndexError, "index out of bounds")
proc `[]`*(s: SharedString; ab: Slice[int]): SharedString =
#incRef(src.buffer)
if ab.a < s.len:
result.buffer = s.buffer
result.first = ab.a
result.len = min(s.len, ab.b - ab.a + 1)
# else: produce empty string ;-)
proc newBuffer(cap, len: int): Buffer =
assert cap >= len
result = cast[Buffer](allocShared0(sizeof(int)*3 + cap))
result.refcount = 0
result.capacity = cap
result.realLen = len
proc newSharedString*(len: Natural): SharedString =
if len != 0:
# optimization: Don't have an underlying buffer when 'len == 0'
result.buffer = newBuffer(len, len)
result.first = 0
result.len = len
proc newSharedString*(s: string): SharedString =
let len = s.len
if len != 0:
# optimization: Don't have an underlying buffer when 'len == 0'
result.buffer = newBuffer(len, len)
copyMem(addr result.buffer.data[0], cstring(s), s.len)
result.first = 0
result.len = len
when declared(atomicLoadN):
template load(x): expr = atomicLoadN(addr x, ATOMIC_SEQ_CST)
else:
# XXX Fixme
template load(x): expr = x
proc add*(s: var SharedString; t: cstring; len: Natural) =
if len == 0: return
let newLen = s.len + len
if s.buffer.isNil:
s.buffer = newBuffer(len, len)
copyMem(addr s.buffer.data[0], t, len)
s.len = len
elif newLen >= s.buffer.capacity or s.first != 0 or
s.len != s.buffer.realLen or load(s.buffer.refcount) > 1:
let oldBuf = s.buffer
s.buffer = newBuffer(max(s.buffer.capacity * 3 div 2, newLen), newLen)
copyMem(addr s.buffer.data[0], addr oldBuf.data[s.first], s.len)
copyMem(addr s.buffer.data[s.len], t, len)
decRef(oldBuf)
else:
copyMem(addr s.buffer.data[s.len], t, len)
s.buffer.realLen += len
s.len += len
proc add*(s: var SharedString; t: string) =
s.add(t.cstring, t.len)
proc rawData*(s: var SharedString): pointer =
if s.buffer.isNil: result = nil
else: result = addr s.buffer.data[s.first]
proc add*(s: var SharedString; t: SharedString) =
if t.buffer.isNil: return
s.add(cast[cstring](addr s.buffer.data[s.first]), t.len)
proc `$`*(s: SharedString): string =
result = newString(s.len)
if s.len > 0:
copyMem(addr result[0], addr s.buffer.data[s.first], s.len)
proc `==`*(s: SharedString; t: string): bool =
if s.buffer.isNil: result = t.len == 0
else: result = t.len == s.len and equalMem(addr s.buffer.data[s.first],
cstring(t), t.len)
proc `==`*(s, t: SharedString): bool =
if s.buffer.isNil: result = t.len == 0
else: result = t.len == s.len and equalMem(addr s.buffer.data[s.first],
addr t.buffer.data[t.first], t.len)
iterator items*(s: SharedString): char =
let buf = s.buffer.data
let x = s.first
if buf != nil:
for i in 0..<s.len:
yield buf[i+x]
import hashes
proc hash*(s: SharedString): THash =
var h: THash = 0
for x in s: h = h !& x.hash
result = !$h
|