acme
Foundational cross-platform layer of the ca2 framework
Loading...
Searching...
No Matches
set.h
1#pragma once
2
3
4#include "hash_table.h"
5#include "list_iterator.h"
6#include "range.h"
7#include "single.h"
8
9
10template < typename ITEM, enum_allocate t_eallocate >
11class node_set_base :
12 public ::range < ::list_iterator < ::set_node < ITEM > * > >
13{
14public:
15
16
17 using BASE_RANGE = ::range < ::list_iterator < ::set_node < ITEM > * > >;
18
19
20 using BASE_NODE = ::set_node < ITEM > ;
21 using BASE_ITEM = typename BASE_NODE::BASE_ITEM;
22 using HASH_TABLE = set_dynamic_hash_table < ITEM >;
23 using KEY = typename BASE_NODE::KEY;
24 using ARG_KEY = typename BASE_NODE::ARG_KEY;
25 using PAYLOAD = typename BASE_NODE::PAYLOAD;
26 using ARG_PAYLOAD = typename BASE_NODE::ARG_PAYLOAD;
27 using BASE_PAYLOAD = typename BASE_NODE::PAYLOAD;
28
29 using CONST_ARG_KEY = const non_const<typename BASE_NODE::ARG_KEY>;
30
31 using iterator = typename BASE_RANGE::iterator;
32 using const_iterator = typename BASE_RANGE::const_iterator;
33
34 using item_iterator = ::element1_list_iterator < BASE_NODE * >;
35 using payload_iterator = ::element2_list_iterator < BASE_NODE * >;
36 using const_item_iterator = typename item_iterator::const_iterator;
37 using const_payload_iterator = typename payload_iterator::const_iterator;
38
39
40 HASH_TABLE m_hashtable;
41 ::collection::count m_count;
42
43
44 node_set_base();
45 template <typename T, ::collection::count count>
46 node_set_base(const T (&itema)[count]) :
47 node_set_base(itema, count)
48 {
49
50 }
51 node_set_base(BASE_ITEM * pitem, ::i32 iCount);
52 node_set_base(const ::std::initializer_list < BASE_ITEM > & list_base);
53 node_set_base(const node_set_base & m);
54
55 //
56 // pair_map_base();
57 // pair_map_base(const PAIR * iterator, ::collection::count c);
58 // pair_map_base(const ::std::initializer_list < PAIR > & list_base);
59 // pair_map_base(const pair_map_base & m);
60 // ~pair_map_base();
61
62 ~node_set_base();
63
64 void construct();
65
66 ::collection::count get_count() const;
67 ::collection::count get_size() const;
68 ::collection::count size() const;
69 ::collection::count count() const;
70 bool is_empty() const;
71 bool empty() const;
72
73 bool find(ARG_KEY key, PAYLOAD & payload) const;
74
75 const_iterator find(ARG_KEY key) const;
76
77 iterator get(ARG_KEY key);
78
79 PAYLOAD * defer_get(ARG_KEY key) const;
80
81 bool should_set(ARG_KEY key)
82 {
83
84 if (has(key))
85 {
86
87 return false;
88
89 }
90
91 set_key(key);
92
93 return true;
94
95 }
96
97
98 // PAYLOAD * payload(ARG_KEY key);
99 // const PAYLOAD * payload(ARG_KEY key) const
100 // {
101 //
102 // return ((node_set_base *)this)->defer_get(key);
103 //
104 // }
105
106
107 template < typename TKEY >
108 auto pop(const TKEY & key)
109 {
110
111 auto p = this->find(key);
112
113 auto payload = p->payload();
114
115 this->erase(p);
116
117 return payload;
118
119 }
120
121 //Operations
122 //find and add if not there
123 PAYLOAD & operator[](ARG_KEY key);
124 const PAYLOAD & operator[](ARG_KEY key) const;
125
126 //iterator find_iterator(ARG_KEY key);
127 //const_iterator find_iterator(ARG_KEY key) const;
128
129 inline iterator set_key(ARG_KEY key);
130
131 iterator set_item(const BASE_ITEM & item)
132 {
133
134 return set_at((ARG_KEY) item.key(), (ARG_PAYLOAD) item.payload());
135
136 }
137
138 bool erase(iterator iterator);
139 bool contains(iterator iterator) const;
140
141 bool toggle(ARG_KEY key)
142 {
143
144 auto pnode = this->find(key);
145
146 if (pnode)
147 {
148
149 this->erase(pnode);
150
151 return false;
152
153 }
154 else
155 {
156
157 set_item(key);
158
159 return true;
160
161 }
162
163 }
164
165
166 inline bool erase(ARG_KEY key)
167 {
168
169 auto p = this->find(key);
170
171 if (!p)
172 {
173
174 return false;
175
176 }
177
178 this->erase(p);
179
180 return true;
181
182 }
183
184
185 template < typename iterator >
186 inline void erase_range(const iterator & begin, const iterator & last)
187 {
188
189 for(auto it = begin; it != last; it++)
190 {
191
192 erase(it);
193
194 }
195
196 }
197
198
199 inline bool unhash(iterator iterator);
200
201 void erase_all();
202 void clear();
203 //void Empty();
204
205
206 ::collection::count count(ARG_KEY key) const;
207 bool has(ARG_KEY key) const;
208 bool contains(ARG_KEY key) const;
209
210
211 ::u32 GetHashTableSize() const
212 {
213
214 return m_hashtable.GetHashTableSize();
215
216 }
217
218
219 void InitHashTable(::u32 hashSize,bool bAllocNow = true);
220
221
222 PAYLOAD defer_get(ARG_KEY argkey, ARG_PAYLOAD valueDefault) const;
223
224
225 void assign(node_set_base & set)
226 {
227
228 auto it = set.begin();
229
230 while(it.is_set())
231 {
232
233 set_item(*it);
234
235 it++;
236
237 }
238
239 }
240
241
242 BASE_NODE* __new_node(ARG_KEY key);
243 void __delete_node(BASE_NODE* pnode);
244
245 iterator _new(ARG_KEY key, ::u32& uiPack, ::u32& uiHash);
246 void _free(iterator pnode);
247 iterator _find(ARG_KEY key, ::u32& uiPack, ::u32& uiHash) const;
248 //iterator _get(ARG_KEY key);
249
250
251 template < prototype_container CONTAINER >
252 ::collection::count erase_nodes(CONTAINER container)
253 {
254
255 ::collection::count countRemoved = 0;
256
257 for(auto & KEY : container)
258 {
259
260 if(this->erase(KEY))
261 {
262
263 countRemoved++;
264
265 }
266
267 }
268
269 return countRemoved;
270
271 }
272
273
274 template < typename PRED >
275 iterator predicate_find(PRED pred)
276 {
277
278 auto p = this->begin();
279
280 while (p)
281 {
282
283 if (pred(p))
284 {
285
286 return p.m_p;
287
288 }
289
290 p++;
291
292 }
293
294 return nullptr;
295
296 }
297
298 node_set_base & operator = (const node_set_base & m);
299
300
301 template < typename TYPE >
302 ::pointer<TYPE>get_typed_ptr(::collection::index i = 0)
303 {
304
305 ::pointer<TYPE>p;
306
307 for(auto & pvalue : *this)
308 {
309
310 p = pvalue;
311
312 if(p)
313 {
314
315 if(i <= 0)
316 {
317
318 return p;
319
320 }
321
322 i--;
323
324 }
325
326 }
327
328 return nullptr;
329
330 }
331
332
333 template < prototype_container CONTAINER >
334 void add_keys(const CONTAINER& container)
335 {
336
337 for (auto& item : container)
338 {
339
340 this->set_key(item);
341
342 }
343
344 }
345
346
347 template < prototype_container CONTAINER >
348 void erase_keys(const CONTAINER& container)
349 {
350
351 for (auto& KEY : container)
352 {
353
354 this->erase(KEY);
355
356 }
357
358 }
359
360
361 void container_ok() const;
362
363
364 //void construct();
365
366
367 // ::collection::count get_count() const;
368 // ::collection::count get_size() const;
369 // ::collection::count size() const;
370 // ::collection::count count() const;
371 // bool is_empty() const;
372 // bool empty() const;
373 //
374
375
376 //find
377 //bool find(ARG_KEY key, PAYLOAD& rValue) const;
378 //const_iterator find(ARG_KEY key) const;
379 //iterator find(ARG_KEY key);
380
381
382 //PAYLOAD * defer_get(ARG_KEY key);
383
384
385 //inline typename pair_map_base < PAIR >::iterator get_item(ARG_KEY key);
386
387
388 // template < typename TITEM >
389 // auto pop(const TITEM & key)
390 // {
391 //
392 // auto value = operator[](key);
393 //
394 // this->erase_item(key);
395 //
396 // return value;
397 //
398 // }
399 //
400 // // //Operations
401 // //find and add if not there
402 // inline PAYLOAD & operator[](ARG_KEY key);
403 // inline const PAYLOAD & operator[](ARG_KEY key) const;
404
405
406 iterator set_at(ARG_KEY key, ARG_PAYLOAD payload)
407 {
408
409 auto p = this->get(key);
410
411 p->defer_set_payload(payload);
412
413 return p;
414
415 }
416
417
418 //bool unhash(iterator iterator);
419
420 //removing existing (key, ?) node
421 //inline bool erase_item(ARG_KEY key) { auto p = this->find_item(key); return p ? this->erase(p) : false; }
422
423
424 template < typename PAYLOAD2 >
425 iterator find_first_payload(const PAYLOAD2 & payload) const;
426
427
428 template < typename PAYLOAD2 >
429 inline bool erase_first_payload(const PAYLOAD2 payload)
430 {
431
432 auto iterator = this->find_first_payload(payload);
433
434 if (!iterator)
435 {
436
437 return false;
438
439 }
440
441 this->erase(iterator);
442
443 return true;
444
445 }
446
447
448
449 inline auto items() { return ::range<item_iterator>(*(item_iterator *)&this->begin(), *(item_iterator *)&this->end()); }
450 inline auto payloads() { return ::range<payload_iterator>(*(payload_iterator *)&this->begin(), *(payload_iterator *)&this->end()); }
451 inline auto items() const { return ::range<const_item_iterator>((item_iterator)this->begin(), (item_iterator)this->end()); }
452 inline auto payloads() const { return ::range<const_payload_iterator>((payload_iterator )this->begin(), (payload_iterator)this->end()); }
453
454
455
456 //
457 // ::collection::count key_count(ARG_KEY key) const;
458 // bool has_key(ARG_KEY key) const;
459 // bool contains_key(ARG_KEY key) const;
460
461 //iterating all (key, value) pairs
462// POSITION get_start_position() const;
463
464 //inline const iterator get_start() const;
465 //inline iterator get_start();
466
467 //void get_next(iterator & rNextPosition, ITEM& rKey, PAYLOAD& rValue) const;
468
469 //const iterator get_next(const iteratorpnodeRet) const;
470 //iterator get_next(const iteratorpnodeRet);
471
472 // //advanced features for derived classes
473 // ::u32 GetHashTableSize() const
474 // {
475 //
476 // return this->m_hashtable.GetHashTableSize();
477 // //
478 // // }
479 //
480 //
481 // void InitHashTable(::u32 hashSize,bool bAllocNow = true);
482 //
483 //
484 // PAYLOAD get(ARG_KEY key, ARG_PAYLOAD valueDefault);
485 //
486
487
488 void merge_set(const node_set_base & set)
489 {
490
491 for(auto & item : set)
492 {
493
494 this->set_item(item);
495
496 }
497
498 }
499
500
501 void defer_merge(const node_set_base& set)
502 {
503
504 for (auto& item : set)
505 {
506
507 if (!this->has(item.key()))
508 {
509
510 this->set_item(item);
511
512 }
513
514 }
515
516 }
517
518
519 //inline iterator find_item(ARG_KEY key) const { return find_node(key); }
520
521 //using BASE_SET::find_item;
522 //inline const_iterator find_item(ARG_KEY key) const { return ((pair_map_base *) this)->find_item(key); }
523
524
525 //BASE_NODE * new_node(ARG_KEY key, ::u32 uiPack, ::u32 uiHash);
526 inline void hash(iterator iterator, ::u32 uiPack, ::u32 uiHash);
527 void attach(iterator iterator, ::u32 uiPack, ::u32 uiHash);
528 //bool erase(iterator iterator);
529 void detach(iterator iterator);
530 void hash(::u32& uiPack, ::u32& uiHash, ARG_KEY) const;
531 //inline iterator node_at(ARG_KEY, ::u32 & uiPack, ::u32 & uiHash) const;
532 //inline const_iterator node_at(ARG_KEY, ::u32& uiPack, ::u32& uiHash) const;
533
534 // void transfer(iterator iterator, pair_map_base * iterator_map = nullptr);
535 // void transfer(pair_map_base* iterator_map, ARG_KEY key);
536
539
540
541 template < class ARRAY >
542 bool erase_key_array(ARRAY a)
543 {
544
545 bool bRemoved = false;
546
547 for(::collection::index i = 0; i < a.get_count(); i++)
548 {
549
550 bRemoved |= erase_key(a[i]);
551
552 }
553
554 return bRemoved;
555
556 }
557
558
559 template < class ARRAY >
560 ::collection::count erase_node_array(ARRAY a)
561 {
562
563 ::collection::count countRemoved = 0;
564
565 for(::collection::index i = 0; i < a.get_count(); i++)
566 {
567
568 if(erase_node(a[i]))
569 {
570
571 countRemoved++;
572
573 }
574
575 }
576
577 return countRemoved;
578
579 }
580
581
582 //void merge_set(const node_set_base & set)
583 //{
584
585 // for (auto & item : set)
586 // {
587
588 // this->set_item(item);
589
590 // }
591
592 //}
593
594
595
596
597
598 //virtual void on_after_read() override {}
599
600
601 //PAIR & element_at(::collection::index iIndex)
602 //{
603 // return this->elements().element_at(iIndex);
604 //}
605 //
606 // template < typename PRED >
607 // typename BASE_NODE * predicate_find(PRED pred)
608 // {
609 //
610 // auto pnode = this->begin();
611 //
612 // while (::is_ok(pnode))
613 // {
614 //
615 // if (pred(pnode))
616 // {
617 //
618 // return p;
619 //
620 // }
621 //
622 // p++;
623 //
624 // }
625 //
626 // return nullptr;
627 //
628 // }
629
630 // node_set_base & operator = (const node_set_base & m);
631 //
632 //
633 // template < typename TYPE >
634 // ::pointer<TYPE>get_typed_ptr(::collection::index i = 0)
635 // {
636 //
637 // ::pointer<TYPE>p;
638 //
639 // for(auto & node : *this)
640 // {
641 //
642 // p = (*node).element2();
643 //
644 // if(p)
645 // {
646 //
647 // if(i <= 0)
648 // {
649 //
650 // return p;
651 //
652 // }
653 //
654 // i--;
655 //
656 // }
657 //
658 // }
659 //
660 // return nullptr;
661 //
662 // }
663 //
664
665
666 void transfer(iterator iterator, node_set_base * pnodesetbase = nullptr);
667 void transfer(node_set_base * pnodesetbase, ARG_KEY key);
668
669
670};
671
672
673template < typename NODE, enum_allocate t_eallocate >
674inline ::collection::count node_set_base < NODE, t_eallocate >::get_count() const
675{
676 return m_count;
677}
678
679template < typename NODE, enum_allocate t_eallocate >
680inline ::collection::count node_set_base < NODE, t_eallocate >::get_size() const
681{
682 return m_count;
683}
684
685template < typename NODE, enum_allocate t_eallocate >
686inline ::collection::count node_set_base < NODE, t_eallocate >::count() const
687{
688 return m_count;
689}
690
691template < typename NODE, enum_allocate t_eallocate >
692inline ::collection::count node_set_base < NODE, t_eallocate >::size() const
693{
694 return m_count;
695}
696
697template < typename NODE, enum_allocate t_eallocate >
698node_set_base < NODE, t_eallocate > & node_set_base < NODE, t_eallocate >::operator = (const node_set_base & m)
699{
700
701 if(this != &m)
702 {
703
704 erase_all();
705
706 for(auto & item : m)
707 {
708
709 set_item(item);
710
711 }
712
713 }
714
715 return *this;
716
717}
718
719
720template < typename NODE, enum_allocate t_eallocate >
721inline bool node_set_base < NODE, t_eallocate >::is_empty() const
722{
723
724 return m_count == 0;
725
726}
727
728
729template < typename NODE, enum_allocate t_eallocate >
730inline bool node_set_base < NODE, t_eallocate >::empty() const
731{
732
733 return m_count == 0;
734
735}
736
737
738template < typename NODE, enum_allocate t_eallocate >
739inline typename node_set_base < NODE, t_eallocate >::iterator
740node_set_base < NODE, t_eallocate >::set_key(ARG_KEY key)
741{
742
743 auto iterator = get(key);
744
745 return iterator;
746
747}
748
749
750template < typename NODE, enum_allocate t_eallocate >
751void node_set_base < NODE, t_eallocate >::construct()
752{
753
754 m_count = 0;
755 this->m_begin = nullptr;
756 this->m_end = nullptr;
757
758}
759
760
761template < typename NODE, enum_allocate t_eallocate >
762node_set_base < NODE, t_eallocate >::node_set_base()
763{
764
765 construct();
766
767}
768
769
770template < typename NODE, enum_allocate t_eallocate >
771node_set_base < NODE, t_eallocate >::node_set_base(const ::std::initializer_list < BASE_ITEM > & items)
772{
773
774 construct();
775
776 for(auto & item : items)
777 {
778
779 set_item(item);
780
781 }
782
783}
784
785
786template < typename NODE, enum_allocate t_eallocate >
787node_set_base < NODE, t_eallocate >::node_set_base(BASE_ITEM * pitem, ::i32 iCount)
788{
789
790 construct();
791
792 for(::i32 i = 0; i < iCount; i++)
793 {
794
795 set_item(pitem[i]);
796
797 }
798
799}
800
801
802template < typename NODE, enum_allocate t_eallocate >
803node_set_base < NODE, t_eallocate >::node_set_base(const node_set_base & m)
804{
805
806 construct();
807
808 for(auto & item : m)
809 {
810
811 set_item(item);
812
813 }
814
815}
816
817
818template < typename NODE, enum_allocate t_eallocate >
819void node_set_base < NODE, t_eallocate >::erase_all()
820{
821
822 //ASSERT_OK(this);
823
824 if(this->begin())
825 {
826 // destroy elements (KEYs and loads - KEY load pair)
827
828 iterator pnext;
829
830 for (auto p = this->begin(); p; p = pnext)
831 {
832
833 pnext = p + 1;
834
835 //__delete(p.get());
836 delete p.get();
837
838 }
839
840 }
841
842 m_hashtable.erase_all();
843
844 m_count = 0;
845 //this->m_pnodeFree = nullptr;
846
847 //if(m_pplex != nullptr)
848 //{
849
850 // m_pplex->FreeDataChain();
851 // m_pplex = nullptr;
852
853 //}
854
855 this->m_begin = nullptr;
856
857}
858
859
860template < typename NODE, enum_allocate t_eallocate >
861inline void node_set_base < NODE, t_eallocate >::clear()
862{
863 erase_all();
864}
865
866//template < typename NODE, enum_allocate t_eallocate >
867//inline void node_set_base < NODE, t_eallocate >::Empty()
868//{
869// clear();
870//}
871
872template < typename NODE, enum_allocate t_eallocate >
873node_set_base < NODE, t_eallocate >::~node_set_base()
874{
875 erase_all();
876 ASSERT(m_count == 0);
877}
878
879template < typename NODE, enum_allocate t_eallocate >
880typename node_set_base < NODE, t_eallocate >::BASE_NODE*
881node_set_base < NODE, t_eallocate >::__new_node(ARG_KEY key)
882{
883
884 if constexpr(t_eallocate == e_allocate_malloc)
885 {
886
887 auto pnode = (BASE_NODE*)::malloc(sizeof(BASE_NODE));
888
889 ::new (pnode) BASE_NODE(key);
890
891 return pnode;
892
893 }
894 else
895 {
896
897 auto pnode = øraw_new BASE_NODE(key);
898
899 return pnode;
900
901 }
902
903}
904
905
906template < typename NODE, enum_allocate t_eallocate >
907void node_set_base < NODE, t_eallocate >::__delete_node(BASE_NODE* pnode)
908{
909
910 if constexpr (t_eallocate == e_allocate_malloc)
911 {
912
913 pnode->~BASE_NODE();
914
915 ::free(pnode);
916
917 }
918 else
919 {
920
921 delete pnode;
922
923 }
924
925}
926
927
928template < typename NODE, enum_allocate t_eallocate >
929typename node_set_base < NODE, t_eallocate >::iterator node_set_base < NODE, t_eallocate >::_new(ARG_KEY key, ::u32& uiPack, ::u32& uiHash)
930{
931
932 // not precise (memleak? a watch dog can restart from the last check point... continuable tasks need...) but self-healing(self-recoverable/not-fatal)...
933 if (::is_null(m_hashtable.m_ppHash))
934 {
935
936 InitHashTable(m_hashtable.GetHashTableSize());
937
938 }
939
940 ENSURE(m_hashtable.m_ppHash);
941
942 auto p = this->__new_node(key);
943
944 if(this->m_begin)
945 {
946
947 this->m_begin.m_p->m_back = p;
948
949 }
950
951 if(m_hashtable.m_ppHash[uiPack])
952 {
953
954 m_hashtable.m_ppHash[uiPack]->m_pbackHash = &p->m_nextHash;
955
956 }
957
958 p->m_nextHash = m_hashtable.m_ppHash[uiPack];
959
960 m_hashtable.m_ppHash[uiPack] = p;
961
962 p->m_pbackHash = &m_hashtable.m_ppHash[uiPack];
963
964 p->m_next = this->m_begin.get();
965
966 this->m_begin = p;
967
968 this->m_begin.m_p->m_back = nullptr;
969
970 m_count++;
971
972 ASSERT(m_count > 0); // make sure we don't overflow
973
974 return p;
975
976}
977
978
979template < typename NODE, enum_allocate t_eallocate >
980void node_set_base < NODE, t_eallocate >::_free(iterator iterator)
981{
982
983 auto pnode = iterator.m_p;
984
985 auto next = pnode->m_next;
986
987 if(pnode->m_next != nullptr)
988 {
989
990 pnode->m_next->m_back = pnode->m_back;
991
992 }
993
994 if(pnode->m_back != nullptr)
995 {
996
997 pnode->m_back->m_next = pnode->m_next;
998
999 }
1000
1001 if(this->m_begin.get() == pnode)
1002 {
1003
1004 this->m_begin = next;
1005
1006 if(this->m_begin)
1007 {
1008
1009 this->m_begin.m_p->m_back = nullptr;
1010
1011 }
1012
1013 }
1014
1015 //__delete(iterator.get());
1016
1017 this->__delete_node(pnode);
1018
1019 //iterator->m_next = this->m_pnodeFree;
1020
1021 //this->m_pnodeFree = iterator;
1022
1023 m_count--;
1024
1025 ASSERT(m_count >= 0); // make sure we don't underflow
1026
1027 // if no more elements, cleanup completely
1028 if (m_count == 0)
1029 {
1030
1031 erase_all();
1032
1033 }
1034
1035}
1036
1037
1038template < typename NODE, enum_allocate t_eallocate >
1039typename node_set_base < NODE, t_eallocate >::iterator
1040node_set_base < NODE, t_eallocate >::_find(ARG_KEY key, ::u32& uiPack, ::u32& uiHash) const
1041{
1042
1043 uiHash = ::as_hash32(key).m_u;
1044
1045 uiPack = uiHash % m_hashtable.GetHashTableSize();
1046
1047 if (is_empty())
1048 {
1049
1050 return nullptr;
1051
1052 }
1053
1054 for(auto p = m_hashtable.m_ppHash[uiPack]; p; p = p->m_nextHash)
1055 {
1056
1057 if (EqualElements<ARG_KEY>(p->key(), key))
1058 {
1059
1060 return p;
1061
1062 }
1063
1064 }
1065
1066 return nullptr;
1067
1068}
1069
1070
1071// template < typename NODE, enum_allocate t_eallocate >
1072// bool node_set_base < NODE, t_eallocate >::find(ARG_KEY key, PAYLOAD & payload) const
1073// {
1074//
1075// ::u32 uiPack, uiHash;
1076//
1077// auto p = find_node(key, uiPack, uiHash);
1078//
1079// if (!p)
1080// {
1081//
1082// return false; // not in set
1083//
1084// }
1085//
1086// payload = p->payload();
1087//
1088// return true;
1089//
1090// }
1091
1092//
1093// //template < typename NODE, enum_allocate t_eallocate >
1094//
1095//
1096// template < typename NODE, enum_allocate t_eallocate >
1097// typename node_set_base < NODE, t_eallocate >::const_iterator
1098// node_set_base < NODE, t_eallocate >::find(ARG_KEY key) const
1099// {
1100//
1101// return ((node_set_base *)this)->find(key);
1102//
1103// }
1104
1105
1106template < typename NODE, enum_allocate t_eallocate >
1107typename node_set_base < NODE, t_eallocate >::const_iterator
1108node_set_base < NODE, t_eallocate >::find(ARG_KEY key) const
1109{
1110
1111 ::u32 uiPack;
1112
1113 ::u32 uiHash;
1114
1115 auto pnode = _find(key, uiPack, uiHash);
1116
1117 return pnode;
1118
1119}
1120
1121
1122template < typename NODE, enum_allocate t_eallocate >
1123bool node_set_base < NODE, t_eallocate >::find(ARG_KEY key, PAYLOAD & payload) const
1124{
1125
1126 auto iterator = find(key);
1127
1128 if (!iterator)
1129 {
1130
1131 return false;
1132
1133 }
1134
1135 payload = iterator->payload();
1136
1137 return true;
1138
1139}
1140
1141
1142template < typename NODE, enum_allocate t_eallocate >
1143typename node_set_base < NODE, t_eallocate >::PAYLOAD *
1144node_set_base < NODE, t_eallocate >::defer_get(ARG_KEY key) const
1145{
1146
1147 auto iterator = find(key);
1148
1149 if (!iterator)
1150 {
1151
1152 return nullptr;
1153
1154 }
1155
1156 return &iterator->payload();
1157
1158}
1159
1160
1161// template < typename NODE, enum_allocate t_eallocate >
1162// inline typename node_set_base < NODE, t_eallocate >::iterator
1163// node_set_base < NODE, t_eallocate >::find(ARG_KEY key)
1164// {
1165//
1166// ::u32 nCluster, nHash;
1167//
1168// auto iterator = ((node_set_base *)this)->_find(key, nCluster, nHash);
1169//
1170// return iterator;
1171//
1172// }
1173
1174
1175// template < typename NODE, enum_allocate t_eallocate >
1176// inline typename node_set_base < NODE, t_eallocate >::const_iterator
1177// node_set_base < NODE, t_eallocate >::find(ARG_KEY key) const
1178// {
1179//
1180// return ((node_set_base *)this)->find(key);
1181//
1182// }
1183//
1184// template < typename NODE, enum_allocate t_eallocate >
1185// typename node_set_base < NODE, t_eallocate >::const_iterator
1186// node_set_base < NODE, t_eallocate >::get(ARG_KEY key) const
1187// {
1188//
1189// return ((node_set_base*)this)->get(key);
1190//
1191// }
1192
1193
1194template < typename NODE, enum_allocate t_eallocate >
1195typename node_set_base < NODE, t_eallocate >::iterator
1196node_set_base < NODE, t_eallocate >::get(ARG_KEY key)
1197{
1198
1199 ::u32 uiPack, uiHash;
1200
1201 auto iterator = _find(key, uiPack, uiHash);
1202
1203 if(!iterator)
1204 {
1205
1206 iterator = _new(key, uiPack, uiHash);
1207
1208 }
1209
1210 return iterator;
1211
1212}
1213
1214
1215template < typename NODE, enum_allocate t_eallocate >
1216typename node_set_base < NODE, t_eallocate >::PAYLOAD & node_set_base < NODE, t_eallocate >::operator[](ARG_KEY key)
1217{
1218
1219 return get(key)->payload();
1220
1221}
1222
1223
1224template < typename NODE, enum_allocate t_eallocate >
1225const typename node_set_base < NODE, t_eallocate >::PAYLOAD & node_set_base < NODE, t_eallocate >::operator[](ARG_KEY key) const
1226{
1227
1228 auto iterator = find(key);
1229
1230 if (!iterator)
1231 {
1232
1233 throw_exception(error_key_not_found);
1234
1235 }
1236
1237 return iterator->payload();
1238
1239}
1240
1241
1242template < typename NODE, enum_allocate t_eallocate >
1243inline bool node_set_base < NODE, t_eallocate >::erase(iterator iterator)
1244{
1245
1246 if(iterator.m_p->m_nextHash != nullptr)
1247 {
1248
1249 iterator.m_p->m_nextHash->m_pbackHash = iterator.m_p->m_pbackHash;
1250
1251 }
1252
1253 *iterator.m_p->m_pbackHash = iterator.m_p->m_nextHash;
1254
1255 _free(iterator);
1256
1257 return true;
1258
1259}
1260
1261
1262template<typename NODE, enum_allocate t_eallocate>
1263inline bool node_set_base<NODE, t_eallocate>::contains(iterator iterator) const
1264{
1265
1266 auto it = find(iterator->key());
1267
1268 if (!it)
1269 {
1270
1271 return false;
1272
1273 }
1274
1275 return it.m_p == iterator.m_p;
1276
1277}
1278
1279
1280template < typename NODE, enum_allocate t_eallocate >
1281inline ::collection::count node_set_base < NODE, t_eallocate >::count(ARG_KEY key) const
1282{
1283
1284 return this->find(key) ? 1 : 0;
1285
1286}
1287
1288
1289template < typename NODE, enum_allocate t_eallocate >
1290bool node_set_base < NODE, t_eallocate >::has(ARG_KEY key) const
1291{
1292
1293 return this->count(key) > 0;
1294
1295}
1296
1297
1298template < typename NODE, enum_allocate t_eallocate >
1299bool node_set_base < NODE, t_eallocate >::contains(ARG_KEY key) const
1300{
1301
1302 return this->has(key);
1303
1304}
1305
1306
1307//template < typename NODE, enum_allocate t_eallocate >
1308//void node_set_base < NODE, t_eallocate >::get_next(iterator & iterator,
1309// KEY& rKey, KEY& payload) const
1310//{
1311//
1312// rKey = iterator->KEY();
1313//
1314// payload = iterator->KEY();
1315//
1316// iterator = iterator->m_next;
1317//
1318//}
1319//
1320//
1321//template < typename NODE, enum_allocate t_eallocate >
1322//inline const typename node_set_base < NODE, t_eallocate >::iterator
1323//node_set_base < NODE, t_eallocate >::get_next(const iterator iterator) const
1324//{
1325//
1326// return iterator->m_next;
1327//
1328//}
1329//
1330//
1331//template < typename NODE, enum_allocate t_eallocate >
1332//inline typename node_set_base < NODE, t_eallocate >::iterator
1333//node_set_base < NODE, t_eallocate >::get_next(const iterator iterator)
1334//{
1335//
1336// return iterator->m_next;
1337//
1338//}
1339
1340
1341template < typename NODE, enum_allocate t_eallocate >
1342typename node_set_base < NODE, t_eallocate >::PAYLOAD node_set_base < NODE, t_eallocate > ::defer_get(ARG_KEY key, ARG_PAYLOAD payloadDefault) const
1343{
1344
1345 auto iterator = find(key);
1346
1347 if (!iterator)
1348 {
1349
1350 return payloadDefault;
1351
1352 }
1353
1354 return iterator->payload();
1355
1356}
1357
1358
1359//template < typename NODE, enum_allocate t_eallocate >
1360//void node_set_base < NODE, t_eallocate >::assert_ok() const
1361//{
1362//
1363// ::matter::assert_ok();
1364//
1365// ASSERT(GetHashTableSize() > 0);
1366//
1367// ASSERT(m_count == 0 || m_hashtable.m_ppHash != nullptr);
1368// // non-empty set should have hash table
1369//
1370//}
1371//
1372
1373using f64_set = set < ::f64 >;
1374
1375using dword_set = set < ::u32 >;
1376
1377using uptr_set = set < ::uptr >;
1378
1379//template < typename KEY_TYPE >
1380//class KEY
1381//{
1382//
1383//
1384// using KEY = KEY_TYPE;
1385// using TYPE = KEY;
1386// using ARG_TYPE = argument_of < KEY & >;
1387//
1388//
1389// // Contract
1390// // KEY & KEY();
1391// // KEY & KEY();
1392// // ARG_KEY key() const;
1393// // ARG_KEY key() const;
1394//
1395//};
1396
1397
1398template < typename NODE, enum_allocate t_eallocate >
1399using key_set = node_set_base < NODE, t_eallocate >;
1400
1401
1402#define __declare_key(xkeytype, xkey) \
1403struct xkeytype : public ::KEY < xkeytype > \
1404{ \
1405\
1406 PAIR_DEFAULT_IMPL(xkeytype, KEY, ARG_KEY, xkey); \
1407 KEY & KEY() { return xkey; } \
1408 ARG_KEY key() const { return xkey; } \
1409}
1410
1411
1412#ifdef CPP17
1413#define __declare_key_tuple_size(KEY) \
1414template<> ALIENATED_ANDROID_ANARCHY ::std::tuple_size< KEY > : ::std::integral_constant<size_t, 1> {} }
1415#endif
1416
1417
1418#define __declare_set(xsettype, xkeyvaluetype, xkeytype, xkey, xvaluetype, xvalue) \
1419__declare_key_value(xkeyvaluetype, xkeytype, xkey, xvaluetype, xvalue); \
1420using xsettype = pair_set < xkeyvaluetype >
1421
1422
1423#ifdef CPP17
1424#define __declare_set_key_value(xsettype, xkeyvaluetype, xkeytype, xkey, xvaluetype, xvalue) \
1425__declare_set(xkeyvaluetype, xkeytype, xkey, xvaluetype, xvalue); \
1426__declare_pair_tuple_size(xsettype)
1427#else
1428
1429#define __declare_set_key_value(xsettype, xkeyvaluetype, xkeytype, xkey, xvaluetype, xvalue) \
1430__declare_set(xkeyvaluetype, xkeytype, xkey, xvaluetype, xvalue);
1431
1432#endif
1433
1434
1435using iptr_set = set < iptr >;
1436
1437using index_set = set < ::collection::index >;
1438
1439using string_set = set < string >;
1440
1441
1442
1443
1444//#pragma once
1445
1446
1447template < typename NODE, enum_allocate t_eallocate >
1448void node_set_base < NODE, t_eallocate >::InitHashTable(
1449 ::u32 nHashSize, bool bAllocNow)
1450//
1451// Used to force allocation of a hash table or to override the default
1452// hash table i32_size of (which is fairly small)
1453{
1454
1455 //ASSERT_OK(this);
1456 ASSERT(this->m_count == 0);
1457 ASSERT(nHashSize > 0);
1458
1459 this->m_hashtable.InitHashTable(nHashSize,bAllocNow);
1460
1461}
1462
1463
1464template < typename NODE, enum_allocate t_eallocate >
1465inline bool node_set_base < NODE, t_eallocate >::unhash(iterator iterator)
1466// erase - return true if erased
1467{
1468
1469 if(::is_set(iterator.m_p->m_nextHash))
1470 {
1471
1472 iterator.m_p->m_nextHash->m_pbackHash = iterator.m_p->m_pbackHash;
1473
1474 }
1475
1476 *iterator.m_p->m_pbackHash = iterator.m_p->m_nextHash;
1477
1478 return true;
1479
1480}
1481
1482
1483template < typename ITEM, enum_allocate t_eallocate >
1484void node_set_base < ITEM, t_eallocate >::transfer(node_set_base* pnodesetbase, ARG_KEY key)
1485{
1486
1487 ::u32 uiPack;
1488
1489 ::u32 uiHash;
1490
1491 auto pnode = pnodesetbase->_find(key, uiPack, uiHash);
1492
1493 if (pnode)
1494 {
1495
1496 pnodesetbase->detach(pnode);
1497
1498 attach(pnode, uiPack, uiHash);
1499
1500 }
1501
1502}
1503
1504
1505template < typename ITEM, enum_allocate t_eallocate >
1506void node_set_base < ITEM, t_eallocate >::transfer(iterator iterator, node_set_base * pnodesetbase)
1507{
1508
1509 if (pnodesetbase == this)
1510 {
1511
1512 return;
1513
1514 }
1515
1516 if (::is_set(pnodesetbase))
1517 {
1518
1519 pnodesetbase->detach(iterator);
1520
1521 }
1522
1523 ::u32 uiPack;
1524
1525 ::u32 uiHash;
1526
1527 hash(uiPack, uiHash, iterator->key());
1528
1529 attach(iterator, uiPack, uiHash);
1530
1531}
1532
1533
1534
1535template < typename ITEM, enum_allocate t_eallocate >
1536void node_set_base < ITEM, t_eallocate >::attach(iterator iterator, ::u32 uiPack, ::u32 uiHash)
1537{
1538
1539 hash(iterator, uiPack, uiHash);
1540
1541 auto pnode = iterator.m_p;
1542
1543 if (this->m_begin)
1544 {
1545
1546 this->m_begin.m_p->m_back = pnode;
1547
1548 }
1549
1550 pnode->m_next = this->begin().m_p;
1551
1552 this->begin() = pnode;
1553
1554 this->begin().m_p->m_back = nullptr;
1555
1556 this->m_count++;
1557
1558 ASSERT(this->m_count > 0); // make sure we don't overflow
1559
1560}
1561
1562
1563template < typename ITEM, enum_allocate t_eallocate >
1564void node_set_base < ITEM, t_eallocate >::hash(iterator iterator, ::u32 uiPack, ::u32 uiHash)
1565{
1566
1567 auto pnode = iterator.m_p;
1568
1569 // not precise (memleak? a watch dog can restart from the last check point... continuable tasks need...) but self-healing(self-recoverable/not-fatal)...
1570 if (::is_null(this->m_hashtable.m_ppHash))
1571 {
1572
1573 InitHashTable(this->m_hashtable.GetHashTableSize());
1574
1575 }
1576
1577 if (::is_set(this->m_hashtable.m_ppHash[uiPack]))
1578 {
1579
1580 this->m_hashtable.m_ppHash[uiPack]->m_pbackHash = &pnode->m_nextHash;
1581
1582 }
1583
1584 pnode->m_nextHash = this->m_hashtable.m_ppHash[uiPack];
1585
1586 this->m_hashtable.m_ppHash[uiPack] = pnode;
1587
1588 pnode->m_pbackHash = &this->m_hashtable.m_ppHash[uiPack];
1589
1590}
1591
1592
1593template < typename ITEM, enum_allocate t_eallocate >
1594void node_set_base < ITEM, t_eallocate >::hash(::u32& uiPack, ::u32& uiHash, ARG_KEY key) const
1595{
1596
1597 uiHash = ::as_hash32(key).m_u;
1598
1599 uiPack = uiHash % this->m_hashtable.GetHashTableSize();
1600
1601}
1602
1603
1604template < typename ITEM, enum_allocate t_eallocate >
1605void node_set_base < ITEM, t_eallocate >::detach(iterator iterator)
1606{
1607
1608 auto pnode = iterator.m_p;
1609
1610 this->unhash(iterator);
1611
1612 auto next = pnode->m_next;
1613
1614 if (::is_set(pnode->m_next))
1615 {
1616
1617 pnode->m_next->m_back = pnode->m_back;
1618
1619 }
1620
1621 if (::is_set(pnode->m_back))
1622 {
1623
1624 pnode->m_back->m_next = pnode->m_next;
1625
1626 }
1627
1628 if (this->m_begin.get() == pnode)
1629 {
1630
1631 this->m_begin = next;
1632
1633 if (::is_set(this->m_begin))
1634 {
1635
1636 this->m_begin.m_p->m_back = nullptr;
1637
1638 }
1639
1640 }
1641
1642 //delete iterator;
1643
1644 //iterator->m_next = this->m_pnodeFree;
1645
1646 //this->m_pnodeFree = iterator;
1647
1648 this->m_count--;
1649
1650 ASSERT(this->m_count >= 0); // make sure we don't underflow
1651
1652 // if no more elements, cleanup completely
1653 if (this->m_count == 0)
1654 {
1655
1656 this->erase_all();
1657
1658 }
1659
1660}
1661
1662
1663
1664
1665
1666template < typename ITEM, enum_allocate t_eallocate >
1667template < typename PAYLOAD2 >
1668inline typename node_set_base < ITEM, t_eallocate >::iterator
1669node_set_base < ITEM, t_eallocate >::find_first_payload(const PAYLOAD2 & payload) const
1670{
1671
1672 auto p = this->begin();
1673
1674 while(p)
1675 {
1676
1677 if(p->payload() == payload)
1678 {
1679
1680 return p;
1681
1682 }
1683
1684 p++;
1685
1686 }
1687
1688 return nullptr;
1689
1690}
1691
1692
1693
item
Definition item.h:93
list_base
Definition list.h:33
node_set_base
Definition set.h:13
payload
Definition payload.h:54
iterator
Definition std_iterator.h:49