summaryrefslogtreecommitdiff
path: root/libbanshee/libcompat/radix-tree.c
blob: 18f8929ad2dae3abf9e2cf0bf3f70da95bdb40ce (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
/*
 * Modified to work in GCC in 2003 by Daniel Berlin 
 * Copyright (C) 2001 Momchil Velikov
 * Portions Copyright (C) 2001 Christoph Hellwig
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2, or (at
 * your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */
#include <unistd.h>
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include  "radix-tree.h"
#define ARRAY_SIZE(a) (sizeof (a) / sizeof ((a)[0]))
/*
 * Radix tree node definition.
 */
#define RADIX_TREE_MAP_SHIFT  6
#define RADIX_TREE_MAP_SIZE  (1UL << RADIX_TREE_MAP_SHIFT)
#define RADIX_TREE_MAP_MASK  (RADIX_TREE_MAP_SIZE-1)

struct radix_tree_node {
  unsigned int	count;
  void		*slots[RADIX_TREE_MAP_SIZE];
};

struct radix_tree_path {
  struct radix_tree_node *node, **slot;
};

#define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)

static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH];


/*
 * This assumes that the caller has performed appropriate preallocation, and
 * that the caller has pinned this thread of control to the current CPU.
 */
static struct radix_tree_node *
radix_tree_node_alloc(struct radix_tree_root *root)
{
  struct radix_tree_node *ret;
  
  ret = (struct radix_tree_node *)
    calloc (1, sizeof (struct radix_tree_node));
  if (!ret)
    abort ();
  return ret;
}

static inline void
radix_tree_node_free(struct radix_tree_node *node)
{
  free (node);
}


/*
 *	Return the maximum key which can be store into a
 *	radix tree with height HEIGHT.
 */
static inline unsigned long radix_tree_maxindex(unsigned int height)
{
  return height_to_maxindex[height];
}

/*
 *	Extend a radix tree so it can store key @index.
 */
static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
{
  struct radix_tree_node *node;
  unsigned int height;
  
  /* Figure out what the height should be.  */
  height = root->height + 1;
  while (index > radix_tree_maxindex(height))
    height++;
  
  if (root->rnode) {
    do {
      if (!(node = radix_tree_node_alloc(root)))
	return -ENOMEM;
      
      /* Increase the height.  */
      node->slots[0] = root->rnode;
      node->count = 1;
      root->rnode = node;
      root->height++;
    } while (height > root->height);
  } else 
    root->height = height;
  
  return 0;
}

/**
 *	radix_tree_insert    -    insert into a radix tree
 *	@root:		radix tree root
 *	@index:		index key
 *	@item:		item to insert
 *
 *	Insert an item into the radix tree at position @index.
 */
int radix_tree_insert(struct radix_tree_root *root, unsigned long index,
		      void *item)
{
  struct radix_tree_node *node = NULL, *tmp, **slot;
  unsigned int height, shift;
  int error;
  
  /* Make sure the tree is high enough.  */
  if (index > radix_tree_maxindex(root->height)) {
    error = radix_tree_extend(root, index);
    if (error)
      return error;
  }
  
  slot = &root->rnode;
  height = root->height;
  shift = (height-1) * RADIX_TREE_MAP_SHIFT;
  
  while (height > 0) {
    if (*slot == NULL) {
      /* Have to add a child node.  */
      if (!(tmp = radix_tree_node_alloc(root)))
	return -ENOMEM;
      *slot = tmp;
      if (node)
	node->count++;
    }
    
    /* Go a level down.  */
    node = *slot;
    slot = (struct radix_tree_node **)
      (node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
    shift -= RADIX_TREE_MAP_SHIFT;
    height--;
  }
  
  if (*slot != NULL)
    return -EEXIST;
  if (node)
    node->count++;
  
  *slot = item;
  return 0;
}

/**
 *	radix_tree_lookup    -    perform lookup operation on a radix tree
 *	@root:		radix tree root
 *	@index:		index key
 *
 *	Lookup them item at the position @index in the radix tree @root.
 */
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
  unsigned int height, shift;
  struct radix_tree_node **slot;
  
  height = root->height;
  if (index > radix_tree_maxindex(height))
    return NULL;
  
  shift = (height-1) * RADIX_TREE_MAP_SHIFT;
  slot = &root->rnode;
  
  while (height > 0) {
    if (*slot == NULL)
      return NULL;
    
    slot = (struct radix_tree_node **)
      ((*slot)->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
    shift -= RADIX_TREE_MAP_SHIFT;
    height--;
  }
  
  return (void *) *slot;
}

static /* inline */ unsigned int
__lookup(struct radix_tree_root *root, void **results, unsigned long index,
	 unsigned int max_items, unsigned long *next_index)
{
  unsigned int nr_found = 0;
  unsigned int shift;
  unsigned int height = root->height;
  struct radix_tree_node *slot;
  
  shift = (height-1) * RADIX_TREE_MAP_SHIFT;
  slot = root->rnode;
  
  while (height > 0) {
    unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
    
    for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
      if (slot->slots[i] != NULL)
	break;
      index &= ~((1 << shift) - 1);
      index += 1 << shift;
      if (index == 0)
	goto out;	/* 32-bit wraparound */
    }
    if (i == RADIX_TREE_MAP_SIZE)
      goto out;
    height--;
    if (height == 0) {	/* Bottom level: grab some items */
      unsigned long j = index & RADIX_TREE_MAP_MASK;
      
      for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
	index++;
	if (slot->slots[j]) {
	  results[nr_found++] = slot->slots[j];
	  if (nr_found == max_items)
	    goto out;
	}
      }
    }
    shift -= RADIX_TREE_MAP_SHIFT;
    slot = slot->slots[i];
  }
 out:
  *next_index = index;
  return nr_found;
}

/**
 *	radix_tree_gang_lookup - perform multiple lookup on a radix tree
 *	@root:		radix tree root
 *	@results:	where the results of the lookup are placed
 *	@first_index:	start the lookup from this key
 *	@max_items:	place up to this many items at *results
 *
 *	Performs an index-ascending scan of the tree for present items.  Places
 *	them at *@results and returns the number of items which were placed at
 *	*@results.
 *
 *	The implementation is naive.
 */
unsigned int
radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
		       unsigned long first_index, unsigned int max_items)
{
  const unsigned long max_index = radix_tree_maxindex(root->height);
  unsigned long cur_index = first_index;
  unsigned int ret = 0;
  
  if (root->rnode == NULL)
    goto out;
  if (max_index == 0) {			/* Bah.  Special case */
    if (first_index == 0) {
      if (max_items > 0) {
	*results = root->rnode;
	ret = 1;
      }
    }
    goto out;
  }
  while (ret < max_items) {
    unsigned int nr_found;
    unsigned long next_index;	/* Index of next search */
    
    if (cur_index > max_index)
      break;
    nr_found = __lookup(root, results + ret, cur_index,
			max_items - ret, &next_index);
    ret += nr_found;
    if (next_index == 0)
      break;
    cur_index = next_index;
  }
 out:
  return ret;
}

/**
 *	radix_tree_delete    -    delete an item from a radix tree
 *	@root:		radix tree root
 *	@index:		index key
 *
 *	Remove the item at @index from the radix tree rooted at @root.
 *
 *	Returns the address of the deleted item, or NULL if it was not present.
 */
void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
{
  struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
  unsigned int height, shift;
  void *ret = NULL;
  
  height = root->height;
  if (index > radix_tree_maxindex(height))
    goto out;
  
  shift = (height-1) * RADIX_TREE_MAP_SHIFT;
  pathp->node = NULL;
  pathp->slot = &root->rnode;
  
  while (height > 0) {
    if (*pathp->slot == NULL)
      goto out;
    
    pathp[1].node = *pathp[0].slot;
    pathp[1].slot = (struct radix_tree_node **)
      (pathp[1].node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
    pathp++;
    shift -= RADIX_TREE_MAP_SHIFT;
    height--;
  }
  
  ret = *pathp[0].slot;
  if (ret == NULL)
    goto out;
  
  *pathp[0].slot = NULL;
  while (pathp[0].node && --pathp[0].node->count == 0) {
    pathp--;
    *pathp[0].slot = NULL;
    radix_tree_node_free(pathp[1].node);
  }
  
  if (root->rnode == NULL)
    root->height = 0;  /* Empty tree, we can reset the height */
 out:
  return ret;
}


static unsigned long __maxindex(unsigned int height)
{
  unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
  unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
  
  if (tmp >= RADIX_TREE_INDEX_BITS)
    index = ~0UL;
  return index;
}

static void radix_tree_init_maxindex(void)
{
  unsigned int i;
  
  for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
    height_to_maxindex[i] = __maxindex(i);
}

void radix_tree_init(void)
{
  radix_tree_init_maxindex();
}