| /* { dg-do run } */ |
| /* { dg-options "-std=gnu99 -Wall -Wextra -O1" } */ |
| |
| extern void *memset (void*, int, __SIZE_TYPE__); |
| extern void abort (void); |
| |
| struct radix_tree_root { |
| unsigned int height; |
| struct radix_tree_node *rnode; |
| }; |
| |
| struct radix_tree_node { |
| unsigned int count; |
| void *slots[64]; |
| unsigned long tags[2][2]; |
| }; |
| |
| struct radix_tree_path { |
| struct radix_tree_node *node, **slot; |
| int offset; |
| }; |
| |
| static unsigned long height_to_maxindex[7] = |
| {0, 63, 4095, 262143, 16777215, 1073741823, 4294967295}; |
| |
| static inline void tag_clear(struct radix_tree_node *node, int tag, int offset) |
| { |
| int nr; |
| volatile unsigned long *addr; |
| #if(__SIZEOF_INT__ >= 4) |
| int mask; |
| #else |
| long mask; |
| #endif |
| |
| nr = offset; |
| addr = &node->tags[tag][0]; |
| |
| addr += nr >> 5; |
| mask = 1 << (nr & 0x1f); |
| *addr &= ~mask; |
| } |
| |
| void *radix_tree_tag_clear(struct radix_tree_root *root, unsigned long index, int tag) |
| { |
| struct radix_tree_path path[7], *pathp = path; |
| unsigned int height, shift; |
| void *ret = 0; |
| |
| height = root->height; |
| if (index > height_to_maxindex[height]) |
| goto out; |
| |
| shift = (height - 1) * 6; |
| pathp->node = 0; |
| pathp->slot = &root->rnode; |
| |
| while (height > 0) { |
| int offset; |
| |
| if (*pathp->slot == 0) |
| goto out; |
| |
| offset = (index >> shift) & (64-1); |
| pathp[1].offset = offset; |
| pathp[1].node = *pathp[0].slot; |
| pathp[1].slot = (struct radix_tree_node **) |
| (pathp[1].node->slots + offset); |
| pathp++; |
| shift -= 6; |
| height--; |
| } |
| |
| ret = *pathp[0].slot; |
| if (ret == 0) |
| goto out; |
| |
| do { |
| int idx; |
| |
| tag_clear(pathp[0].node, tag, pathp[0].offset); |
| for (idx = 0; idx < 2; idx++) { |
| if (pathp[0].node->tags[tag][idx]) |
| goto out; |
| } |
| pathp--; |
| } while (pathp[0].node); |
| out: |
| return ret; |
| } |
| |
| int main () |
| { |
| struct radix_tree_root r; |
| struct radix_tree_node node; |
| void *p = (void *) 0xdeadbeef; |
| |
| r.height = 1; |
| r.rnode = &node; |
| |
| memset (&node, 0, sizeof (node)); |
| |
| node.count = 1; |
| node.slots [13] = p; |
| |
| radix_tree_tag_clear (&r, 13, 1); |
| |
| if (r.rnode->slots[13] != p) |
| abort (); |
| return 0; |
| } |