scikit-image

1
"""FIFO queue that preserves history until explicitly cleared.
2

3
.. warning::
4

5
    One must define the type "QueueItem" before including this file. This makes
6
    it possible to store different types as QueueItems.
7

8
This queue can be operated like a class. The structure stores the state of the
9
instance and the contained functions act as instance methods. The important
10
distinction compared to normal queues is that popping an element doesn't remove
11
it internally. Thus unless the queue's internal buffer is explicitly cleared
12
(see `queue_clear`) popped items can be restored at anytime using
13
`queue_restore`.
14

15
A possible application of this special functionality might be when actions
16
performed on popped items must be undone at a later stage.
17

18
Example
19
-------
20
::
21

22
    cdef QueueWithHistory queue
23
    cdef QueueItem item
24

25
    queue_init(&queue, 5)
26
    try:
27
        for i in range(10):
28
            item = <QueueItem>i
29
            queue_push(&queue, &item)
30

31
        while queue_pop(&queue, &item):
32
            print(item)  # Prints 0 to 9
33

34
        queue_restore(&queue)
35

36
        while queue_pop(&queue, &item):
37
            print(item)  # Prints 0 to 9 again
38
    finally:
39
        queue_exit(&queue)
40
"""
41

42
from libc.stdlib cimport malloc, realloc, free
43

44

45
# Store state of queue
46
cdef struct QueueWithHistory:
47
    QueueItem* _buffer_ptr
48
    Py_ssize_t _buffer_size  # Maximal number of elements the buffer can store
49
    Py_ssize_t _index_valid  # Index to most recently inserted item
50
    Py_ssize_t _index_consumed  # Index to most recently consumed item
51

52

53
cdef inline void queue_init(QueueWithHistory* self, Py_ssize_t buffer_size) noexcept nogil:
54
    """Initialize the queue and its buffer size.
55

56
    The size is defined as the number of queue items to fit into the initial
57
    buffer, thus its true memory size is `buffer_size * sizeof(QueueItem)`. Be
58
    sure to call `queue_exit` after calling this function to free the allocated
59
    memory!
60
    """
61
    self._buffer_ptr = <QueueItem*>malloc(buffer_size * sizeof(QueueItem))
62
    if not self._buffer_ptr:
63
        with gil:
64
            raise MemoryError("couldn't allocate buffer")
65
    self._buffer_size = buffer_size
66
    self._index_consumed = -1
67
    self._index_valid = -1
68

69

70
cdef inline void queue_push(QueueWithHistory* self, QueueItem* item_ptr) noexcept nogil:
71
    """Enqueue a new item."""
72
    self._index_valid += 1
73
    if self._buffer_size <= self._index_valid:
74
        _queue_grow_buffer(self)
75
    self._buffer_ptr[self._index_valid] = item_ptr[0]
76

77

78
cdef inline unsigned char queue_pop(QueueWithHistory* self,
79
                                    QueueItem* item_ptr) noexcept nogil:
80
    """If not empty pop an item and return 1 otherwise return 0.
81

82
    The item is still preserved in the internal buffer and can be restored with
83
    `queue_restore`. To truly clear the internal buffer use `queue_clear`.
84
    """
85
    if 0 <= self._index_consumed + 1 <= self._index_valid:
86
        self._index_consumed += 1
87
        item_ptr[0] = self._buffer_ptr[self._index_consumed]
88
        return 1
89
    return 0
90

91

92
cdef inline void queue_restore(QueueWithHistory* self) noexcept nogil:
93
    """Restore all consumed items to the queue.
94

95
    The order of the restored queue is the same as previous one, meaning older
96
    items are popped first.
97
    """
98
    self._index_consumed = -1
99

100

101
cdef inline void queue_clear(QueueWithHistory* self) noexcept nogil:#
102
    """Remove all consumable items.
103

104
    After this the old items can't be restored with `queue_restore`.
105
    """
106
    self._index_consumed = -1
107
    self._index_valid = -1
108

109

110
cdef inline void queue_exit(QueueWithHistory* self) noexcept nogil:
111
    """Free the buffer of the queue.
112

113
    Don't use the queue after this command unless `queue_init` is called again.
114
    """
115
    free(self._buffer_ptr)
116

117

118
cdef inline int _queue_grow_buffer(QueueWithHistory* self) except -1 nogil:
119
    """Double the memory used for the buffer."""
120
    cdef QueueItem* new_buffer
121
    self._buffer_size *= 2
122
    new_buffer_ptr = <QueueItem*>realloc(
123
        self._buffer_ptr,
124
        self._buffer_size * sizeof(QueueItem)
125
    )
126
    if not new_buffer_ptr:
127
        with gil:
128
            raise MemoryError("couldn't reallocate buffer")
129
    self._buffer_ptr = new_buffer_ptr
130

131
    return 0
132