111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert//===----------------------------------------------------------------------===// 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// The LLVM Compiler Infrastructure 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is dual licensed under the MIT and the University of Illinois Open 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Source Licenses. See LICENSE.TXT for details. 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert//===----------------------------------------------------------------------===// 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <deque> 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// void pop_front() 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <deque> 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <cassert> 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include "min_allocator.h" 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttemplate <class C> 2011cd02dfb91661c65134cac258cf5924270e9d2Dan AlbertC 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albertmake(int size, int start = 0 ) 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const int b = 4096 / sizeof(int); 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert int init = 0; 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (start > 0) 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert init = (start+1) / b + ((start+1) % b != 0); 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert init *= b; 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert --init; 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert C c(init, 0); 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (int i = 0; i < init-start; ++i) 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert c.pop_back(); 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (int i = 0; i < size; ++i) 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert c.push_back(i); 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (int i = 0; i < start; ++i) 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert c.pop_front(); 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return c; 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttemplate <class C> 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albertvoid 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttest(C& c1) 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename C::iterator I; 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::size_t c1_osize = c1.size(); 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert c1.pop_front(); 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(c1.size() == c1_osize - 1); 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(distance(c1.begin(), c1.end()) == c1.size()); 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert I i = c1.begin(); 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (int j = 1; j < c1.size(); ++j, ++i) 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(*i == j); 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttemplate <class C> 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albertvoid 5711cd02dfb91661c65134cac258cf5924270e9d2Dan AlberttestN(int start, int N) 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (N != 0) 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert C c1 = make<C>(N, start); 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert test(c1); 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albertint main() 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049}; 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const int N = sizeof(rng)/sizeof(rng[0]); 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (int i = 0; i < N; ++i) 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (int j = 0; j < N; ++j) 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert testN<std::deque<int> >(rng[i], rng[j]); 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if __cplusplus >= 201103L 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049}; 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const int N = sizeof(rng)/sizeof(rng[0]); 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (int i = 0; i < N; ++i) 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (int j = 0; j < N; ++j) 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert testN<std::deque<int, min_allocator<int>> >(rng[i], rng[j]); 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} 85