compiler-rt/lib/sanitizer_common/tests/sanitizer_list_test.cpp

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