1#cython: embedsignature=True
2#cython: language_level=2
3# Copyright (c) 2015-2019 by Farsight Security, Inc.
4#
5# Licensed under the Apache License, Version 2.0 (the "License");
6# you may not use this file except in compliance with the License.
7# You may obtain a copy of the License at
8#
9#    http://www.apache.org/licenses/LICENSE-2.0
10#
11# Unless required by applicable law or agreed to in writing, software
12# distributed under the License is distributed on an "AS IS" BASIS,
13# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14# See the License for the specific language governing permissions and
15# limitations under the License.
16include "mtbl.pxi"
17import threading
18
19DEFAULT_SORTER_TEMP_DIR = '/var/tmp'
20DEFAULT_SORTER_MEMORY = 1073741824
21
22COMPRESSION_NONE = MTBL_COMPRESSION_NONE
23COMPRESSION_SNAPPY = MTBL_COMPRESSION_SNAPPY
24COMPRESSION_ZLIB = MTBL_COMPRESSION_ZLIB
25COMPRESSION_LZ4 = MTBL_COMPRESSION_LZ4
26COMPRESSION_LZ4HC = MTBL_COMPRESSION_LZ4HC
27
28class KeyOrderError(Exception):
29    pass
30
31class TableClosedException(Exception):
32    pass
33
34class UnknownCompressionTypeException(Exception):
35    pass
36
37class UninitializedException(Exception):
38    pass
39
40class VarintDecodingError(Exception):
41    pass
42
43ImmutableError = TypeError('object does not support mutation')
44
45def to_bytes(value):
46    """
47    to_bytes(v) -> return a bytes object from a bytes, str, and bytearray; raises a ValueError if the conversion fails
48    """
49    # bytes needs to be before str because in py2 str is already bytes
50    if isinstance(value, bytes):
51        b = value
52    elif isinstance(value, str):
53        b = value.encode()
54    elif isinstance(value, bytearray):
55        b = bytes(value)
56    else:
57        raise ValueError('Only str, bytes, and bytearrays are allowed.')
58    return b
59
60def from_bytes(bytes value, bool return_bytes=False):
61    """
62    from_bytes(v) -> given bytes returns str by UTF-8 decoding it. returns the bytes unchanged if decoding
63    fails
64
65    Keyword arguments:
66    return_bytes -- whether to return data as bytes without attempting to convert it to str (default False)
67    """
68    if return_bytes:
69        return value
70
71    if isinstance(value, str): #py2
72        v = value
73    else: #py3
74        try:
75            v = value.decode('utf-8')
76        except UnicodeDecodeError:
77            v = value
78    return v
79
80def varint_length(uint64_t value):
81    """varint_length(v) -> number of bytes the integer v would require in varint encoding."""
82    return mtbl_varint_length(value)
83
84def varint_length_packed(py_buf):
85    """varint_length_packed(b) -> number of varint-packed bytes at the start of b."""
86    cdef uint8_t *buf
87    cdef Py_ssize_t len_buf
88    cdef size_t sz
89    len_buf = len(py_buf)
90    py_buf = to_bytes(py_buf)
91    buf = py_buf
92    with nogil:
93        sz = mtbl_varint_length_packed(buf, len_buf)
94    if sz == 0:
95        raise VarintDecodingError
96    return sz
97
98def varint_encode(long v):
99    """varint_encode(v) -> encode integer v using packed variable-width encoding."""
100    cdef uint8_t buf[10]
101    cdef size_t sz
102    with nogil:
103        sz = mtbl_varint_encode64(buf, v)
104    rv = buf[:sz]
105    return <bytes> buf[:sz]
106
107def varint_decode(py_buf):
108    """varint_decode(b) -> decode variable-width packed integer from b"""
109    cdef uint64_t val
110    cdef const uint8_t *buf
111    cdef Py_ssize_t len_buf
112    cdef size_t bytes_read
113
114    # This allows the function to accept strings like '\x01' to '\x7f' in py3
115    py_buf = to_bytes(py_buf)
116
117    buf = <uint8_t *> py_buf
118    len_buf = len(py_buf)
119    if mtbl_varint_length_packed(buf, len_buf) == 0:
120        raise VarintDecodingError
121    with nogil:
122        mtbl_varint_decode64(buf, &val)
123    return val
124
125@cython.internal
126cdef class iterkeys(object):
127    cdef mtbl_iter *_instance
128    cdef object _parent
129    cdef bool return_bytes
130
131    def __cinit__(self):
132        self._instance = NULL
133
134    def __init__(self, object _parent, bool return_bytes=False):
135        self._parent = _parent
136        self.return_bytes = return_bytes
137
138    def __dealloc__(self):
139        with nogil:
140            mtbl_iter_destroy(&self._instance)
141
142    def __iter__(self):
143        return self
144
145    def __next__(self):
146        cdef mtbl_res res
147        cdef const uint8_t *key
148        cdef const uint8_t *val
149        cdef size_t len_key
150        cdef size_t len_val
151
152        if self._instance == NULL:
153            raise StopIteration
154
155        with nogil:
156            res = mtbl_iter_next(self._instance, &key, &len_key, &val, &len_val)
157        if res == mtbl_res_failure:
158            raise StopIteration
159
160        return from_bytes(key[:len_key], self.return_bytes)
161@cython.internal
162cdef class itervalues(object):
163    cdef mtbl_iter *_instance
164    cdef object _parent
165    cdef bool return_bytes
166
167    def __cinit__(self):
168        self._instance = NULL
169
170    def __init__(self, object _parent, bool return_bytes=False):
171        self._parent = _parent
172        self.return_bytes = return_bytes
173
174    def __dealloc__(self):
175        with nogil:
176            mtbl_iter_destroy(&self._instance)
177
178    def __iter__(self):
179        return self
180
181    def __next__(self):
182        cdef mtbl_res res
183        cdef const uint8_t *key
184        cdef const uint8_t *val
185        cdef size_t len_key
186        cdef size_t len_val
187
188        if self._instance == NULL:
189            raise StopIteration
190
191        with nogil:
192            res = mtbl_iter_next(self._instance, &key, &len_key, &val, &len_val)
193        if res == mtbl_res_failure:
194            raise StopIteration
195        return from_bytes(val[:len_val], self.return_bytes)
196
197@cython.internal
198cdef class iteritems(object):
199    cdef mtbl_iter *_instance
200    cdef object _parent
201    cdef bool return_bytes
202
203    def __cinit__(self):
204        self._instance = NULL
205
206    def __init__(self, object _parent, bool return_bytes=False):
207        self._parent = _parent
208        self.return_bytes = return_bytes
209
210    def __dealloc__(self):
211        with nogil:
212            mtbl_iter_destroy(&self._instance)
213
214    def __iter__(self):
215        return self
216
217    def __next__(self):
218        cdef mtbl_res res
219        cdef const uint8_t *key
220        cdef const uint8_t *val
221        cdef size_t len_key
222        cdef size_t len_val
223
224        if self._instance == NULL:
225            raise StopIteration
226
227        with nogil:
228            res = mtbl_iter_next(self._instance, &key, &len_key, &val, &len_val)
229
230        if res == mtbl_res_failure:
231            raise StopIteration
232
233        return (from_bytes(key[:len_key], self.return_bytes), from_bytes(val[:len_val], self.return_bytes))
234
235cdef get_iterkeys(parent, mtbl_iter *instance, bool return_bytes=False):
236    it = iterkeys(parent, return_bytes)
237    it._instance = instance
238    return it
239
240cdef get_itervalues(parent, mtbl_iter *instance, bool return_bytes=False):
241    it = itervalues(parent, return_bytes)
242    it._instance = instance
243    return it
244
245cdef get_iteritems(parent, mtbl_iter *instance, bool return_bytes=False):
246    it = iteritems(parent, return_bytes)
247    it._instance = instance
248    return it
249
250@cython.internal
251cdef class DictMixin(object):
252    def __iter__(self):
253        return self.iterkeys()
254
255    def iter(self):
256        return self.iterkeys()
257
258    def items(self):
259        """D.items() -> list of D's (key, value) pairs, as 2-tuples"""
260        return [ (k, v) for k, v in self.iteritems() ]
261
262    def keys(self):
263        """D.keys() -> list of D's keys"""
264        return [ k for k in self.iterkeys() ]
265
266    def values(self):
267        """D.values() -> list of D's values"""
268        return [ v for v in self.itervalues() ]
269
270    def __delitem__(self, key):
271        """will raise ImmutableError"""
272        raise ImmutableError
273
274    def __setitem__(self, key, value):
275        """will raise ImmutableError"""
276        raise ImmutableError
277
278    def pop(self, *a, **b):
279        """will raise ImmutableError"""
280        raise ImmutableError
281
282    def popitem(self):
283        """will raise ImmutableError"""
284        raise ImmutableError
285
286    def update(self, *a, **b):
287        """will raise ImmutableError"""
288        raise ImmutableError
289
290cdef class reader(DictMixin):
291    """
292    reader(fname) -> new MTBL reader initialized from file fname
293
294    Keyword arguments:
295    verify_checksums -- whether to verify data block checksums (default False)
296    return_bytes -- whether to return data as bytes without attempting to convert it to str (default False)
297    """
298    cdef mtbl_reader *_instance
299    cdef bool return_bytes
300
301    def __cinit__(self):
302        self._instance = NULL
303
304    def __dealloc__(self):
305        with nogil:
306            mtbl_reader_destroy(&self._instance)
307
308    def __init__(self, str fname, bool verify_checksums=False, bool return_bytes=False):
309        cdef mtbl_reader_options *opt
310        cdef bytes tfn_bytes = fname.encode('utf-8')
311        cdef char *tfn = tfn_bytes
312        self.return_bytes = return_bytes
313
314        with nogil:
315            opt = mtbl_reader_options_init()
316            mtbl_reader_options_set_verify_checksums(opt, verify_checksums)
317            self._instance = mtbl_reader_init(tfn, opt)
318            mtbl_reader_options_destroy(&opt)
319
320        if (self._instance == NULL):
321            raise IOError("unable to open file: '%s'" % fname)
322
323    cdef check_initialized(self):
324        if self._instance == NULL:
325            raise UninitializedException
326
327    def iterkeys(self):
328        """R.iterkeys() -> an iterator over the keys of R."""
329        self.check_initialized()
330        return get_iterkeys(self, mtbl_source_iter(mtbl_reader_source(self._instance)), self.return_bytes)
331
332    def itervalues(self):
333        """R.itervalues() -> an iterator over the values of R."""
334        self.check_initialized()
335        return get_itervalues(self, mtbl_source_iter(mtbl_reader_source(self._instance)), self.return_bytes)
336
337    def iteritems(self):
338        """R.iteritems() -> an iterator over the (key, value) items of R."""
339        self.check_initialized()
340        return get_iteritems(self, mtbl_source_iter(mtbl_reader_source(self._instance)), self.return_bytes)
341
342    def __contains__(self, py_key):
343        """R.__contains__(k) -> True if R has a key k, else False"""
344        try:
345            self.__getitem__(py_key)
346            return True
347        except KeyError:
348            pass
349        return False
350
351    def has_key(self, py_key):
352        """R.has_key(k) -> True if R has a key k, else False."""
353        return self.__contains__(py_key)
354
355    def get(self, py_key, default=None):
356        """R.get(k[,d]) -> R[k] if k in R, else d.  d defaults to None."""
357        try:
358            return self.__getitem__(py_key)
359        except KeyError:
360            pass
361        return default
362
363    def get_range(self, py_key0, py_key1):
364        """
365        R.get_range(key0, key1) -> an iterator over all (key, value) items in R where key is
366        between key0 and key1 inclusive.
367        """
368        cdef mtbl_res res
369        cdef const uint8_t *key0
370        cdef const uint8_t *key1
371        cdef size_t len_key0
372        cdef size_t len_key1
373
374        self.check_initialized()
375
376        t = to_bytes(py_key0)
377        key0 = <uint8_t *> t
378        len_key0 = len(t)
379        t = to_bytes(py_key1)
380        key1 = <uint8_t *> t
381        len_key1 = len(t)
382
383        return get_iteritems(self, mtbl_source_get_range(
384            mtbl_reader_source(self._instance), key0, len_key0, key1, len_key1), self.return_bytes)
385
386    def get_prefix(self, py_key):
387        """
388        R.get_prefix(key_prefix) -> an iterator over all (key, value) items in R where key
389        begins with key_prefix.
390        """
391        cdef mtbl_res res
392        cdef const uint8_t *key
393        cdef size_t len_key
394
395        self.check_initialized()
396
397        t = to_bytes(py_key)
398        key = <uint8_t *> t
399        len_key = len(t)
400
401        return get_iteritems(self, mtbl_source_get_prefix(
402            mtbl_reader_source(self._instance), key, len_key), self.return_bytes)
403
404    def __getitem__(self, py_key):
405        cdef mtbl_iter *it
406        cdef mtbl_res res
407        cdef const uint8_t *key
408        cdef const uint8_t *val
409        cdef size_t len_key
410        cdef size_t len_val
411
412        self.check_initialized()
413
414        t = to_bytes(py_key)
415        key = <uint8_t *> t
416        len_key = len(t)
417
418        items = []
419        with nogil:
420            it = mtbl_source_get(mtbl_reader_source(self._instance), key, len_key)
421        if it == NULL:
422            raise KeyError(py_key)
423        while True:
424            with nogil:
425                res = mtbl_iter_next(it, &key, &len_key, &val, &len_val)
426            if res == mtbl_res_failure:
427                break
428            items.append(from_bytes(val[:len_val], self.return_bytes))
429        with nogil:
430            mtbl_iter_destroy(&it)
431        if not items:
432            raise KeyError(py_key)
433        return items
434
435cdef class writer(object):
436    """
437    writer(fname) -> new MTBL writer, output to file fname
438
439    Keyword arguments:
440    compression -- compression type (default COMPRESSION_NONE)
441    block_size -- maximum data block size in bytes (default 8192)
442    block_restart_interval -- how frequently to restart key prefix compression (default 16)
443    """
444    cdef mtbl_writer *_instance
445    cdef _lock
446
447    def __cinit__(self):
448        self._instance = NULL
449
450    def __dealloc__(self):
451        with nogil:
452            mtbl_writer_destroy(&self._instance)
453
454    def __init__(self,
455            str fname,
456            mtbl_compression_type compression=COMPRESSION_NONE,
457            size_t block_size=8192,
458            size_t block_restart_interval=16):
459        if not (compression == COMPRESSION_NONE or
460                compression == COMPRESSION_SNAPPY or
461                compression == COMPRESSION_ZLIB or
462                compression == COMPRESSION_LZ4 or
463                compression == COMPRESSION_LZ4HC):
464            raise UnknownCompressionTypeException
465
466        self._lock = threading.Semaphore()
467
468        cdef bytes tfn_bytes = fname.encode('utf-8')
469        cdef char *tfn = tfn_bytes
470        cdef mtbl_writer_options *opt
471
472        with nogil:
473            opt = mtbl_writer_options_init()
474            mtbl_writer_options_set_compression(opt, compression)
475            mtbl_writer_options_set_block_size(opt, block_size)
476            mtbl_writer_options_set_block_restart_interval(opt, block_restart_interval)
477            self._instance = mtbl_writer_init(tfn, opt)
478            mtbl_writer_options_destroy(&opt)
479        if self._instance == NULL:
480            raise IOError("unable to initialize file: '%s'" % fname)
481
482    def close(self):
483        """W.close() -- finalize and close the writer"""
484        with self._lock:
485            with nogil:
486                mtbl_writer_destroy(&self._instance)
487
488    def __setitem__(self, py_key, py_val):
489        """
490        W.__setitem__(key, value) <==> W[key] = value
491
492        Adds a new (key, value) entry to the writer. key and value must be byte
493        strings, and key must be lexicographically greater than any previously
494        written key.
495        """
496        cdef mtbl_res res
497        cdef const uint8_t *key
498        cdef const uint8_t *val
499        cdef size_t len_key
500        cdef size_t len_val
501
502        if self._instance == NULL:
503            raise TableClosedException
504
505        py_key = to_bytes(py_key)
506        py_val = to_bytes(py_val)
507
508        key = <uint8_t *> py_key
509        val = <uint8_t *> py_val
510        len_key = len(py_key)
511        len_val = len(py_val)
512
513        with self._lock:
514            with nogil:
515                res = mtbl_writer_add(self._instance, key, len_key, val, len_val)
516
517        if res == mtbl_res_failure:
518            raise KeyOrderError
519
520    def __delitem__(self, key):
521        """will raise ImmutableError"""
522        raise ImmutableError
523
524cdef void merge_func_wrapper(void *clos,
525        uint8_t *key, size_t len_key,
526        uint8_t *val0, size_t len_val0,
527        uint8_t *val1, size_t len_val1,
528        uint8_t **merged_val, size_t *len_merged_val) with gil:
529    cdef bytes py_key
530    cdef bytes py_val0
531    cdef bytes py_val1
532    cdef bytes py_merged_val
533    py_key = key[:len_key]
534    py_val0 = val0[:len_val0]
535    py_val1 = val1[:len_val1]
536
537    py_merged_val = (<object> clos)(py_key, py_val0, py_val1)
538    len_merged_val[0] = <size_t> len(py_merged_val)
539    merged_val[0] = <uint8_t *> malloc(len_merged_val[0])
540    t = py_merged_val
541    memcpy(merged_val[0], <uint8_t *>py_merged_val, len_merged_val[0])
542
543cdef class merger(object):
544    """
545    merger(merge_func) -> new MTBL merger
546
547    merge_func is the user-supplied value merging function:
548
549        merge_func(key, val0, val1) -> merged_val
550
551    all parameters are byte strings, and the return value must be a byte string.
552    """
553    cdef mtbl_merger *_instance
554    cdef set _references
555    cdef _lock
556    cdef object merge_func
557    cdef bool return_bytes
558
559    def __cinit__(self):
560        self._instance = NULL
561
562    def __dealloc__(self):
563        with nogil:
564            mtbl_merger_destroy(&self._instance)
565
566    def __init__(self, object merge_func, bool return_bytes=False):
567        cdef mtbl_merger_options *opt
568        self.merge_func = merge_func
569        opt = mtbl_merger_options_init()
570        mtbl_merger_options_set_merge_func(opt,
571                                           <mtbl_merge_func> merge_func_wrapper,
572                                           <void *> merge_func)
573        self._instance = mtbl_merger_init(opt)
574        mtbl_merger_options_destroy(&opt)
575        self._references = set()
576        self._lock = threading.Semaphore()
577        self.return_bytes = return_bytes
578
579    def add_reader(self, reader r):
580        """M.add_reader(mtbl.reader) -- add a reader object as a merge input"""
581        with self._lock:
582            with nogil:
583                mtbl_merger_add_source(self._instance, mtbl_reader_source(r._instance))
584        self._references.add(r)
585
586    def write(self, writer w):
587        """M.write(mtbl.writer) -- dump merged output to writer"""
588        cdef mtbl_res res
589
590        with w._lock:
591            with nogil:
592                res = mtbl_source_write(mtbl_merger_source(self._instance), w._instance)
593        if res != mtbl_res_success:
594            raise RuntimeError
595
596    def __iter__(self):
597        return self.iterkeys()
598
599    def iterkeys(self):
600        """M.iterkeys() -> an iterator over the merged keys of M."""
601        return get_iterkeys(self, mtbl_source_iter(mtbl_merger_source(self._instance)), self.return_bytes)
602
603    def itervalues(self):
604        """M.itervalues() -> an iterator over the merged values of M."""
605        return get_itervalues(self, mtbl_source_iter(mtbl_merger_source(self._instance)), self.return_bytes)
606
607    def iteritems(self):
608        """M.iteritems() -> an iterator over the merged (key, value) items of M."""
609        return get_iteritems(self, mtbl_source_iter(mtbl_merger_source(self._instance)), self.return_bytes)
610
611    def get(self, bytes py_key):
612        """
613        M.get(key) -> an iterator over all (key, value) items in M which match key.
614        """
615        cdef mtbl_res res
616        cdef const uint8_t *key
617        cdef size_t len_key
618
619        t = py_key
620        key = <uint8_t *> t
621        len_key = len(py_key)
622
623        return get_iteritems(self,
624                mtbl_source_get(mtbl_merger_source(self._instance), key, len_key), self.return_bytes)
625
626    def get_range(self, bytes py_key0, bytes py_key1):
627        """
628        M.get_range(key0, key1) -> an iterator over all (key, value) items in M where key is
629        between key0 and key1 inclusive.
630        """
631        cdef mtbl_res res
632        cdef const uint8_t *key0
633        cdef const uint8_t *key1
634        cdef size_t len_key0
635        cdef size_t len_key1
636
637        t = py_key0
638        key0 = <uint8_t *> t
639        t = py_key1
640        key1 = <uint8_t *> t
641        len_key0 = len(py_key0)
642        len_key1 = len(py_key1)
643
644        return get_iteritems(self, mtbl_source_get_range(
645            mtbl_merger_source(self._instance), key0, len_key0, key1, len_key1), self.return_bytes)
646
647    def get_prefix(self, bytes py_key):
648        """
649        M.get_prefix(key_prefix) -> an iterator over all (key, value) items in M where key
650        begins with key_prefix.
651        """
652        cdef mtbl_res res
653        cdef const uint8_t *key
654        cdef size_t len_key
655
656        t = py_key
657        key = <uint8_t *> t
658        len_key = len(py_key)
659
660        return get_iteritems(self, mtbl_source_get_prefix(
661            mtbl_merger_source(self._instance), key, len_key), self.return_bytes)
662
663cdef class sorter(object):
664    """
665    sorter(merge_func) -> new MTBL sorter
666
667    merge_func is the user-supplied value merging function:
668
669        merge_func(key, val0, val1) -> merged_val
670
671    all parameters are byte strings, and the return value must be a byte string.
672
673    Keyword arguments:
674    temp_dir -- temporary directory (default "/var/tmp")
675    max_memory -- maxmimum amount of memory for in-memory sorting in bytes (default 1 GB)
676    """
677    cdef mtbl_sorter *_instance
678    cdef _lock
679    cdef bool return_bytes
680
681    def __cinit__(self):
682        self._instance = NULL
683
684    def __dealloc__(self):
685        with nogil:
686            mtbl_sorter_destroy(&self._instance)
687
688    def __init__(self,
689                 object merge_func,
690                 str temp_dir=DEFAULT_SORTER_TEMP_DIR,
691                 size_t max_memory=DEFAULT_SORTER_MEMORY,
692                 bool return_bytes=False):
693        cdef mtbl_sorter_options *opt
694        self._lock = threading.Semaphore()
695
696        with nogil:
697            opt = mtbl_sorter_options_init()
698
699        mtbl_sorter_options_set_merge_func(opt,
700                                           <mtbl_merge_func> merge_func_wrapper,
701                                           <void *> merge_func)
702
703        mtbl_sorter_options_set_temp_dir(opt, temp_dir.encode('utf-8'))
704        mtbl_sorter_options_set_max_memory(opt, max_memory)
705        with nogil:
706            self._instance = mtbl_sorter_init(opt)
707            mtbl_sorter_options_destroy(&opt)
708        self.return_bytes = return_bytes
709
710    def write(self, writer w):
711        """S.write(mtbl.writer) -- dump sorted output to writer"""
712        cdef mtbl_res res
713
714        with w._lock:
715            with nogil:
716                res = mtbl_sorter_write(self._instance, w._instance)
717        if res != mtbl_res_success:
718            raise RuntimeError
719
720    def __setitem__(self, py_key, py_val):
721        """
722        S.__setitem__(key, value) <==> S[key] = value
723
724        Adds a new (key, value) item to the sorter. If the key already exists,
725        the user-supplied merge function will be called to merge the
726        conflicting values.
727        """
728        cdef mtbl_res res
729        cdef const uint8_t *key
730        cdef const uint8_t *val
731        cdef size_t len_key
732        cdef size_t len_val
733
734        if self._instance == NULL:
735            raise RuntimeError
736
737        py_key = to_bytes(py_key)
738        py_val = to_bytes(py_val)
739
740        t = py_key
741        key = <uint8_t *> t
742        t = py_val
743        val = <uint8_t *> t
744        len_key = len(py_key)
745        len_val = len(py_val)
746
747        with self._lock:
748            with nogil:
749                res = mtbl_sorter_add(self._instance, key, len_key, val, len_val)
750        if res == mtbl_res_failure:
751            raise KeyOrderError
752
753    def __delitem__(self, key):
754        """will raise ImmutableError"""
755        raise ImmutableError
756
757    def __iter__(self):
758        return self.iterkeys()
759
760    def iterkeys(self):
761        """S.iterkeys() -> an iterator over the sorted keys of R."""
762        return get_iterkeys(self, mtbl_sorter_iter(self._instance), self.return_bytes)
763
764    def itervalues(self):
765        """S.itervalues() -> an iterator over the sorted values of R."""
766        return get_itervalues(self, mtbl_sorter_iter(self._instance), self.return_bytes)
767
768    def iteritems(self):
769        """S.iteritems() -> an iterator over the sorted (key, value) items of R."""
770        return get_iteritems(self, mtbl_sorter_iter(self._instance), self.return_bytes)
771