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  }