radix-tree.h (4d693d08607ab319095ec8942909df4b4aebdf66) radix-tree.h (14b468791fa955d442f962fdf5207dfd39a131c8)
1/*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2006 Nick Piggin
5 * Copyright (C) 2012 Konstantin Khlebnikov
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License as

--- 66 unchanged lines hidden (view full) ---

75
76#define RADIX_TREE_TAG_LONGS \
77 ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
78
79#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
80#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
81 RADIX_TREE_MAP_SHIFT))
82
1/*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2006 Nick Piggin
5 * Copyright (C) 2012 Konstantin Khlebnikov
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License as

--- 66 unchanged lines hidden (view full) ---

75
76#define RADIX_TREE_TAG_LONGS \
77 ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
78
79#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
80#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
81 RADIX_TREE_MAP_SHIFT))
82
83/* Internally used bits of node->count */
84#define RADIX_TREE_COUNT_SHIFT (RADIX_TREE_MAP_SHIFT + 1)
85#define RADIX_TREE_COUNT_MASK ((1UL << RADIX_TREE_COUNT_SHIFT) - 1)
86
87struct radix_tree_node {
88 unsigned char shift; /* Bits remaining in each slot */
89 unsigned char offset; /* Slot offset in parent */
83struct radix_tree_node {
84 unsigned char shift; /* Bits remaining in each slot */
85 unsigned char offset; /* Slot offset in parent */
90 unsigned int count; /* Total entry count */
86 unsigned char count; /* Total entry count */
91 unsigned char exceptional; /* Exceptional entry count */
92 union {
93 struct {
94 /* Used when ascending tree */
95 struct radix_tree_node *parent;
96 /* For tree user */
97 void *private_data;
98 };

--- 166 unchanged lines hidden (view full) ---

265void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
266typedef void (*radix_tree_update_node_t)(struct radix_tree_node *, void *);
267void __radix_tree_replace(struct radix_tree_root *root,
268 struct radix_tree_node *node,
269 void **slot, void *item,
270 radix_tree_update_node_t update_node, void *private);
271void radix_tree_replace_slot(struct radix_tree_root *root,
272 void **slot, void *item);
87 unsigned char exceptional; /* Exceptional entry count */
88 union {
89 struct {
90 /* Used when ascending tree */
91 struct radix_tree_node *parent;
92 /* For tree user */
93 void *private_data;
94 };

--- 166 unchanged lines hidden (view full) ---

261void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
262typedef void (*radix_tree_update_node_t)(struct radix_tree_node *, void *);
263void __radix_tree_replace(struct radix_tree_root *root,
264 struct radix_tree_node *node,
265 void **slot, void *item,
266 radix_tree_update_node_t update_node, void *private);
267void radix_tree_replace_slot(struct radix_tree_root *root,
268 void **slot, void *item);
273bool __radix_tree_delete_node(struct radix_tree_root *root,
269void __radix_tree_delete_node(struct radix_tree_root *root,
274 struct radix_tree_node *node);
275void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *);
276void *radix_tree_delete(struct radix_tree_root *, unsigned long);
277void radix_tree_clear_tags(struct radix_tree_root *root,
278 struct radix_tree_node *node,
279 void **slot);
280unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
281 void **results, unsigned long first_index,

--- 295 unchanged lines hidden --- 		270 struct radix_tree_node *node);
271void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *);
272void *radix_tree_delete(struct radix_tree_root *, unsigned long);
273void radix_tree_clear_tags(struct radix_tree_root *root,
274 struct radix_tree_node *node,
275 void **slot);
276unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
277 void **results, unsigned long first_index,

--- 295 unchanged lines hidden ---