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