1#
2#
3#            Nim's Runtime Library
4#        (c) Copyright 2015 Andreas Rumpf
5#
6#    See the file "copying.txt", included in this
7#    distribution, for details about the copyright.
8#
9
10## Shared string support for Nim.
11
12type
13  UncheckedCharArray = UncheckedArray[char]
14
15type
16  Buffer = ptr object
17    refcount: int
18    capacity, realLen: int
19    data: UncheckedCharArray
20
21  SharedString* = object ## A string that can be shared. Slicing is O(1).
22    buffer: Buffer
23    first, len: int
24
25proc decRef(b: Buffer) {.inline.} =
26  if atomicDec(b.refcount) <= 0:
27    deallocShared(b)
28
29proc incRef(b: Buffer) {.inline.} =
30  atomicInc(b.refcount)
31
32{.experimental.}
33
34proc `=destroy`*(s: SharedString) =
35  #echo "destroyed"
36  if not s.buffer.isNil:
37    decRef(s.buffer)
38
39when false:
40  proc `=copy`*(dest: var SharedString; src: SharedString) =
41    incRef(src.buffer)
42    if not dest.buffer.isNil:
43      decRef(dest.buffer)
44    dest.buffer = src.buffer
45    dest.first = src.first
46    dest.len = src.len
47
48proc len*(s: SharedString): int = s.len
49
50proc `[]`*(s: SharedString; i: Natural): char =
51  if i < s.len: result = s.buffer.data[i+s.first]
52  else: raise newException(IndexDefect, formatErrorIndexBound(i, s.len-1))
53
54proc `[]=`*(s: var SharedString; i: Natural; value: char) =
55  if i < s.len: s.buffer.data[i+s.first] = value
56  else: raise newException(IndexDefect, formatErrorIndexBound(i, s.len-1))
57
58proc `[]`*(s: SharedString; ab: HSlice[int, int]): SharedString =
59  #incRef(src.buffer)
60  if ab.a < s.len:
61    result.buffer = s.buffer
62    result.first = ab.a
63    result.len = min(s.len, ab.b - ab.a + 1)
64  # else: produce empty string ;-)
65
66proc newBuffer(cap, len: int): Buffer =
67  assert cap >= len
68  result = cast[Buffer](allocShared0(sizeof(int)*3 + cap))
69  result.refcount = 0
70  result.capacity = cap
71  result.realLen = len
72
73proc newSharedString*(len: Natural): SharedString =
74  if len != 0:
75    # optimization: Don't have an underlying buffer when 'len == 0'
76    result.buffer = newBuffer(len, len)
77  result.first = 0
78  result.len = len
79
80proc newSharedString*(s: string): SharedString =
81  let len = s.len
82  if len != 0:
83    # optimization: Don't have an underlying buffer when 'len == 0'
84    result.buffer = newBuffer(len, len)
85    copyMem(addr result.buffer.data[0], cstring(s), s.len)
86  result.first = 0
87  result.len = len
88
89when declared(atomicLoadN):
90  template load(x): untyped = atomicLoadN(addr x, ATOMIC_SEQ_CST)
91else:
92  # XXX Fixme
93  template load(x): untyped = x
94
95proc add*(s: var SharedString; t: cstring; len: Natural) =
96  if len == 0: return
97  let newLen = s.len + len
98  if s.buffer.isNil:
99    s.buffer = newBuffer(len, len)
100    copyMem(addr s.buffer.data[0], t, len)
101    s.len = len
102  elif newLen >= s.buffer.capacity or s.first != 0 or
103      s.len != s.buffer.realLen or load(s.buffer.refcount) > 1:
104    let oldBuf = s.buffer
105    s.buffer = newBuffer(max(s.buffer.capacity * 3 div 2, newLen), newLen)
106    copyMem(addr s.buffer.data[0], addr oldBuf.data[s.first], s.len)
107    copyMem(addr s.buffer.data[s.len], t, len)
108    decRef(oldBuf)
109  else:
110    copyMem(addr s.buffer.data[s.len], t, len)
111    s.buffer.realLen += len
112    s.len += len
113
114proc add*(s: var SharedString; t: string) =
115  s.add(t.cstring, t.len)
116
117proc rawData*(s: var SharedString): pointer =
118  if s.buffer.isNil: result = nil
119  else: result = addr s.buffer.data[s.first]
120
121proc add*(s: var SharedString; t: SharedString) =
122  if t.buffer.isNil: return
123  s.add(cast[cstring](addr s.buffer.data[s.first]), t.len)
124
125proc `$`*(s: SharedString): string =
126  result = newString(s.len)
127  if s.len > 0:
128    copyMem(addr result[0], addr s.buffer.data[s.first], s.len)
129
130proc `==`*(s: SharedString; t: string): bool =
131  if s.buffer.isNil: result = t.len == 0
132  else: result = t.len == s.len and equalMem(addr s.buffer.data[s.first],
133                                             cstring(t), t.len)
134
135proc `==`*(s, t: SharedString): bool =
136  if s.buffer.isNil: result = t.len == 0
137  else: result = t.len == s.len and equalMem(addr s.buffer.data[s.first],
138                                             addr t.buffer.data[t.first], t.len)
139
140iterator items*(s: SharedString): char =
141  let buf = s.buffer.data
142  let x = s.first
143  if buf != nil:
144    for i in 0..<s.len:
145      yield buf[i+x]
146
147import hashes
148
149proc hash*(s: SharedString): THash =
150  var h: THash = 0
151  for x in s: h = h !& x.hash
152  result = !$h
153