• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision114 (tree)
Time2018-09-06 02:49:03
Authorquiret

Log Message

- changed the unittests .vcxproj file to wildcard-include the common headers
- added eir::Vector object for non-STL dynamic arrays
- planned eir::Map and eir::String objects
- added unit tests for eir::Vector

Change Summary

Incremental Difference

--- unittests/src/main.cpp (revision 113)
+++ unittests/src/main.cpp (revision 114)
@@ -11,6 +11,7 @@
1111 extern void HEAP_TESTS( void );
1212 extern void DTS_TESTS( void );
1313 extern void AVLTREE_TESTS( void );
14+extern void VECTOR_TESTS( void );
1415
1516 #ifdef _WIN32
1617 // Shell extension test.
@@ -26,6 +27,7 @@
2627 HEAP_TESTS();
2728 DTS_TESTS();
2829 AVLTREE_TESTS();
30+ VECTOR_TESTS();
2931
3032 //Test_DTSConditionalStructing();
3133
--- unittests/src/vector.cpp (revision 0)
+++ unittests/src/vector.cpp (revision 114)
@@ -0,0 +1,126 @@
1+// Eir Vector tests.
2+#include <sdk/Vector.h>
3+#include <sdk/OSUtils.memheap.h>
4+
5+static NativeHeapAllocator heapAlloc;
6+
7+struct VectorHeapAllocator
8+{
9+ static void* Allocate( void *objPtr, size_t memSize )
10+ {
11+ return heapAlloc.Allocate( memSize );
12+ }
13+
14+ static bool Resize( void *objPtr, void *memPtr, size_t memSize )
15+ {
16+ return heapAlloc.SetAllocationSize( memPtr, memSize );
17+ }
18+
19+ static void Free( void *objPtr, void *memPtr )
20+ {
21+ heapAlloc.Free( memPtr );
22+ }
23+};
24+
25+typedef eir::Vector <long long, VectorHeapAllocator> VectorWithHeap;
26+
27+void VECTOR_TESTS( void )
28+{
29+ printf( "testing vector simple item add and remove..." );
30+ {
31+ // Create a specialized vector that uses the native heap allocator.
32+ VectorWithHeap vector;
33+
34+ vector.AddToBack( 1 );
35+
36+ assert( vector.GetCount() == 1 );
37+
38+ vector.RemoveFromBack();
39+
40+ assert( vector.GetCount() == 0 );
41+ }
42+ printf( "ok.\n" );
43+
44+ printf( "testing vector multi item add and multi item remove..." );
45+ {
46+ const int NUM_ITEMS = 6;
47+
48+ VectorWithHeap vector;
49+
50+ for ( int n = 0; n < NUM_ITEMS; n++ )
51+ {
52+ vector.AddToBack( n );
53+ }
54+
55+ assert( vector.GetCount() == NUM_ITEMS );
56+
57+ int n = ( NUM_ITEMS - 1 );
58+
59+ while ( vector.GetCount() > 0 )
60+ {
61+ assert( vector.GetBack() == n-- );
62+
63+ vector.RemoveFromBack();
64+ }
65+ }
66+ printf( "ok.\n" );
67+
68+ printf( "testing vector add with obstruction..." );
69+ {
70+ VectorWithHeap vh1, vh2;
71+
72+ vh1.AddToBack( 5 );
73+ vh2.AddToBack( 1 );
74+ vh1.AddToBack( 1337 );
75+ }
76+ printf( "ok.\n" );
77+
78+ printf( "testing vector much addition..." );
79+ {
80+ VectorWithHeap vh;
81+
82+ for ( int n = 0; n < 1000; n++ )
83+ {
84+ vh.AddToBack( n );
85+ }
86+
87+ assert( vh.GetCount() == 1000 );
88+ }
89+ printf( "ok.\n" );
90+
91+ printf( "testing vector copy..." );
92+ {
93+ VectorWithHeap vh1, vh2;
94+
95+ vh1.AddToBack( 1 );
96+ vh2.AddToBack( 2 );
97+ vh2.AddToBack( 3 );
98+
99+ vh1 = vh2;
100+
101+ assert( vh1.GetCount() == 2 );
102+ assert( vh1[0] == 2 );
103+ assert( vh1[1] == 3 );
104+ }
105+ printf( "ok.\n" );
106+
107+ printf( "testing vector move..." );
108+ {
109+ VectorWithHeap vh1, vh2;
110+
111+ vh1.AddToBack( 5 );
112+ vh2.AddToBack( 10 );
113+
114+ vh1 = std::move( vh2 );
115+
116+ // After moving addition should still work.
117+ vh1.AddToBack( 15 );
118+
119+ assert( vh1.GetCount() == 2 );
120+
121+ vh2.AddToBack( 1 );
122+
123+ assert( vh2.GetCount() == 1 );
124+ }
125+ printf( "ok.\n" );
126+}
\ No newline at end of file
--- common/sdk/Vector.h (revision 0)
+++ common/sdk/Vector.h (revision 114)
@@ -0,0 +1,323 @@
1+/*****************************************************************************
2+*
3+* PROJECT: Multi Theft Auto v1.2
4+* LICENSE: See LICENSE in the top level directory
5+* FILE: Shared/core/Vector.h
6+* PURPOSE: Optimized Vector implementation
7+*
8+* Multi Theft Auto is available from http://www.multitheftauto.com/
9+*
10+*****************************************************************************/
11+
12+// Once we had the native heap allocator done, we realized that we had quite some cool
13+// memory semantics that the standard memory allocators (even from OS side) do not support.
14+// So we decided to roll our own SDK classes to optimize for those facts.
15+// It is also a good idea to consolidate the API; do not trust the STL too much!
16+
17+#ifndef _EIR_VECTOR_HEADER_
18+#define _EIR_VECTOR_HEADER_
19+
20+#include "eirutils.h"
21+#include "MacroUtils.h"
22+
23+#include <algorithm>
24+#include <assert.h>
25+
26+namespace eir
27+{
28+
29+template <typename structType, typename allocatorType>
30+struct Vector
31+{
32+ inline Vector( void )
33+ {
34+ this->data_entries = nullptr;
35+ this->data_count = 0;
36+ }
37+
38+private:
39+ static AINLINE structType* make_data_copy( void *objPtr, const structType *right_data, size_t right_count )
40+ {
41+ structType *data_entries = (structType*)allocatorType::Allocate( objPtr, right_count * sizeof(structType) );
42+
43+ if ( data_entries == nullptr )
44+ {
45+ throw eir_exception();
46+ }
47+
48+ try
49+ {
50+ for ( size_t n = 0; n < right_count; n++ )
51+ {
52+ new ( data_entries + n ) structType( right_data[n] );
53+ }
54+ }
55+ catch( ... )
56+ {
57+ allocatorType::Free( objPtr, data_entries );
58+
59+ throw;
60+ }
61+
62+ return data_entries;
63+ }
64+
65+public:
66+ inline Vector( const Vector& right )
67+ {
68+ size_t right_count = right.data_count;
69+ structType *data_entries = nullptr;
70+
71+ if ( right_count > 0 )
72+ {
73+ structType *right_data = right.data_entries;
74+
75+ data_entries = make_data_copy( right_data, right_count );
76+ }
77+
78+ this->data_entries = data_entries;
79+ this->data_count = right_count;
80+ }
81+
82+ // WARNING: only move if allocator stays the same.
83+ inline Vector( Vector&& right )
84+ {
85+ this->data_entries = right.data_entries;
86+ this->data_count = right.data_count;
87+
88+ right.data_entries = nullptr;
89+ right.data_count = 0;
90+ }
91+
92+private:
93+ static AINLINE void release_data( void *objPtr, structType *data_entries, size_t data_count )
94+ {
95+ if ( data_entries )
96+ {
97+ for ( size_t n = 0; n < data_count; n++ )
98+ {
99+ data_entries[n].~structType();
100+ }
101+
102+ allocatorType::Free( objPtr, data_entries );
103+ }
104+ }
105+
106+public:
107+ inline ~Vector( void )
108+ {
109+ release_data( this, this->data_entries, this->data_count );
110+ }
111+
112+ inline Vector& operator = ( const Vector& right )
113+ {
114+ size_t right_count = right.data_count;
115+ structType *new_data_entries = nullptr;
116+
117+ if ( right_count > 0 )
118+ {
119+ new_data_entries = make_data_copy( this, right.data_entries, right_count );
120+ }
121+
122+ // Swap old with new.
123+ release_data( this, this->data_entries, this->data_count );
124+
125+ this->data_entries = new_data_entries;
126+ this->data_count = right_count;
127+
128+ return *this;
129+ }
130+
131+ // WARNING: only move if allocator stays the same.
132+ inline Vector& operator = ( Vector&& right )
133+ {
134+ this->data_entries = right.data_entries;
135+ this->data_count = right.data_count;
136+
137+ right.data_entries = nullptr;
138+ right.data_count = 0;
139+
140+ return *this;
141+ }
142+
143+private:
144+ template <typename callbackType>
145+ AINLINE void recast_memory( size_t new_item_count, size_t newRequiredSize, const callbackType& cb )
146+ {
147+ // Try to fetch new memory.
148+ void *new_data_ptr = allocatorType::Allocate( this, newRequiredSize );
149+
150+ if ( new_data_ptr == nullptr )
151+ {
152+ throw eir_exception();
153+ }
154+
155+ // Construct the memory.
156+ size_t old_count = this->data_count;
157+ structType *old_data = this->data_entries;
158+
159+ try
160+ {
161+ for ( size_t n = 0; n < new_item_count; n++ )
162+ {
163+ const structType *old_entry = nullptr;
164+
165+ if ( n < old_count )
166+ {
167+ old_entry = ( old_data + n );
168+ }
169+
170+ cb( (structType*)new_data_ptr + n, old_entry, n );
171+ }
172+ }
173+ catch( ... )
174+ {
175+ // We do not add the item to our array, so clean-up.
176+ allocatorType::Free( this, new_data_ptr );
177+
178+ throw;
179+ }
180+
181+ // Delete the old data.
182+ if ( old_data )
183+ {
184+ release_data( this, old_data, old_count );
185+ }
186+
187+ this->data_entries = (structType*)new_data_ptr;
188+ this->data_count = new_item_count;
189+ }
190+
191+public:
192+ // Simple modification methods.
193+ inline void AddToBack( const structType& item )
194+ {
195+ size_t oldCount = ( this->data_count );
196+ size_t newCount = ( oldCount + 1 );
197+ size_t newRequiredSize = newCount * sizeof(structType);
198+
199+ structType *use_data = this->data_entries;
200+
201+ if ( use_data )
202+ {
203+ bool gotToResize = allocatorType::Resize( this, use_data, newRequiredSize );
204+
205+ if ( !gotToResize )
206+ {
207+ recast_memory( newCount, newRequiredSize,
208+ [&]( void *memPtr, const structType *old_item, size_t idx )
209+ {
210+ if ( idx == oldCount )
211+ {
212+ new (memPtr) structType( item );
213+ }
214+ else
215+ {
216+ new (memPtr) structType( *old_item );
217+ }
218+ });
219+
220+ return;
221+ }
222+ }
223+ else
224+ {
225+ use_data = (structType*)allocatorType::Allocate( this, newRequiredSize );
226+
227+ this->data_entries = use_data;
228+ }
229+
230+ // We just have to add at back.
231+ new ( use_data + oldCount ) structType( item );
232+
233+ this->data_count = newCount;
234+ }
235+
236+ inline void RemoveFromBack( void )
237+ {
238+ size_t oldCount = this->data_count;
239+
240+ if ( oldCount == 0 )
241+ return;
242+
243+ size_t newCount = ( oldCount - 1 );
244+
245+ // We can always shrink memory, so go for it.
246+ structType *use_data = this->data_entries;
247+
248+ use_data[ newCount ].~structType();
249+
250+ if ( newCount == 0 )
251+ {
252+ allocatorType::Free( this, use_data );
253+
254+ // Gotta do this.
255+ this->data_entries = nullptr;
256+ }
257+ else
258+ {
259+ bool resizeSuccess = allocatorType::Resize( this, use_data, sizeof(structType) * newCount );
260+
261+ assert( resizeSuccess == true );
262+ }
263+
264+ this->data_count = newCount;
265+ }
266+
267+ inline size_t GetCount( void ) const
268+ {
269+ return this->data_count;
270+ }
271+
272+ inline structType& operator [] ( size_t idx )
273+ {
274+ if ( idx >= this->data_count )
275+ {
276+ throw eir_exception();
277+ }
278+
279+ return this->data_entries[ idx ];
280+ }
281+
282+ inline const structType& operator [] ( size_t idx ) const
283+ {
284+ if ( idx >= this->data_count )
285+ {
286+ throw eir_exception();
287+ }
288+
289+ return this->data_entries[ idx ];
290+ }
291+
292+ inline structType& GetBack( void )
293+ {
294+ size_t curCount = this->data_count;
295+
296+ if ( curCount == 0 )
297+ {
298+ throw eir_exception();
299+ }
300+
301+ return this->data_entries[ curCount - 1 ];
302+ }
303+
304+ inline structType& GetBack( void ) const
305+ {
306+ size_t curCount = this->data_count;
307+
308+ if ( curCount == 0 )
309+ {
310+ throw eir_exception();
311+ }
312+
313+ return this->data_entries[ curCount - 1 ];
314+ }
315+
316+private:
317+ structType *data_entries;
318+ size_t data_count;
319+};
320+
321+}
322+
323+#endif //_EIR_VECTOR_HEADER_
\ No newline at end of file
--- common/sdk/AVLTree.h (revision 113)
+++ common/sdk/AVLTree.h (revision 114)
@@ -2,7 +2,7 @@
22 *
33 * PROJECT: Multi Theft Auto v1.2
44 * LICENSE: See LICENSE in the top level directory
5-* FILE: Shared/core/OSUtils.avltree.h
5+* FILE: Shared/core/AVLTree.h
66 * PURPOSE: AVL-tree implementation (for the native heap allocator)
77 *
88 * Multi Theft Auto is available from http://www.multitheftauto.com/
@@ -23,6 +23,7 @@
2323 // request sizes and we ought to decide fast in which free slot allocation might be
2424 // possible.
2525 // Note that this is NOT a naive implementation of AVL tree.
26+// Also used in the Map implementation.
2627
2728 // Useful to fetch an actual struct if AVLNode is a struct-member.
2829 #define AVL_GETITEM( type, nodePtr, nodeMemb ) ( (type*)( (char*)nodePtr - offsetof(type, nodeMemb) ) )
@@ -343,6 +344,9 @@
343344 return iter;
344345 }
345346
347+ // Note that we assume here that we have a "nearly-correct" AVL tree, which means
348+ // that there is at max an error of one, a difference of 2 in height compared to
349+ // the other child subtree.
346350 AINLINE void update_invalidated_tree_height( AVLNode *parent )
347351 {
348352 while ( parent != nullptr )
@@ -667,10 +671,15 @@
667671 return true;
668672 }
669673
674+ // Iterates over every same-value node of a node-stack. The walkNode must be a node
675+ // that is linked to the AVL tree (not a node-stack member itself).
670676 struct nodestack_iterator
671677 {
672678 AINLINE nodestack_iterator( AVLNode *walkNode )
673679 {
680+ // Must not be part of node-stack.
681+ assert( walkNode->parent != walkNode );
682+
674683 this->curNode = walkNode;
675684 this->nodestack = nullptr;
676685 this->doesIterateNodestack = false;
--- common/sdk/String.h (revision 0)
+++ common/sdk/String.h (revision 114)
@@ -0,0 +1,29 @@
1+/*****************************************************************************
2+*
3+* PROJECT: Multi Theft Auto v1.2
4+* LICENSE: See LICENSE in the top level directory
5+* FILE: Shared/core/String.h
6+* PURPOSE: Optimized String implementation
7+*
8+* Multi Theft Auto is available from http://www.multitheftauto.com/
9+*
10+*****************************************************************************/
11+
12+// We can also use optimized memory semantics for Strings, aswell.
13+// After all appending to a String should not cast another malloc, just a resize of
14+// the underlying memory buffer.
15+
16+#ifndef _EIR_STRING_HEADER_
17+#define _EIR_STRING_HEADER_
18+
19+#include "eirutils.h"
20+#include "MacroUtils.h"
21+
22+namespace eir
23+{
24+
25+// TODO.
26+
27+}
28+
29+#endif //_EIR_STRING_HEADER_
\ No newline at end of file
--- common/sdk/Map.h (revision 0)
+++ common/sdk/Map.h (revision 114)
@@ -0,0 +1,30 @@
1+/*****************************************************************************
2+*
3+* PROJECT: Multi Theft Auto v1.2
4+* LICENSE: See LICENSE in the top level directory
5+* FILE: Shared/core/Map.h
6+* PURPOSE: Optimized Map implementation
7+*
8+* Multi Theft Auto is available from http://www.multitheftauto.com/
9+*
10+*****************************************************************************/
11+
12+// Since we have the AVLTree class and the optimized native heap allocator semantics,
13+// we can get to implement a Map aswell. Sometimes we require Maps, so we do not want to
14+// depend on the STL things that often come with weird dependencies to third-party modules
15+// (specifically on the Linux implementation).
16+
17+#ifndef _EIR_MAP_HEADER_
18+#define _EIR_MAP_HEADER_
19+
20+#include "eirutils.h"
21+#include "MacroUtils.h"
22+
23+namespace eir
24+{
25+
26+// TODO.
27+
28+}
29+
30+#endif //_EIR_MAP_HEADER_
\ No newline at end of file
--- common/sdk/OSUtils.memheap.h (revision 113)
+++ common/sdk/OSUtils.memheap.h (revision 114)
@@ -183,7 +183,7 @@
183183
184184 size_t memOff = (size_t)memPtr;
185185
186- size_t memHandleOff = UINT_DOWNPUSH( memOff - sizeof(VMemAllocation), VMemIsland::HEADER_ALIGNMENT );
186+ size_t memHandleOff = UINT_DOWNPUSH( memOff - header_size, VMemIsland::HEADER_ALIGNMENT );
187187
188188 VMemAllocation *memHandle = (VMemAllocation*)memHandleOff;
189189
@@ -209,12 +209,16 @@
209209 inline bool SetAllocationSize( void *memPtr, size_t newSize )
210210 {
211211 // We can only fail if the allocation does not fit with regards to the remaining free space.
212+ // Or the required data size is zero (makes no sense!)
212213
214+ if ( newSize == 0 )
215+ return false;
216+
213217 size_t header_size = sizeof(VMemAllocation);
214218
215219 size_t memOff = (size_t)memPtr;
216220
217- size_t memHandleOff = UINT_DOWNPUSH( memOff - sizeof(VMemAllocation), VMemIsland::HEADER_ALIGNMENT );
221+ size_t memHandleOff = UINT_DOWNPUSH( memOff - header_size, VMemIsland::HEADER_ALIGNMENT );
218222
219223 VMemAllocation *memHandle = (VMemAllocation*)memHandleOff;
220224
@@ -277,7 +281,7 @@
277281
278282 size_t memOff = (size_t)memPtr;
279283
280- size_t memHandleOff = UINT_DOWNPUSH( memOff - sizeof(VMemAllocation), VMemIsland::HEADER_ALIGNMENT );
284+ size_t memHandleOff = UINT_DOWNPUSH( memOff - header_size, VMemIsland::HEADER_ALIGNMENT );
281285
282286 VMemAllocation *memHandle = (VMemAllocation*)memHandleOff;
283287
--- common/sdk/eirutils.h (revision 0)
+++ common/sdk/eirutils.h (revision 114)
@@ -0,0 +1,20 @@
1+/*****************************************************************************
2+*
3+* PROJECT: Multi Theft Auto v1.2
4+* LICENSE: See LICENSE in the top level directory
5+* FILE: Shared/core/eirutils.h
6+* PURPOSE: Things that are commonly used but do not warrant for own header
7+*
8+* Multi Theft Auto is available from http://www.multitheftauto.com/
9+*
10+*****************************************************************************/
11+
12+#ifndef _EIR_COMMON_SDK_UTILITIES_
13+#define _EIR_COMMON_SDK_UTILITIES_
14+
15+// TODO: flesh out this exception stuff.
16+struct eir_exception
17+{
18+};
19+
20+#endif //_EIR_COMMON_SDK_UTILITIES_
\ No newline at end of file
Show on old repository browser