gcc/testsuite/gcc.dg/pr18241-1.c

   1 /* { dg-do run } */
   2 /* { dg-options "-std=gnu99 -Wall -Wextra -O1" } */
   3
   4 extern void *memset (void*, int, __SIZE_TYPE__);
   5 extern void abort (void);
   6
   7 struct radix_tree_root {
   8         unsigned int height;
   9         struct radix_tree_node *rnode;
  10 };
  11
  12 struct radix_tree_node {
  13         unsigned int count;
  14         void *slots[64];
  15         unsigned long tags[2][2];
  16 };
  17
  18 struct radix_tree_path {
  19         struct radix_tree_node *node, **slot;
  20         int offset;
  21 };
  22
  23 static unsigned long height_to_maxindex[7] =
  24 {0, 63, 4095, 262143, 16777215, 1073741823, 4294967295};
  25
  26 static inline void tag_clear(struct radix_tree_node *node, int tag, int offset)
  27 {
  28         int nr;
  29         volatile unsigned long *addr;
  30 #if(__SIZEOF_INT__ >= 4)
  31         int mask;
  32 #else
  33         long mask;
  34 #endif
  35
  36         nr = offset;
  37         addr = &node->tags[tag][0];
  38
  39         addr += nr >> 5;
  40         mask = 1 << (nr & 0x1f);
  41         *addr &= ~mask;
  42 }
  43
  44 void *radix_tree_tag_clear(struct radix_tree_root *root, unsigned long index, int tag)
  45 {
  46         struct radix_tree_path path[7], *pathp = path;
  47         unsigned int height, shift;
  48         void *ret = 0;
  49
  50         height = root->height;
  51         if (index > height_to_maxindex[height])
  52                 goto out;
  53
  54         shift = (height - 1) * 6;
  55         pathp->node = 0;
  56         pathp->slot = &root->rnode;
  57
  58         while (height > 0) {
  59                 int offset;
  60
  61                 if (*pathp->slot == 0)
  62                         goto out;
  63
  64                 offset = (index >> shift) & (64-1);
  65                 pathp[1].offset = offset;
  66                 pathp[1].node = *pathp[0].slot;
  67                 pathp[1].slot = (struct radix_tree_node **)
  68                         (pathp[1].node->slots + offset);
  69                 pathp++;
  70                 shift -= 6;
  71                 height--;
  72         }
  73
  74         ret = *pathp[0].slot;
  75         if (ret == 0)
  76                 goto out;
  77
  78         do {
  79                 int idx;
  80
  81                 tag_clear(pathp[0].node, tag, pathp[0].offset);
  82                 for (idx = 0; idx < 2; idx++) {
  83                         if (pathp[0].node->tags[tag][idx])
  84                                 goto out;
  85                 }
  86                 pathp--;
  87         } while (pathp[0].node);
  88 out:
  89         return ret;
  90 }
  91
  92 int main ()
  93 {
  94         struct radix_tree_root r;
  95         struct radix_tree_node node;
  96         void *p = (void *) 0xdeadbeef;
  97
  98         r.height = 1;
  99         r.rnode = &node;
 100
 101         memset (&node, 0, sizeof (node));
 102
 103         node.count = 1;
 104         node.slots [13] = p;
 105
 106         radix_tree_tag_clear (&r, 13, 1);
 107
 108         if (r.rnode->slots[13] != p)
 109                 abort ();
 110         return 0;
 111 }