kblib 0.2.3
General utilities library for modern C++
bits.h
Go to the documentation of this file.
1/* *****************************************************************************
2 * kblib is a general utility library for C++14 and C++17, intended to provide
3 * performant high-level abstractions and more expressive ways to do simple
4 * things.
5 *
6 * Copyright (c) 2021 killerbee
7 *
8 * This program is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program. If not, see <https://www.gnu.org/licenses/>.
20 * ****************************************************************************/
21
31#ifndef KBLIB_BITS_H
32#define KBLIB_BITS_H
33
34#include <algorithm>
35#include <array>
36#include <bitset>
37#include <limits>
38#include <memory>
39#include <utility>
40#include <vector>
41
42#include <iostream>
43
44#include "fakestd.h"
45#include "simple.h"
46#include "stats.h"
47#include "tdecl.h"
48#include "traits.h"
49
50namespace kblib {
51
52template <typename Int>
53constexpr int bits_of = std::numeric_limits<Int>::digits;
54
55#if KBLIB_USE_CXX17
56
57namespace detail_bits {
58
59 template <typename Key, typename Value>
60 class trie_node {
61 std::unique_ptr<std::array<trie_node, 4>> children;
62 unsigned char storage[sizeof(Value)]{};
63 bool exists = false;
64
65 template <typename... Args>
66 auto create(Args&&... args) noexcept(
67 std::is_nothrow_constructible<Value, Args...>::value) -> Value& {
68 clear();
69 // This variable must exist for exception safety. exists should not be
70 // set to true if an exception is thrown.
71 auto v = *new (storage) Value(args...);
72 exists = true;
73 return *v;
74 }
75
76 auto clear() noexcept -> void {
77 if (exists) {
78 get()->~Value();
79 }
80 return;
81 }
82
83 KBLIB_NODISCARD auto get() noexcept -> Value& {
84 assert(exists);
85 return *reinterpret_cast<Value*>(storage);
86 }
87 KBLIB_NODISCARD auto get() const noexcept -> const Value& {
88 assert(exists);
89 return *reinterpret_cast<Value*>(storage);
90 }
91 };
92
93} // namespace detail_bits
94/*
95template <typename Key, typename Value>
96class bit_trie {
97 public:
98 using value_type = Value;
99 using key_type = Key;
100 using mapped_type = Value;
101
102 static_assert(std::is_integral<key_type>::value,
103 "key_type must be an integral type.");
104 static_assert(std::is_nothrow_destructible<mapped_type>::value,
105 "mapped_type must be nothrow destructible.");
106
107 void insert(key_type, const mapped_type&);
108 void insert(key_type, mapped_type&&);
109
110 private:
111 std::array<detail_bits::trie_node, bits_of<key_type>> roots;
112};//*/
113
114template <typename Key, Key key_range, typename Value>
116 public:
117 struct key_type {
119 std::uint16_t bits : filg2(key_range);
120 };
121
122 using value_type = Value;
123 using mapped_type = Value;
129 using const_pointer = const value_type*;
130
131 template <typename V>
132 class iterator_t;
133
136 using reverse_iterator = std::reverse_iterator<iterator>;
137 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
138
139 using bitset_type = std::bitset<bits_of<Key>>;
140
141 static_assert(std::is_integral<Key>::value, "Key must be an integral type.");
142 static_assert(std::is_unsigned<Key>::value, "Key must be unsigned.");
143 static_assert(std::is_nothrow_destructible<mapped_type>::value,
144 "mapped_type must be nothrow destructible.");
145
146 KBLIB_NODISCARD auto at(key_type key) const noexcept(false)
147 -> const_reference {
148 if (empty()) {
149 throw std::out_of_range("searched in an empty compact_bit_trie");
150 }
151 if (key.bits > bits_of<Key>) {
152 throw std::invalid_argument("key prefix longer than key length");
153 }
154 size_type node = 1;
155 const bitset_type search = key.prefix;
156 int idx = 0;
157 while (node and idx < key.bits) {
158 if (auto val = storage[node].val) {
159 return values[val];
160 } else {
161 node = storage[node].children[search[idx++]];
162 }
163 }
164 throw std::out_of_range("key not found in compact_bit_trie");
165 }
166
167 KBLIB_NODISCARD auto at(key_type key) noexcept(false) -> reference {
168 if (empty()) {
169 throw std::out_of_range("searched in an empty compact_bit_trie");
170 }
171 if (key.bits > bits_of<Key>) {
172 throw std::invalid_argument("key prefix longer than key length");
173 }
174 size_type node = 1;
175 const bitset_type search = key.prefix;
176 int idx = 0;
177 while (node and idx < key.bits) {
178 if (auto val = storage[node].val) {
179 return values[val];
180 } else {
181 node = storage[node].children[search[idx++]];
182 }
183 }
184 throw std::out_of_range("key not found in compact_bit_trie");
185 }
186
187 KBLIB_NODISCARD auto find_deep(key_type key, size_type depth = -1) const
188 noexcept(false) -> const_reference {
189 if (empty()) {
190 throw std::out_of_range("searched in an empty compact_bit_trie");
191 }
192 if (key.bits > bits_of<Key>) {
193 throw std::invalid_argument("key prefix longer than key length");
194 }
195 size_type node = 1;
196 size_type found = 0;
197 const bitset_type search = key.prefix;
198 int idx = 0;
199 while (node and idx < key.bits) {
200 if (auto val = storage[node].val) {
201 found = val;
202 if (depth--) {
203 break;
204 }
205 }
206 node = storage[node].children[search[idx++]];
207 }
208 if (found) {
209 return values[found];
210 } else {
211 throw std::out_of_range("key not found in compact_bit_trie");
212 }
213 }
214
216 size_type depth = -1) noexcept(false)
217 -> reference {
218 if (empty()) {
219 throw std::out_of_range("searched in an empty compact_bit_trie");
220 }
221 if (key.bits > bits_of<Key>) {
222 throw std::invalid_argument("key prefix longer than key length");
223 }
224 size_type node = 1;
225 size_type found = 0;
226 const bitset_type search = key.prefix;
227 int idx = 0;
228 while (node and idx < key.bits) {
229 if (auto val = storage[node].val) {
230 found = val;
231 if (depth--) {
232 break;
233 }
234 }
235 node = storage[node].children[search[idx++]];
236 }
237 if (found) {
238 return values[found];
239 } else {
240 throw std::out_of_range("key not found in compact_bit_trie");
241 }
242 }
243
244 KBLIB_NODISCARD auto empty() const noexcept -> bool {
245 return values.empty();
246 }
247
248 template <typename... Ts>
249 auto emplace(key_type key, Ts&&... args) -> bool {
250 size_type node = get_storage_node_for(key);
251 if (auto& v = storage[node].val; v != max) {
252 return false;
253 } else {
254 values.emplace_back(std::forward<Ts>(args)...);
255 v = static_cast<size_type>(values.size() - 1);
256 return true;
257 }
258 }
259
260 auto insert(key_type key, const value_type& value) -> bool {
261 return emplace(key, value);
262 }
263 auto insert(key_type key, value_type&& value) -> bool {
264 return emplace(key, std::move(value));
265 }
266
267 auto insert_or_assign(key_type key, const value_type& value) -> reference {
268 size_type node = get_storage_node_for(key);
269 auto& v = storage[node].val;
270 if (v != -1) {
271 values.push_back(value);
272 v = static_cast<size_type>(values.size() - 1);
273 } else {
274 values[v] = value;
275 }
276 return values[v];
277 }
278
280 size_type node = get_storage_node_for(key);
281 auto& v = storage[node].val;
282 if (v != -1) {
283 values.push_back(std::move(value));
284 v = static_cast<size_type>(values.size() - 1);
285 } else {
286 values[v] = std::move(value);
287 }
288 return values[v];
289 }
290
291 bool erase(key_type key);
292 bool prune(key_type prefix);
293 auto clear() -> void {
294 storage.clear();
295 values.clear();
296 }
297
298 KBLIB_NODISCARD auto size() const noexcept -> size_type {
299 return static_cast<size_type>(values.size());
300 }
301
302 KBLIB_NODISCARD auto memory_use() const noexcept -> std::size_t {
303 return storage.capacity() * sizeof(inline_node)
304 + values.size() * sizeof(Value);
305 }
306
307 auto shrink_to_fit() -> void {
308 storage.shrink_to_fit();
309 values.shrink_to_fit();
310 }
311
312 private:
313 struct inline_node {
314 size_type children[2];
315 size_type parent;
316 size_type val;
317 };
318 std::vector<inline_node> storage;
319 std::vector<Value> values;
320
321 auto do_init() -> void {
322 if (storage.size() < 2) {
323 storage.resize(2);
324 storage[0] = {};
325 storage[1] = {};
326 }
327 }
328
329 KBLIB_NODISCARD auto get_storage_node_for(key_type key) -> size_type {
330 if (key.bits > bits_of<Key>) {
331 throw std::invalid_argument("key prefix longer than key length");
332 }
333 const bitset_type search = key.prefix;
334 size_type node = 1;
335 do_init();
336 for (std::size_t i : range<std::size_t>(key.bits - 1)) {
337 if (auto n = storage[node].children[std::as_const(search)[i]]) {
338 node = n;
339 } else {
340 storage.push_back({{0, 0}, node, max});
341 node = static_cast<size_type>(storage.size() - 1);
342 storage[node].children[std::as_const(search)[i]] = node;
343 }
344 }
345 return node;
346 }
347
348 public:
349 template <typename V>
351 public:
352 using value_type = V;
353 using pointer = V*;
354 using reference = V&;
356 using iterator_category = std::bidirectional_iterator_tag;
357
358 iterator_t() = default;
360 : tree_ptr{&range.storage}
361 , values_ptr{&range.values}
362 , node{0} {}
363
364 auto operator*() const noexcept -> reference {
365 return (*values_ptr)[(*tree_ptr)[node].val];
366 }
367 auto operator->() const noexcept -> pointer {
368 return std::addressof((*values_ptr)[(*tree_ptr)[node].val]);
369 }
371
372 private:
374 : iterator_t(range) {
375 node = n_;
376 }
377
378 const std::vector<inline_node>* tree_ptr{};
379 const std::vector<Value>* values_ptr{};
380 size_type node{};
381 };
382};
383
394constexpr inline auto memswap(unsigned char* A, unsigned char* B,
395 std::size_t size) noexcept -> void {
396 for (auto i : range(size)) {
397 (swap)(A[i], B[i]);
398 }
399 return;
400}
401
412inline auto memswap(void* A, void* B, std::size_t size) noexcept -> void {
413 auto Ab = static_cast<unsigned char*>(A);
414 auto Bb = static_cast<unsigned char*>(B);
415 memswap(Ab, Bb, size);
416 return;
417}
418
419#endif
420
436template <unsigned offset, unsigned size, typename Storage>
437struct bitfield {
438 auto operator()() const noexcept -> Storage {
439 return (raw >> offset) & ((1u << size) - 1);
440 }
441 auto operator()(const Storage val) noexcept -> Storage {
442 // Clear the bits for this field
443 raw &= ~(((1u << size) - 1) << offset);
444 // Set the field
445 raw |= (val & ((1u << size) - 1)) << offset;
446 return val;
447 }
448 operator Storage() const noexcept { return (*this)(); }
449 auto operator=(Storage val) noexcept -> Storage { return (*this)(val); }
450 Storage raw;
451 // Is this a good idea?
452 auto operator&() -> void = delete;
453};
454
455namespace detail_bits {
456
465 template <typename Parent, typename ReturnT,
466 ReturnT (Parent::*Set)(ReturnT) noexcept,
467 ReturnT (Parent::*Get)() const noexcept>
469 Parent* p;
470 constexpr auto operator=(ReturnT val) noexcept -> ReturnT {
471 return (p->*Set)(val);
472 }
473 constexpr operator ReturnT() const noexcept { return (p->*Get)(); }
474 };
475
476} // namespace detail_bits
477
484#define KBLIB_INTERNAL_BITFIELD_MACRO(offset, size, name, raw) \
485 static_assert(offset >= 0 and size > 0, \
486 "BITFIELD cannot have negative offset or size"); \
487 \
488 private: \
489 constexpr auto name##_get_impl() const noexcept->decltype(raw) { \
490 return (raw >> kblib::to_unsigned(offset)) \
491 & ((decltype(raw)(1) << kblib::to_unsigned(size)) - 1u); \
492 } \
493 \
494 public: \
495 KBLIB_NODISCARD constexpr auto name() const noexcept->decltype(raw) { \
496 return name##_get_impl(); \
497 } \
498 \
499 private: \
500 constexpr auto name##_set_impl(const decltype(raw) val) noexcept->decltype( \
501 raw) { \
502 /* Clear the bits for this field */ \
503 raw &= ~(((decltype(raw)(1) << kblib::to_unsigned(size)) - 1u) \
504 << kblib::to_unsigned(offset)); \
505 /* Set the field */ \
506 raw |= (val & ((decltype(raw)(1) << kblib::to_unsigned(size)) - 1u)) \
507 << kblib::to_unsigned(offset); \
508 return val; \
509 } \
510 \
511 public: \
512 constexpr auto name(const decltype(raw) val) noexcept->decltype(raw) { \
513 return name##_set_impl(val); \
514 } \
515 \
516 KBLIB_NODISCARD constexpr auto name() noexcept->auto { \
517 using Parent = std::remove_pointer<decltype(this)>::type; \
518 return kblib::detail_bits::bitfield_proxy<Parent, decltype(raw), \
519 &Parent::name##_set_impl, \
520 &Parent::name##_get_impl>{ \
521 this}; \
522 } \
523 \
524 template <decltype(raw) val, decltype(raw) basis = 0> \
525 constexpr static decltype(raw) set_##name##_v \
526 = (basis \
527 & ~(((decltype(raw)(1) << kblib::to_unsigned(size)) - 1u) \
528 << kblib::to_unsigned(offset))) \
529 | (val & ((decltype(raw)(1) << kblib::to_unsigned(size)) - 1u)) \
530 << kblib::to_unsigned(offset); \
531 \
532 template <decltype(raw) basis> \
533 constexpr static decltype(raw) get_##name##_v \
534 = (basis >> kblib::to_unsigned(offset)) \
535 & ((decltype(raw)(1) << kblib::to_unsigned(size)) - 1u); \
536 constexpr static std::size_t name##_shift_v = offset; \
537 constexpr static std::size_t name##_width_v = size;
538
539namespace detail_bits {
540
541 template <typename Type, typename Storage>
542 struct pun_proxy {
543 Storage& base;
544 auto operator=(const Type val) noexcept -> pun_proxy& {
545 std::memcpy(&base, &val, sizeof val);
546 return *this;
547 }
548 operator Type() const noexcept {
549 Type ret;
550 std::memcpy(&ret, &base, sizeof ret);
551 return ret;
552 }
553 };
554
555 template <typename Type, typename Storage>
557 Storage& base;
558 Type data;
559 bool dirty = false;
560 operator Type&() noexcept {
561 if (dirty) {
562 std::memcpy(&base, &data, sizeof data);
563 }
564 dirty = true;
565 return data;
566 }
567 operator const Type&() const noexcept {
568 if (dirty) {
569 std::memcpy(&base, &data, sizeof data);
570 }
571 return data;
572 }
574 if (dirty) {
575 std::memcpy(&base, &data, sizeof data);
576 }
577 }
582 };
583
584 template <typename T>
586 using type = T;
587 };
588 template <typename T, std::size_t N>
590 using type = std::array<T, N>;
591 };
592 template <typename T>
594 using type = std::array<T, 0>;
595 };
596
597 template <typename T, std::size_t S>
599 using type = T;
600 };
601 template <typename T, std::size_t N, std::size_t S>
603 using type = std::array<T, N>;
604 };
605 template <typename T, std::size_t S>
607 using type = std::array<T, S / sizeof(T)>;
608 };
609
610 template <typename P, typename Type, std::size_t S, std::size_t,
611 bool aliases
612 = is_aliasing_type_v<typename std::remove_extent<Type>::type>>
613 struct pun_el {
614
616
617 static_assert(std::is_trivially_copyable<type>::value,
618 "Type must be trivially copyable");
619
620 KBLIB_NODISCARD auto get() noexcept -> auto {
621 return pun_proxy<type, decltype(P::raw)>{static_cast<P*>(this)->raw};
622 }
623 KBLIB_NODISCARD auto get() const noexcept -> auto {
624 return pun_proxy<const type, const decltype(P::raw)>{
625 static_cast<const P*>(this)->raw};
626 }
627 };
628
629 template <typename P, typename Type, std::size_t S, std::size_t I>
630 struct pun_el<P, Type[S], S, I, true> {
631 using type = Type[S];
632
633 KBLIB_NODISCARD auto get() noexcept -> decltype(auto) {
634 return reinterpret_cast<type&>(static_cast<P*>(this)->raw);
635 }
636 KBLIB_NODISCARD auto get() const noexcept -> decltype(auto) {
637 return reinterpret_cast<const type&>(static_cast<const P*>(this)->raw);
638 }
639 };
640
641 template <typename P, typename Type, std::size_t S, std::size_t I>
642 struct pun_el<P, Type[], S, I, true> {
643 using type = Type[S];
644
645 KBLIB_NODISCARD auto get() noexcept -> decltype(auto) {
646 return reinterpret_cast<type&>(static_cast<P*>(this)->raw);
647 }
648 KBLIB_NODISCARD auto get() const noexcept -> decltype(auto) {
649 return reinterpret_cast<const type&>(static_cast<const P*>(this)->raw);
650 }
651 };
652
653 template <std::size_t S, typename I_S, typename... Types>
655
656 template <std::size_t S, std::size_t... Is, typename... Types>
657 struct punner_impl<S, std::index_sequence<Is...>, Types...>
658 : pun_el<punner_impl<S, std::index_sequence<Is...>, Types...>, Types, S,
659 Is>... {
660
661 alignas(std::max({alignof(typename std::remove_extent<
662 Types>::type)...})) unsigned char raw[S]{};
663 };
664
665 template <typename... Types>
666 constexpr std::size_t max_size
667 = std::max({sizeof(typename array_filter<Types>::type)...});
668
669} // namespace detail_bits
670
671template <typename... Types>
672struct punner
673 : private detail_bits::punner_impl<detail_bits::max_size<Types...>,
674 std::index_sequence_for<Types...>,
675 Types...> {
676 private:
677 constexpr static std::size_t storage_size = detail_bits::max_size<Types...>;
678 using impl_t
679 = detail_bits::punner_impl<storage_size,
680 std::index_sequence_for<Types...>, Types...>;
681 using tuple_t = std::tuple<Types...>;
682 template <std::size_t I>
683 using r_element_t = typename std::tuple_element<I, tuple_t>::type;
684
685 static_assert(std::is_standard_layout<impl_t>::value, "");
686
687 public:
688 template <std::size_t I>
690 template <std::size_t I>
691 using element_t = typename base_t<I>::type;
692
693 template <std::size_t I>
694 KBLIB_NODISCARD auto get() & noexcept -> decltype(auto) {
695 static_assert(std::is_base_of<base_t<I>, impl_t>::value, "");
696 return static_cast<base_t<I>&>(*this).get();
697 }
698 template <std::size_t I>
699 KBLIB_NODISCARD auto get() const& noexcept -> decltype(auto) {
700 return static_cast<const base_t<I>&>(*this).get();
701 }
702 template <std::size_t I>
703 KBLIB_NODISCARD auto get() && noexcept -> decltype(auto) {
704 return static_cast<base_t<I>&&>(*this).get();
705 }
706 template <std::size_t I>
707 KBLIB_NODISCARD auto get() const&& noexcept -> decltype(auto) {
708 return static_cast<const base_t<I>&&>(*this).get();
709 }
710};
711
712} // namespace kblib
713
714namespace std {
715
716template <std::size_t I, typename... Types>
717struct tuple_element<I, kblib::punner<Types...>> {
718 using type = typename kblib::punner<Types...>::template element_t<I>;
719};
720
721template <typename... Types>
722struct tuple_size<kblib::punner<Types...>>
723 : public std::integral_constant<std::size_t, sizeof...(Types)> {};
724
725} // namespace std
726
727namespace kblib {
728
729template <std::size_t I, typename... Types>
730KBLIB_NODISCARD auto get(punner<Types...>& p) noexcept -> decltype(auto) {
731 return p.template get<I>();
732}
733template <std::size_t I, typename... Types>
734KBLIB_NODISCARD auto get(const punner<Types...>& p) noexcept -> decltype(auto) {
735 return p.template get<I>();
736}
737template <std::size_t I, typename... Types>
738KBLIB_NODISCARD auto get(punner<Types...>&& p) noexcept -> decltype(auto) {
739 return p.template get<I>();
740}
741template <std::size_t I, typename... Types>
742KBLIB_NODISCARD auto get(const punner<Types...>&& p) noexcept
743 -> decltype(auto) {
744 return p.template get<I>();
745}
746
747#if KBLIB_USE_CXX17
748template <typename Type, auto Storage>
750 private:
751 using sptr_t = decltype(Storage);
752 using class_t = kblib::class_t<Storage>;
753 using member_t = kblib::member_of_t<sptr_t>;
756
757 static_assert(sizeof(Type) <= sizeof(member_t),
758 "Type will not fit in the provided storage.");
759 static_assert(std::is_trivially_copyable_v<Type>,
760 "Type must be trivially copyable.");
761 static_assert(
762 std::is_trivially_copyable_v<std::remove_all_extents_t<member_t>>,
763 "Storage type must be trivially copyable.");
764
765 KBLIB_NODISCARD auto base() noexcept -> member_t& {
766 return reinterpret_cast<class_t*>(this)->*Storage;
767 }
768 KBLIB_NODISCARD auto base() const noexcept -> const member_t& {
769 return reinterpret_cast<const class_t*>(this)->*Storage;
770 }
771
772 public:
773 KBLIB_NODISCARD auto operator()() const noexcept -> const_proxy_t {
774 return {base()};
775 }
776 auto operator()(const Type val) noexcept -> proxy_t {
777 std::memcpy(&base(), &val, sizeof val);
778 return {base()};
779 }
780 operator Type() const noexcept { return (*this)(); }
781 auto operator=(const Type val) noexcept -> proxy_t { return (*this)(val); }
782};
783
784template <typename Type, std::size_t N, auto Storage>
785class union_pun<Type[N], Storage> {
786 private:
787 using class_t = kblib::class_t<Storage>;
788 using member_t = kblib::member_t<class_t, Storage>;
789 using type = std::array<Type, N>;
792
793 static_assert(sizeof(type) <= sizeof(member_t),
794 "Type will not fit in the provided storage.");
795 static_assert(std::is_trivially_copyable_v<type>,
796 "Type must be trivially copyable.");
797 static_assert(
798 std::is_trivially_copyable_v<std::remove_all_extents_t<member_t>>,
799 "Storage type must be trivially copyable.");
800
801 KBLIB_NODISCARD auto base() noexcept -> member_t& {
802 return reinterpret_cast<class_t*>(this)->*Storage;
803 }
804 KBLIB_NODISCARD auto base() const noexcept -> const member_t& {
805 return reinterpret_cast<const class_t*>(this)->*Storage;
806 }
807
808 public:
809 KBLIB_NODISCARD auto operator()() const noexcept -> const_proxy_t {
810 return {base()};
811 }
812 auto operator()(const Type (&val)[N]) noexcept -> proxy_t {
813 std::memcpy(&base(), &val, sizeof val);
814 return {base()};
815 }
816 operator type() const noexcept { return (*this)(); }
817 auto operator=(const Type (&val)[N]) noexcept -> proxy_t {
818 return (*this)(val);
819 }
820};
821#endif
822
823} // namespace kblib
824
825#endif // KBLIB_BITS_H
826
827#if KBLIB_DEF_MACROS and not defined(BITFIELD)
856#define BITFIELD(offset, size, name, raw) \
857 KBLIB_INTERNAL_BITFIELD_MACRO(offset, size, name, raw)
858#endif // KBLIB_DEF_MACROS and not defined(BITFIELD)
iterator_t(const compact_bit_trie &range)
Definition: bits.h:359
compact_bit_trie::difference_type difference_type
Definition: bits.h:355
auto operator->() const noexcept -> pointer
Definition: bits.h:367
auto operator++() -> iterator_t
Definition: bits.h:370
auto operator*() const noexcept -> reference
Definition: bits.h:364
std::bidirectional_iterator_tag iterator_category
Definition: bits.h:356
auto clear() -> void
Definition: bits.h:293
auto memory_use() const noexcept -> std::size_t
Definition: bits.h:302
auto insert(key_type key, const value_type &value) -> bool
Definition: bits.h:260
const value_type * const_pointer
Definition: bits.h:129
value_type * pointer
Definition: bits.h:128
auto at(key_type key) const noexcept(false) -> const_reference
Definition: bits.h:146
value_type & reference
Definition: bits.h:126
auto at(key_type key) noexcept(false) -> reference
Definition: bits.h:167
uint_smallest_t< key_range > size_type
Definition: bits.h:124
auto emplace(key_type key, Ts &&... args) -> bool
Definition: bits.h:249
auto empty() const noexcept -> bool
Definition: bits.h:244
auto insert_or_assign(key_type key, const value_type &value) -> reference
Definition: bits.h:267
auto insert_or_assign(key_type key, value_type &&value) -> reference
Definition: bits.h:279
auto size() const noexcept -> size_type
Definition: bits.h:298
bool prune(key_type prefix)
std::bitset< bits_of< Key > > bitset_type
Definition: bits.h:139
std::reverse_iterator< iterator > reverse_iterator
Definition: bits.h:136
auto find_deep(key_type key, size_type depth=-1) const noexcept(false) -> const_reference
Definition: bits.h:187
int_smallest_t< key_range > difference_type
Definition: bits.h:125
bool erase(key_type key)
const value_type & const_reference
Definition: bits.h:127
auto insert(key_type key, value_type &&value) -> bool
Definition: bits.h:263
auto find_deep(key_type key, size_type depth=-1) noexcept(false) -> reference
Definition: bits.h:215
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: bits.h:137
auto shrink_to_fit() -> void
Definition: bits.h:307
auto operator()() const noexcept -> const_proxy_t
Definition: bits.h:809
auto operator=(const Type(&val)[N]) noexcept -> proxy_t
Definition: bits.h:817
auto operator()(const Type(&val)[N]) noexcept -> proxy_t
Definition: bits.h:812
auto operator()(const Type val) noexcept -> proxy_t
Definition: bits.h:776
auto operator=(const Type val) noexcept -> proxy_t
Definition: bits.h:781
auto operator()() const noexcept -> const_proxy_t
Definition: bits.h:773
This header provides some features of C++17 <type_traits> and other headers for C++14,...
constexpr std::size_t max_size
Definition: bits.h:667
constexpr struct kblib::nums::max_t max
The main namespace in which all entities from kblib are defined.
Definition: algorithm.h:44
constexpr auto size(const C &c) -> decltype(c.size())
Definition: fakestd.h:1070
constexpr auto memswap(unsigned char *A, unsigned char *B, std::size_t size) noexcept -> void
Swaps memory ranges.
Definition: bits.h:394
struct kblib::@0 swap
typename int_smallest< I >::type int_smallest_t
Definition: simple.h:201
constexpr auto filg2(const std::bitset< std::numeric_limits< std::uintmax_t >::digits > val) noexcept -> int
Floored integer binary logarithm. Returns floor(lb(val)).
Definition: simple.h:166
constexpr auto range(Value min, Value max, Delta step=0) -> range_t< Value, Delta >
Constructs a range from beginning, end, and step amount. The range is half-open, that is min is in th...
Definition: iterators.h:621
typename member_of< T >::type member_of_t
Definition: traits.h:297
auto get(punner< Types... > &p) noexcept -> decltype(auto)
Definition: bits.h:730
constexpr int bits_of
Definition: bits.h:53
typename uint_smallest< I >::type uint_smallest_t
Definition: simple.h:198
Definition: bits.h:714
Provides general utilities which do not fit in any more specific header.
Provides numerical and mathematical utilities.
Implements a bitfield abstraction. May be used in a union with other bitfields.
Definition: bits.h:437
Storage raw
Definition: bits.h:450
auto operator&() -> void=delete
auto operator()(const Storage val) noexcept -> Storage
Definition: bits.h:441
auto operator()() const noexcept -> Storage
Definition: bits.h:438
auto operator=(Storage val) noexcept -> Storage
Definition: bits.h:449
std::array< T, S/sizeof(T)> type
Definition: bits.h:607
array_pun_proxy & operator=(const array_pun_proxy &)=delete
array_pun_proxy(array_pun_proxy &&)=delete
array_pun_proxy & operator=(array_pun_proxy &&)=delete
array_pun_proxy(const array_pun_proxy &)=delete
A proxy reference type for BITFIELD-declared bitfields.
Definition: bits.h:468
constexpr auto operator=(ReturnT val) noexcept -> ReturnT
Definition: bits.h:470
auto get() const noexcept -> decltype(auto)
Definition: bits.h:648
auto get() noexcept -> decltype(auto)
Definition: bits.h:645
auto get() noexcept -> decltype(auto)
Definition: bits.h:633
auto get() const noexcept -> decltype(auto)
Definition: bits.h:636
auto get() const noexcept -> auto
Definition: bits.h:623
typename array_filter2< Type, S >::type type
Definition: bits.h:615
auto get() noexcept -> auto
Definition: bits.h:620
auto operator=(const Type val) noexcept -> pun_proxy &
Definition: bits.h:544
auto get() &noexcept -> decltype(auto)
Definition: bits.h:694
auto get() &&noexcept -> decltype(auto)
Definition: bits.h:703
typename base_t< I >::type element_t
Definition: bits.h:691
auto get() const &noexcept -> decltype(auto)
Definition: bits.h:699
auto get() const &&noexcept -> decltype(auto)
Definition: bits.h:707
typename kblib::punner< Types... >::template element_t< I > type
Definition: bits.h:718
Provides macros and basic templates used by the rest of kblib.
#define KBLIB_NODISCARD
This internal macro is used to provide a fallback for [[nodiscard]] in C++14.
Definition: tdecl.h:81
Contains some type traits not in the standard library that are useful in the implementation of kblib.
Definition: bits.cpp:164