diff options
Diffstat (limited to 'lib/pure')
| -rw-r--r-- | lib/pure/asyncdispatch.nim | 12 | ||||
| -rw-r--r-- | lib/pure/collections/deques.nim | 266 | ||||
| -rw-r--r-- | lib/pure/collections/queues.nim | 4 | ||||
| -rw-r--r-- | lib/pure/collections/tables.nim | 40 | ||||
| -rw-r--r-- | lib/pure/terminal.nim | 49 |
5 files changed, 349 insertions, 22 deletions
diff --git a/lib/pure/asyncdispatch.nim b/lib/pure/asyncdispatch.nim index 06301b08d..01088c2e7 100644 --- a/lib/pure/asyncdispatch.nim +++ b/lib/pure/asyncdispatch.nim @@ -11,7 +11,7 @@ include "system/inclrtl" import os, oids, tables, strutils, times, heapqueue -import nativesockets, net, queues +import nativesockets, net, deques export Port, SocketFlag @@ -164,7 +164,7 @@ include includes/asyncfutures type PDispatcherBase = ref object of RootRef timers: HeapQueue[tuple[finishAt: float, fut: Future[void]]] - callbacks: Queue[proc ()] + callbacks: Deque[proc ()] proc processTimers(p: PDispatcherBase) {.inline.} = while p.timers.len > 0 and epochTime() >= p.timers[0].finishAt: @@ -172,7 +172,7 @@ proc processTimers(p: PDispatcherBase) {.inline.} = proc processPendingCallbacks(p: PDispatcherBase) = while p.callbacks.len > 0: - var cb = p.callbacks.dequeue() + var cb = p.callbacks.popFirst() cb() proc adjustedTimeout(p: PDispatcherBase, timeout: int): int {.inline.} = @@ -230,7 +230,7 @@ when defined(windows) or defined(nimdoc): result.ioPort = createIoCompletionPort(INVALID_HANDLE_VALUE, 0, 0, 1) result.handles = initSet[AsyncFD]() result.timers.newHeapQueue() - result.callbacks = initQueue[proc ()](64) + result.callbacks = initDeque[proc ()](64) var gDisp{.threadvar.}: PDispatcher ## Global dispatcher proc getGlobalDispatcher*(): PDispatcher = @@ -987,7 +987,7 @@ else: new result result.selector = newSelector() result.timers.newHeapQueue() - result.callbacks = initQueue[proc ()](64) + result.callbacks = initDeque[proc ()](64) var gDisp{.threadvar.}: PDispatcher ## Global dispatcher proc getGlobalDispatcher*(): PDispatcher = @@ -1417,7 +1417,7 @@ proc recvLine*(socket: AsyncFD): Future[string] {.async, deprecated.} = proc callSoon*(cbproc: proc ()) = ## Schedule `cbproc` to be called as soon as possible. ## The callback is called when control returns to the event loop. - getGlobalDispatcher().callbacks.enqueue(cbproc) + getGlobalDispatcher().callbacks.addLast(cbproc) proc runForever*() = ## Begins a never ending global dispatcher poll loop. diff --git a/lib/pure/collections/deques.nim b/lib/pure/collections/deques.nim new file mode 100644 index 000000000..c25429778 --- /dev/null +++ b/lib/pure/collections/deques.nim @@ -0,0 +1,266 @@ +# +# +# Nim's Runtime Library +# (c) Copyright 2012 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## Implementation of a `deque`:idx: (double-ended queue). +## The underlying implementation uses a ``seq``. +## +## None of the procs that get an individual value from the deque can be used +## on an empty deque. +## If compiled with `boundChecks` option, those procs will raise an `IndexError` +## on such access. This should not be relied upon, as `-d:release` will +## disable those checks and may return garbage or crash the program. +## +## As such, a check to see if the deque is empty is needed before any +## access, unless your program logic guarantees it indirectly. +## +## .. code-block:: Nim +## proc foo(a, b: Positive) = # assume random positive values for `a` and `b` +## var deq = initDeque[int]() # initializes the object +## for i in 1 ..< a: deq.addLast i # populates the deque +## +## if b < deq.len: # checking before indexed access +## echo "The element at index position ", b, " is ", deq[b] +## +## # The following two lines don't need any checking on access due to the +## # logic of the program, but that would not be the case if `a` could be 0. +## assert deq.peekFirst == 1 +## assert deq.peekLast == a +## +## while deq.len > 0: # checking if the deque is empty +## echo deq.removeLast() +## +## Note: For inter thread communication use +## a `Channel <channels.html>`_ instead. + +import math + +type + Deque*[T] = object + ## A double-ended queue backed with a ringed seq buffer. + data: seq[T] + head, tail, count, mask: int + +proc initDeque*[T](initialSize: int = 4): Deque[T] = + ## Create a new deque. + ## Optionally, the initial capacity can be reserved via `initialSize` as a + ## performance optimization. The length of a newly created deque will still + ## be 0. + ## + ## `initialSize` needs to be a power of two. If you need to accept runtime + ## values for this you could use the ``nextPowerOfTwo`` proc from the + ## `math <math.html>`_ module. + assert isPowerOfTwo(initialSize) + result.mask = initialSize-1 + newSeq(result.data, initialSize) + +proc len*[T](deq: Deque[T]): int {.inline.} = + ## Return the number of elements of `deq`. + result = deq.count + +template emptyCheck(deq) = + # Bounds check for the regular deque access. + when compileOption("boundChecks"): + if unlikely(deq.count < 1): + raise newException(IndexError, "Empty deque.") + +template xBoundsCheck(deq, i) = + # Bounds check for the array like accesses. + when compileOption("boundChecks"): # d:release should disable this. + if unlikely(i >= deq.count): # x < deq.low is taken care by the Natural parameter + raise newException(IndexError, + "Out of bounds: " & $i & " > " & $(deq.count - 1)) + +proc `[]`*[T](deq: Deque[T], i: Natural) : T {.inline.} = + ## Access the i-th element of `deq` by order from first to last. + ## deq[0] is the first, deq[^1] is the last. + xBoundsCheck(deq, i) + return deq.data[(deq.first + i) and deq.mask] + +proc `[]`*[T](deq: var Deque[T], i: Natural): var T {.inline.} = + ## Access the i-th element of `deq` and returns a mutable + ## reference to it. + xBoundsCheck(deq, i) + return deq.data[(deq.head + i) and deq.mask] + +proc `[]=`* [T] (deq: var Deque[T], i: Natural, val : T) {.inline.} = + ## Change the i-th element of `deq`. + xBoundsCheck(deq, i) + deq.data[(deq.head + i) and deq.mask] = val + +iterator items*[T](deq: Deque[T]): T = + ## Yield every element of `deq`. + var i = deq.head + for c in 0 ..< deq.count: + yield deq.data[i] + i = (i + 1) and deq.mask + +iterator mitems*[T](deq: var Deque[T]): var T = + ## Yield every element of `deq`. + var i = deq.head + for c in 0 ..< deq.count: + yield deq.data[i] + i = (i + 1) and deq.mask + +iterator pairs*[T](deq: Deque[T]): tuple[key: int, val: T] = + ## Yield every (position, value) of `deq`. + var i = deq.head + for c in 0 ..< deq.count: + yield (c, deq.data[i]) + i = (i + 1) and deq.mask + +proc contains*[T](deq: Deque[T], item: T): bool {.inline.} = + ## Return true if `item` is in `deq` or false if not found. Usually used + ## via the ``in`` operator. It is the equivalent of ``deq.find(item) >= 0``. + ## + ## .. code-block:: Nim + ## if x in q: + ## assert q.contains x + for e in deq: + if e == item: return true + return false + +proc expandIfNeeded[T](deq: var Deque[T]) = + var cap = deq.mask + 1 + if unlikely(deq.count >= cap): + var n = newSeq[T](cap * 2) + for i, x in deq: # don't use copyMem because the GC and because it's slower. + shallowCopy(n[i], x) + shallowCopy(deq.data, n) + deq.mask = cap * 2 - 1 + deq.tail = deq.count + deq.head = 0 + +proc addFirst*[T](deq: var Deque[T], item: T) = + ## Add an `item` to the beginning of the `deq`. + expandIfNeeded(deq) + inc deq.count + deq.head = (deq.head - 1) and deq.mask + deq.data[deq.head] = item + +proc addLast*[T](deq: var Deque[T], item: T) = + ## Add an `item` to the end of the `deq`. + expandIfNeeded(deq) + inc deq.count + deq.data[deq.tail] = item + deq.tail = (deq.tail + 1) and deq.mask + +proc peekFirst*[T](deq: Deque[T]): T {.inline.}= + ## Returns the first element of `deq`, but does not remove it from the deque. + emptyCheck(deq) + result = deq.data[deq.head] + +proc peekLast*[T](deq: Deque[T]): T {.inline.} = + ## Returns the last element of `deq`, but does not remove it from the deque. + emptyCheck(deq) + result = deq.data[(deq.tail - 1) and deq.mask] + +proc default[T](t: typedesc[T]): T {.inline.} = discard +proc popFirst*[T](deq: var Deque[T]): T {.inline, discardable.} = + ## Remove and returns the first element of the `deq`. + emptyCheck(deq) + dec deq.count + result = deq.data[deq.head] + deq.data[deq.head] = default(type(result)) + deq.head = (deq.head + 1) and deq.mask + +proc popLast*[T](deq: var Deque[T]): T {.inline, discardable.} = + ## Remove and returns the last element of the `deq`. + emptyCheck(deq) + dec deq.count + deq.tail = (deq.tail - 1) and deq.mask + result = deq.data[deq.tail] + deq.data[deq.tail] = default(type(result)) + +proc `$`*[T](deq: Deque[T]): string = + ## Turn a deque into its string representation. + result = "[" + for x in deq: + if result.len > 1: result.add(", ") + result.add($x) + result.add("]") + +when isMainModule: + var deq = initDeque[int](1) + deq.addLast(4) + deq.addFirst(9) + deq.addFirst(123) + var first = deq.popFirst() + deq.addLast(56) + assert(deq.peekLast() == 56) + deq.addLast(6) + assert(deq.peekLast() == 6) + var second = deq.popFirst() + deq.addLast(789) + assert(deq.peekLast() == 789) + + assert first == 123 + assert second == 9 + assert($deq == "[4, 56, 6, 789]") + + assert deq[0] == deq.peekFirst and deq.peekFirst == 4 + assert deq[^1] == deq.peekLast and deq.peekLast == 789 + deq[0] = 42 + deq[^1] = 7 + + assert 6 in deq and 789 notin deq + assert deq.find(6) >= 0 + assert deq.find(789) < 0 + + for i in -2 .. 10: + if i in deq: + assert deq.contains(i) and deq.find(i) >= 0 + else: + assert(not deq.contains(i) and deq.find(i) < 0) + + when compileOption("boundChecks"): + try: + echo deq[99] + assert false + except IndexError: + discard + + try: + assert deq.len == 4 + for i in 0 ..< 5: deq.popFirst() + assert false + except IndexError: + discard + + # grabs some types of resize error. + deq = initDeque[int]() + for i in 1 .. 4: deq.addLast i + deq.popFirst() + deq.popLast() + for i in 5 .. 8: deq.addFirst i + assert $deq == "[8, 7, 6, 5, 2, 3]" + + # Similar to proc from the documentation example + proc foo(a, b: Positive) = # assume random positive values for `a` and `b`. + var deq = initDeque[int]() + assert deq.len == 0 + for i in 1 .. a: deq.addLast i + + if b < deq.len: # checking before indexed access. + assert deq[b] == b + 1 + + # The following two lines don't need any checking on access due to the logic + # of the program, but that would not be the case if `a` could be 0. + assert deq.peekFirst == 1 + assert deq.peekLast == a + + while deq.len > 0: # checking if the deque is empty + assert deq.popFirst() > 0 + + #foo(0,0) + foo(8,5) + foo(10,9) + foo(1,1) + foo(2,1) + foo(1,5) + foo(3,2) \ No newline at end of file diff --git a/lib/pure/collections/queues.nim b/lib/pure/collections/queues.nim index 399e4d413..e4d7eeef1 100644 --- a/lib/pure/collections/queues.nim +++ b/lib/pure/collections/queues.nim @@ -39,8 +39,10 @@ import math +{.warning: "`queues` module is deprecated - use `deques` instead".} + type - Queue*[T] = object ## A queue. + Queue* {.deprecated.} [T] = object ## A queue. data: seq[T] rd, wr, count, mask: int diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index dfd822852..e6e72d9ed 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -778,20 +778,22 @@ proc sort*[A, B](t: OrderedTableRef[A, B], proc del*[A, B](t: var OrderedTable[A, B], key: A) = ## deletes `key` from ordered hash table `t`. O(n) comlexity. - var prev = -1 + var n: OrderedKeyValuePairSeq[A, B] + newSeq(n, len(t.data)) + var h = t.first + t.first = -1 + t.last = -1 + swap(t.data, n) let hc = genHash(key) - forAllOrderedPairs: - if t.data[h].hcode == hc: - if t.first == h: - t.first = t.data[h].next + while h >= 0: + var nxt = n[h].next + if isFilled(n[h].hcode): + if n[h].hcode == hc and n[h].key == key: + dec t.counter else: - t.data[prev].next = t.data[h].next - var zeroValue : type(t.data[h]) - t.data[h] = zeroValue - dec t.counter - break - else: - prev = h + var j = -1 - rawGetKnownHC(t, n[h].key, n[h].hcode) + rawInsert(t, t.data, n[h].key, n[h].val, n[h].hcode, j) + h = nxt proc del*[A, B](t: var OrderedTableRef[A, B], key: A) = ## deletes `key` from ordered hash table `t`. O(n) comlexity. @@ -1157,6 +1159,20 @@ when isMainModule: doAssert(prev < i) prev = i + block: # Deletion from OrderedTable should account for collision groups. See issue #5057. + # The bug is reproducible only with exact keys + const key1 = "boy_jackpot.inGamma" + const key2 = "boy_jackpot.outBlack" + + var t = { + key1: 0, + key2: 0 + }.toOrderedTable() + + t.del(key1) + assert(t.len == 1) + assert(key2 in t) + var t1 = initCountTable[string]() t2 = initCountTable[string]() diff --git a/lib/pure/terminal.nim b/lib/pure/terminal.nim index d4734c3e3..16cf91d40 100644 --- a/lib/pure/terminal.nim +++ b/lib/pure/terminal.nim @@ -13,6 +13,8 @@ ## Windows API. ## Changing the style is permanent even after program termination! Use the ## code ``system.addQuitProc(resetAttributes)`` to restore the defaults. +## Similarly, if you hide the cursor, make sure to unhide it with +## ``showCursor`` before quitting. import macros @@ -29,6 +31,8 @@ when defined(windows): BACKGROUND_GREEN = 32 BACKGROUND_RED = 64 BACKGROUND_INTENSITY = 128 + FOREGROUND_RGB = FOREGROUND_RED or FOREGROUND_GREEN or FOREGROUND_BLUE + BACKGROUND_RGB = BACKGROUND_RED or BACKGROUND_GREEN or BACKGROUND_BLUE type SHORT = int16 @@ -49,6 +53,10 @@ when defined(windows): srWindow: SMALL_RECT dwMaximumWindowSize: COORD + CONSOLE_CURSOR_INFO = object + dwSize: DWORD + bVisible: WINBOOL + proc duplicateHandle(hSourceProcessHandle: HANDLE, hSourceHandle: HANDLE, hTargetProcessHandle: HANDLE, lpTargetHandle: ptr HANDLE, dwDesiredAccess: DWORD, bInheritHandle: WINBOOL, @@ -60,6 +68,14 @@ when defined(windows): lpConsoleScreenBufferInfo: ptr CONSOLE_SCREEN_BUFFER_INFO): WINBOOL{.stdcall, dynlib: "kernel32", importc: "GetConsoleScreenBufferInfo".} + proc getConsoleCursorInfo(hConsoleOutput: HANDLE, + lpConsoleCursorInfo: ptr CONSOLE_CURSOR_INFO): WINBOOL{. + stdcall, dynlib: "kernel32", importc: "GetConsoleCursorInfo".} + + proc setConsoleCursorInfo(hConsoleOutput: HANDLE, + lpConsoleCursorInfo: ptr CONSOLE_CURSOR_INFO): WINBOOL{. + stdcall, dynlib: "kernel32", importc: "SetConsoleCursorInfo".} + proc terminalWidthIoctl*(handles: openArray[Handle]): int = var csbi: CONSOLE_SCREEN_BUFFER_INFO for h in handles: @@ -179,6 +195,30 @@ else: return w return 80 #Finally default to venerable value +when defined(windows): + proc setCursorVisibility(f: File, visible: bool) = + var ccsi: CONSOLE_CURSOR_INFO + let h = conHandle(f) + if getConsoleCursorInfo(h, addr(ccsi)) == 0: + raiseOSError(osLastError()) + ccsi.bVisible = if visible: 1 else: 0 + if setConsoleCursorInfo(h, addr(ccsi)) == 0: + raiseOSError(osLastError()) + +proc hideCursor*(f: File) = + ## Hides the cursor. + when defined(windows): + setCursorVisibility(f, false) + else: + f.write("\e[?25l") + +proc showCursor*(f: File) = + ## Shows the cursor. + when defined(windows): + setCursorVisibility(f, true) + else: + f.write("\e[?25h") + proc setCursorPos*(f: File, x, y: int) = ## Sets the terminal's cursor to the (x,y) position. ## (0,0) is the upper left of the screen. @@ -369,12 +409,13 @@ proc setStyle*(f: File, style: set[Style]) = ## Sets the terminal style. when defined(windows): let h = conHandle(f) + var old = getAttributes(h) and (FOREGROUND_RGB or BACKGROUND_RGB) var a = 0'i16 if styleBright in style: a = a or int16(FOREGROUND_INTENSITY) if styleBlink in style: a = a or int16(BACKGROUND_INTENSITY) if styleReverse in style: a = a or 0x4000'i16 # COMMON_LVB_REVERSE_VIDEO if styleUnderscore in style: a = a or 0x8000'i16 # COMMON_LVB_UNDERSCORE - discard setConsoleTextAttribute(h, a) + discard setConsoleTextAttribute(h, old or a) else: for s in items(style): f.write("\e[" & $ord(s) & 'm') @@ -423,7 +464,7 @@ proc setForegroundColor*(f: File, fg: ForegroundColor, bright=false) = ## Sets the terminal's foreground color. when defined(windows): let h = conHandle(f) - var old = getAttributes(h) and not 0x0007 + var old = getAttributes(h) and not FOREGROUND_RGB if bright: old = old or FOREGROUND_INTENSITY const lookup: array[ForegroundColor, int] = [ @@ -445,7 +486,7 @@ proc setBackgroundColor*(f: File, bg: BackgroundColor, bright=false) = ## Sets the terminal's background color. when defined(windows): let h = conHandle(f) - var old = getAttributes(h) and not 0x0070 + var old = getAttributes(h) and not BACKGROUND_RGB if bright: old = old or BACKGROUND_INTENSITY const lookup: array[BackgroundColor, int] = [ @@ -558,6 +599,8 @@ proc getch*(): char = discard fd.tcsetattr(TCSADRAIN, addr oldMode) # Wrappers assuming output to stdout: +template hideCursor*() = hideCursor(stdout) +template showCursor*() = showCursor(stdout) template setCursorPos*(x, y: int) = setCursorPos(stdout, x, y) template setCursorXPos*(x: int) = setCursorXPos(stdout, x) when defined(windows): |