3 #ifndef __CDSTEST_HDR_SKIPLIST_MAP_H
4 #define __CDSTEST_HDR_SKIPLIST_MAP_H
6 #include "map/hdr_map.h"
10 class SkipListMapHdrTest: public HashMapHdrTest
12 typedef HashMapHdrTest base_class;
13 typedef base_class::other_item wrapped_item;
14 typedef base_class::other_less wrapped_less;
16 template <class Map, typename PrintStat >
22 static int const nLimit = 10000;
23 typedef typename Map::iterator set_iterator;
24 typedef typename Map::const_iterator const_set_iterator;
29 // Test iterator - ascending order
31 CPPUNIT_ASSERT( m.empty() );
33 for ( int i = 0; i < nLimit; ++i ) {
34 CPPUNIT_ASSERT( m.insert(i, i) );
36 CPPUNIT_MSG( PrintStat()(m, "Iterator test, ascending insert order") );
40 for ( set_iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
41 CPPUNIT_ASSERT( (*it).first == it->second.m_val );
42 CPPUNIT_ASSERT( m.find( it->first ));
43 it->second.m_val = (*it).first * 2;
45 if ( it != m.begin() ) {
46 CPPUNIT_ASSERT( nPrevKey + 1 == it->first );
50 CPPUNIT_ASSERT( nCount == nLimit );
53 for ( const_set_iterator it = m.cbegin(), itEnd = m.cend(); it != itEnd; ++it ) {
54 CPPUNIT_ASSERT( (*it).first * 2 == it->second.m_val );
56 if ( it != m.cbegin() ) {
57 CPPUNIT_ASSERT( nPrevKey + 1 == it->first );
61 CPPUNIT_ASSERT( nCount == nLimit );
63 // Test iterator - descending order
65 CPPUNIT_ASSERT( m.empty() );
67 for ( int i = nLimit; i > 0; --i ) {
68 CPPUNIT_ASSERT( m.insert( i - 1, (i-1) * 2) );
70 CPPUNIT_MSG( PrintStat()(m, "Iterator test, descending insert order") );
74 for ( set_iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
75 CPPUNIT_ASSERT( (*it).first * 2 == it->second.m_val );
76 CPPUNIT_ASSERT( m.find( it->first ));
77 it->second.m_val = (*it).first;
79 if ( it != m.begin() ) {
80 CPPUNIT_ASSERT( nPrevKey + 1 == it->first );
84 CPPUNIT_ASSERT( nCount == nLimit );
87 for ( const_set_iterator it = m.cbegin(), itEnd = m.cend(); it != itEnd; ++it ) {
88 CPPUNIT_ASSERT( (*it).first == it->second.m_val );
90 if ( it != m.cbegin() ) {
91 CPPUNIT_ASSERT( nPrevKey + 1 == it->first );
95 CPPUNIT_ASSERT( nCount == nLimit );
97 // Test iterator - random order
99 CPPUNIT_ASSERT( m.empty() );
102 for ( int i = 0; i < nLimit; ++i ) {
105 std::random_shuffle( nRand, nRand + nLimit );
107 for ( int i = 0; i < nLimit; ++i ) {
108 CPPUNIT_ASSERT( m.insert( nRand[i], nRand[i]) );
110 CPPUNIT_MSG( PrintStat()(m, "Iterator test, random insert order") );
115 for ( set_iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
116 CPPUNIT_ASSERT( (*it).first == it->second.m_val );
117 CPPUNIT_ASSERT( m.find( it->first ));
118 it->second.m_val = (*it).first * 2;
120 if ( it != m.begin() ) {
121 CPPUNIT_ASSERT( nPrevKey + 1 == it->first );
123 nPrevKey = it->first;
125 CPPUNIT_ASSERT( nCount == nLimit );
128 for ( const_set_iterator it = m.cbegin(), itEnd = m.cend(); it != itEnd; ++it ) {
129 CPPUNIT_ASSERT( (*it).first * 2 == it->second.m_val );
131 if ( it != m.cbegin() ) {
132 CPPUNIT_ASSERT( nPrevKey + 1 == it->first );
134 nPrevKey = it->first;
136 CPPUNIT_ASSERT( nCount == nLimit );
139 typename Map::guarded_ptr gp;
141 for ( int i = 0; i < nLimit; ++i )
143 std::random_shuffle( arrItem, arrItem + nLimit );
145 typedef base_class::less less;
148 for ( int i = 0; i < nLimit; ++i ) {
149 int nKey = arrItem[i];
151 CPPUNIT_ASSERT( gp );
152 CPPUNIT_ASSERT( !gp.empty());
153 CPPUNIT_CHECK( gp->first == nKey );
154 CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
156 gp = m.extract( nKey );
157 CPPUNIT_ASSERT( gp );
158 CPPUNIT_ASSERT( !gp.empty());
159 CPPUNIT_CHECK( gp->first == nKey );
160 CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
163 CPPUNIT_CHECK( !gp );
164 CPPUNIT_CHECK( !m.extract(nKey));
165 CPPUNIT_CHECK( gp.empty());
167 CPPUNIT_ASSERT( m.empty());
169 for ( int i = 0; i < nLimit; ++i )
170 CPPUNIT_ASSERT( m.insert(arrItem[i], arrItem[i]*2) );
172 // extract_with/get_with
173 for ( int i = 0; i < nLimit; ++i ) {
174 int nKey = arrItem[i];
175 gp = m.get_with( wrapped_item( nKey ), wrapped_less());
176 CPPUNIT_ASSERT( gp );
177 CPPUNIT_ASSERT( !gp.empty());
178 CPPUNIT_CHECK( gp->first == nKey );
179 CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
181 gp = m.extract_with( wrapped_item( nKey ), wrapped_less());
182 CPPUNIT_ASSERT( gp );
183 CPPUNIT_ASSERT( !gp.empty());
184 CPPUNIT_CHECK( gp->first == nKey );
185 CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
187 gp = m.get_with( wrapped_item( nKey ), wrapped_less() );
188 CPPUNIT_CHECK( !gp );
189 CPPUNIT_CHECK( !m.extract_with( wrapped_item(nKey), wrapped_less()));
190 CPPUNIT_CHECK( gp.empty());
192 CPPUNIT_ASSERT( m.empty());
195 for ( int i = 0; i < nLimit; ++i )
196 CPPUNIT_ASSERT( m.insert(arrItem[i], arrItem[i]*2) );
198 for ( int i = 0; i < nLimit; ++i ) {
199 gp = m.extract_min();
200 CPPUNIT_ASSERT( gp );
201 CPPUNIT_ASSERT( !gp.empty());
202 CPPUNIT_CHECK( gp->first == i );
203 CPPUNIT_CHECK( gp->second.m_val == i * 2 );
205 CPPUNIT_CHECK( gp.empty());
207 CPPUNIT_CHECK( !m.extract_min());
210 for ( int i = 0; i < nLimit; ++i )
211 CPPUNIT_ASSERT( m.insert(arrItem[i], arrItem[i]*2) );
213 for ( int i = nLimit - 1; i >= 0; --i ) {
214 gp = m.extract_max();
215 CPPUNIT_ASSERT( gp );
216 CPPUNIT_ASSERT( !gp.empty());
217 CPPUNIT_CHECK( gp->first == i );
218 CPPUNIT_CHECK( gp->second.m_val == i * 2 );
220 CPPUNIT_CHECK( gp.empty());
222 CPPUNIT_CHECK( m.extract_max());
223 CPPUNIT_CHECK( gp.empty());
224 CPPUNIT_ASSERT( m.empty());
227 CPPUNIT_MSG( PrintStat()(m, nullptr) );
230 template <class Map, typename PrintStat >
233 typedef typename Map::iterator iterator;
234 typedef typename Map::const_iterator const_iterator;
238 CPPUNIT_ASSERT( m.empty() );
239 CPPUNIT_ASSERT( check_size( m, 0 ));
241 CPPUNIT_ASSERT( m.find(10) == m.end() );
242 iterator it = m.insert( 10 );
243 CPPUNIT_ASSERT( it != m.end() );
244 CPPUNIT_ASSERT( it->first == 10 );
245 CPPUNIT_ASSERT( it->second.m_val == 0 );
246 CPPUNIT_ASSERT( !m.empty() );
247 CPPUNIT_ASSERT( check_size( m, 1 ));
248 CPPUNIT_ASSERT( m.find(10) == it );
249 CPPUNIT_ASSERT( it->first == 10 );
250 CPPUNIT_ASSERT( it->second.m_val == 0 );
252 CPPUNIT_ASSERT( m.find(100) == m.end() );
253 it = m.insert( 100, 200 );
254 CPPUNIT_ASSERT( it != m.end() );
255 CPPUNIT_ASSERT( !m.empty() );
256 CPPUNIT_ASSERT( check_size( m, 2 ));
257 CPPUNIT_ASSERT( m.find(100) == it );
258 CPPUNIT_ASSERT( it->first == 100 );
259 CPPUNIT_ASSERT( it->second.m_val == 200 );
261 CPPUNIT_ASSERT( m.find(55) == m.end() );
262 it = m.insert_key( 55, insert_functor<Map>() );
263 CPPUNIT_ASSERT( it != m.end() );
264 CPPUNIT_ASSERT( !m.empty() );
265 CPPUNIT_ASSERT( check_size( m, 3 ));
266 CPPUNIT_ASSERT( m.find(55) == it );
267 CPPUNIT_ASSERT( it->first == 55 );
268 CPPUNIT_ASSERT( it->second.m_val == 55 * 3 );
270 CPPUNIT_ASSERT( m.insert( 55 ) == m.end() );
271 CPPUNIT_ASSERT( m.insert( 55, 10 ) == m.end() );
272 CPPUNIT_ASSERT( m.insert_key( 55, insert_functor<Map>()) == m.end() );
274 CPPUNIT_ASSERT( m.find(10) != m.end() );
275 std::pair<iterator, bool> ensureResult = m.ensure( 10 );
276 CPPUNIT_ASSERT( ensureResult.first != m.end() );
277 CPPUNIT_ASSERT( !ensureResult.second );
278 CPPUNIT_ASSERT( !m.empty() );
279 ensureResult.first->second.m_val = ensureResult.first->first * 5;
280 CPPUNIT_ASSERT( check_size( m, 3 ));
281 CPPUNIT_ASSERT( m.find(10) == ensureResult.first );
282 it = m.find_with( 10, typename base_class::less() );
283 CPPUNIT_ASSERT( it != m.end() );
284 CPPUNIT_ASSERT( it->second.m_val == 50 );
286 CPPUNIT_ASSERT( m.find_with(120, base_class::less()) == m.end() );
287 ensureResult = m.ensure( 120 );
288 CPPUNIT_ASSERT( ensureResult.first != m.end() );
289 CPPUNIT_ASSERT( ensureResult.second );
290 CPPUNIT_ASSERT( !m.empty() );
291 CPPUNIT_ASSERT( check_size( m, 4 ));
292 ensureResult.first->second.m_val = ensureResult.first->first * 5;
293 CPPUNIT_ASSERT( m.find_with(120, base_class::less()) == ensureResult.first );
294 it = m.find_with(120, base_class::less());
295 CPPUNIT_ASSERT( it != m.end() );
296 CPPUNIT_ASSERT( it->second.m_val == 120 * 5 );
299 it = m.emplace( 151 ) ; // key = 151, val = 0
300 CPPUNIT_ASSERT( it != m.end() );
301 CPPUNIT_ASSERT( it->first == 151 );
302 CPPUNIT_ASSERT( it->second.m_val == 0 );
304 it = m.emplace( 174, 471 ) ; // key == 174, val = 471
305 CPPUNIT_ASSERT( it != m.end() );
306 CPPUNIT_ASSERT( it->first == 174 );
307 CPPUNIT_ASSERT( it->second.m_val == 471 );
309 it = m.emplace( 190, value_type(91)) ; // key == 190, val = 19
310 CPPUNIT_ASSERT( it != m.end() );
311 CPPUNIT_ASSERT( it->first == 190 );
312 CPPUNIT_ASSERT( it->second.m_val == 91 );
314 it = m.emplace( 151, 1051 );
315 CPPUNIT_ASSERT( it == m.end());
318 CPPUNIT_ASSERT( it != m.end() );
319 CPPUNIT_ASSERT( it->first == 174 );
320 CPPUNIT_ASSERT( it->second.m_val == 471 );
323 CPPUNIT_ASSERT( it != m.end() );
324 CPPUNIT_ASSERT( it->first == 190 );
325 CPPUNIT_ASSERT( it->second.m_val == 91 );
328 CPPUNIT_ASSERT( it != m.end() );
329 CPPUNIT_ASSERT( it->first == 151 );
330 CPPUNIT_ASSERT( it->second.m_val == 0 );
333 CPPUNIT_ASSERT( m.empty() );
334 CPPUNIT_ASSERT( check_size( m, 0 ));
337 for ( int i = 500; i > 0; --i ) {
338 CPPUNIT_ASSERT( m.insert( i, i * 2 ) != m.end() );
340 typename Map::value_type * pVal = m.get_min();
341 CPPUNIT_ASSERT( pVal != nullptr );
342 CPPUNIT_CHECK( pVal->first == i );
343 CPPUNIT_CHECK( pVal->second.m_val == i * 2 );
346 CPPUNIT_ASSERT( m.empty() );
347 CPPUNIT_ASSERT( check_size( m, 0 ));
348 CPPUNIT_CHECK( m.get_min() == nullptr );
349 CPPUNIT_CHECK( m.get_max() == nullptr );
353 for ( int i = 0; i < 500; ++i ) {
354 CPPUNIT_ASSERT( m.insert( i, i * 2 ) != m.end() );
356 typename Map::value_type * pVal = m.get_max();
357 CPPUNIT_ASSERT( pVal != nullptr );
358 CPPUNIT_CHECK( pVal->first == i );
359 CPPUNIT_CHECK( pVal->second.m_val == i * 2 );
361 CPPUNIT_ASSERT( check_size( m, 500 ));
363 for ( iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
364 CPPUNIT_ASSERT( it->first * 2 == (*it).second.m_val );
365 it->second = it->first;
368 Map const& refMap = m;
369 for ( const_iterator it = refMap.begin(), itEnd = refMap.end(); it != itEnd; ++it ) {
370 CPPUNIT_ASSERT( it->first == it->second.m_val );
371 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
374 CPPUNIT_MSG( PrintStat()(m, "SkipListMap statistics") );
378 void SkipList_HP_less();
379 void SkipList_HP_cmp();
380 void SkipList_HP_cmpless();
381 void SkipList_HP_less_stat();
382 void SkipList_HP_cmp_stat();
383 void SkipList_HP_cmpless_stat();
384 void SkipList_HP_xorshift_less();
385 void SkipList_HP_xorshift_cmp();
386 void SkipList_HP_xorshift_cmpless();
387 void SkipList_HP_xorshift_less_stat();
388 void SkipList_HP_xorshift_cmp_stat();
389 void SkipList_HP_xorshift_cmpless_stat();
390 void SkipList_HP_turbopas_less();
391 void SkipList_HP_turbopas_cmp();
392 void SkipList_HP_turbopas_cmpless();
393 void SkipList_HP_turbopas_less_stat();
394 void SkipList_HP_turbopas_cmp_stat();
395 void SkipList_HP_turbopas_cmpless_stat();
396 void SkipList_HP_michaelalloc_less();
397 void SkipList_HP_michaelalloc_cmp();
398 void SkipList_HP_michaelalloc_cmpless();
399 void SkipList_HP_michaelalloc_less_stat();
400 void SkipList_HP_michaelalloc_cmp_stat();
401 void SkipList_HP_michaelalloc_cmpless_stat();
403 void SkipList_DHP_less();
404 void SkipList_DHP_cmp();
405 void SkipList_DHP_cmpless();
406 void SkipList_DHP_less_stat();
407 void SkipList_DHP_cmp_stat();
408 void SkipList_DHP_cmpless_stat();
409 void SkipList_DHP_xorshift_less();
410 void SkipList_DHP_xorshift_cmp();
411 void SkipList_DHP_xorshift_cmpless();
412 void SkipList_DHP_xorshift_less_stat();
413 void SkipList_DHP_xorshift_cmp_stat();
414 void SkipList_DHP_xorshift_cmpless_stat();
415 void SkipList_DHP_turbopas_less();
416 void SkipList_DHP_turbopas_cmp();
417 void SkipList_DHP_turbopas_cmpless();
418 void SkipList_DHP_turbopas_less_stat();
419 void SkipList_DHP_turbopas_cmp_stat();
420 void SkipList_DHP_turbopas_cmpless_stat();
421 void SkipList_DHP_michaelalloc_less();
422 void SkipList_DHP_michaelalloc_cmp();
423 void SkipList_DHP_michaelalloc_cmpless();
424 void SkipList_DHP_michaelalloc_less_stat();
425 void SkipList_DHP_michaelalloc_cmp_stat();
426 void SkipList_DHP_michaelalloc_cmpless_stat();
428 void SkipList_NOGC_less();
429 void SkipList_NOGC_cmp();
430 void SkipList_NOGC_cmpless();
431 void SkipList_NOGC_less_stat();
432 void SkipList_NOGC_cmp_stat();
433 void SkipList_NOGC_cmpless_stat();
434 void SkipList_NOGC_xorshift_less();
435 void SkipList_NOGC_xorshift_cmp();
436 void SkipList_NOGC_xorshift_cmpless();
437 void SkipList_NOGC_xorshift_less_stat();
438 void SkipList_NOGC_xorshift_cmp_stat();
439 void SkipList_NOGC_xorshift_cmpless_stat();
440 void SkipList_NOGC_turbopas_less();
441 void SkipList_NOGC_turbopas_cmp();
442 void SkipList_NOGC_turbopas_cmpless();
443 void SkipList_NOGC_turbopas_less_stat();
444 void SkipList_NOGC_turbopas_cmp_stat();
445 void SkipList_NOGC_turbopas_cmpless_stat();
446 void SkipList_NOGC_michaelalloc_less();
447 void SkipList_NOGC_michaelalloc_cmp();
448 void SkipList_NOGC_michaelalloc_cmpless();
449 void SkipList_NOGC_michaelalloc_less_stat();
450 void SkipList_NOGC_michaelalloc_cmp_stat();
451 void SkipList_NOGC_michaelalloc_cmpless_stat();
453 CPPUNIT_TEST_SUITE(SkipListMapHdrTest)
454 CPPUNIT_TEST(SkipList_HP_less)
455 CPPUNIT_TEST(SkipList_HP_cmp)
456 CPPUNIT_TEST(SkipList_HP_cmpless)
457 CPPUNIT_TEST(SkipList_HP_less_stat)
458 CPPUNIT_TEST(SkipList_HP_cmp_stat)
459 CPPUNIT_TEST(SkipList_HP_cmpless_stat)
460 CPPUNIT_TEST(SkipList_HP_xorshift_less)
461 CPPUNIT_TEST(SkipList_HP_xorshift_cmp)
462 CPPUNIT_TEST(SkipList_HP_xorshift_cmpless)
463 CPPUNIT_TEST(SkipList_HP_xorshift_less_stat)
464 CPPUNIT_TEST(SkipList_HP_xorshift_cmp_stat)
465 CPPUNIT_TEST(SkipList_HP_xorshift_cmpless_stat)
466 CPPUNIT_TEST(SkipList_HP_turbopas_less)
467 CPPUNIT_TEST(SkipList_HP_turbopas_cmp)
468 CPPUNIT_TEST(SkipList_HP_turbopas_cmpless)
469 CPPUNIT_TEST(SkipList_HP_turbopas_less_stat)
470 CPPUNIT_TEST(SkipList_HP_turbopas_cmp_stat)
471 CPPUNIT_TEST(SkipList_HP_turbopas_cmpless_stat)
472 CPPUNIT_TEST(SkipList_HP_michaelalloc_less)
473 CPPUNIT_TEST(SkipList_HP_michaelalloc_cmp)
474 CPPUNIT_TEST(SkipList_HP_michaelalloc_cmpless)
475 CPPUNIT_TEST(SkipList_HP_michaelalloc_less_stat)
476 CPPUNIT_TEST(SkipList_HP_michaelalloc_cmp_stat)
477 CPPUNIT_TEST(SkipList_HP_michaelalloc_cmpless_stat)
479 CPPUNIT_TEST(SkipList_DHP_less)
480 CPPUNIT_TEST(SkipList_DHP_cmp)
481 CPPUNIT_TEST(SkipList_DHP_cmpless)
482 CPPUNIT_TEST(SkipList_DHP_less_stat)
483 CPPUNIT_TEST(SkipList_DHP_cmp_stat)
484 CPPUNIT_TEST(SkipList_DHP_cmpless_stat)
485 CPPUNIT_TEST(SkipList_DHP_xorshift_less)
486 CPPUNIT_TEST(SkipList_DHP_xorshift_cmp)
487 CPPUNIT_TEST(SkipList_DHP_xorshift_cmpless)
488 CPPUNIT_TEST(SkipList_DHP_xorshift_less_stat)
489 CPPUNIT_TEST(SkipList_DHP_xorshift_cmp_stat)
490 CPPUNIT_TEST(SkipList_DHP_xorshift_cmpless_stat)
491 CPPUNIT_TEST(SkipList_DHP_turbopas_less)
492 CPPUNIT_TEST(SkipList_DHP_turbopas_cmp)
493 CPPUNIT_TEST(SkipList_DHP_turbopas_cmpless)
494 CPPUNIT_TEST(SkipList_DHP_turbopas_less_stat)
495 CPPUNIT_TEST(SkipList_DHP_turbopas_cmp_stat)
496 CPPUNIT_TEST(SkipList_DHP_turbopas_cmpless_stat)
497 CPPUNIT_TEST(SkipList_DHP_michaelalloc_less)
498 CPPUNIT_TEST(SkipList_DHP_michaelalloc_cmp)
499 CPPUNIT_TEST(SkipList_DHP_michaelalloc_cmpless)
500 CPPUNIT_TEST(SkipList_DHP_michaelalloc_less_stat)
501 CPPUNIT_TEST(SkipList_DHP_michaelalloc_cmp_stat)
502 CPPUNIT_TEST(SkipList_DHP_michaelalloc_cmpless_stat)
504 CPPUNIT_TEST(SkipList_NOGC_less)
505 CPPUNIT_TEST(SkipList_NOGC_cmp)
506 CPPUNIT_TEST(SkipList_NOGC_cmpless)
507 CPPUNIT_TEST(SkipList_NOGC_less_stat)
508 CPPUNIT_TEST(SkipList_NOGC_cmp_stat)
509 CPPUNIT_TEST(SkipList_NOGC_cmpless_stat)
510 CPPUNIT_TEST(SkipList_NOGC_xorshift_less)
511 CPPUNIT_TEST(SkipList_NOGC_xorshift_cmp)
512 CPPUNIT_TEST(SkipList_NOGC_xorshift_cmpless)
513 CPPUNIT_TEST(SkipList_NOGC_xorshift_less_stat)
514 CPPUNIT_TEST(SkipList_NOGC_xorshift_cmp_stat)
515 CPPUNIT_TEST(SkipList_NOGC_xorshift_cmpless_stat)
516 CPPUNIT_TEST(SkipList_NOGC_turbopas_less)
517 CPPUNIT_TEST(SkipList_NOGC_turbopas_cmp)
518 CPPUNIT_TEST(SkipList_NOGC_turbopas_cmpless)
519 CPPUNIT_TEST(SkipList_NOGC_turbopas_less_stat)
520 CPPUNIT_TEST(SkipList_NOGC_turbopas_cmp_stat)
521 CPPUNIT_TEST(SkipList_NOGC_turbopas_cmpless_stat)
522 CPPUNIT_TEST(SkipList_NOGC_michaelalloc_less)
523 CPPUNIT_TEST(SkipList_NOGC_michaelalloc_cmp)
524 CPPUNIT_TEST(SkipList_NOGC_michaelalloc_cmpless)
525 CPPUNIT_TEST(SkipList_NOGC_michaelalloc_less_stat)
526 CPPUNIT_TEST(SkipList_NOGC_michaelalloc_cmp_stat)
527 CPPUNIT_TEST(SkipList_NOGC_michaelalloc_cmpless_stat)
529 CPPUNIT_TEST_SUITE_END()
535 #endif // #ifndef __CDSTEST_HDR_SKIPLIST_MAP_H