1//===-- sanitizer_list_test.cc --------------------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file is a part of ThreadSanitizer/AddressSanitizer runtime. 11// 12//===----------------------------------------------------------------------===// 13#include "sanitizer_common/sanitizer_list.h" 14#include "gtest/gtest.h" 15 16namespace __sanitizer { 17 18struct ListItem { 19 ListItem *next; 20}; 21 22typedef IntrusiveList<ListItem> List; 23 24static List static_list; 25 26static void SetList(List *l, ListItem *x = 0, 27 ListItem *y = 0, ListItem *z = 0) { 28 l->clear(); 29 if (x) l->push_back(x); 30 if (y) l->push_back(y); 31 if (z) l->push_back(z); 32} 33 34static void CheckList(List *l, ListItem *i1, ListItem *i2 = 0, ListItem *i3 = 0, 35 ListItem *i4 = 0, ListItem *i5 = 0, ListItem *i6 = 0) { 36 if (i1) { 37 CHECK_EQ(l->front(), i1); 38 l->pop_front(); 39 } 40 if (i2) { 41 CHECK_EQ(l->front(), i2); 42 l->pop_front(); 43 } 44 if (i3) { 45 CHECK_EQ(l->front(), i3); 46 l->pop_front(); 47 } 48 if (i4) { 49 CHECK_EQ(l->front(), i4); 50 l->pop_front(); 51 } 52 if (i5) { 53 CHECK_EQ(l->front(), i5); 54 l->pop_front(); 55 } 56 if (i6) { 57 CHECK_EQ(l->front(), i6); 58 l->pop_front(); 59 } 60 CHECK(l->empty()); 61} 62 63TEST(SanitizerCommon, IntrusiveList) { 64 ListItem items[6]; 65 CHECK_EQ(static_list.size(), 0); 66 67 List l; 68 l.clear(); 69 70 ListItem *x = &items[0]; 71 ListItem *y = &items[1]; 72 ListItem *z = &items[2]; 73 ListItem *a = &items[3]; 74 ListItem *b = &items[4]; 75 ListItem *c = &items[5]; 76 77 CHECK_EQ(l.size(), 0); 78 l.push_back(x); 79 CHECK_EQ(l.size(), 1); 80 CHECK_EQ(l.back(), x); 81 CHECK_EQ(l.front(), x); 82 l.pop_front(); 83 CHECK(l.empty()); 84 l.CheckConsistency(); 85 86 l.push_front(x); 87 CHECK_EQ(l.size(), 1); 88 CHECK_EQ(l.back(), x); 89 CHECK_EQ(l.front(), x); 90 l.pop_front(); 91 CHECK(l.empty()); 92 l.CheckConsistency(); 93 94 l.push_front(x); 95 l.push_front(y); 96 l.push_front(z); 97 CHECK_EQ(l.size(), 3); 98 CHECK_EQ(l.front(), z); 99 CHECK_EQ(l.back(), x); 100 l.CheckConsistency(); 101 102 l.pop_front(); 103 CHECK_EQ(l.size(), 2); 104 CHECK_EQ(l.front(), y); 105 CHECK_EQ(l.back(), x); 106 l.pop_front(); 107 l.pop_front(); 108 CHECK(l.empty()); 109 l.CheckConsistency(); 110 111 l.push_back(x); 112 l.push_back(y); 113 l.push_back(z); 114 CHECK_EQ(l.size(), 3); 115 CHECK_EQ(l.front(), x); 116 CHECK_EQ(l.back(), z); 117 l.CheckConsistency(); 118 119 l.pop_front(); 120 CHECK_EQ(l.size(), 2); 121 CHECK_EQ(l.front(), y); 122 CHECK_EQ(l.back(), z); 123 l.pop_front(); 124 l.pop_front(); 125 CHECK(l.empty()); 126 l.CheckConsistency(); 127 128 l.push_back(x); 129 l.push_back(y); 130 l.push_back(z); 131 l.extract(x, y); 132 CHECK_EQ(l.size(), 2); 133 CHECK_EQ(l.front(), x); 134 CHECK_EQ(l.back(), z); 135 l.CheckConsistency(); 136 l.extract(x, z); 137 CHECK_EQ(l.size(), 1); 138 CHECK_EQ(l.front(), x); 139 CHECK_EQ(l.back(), x); 140 l.CheckConsistency(); 141 l.pop_front(); 142 CHECK(l.empty()); 143 144 List l1, l2; 145 l1.clear(); 146 l2.clear(); 147 148 l1.append_front(&l2); 149 CHECK(l1.empty()); 150 CHECK(l2.empty()); 151 152 l1.append_back(&l2); 153 CHECK(l1.empty()); 154 CHECK(l2.empty()); 155 156 SetList(&l1, x); 157 CheckList(&l1, x); 158 159 SetList(&l1, x, y, z); 160 SetList(&l2, a, b, c); 161 l1.append_back(&l2); 162 CheckList(&l1, x, y, z, a, b, c); 163 CHECK(l2.empty()); 164 165 SetList(&l1, x, y); 166 SetList(&l2); 167 l1.append_front(&l2); 168 CheckList(&l1, x, y); 169 CHECK(l2.empty()); 170} 171 172TEST(SanitizerCommon, IntrusiveListAppendEmpty) { 173 ListItem i; 174 List l; 175 l.clear(); 176 l.push_back(&i); 177 List l2; 178 l2.clear(); 179 l.append_back(&l2); 180 CHECK_EQ(l.back(), &i); 181 CHECK_EQ(l.front(), &i); 182 CHECK_EQ(l.size(), 1); 183 l.append_front(&l2); 184 CHECK_EQ(l.back(), &i); 185 CHECK_EQ(l.front(), &i); 186 CHECK_EQ(l.size(), 1); 187} 188 189} // namespace __sanitizer 190