equal
deleted
inserted
replaced
290 EXPORT_SYMBOL(rb_erase); |
290 EXPORT_SYMBOL(rb_erase); |
291 |
291 |
292 /* |
292 /* |
293 * This function returns the first node (in sort order) of the tree. |
293 * This function returns the first node (in sort order) of the tree. |
294 */ |
294 */ |
295 struct rb_node *rb_first(struct rb_root *root) |
295 struct rb_node *rb_first(const struct rb_root *root) |
296 { |
296 { |
297 struct rb_node *n; |
297 struct rb_node *n; |
298 |
298 |
299 n = root->rb_node; |
299 n = root->rb_node; |
300 if (!n) |
300 if (!n) |
303 n = n->rb_left; |
303 n = n->rb_left; |
304 return n; |
304 return n; |
305 } |
305 } |
306 EXPORT_SYMBOL(rb_first); |
306 EXPORT_SYMBOL(rb_first); |
307 |
307 |
308 struct rb_node *rb_last(struct rb_root *root) |
308 struct rb_node *rb_last(const struct rb_root *root) |
309 { |
309 { |
310 struct rb_node *n; |
310 struct rb_node *n; |
311 |
311 |
312 n = root->rb_node; |
312 n = root->rb_node; |
313 if (!n) |
313 if (!n) |
316 n = n->rb_right; |
316 n = n->rb_right; |
317 return n; |
317 return n; |
318 } |
318 } |
319 EXPORT_SYMBOL(rb_last); |
319 EXPORT_SYMBOL(rb_last); |
320 |
320 |
321 struct rb_node *rb_next(struct rb_node *node) |
321 struct rb_node *rb_next(const struct rb_node *node) |
322 { |
322 { |
323 struct rb_node *parent; |
323 struct rb_node *parent; |
324 |
324 |
325 if (rb_parent(node) == node) |
325 if (rb_parent(node) == node) |
326 return NULL; |
326 return NULL; |
329 as we can. */ |
329 as we can. */ |
330 if (node->rb_right) { |
330 if (node->rb_right) { |
331 node = node->rb_right; |
331 node = node->rb_right; |
332 while (node->rb_left) |
332 while (node->rb_left) |
333 node=node->rb_left; |
333 node=node->rb_left; |
334 return node; |
334 return (struct rb_node *)node; |
335 } |
335 } |
336 |
336 |
337 /* No right-hand children. Everything down and left is |
337 /* No right-hand children. Everything down and left is |
338 smaller than us, so any 'next' node must be in the general |
338 smaller than us, so any 'next' node must be in the general |
339 direction of our parent. Go up the tree; any time the |
339 direction of our parent. Go up the tree; any time the |
345 |
345 |
346 return parent; |
346 return parent; |
347 } |
347 } |
348 EXPORT_SYMBOL(rb_next); |
348 EXPORT_SYMBOL(rb_next); |
349 |
349 |
350 struct rb_node *rb_prev(struct rb_node *node) |
350 struct rb_node *rb_prev(const struct rb_node *node) |
351 { |
351 { |
352 struct rb_node *parent; |
352 struct rb_node *parent; |
353 |
353 |
354 if (rb_parent(node) == node) |
354 if (rb_parent(node) == node) |
355 return NULL; |
355 return NULL; |
358 as we can. */ |
358 as we can. */ |
359 if (node->rb_left) { |
359 if (node->rb_left) { |
360 node = node->rb_left; |
360 node = node->rb_left; |
361 while (node->rb_right) |
361 while (node->rb_right) |
362 node=node->rb_right; |
362 node=node->rb_right; |
363 return node; |
363 return (struct rb_node *)node; |
364 } |
364 } |
365 |
365 |
366 /* No left-hand children. Go up till we find an ancestor which |
366 /* No left-hand children. Go up till we find an ancestor which |
367 is a right-hand child of its parent */ |
367 is a right-hand child of its parent */ |
368 while ((parent = rb_parent(node)) && node == parent->rb_left) |
368 while ((parent = rb_parent(node)) && node == parent->rb_left) |