radix-tree.c (27fd38c5226ed0f1712d071880fa8e739eb78650) radix-tree.c (57578c2ea2cb2e0d362a9212ac83cf90221d4883)
1/*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2005 SGI, Christoph Lameter
5 * Copyright (C) 2006 Nick Piggin
6 * Copyright (C) 2012 Konstantin Khlebnikov
7 *
8 * This program is free software; you can redistribute it and/or

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

479 /* Go a level down */
480 height--;
481 shift -= RADIX_TREE_MAP_SHIFT;
482 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
483 node = indirect_to_ptr(slot);
484 slot = node->slots[offset];
485 }
486
1/*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2005 SGI, Christoph Lameter
5 * Copyright (C) 2006 Nick Piggin
6 * Copyright (C) 2012 Konstantin Khlebnikov
7 *
8 * This program is free software; you can redistribute it and/or

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

479 /* Go a level down */
480 height--;
481 shift -= RADIX_TREE_MAP_SHIFT;
482 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
483 node = indirect_to_ptr(slot);
484 slot = node->slots[offset];
485 }
486
487#ifdef CONFIG_RADIX_TREE_MULTIORDER
487 /* Insert pointers to the canonical entry */
488 if ((shift - order) > 0) {
489 int i, n = 1 << (shift - order);
490 offset = offset & ~(n - 1);
491 slot = ptr_to_indirect(&node->slots[offset]);
492 for (i = 0; i < n; i++) {
493 if (node->slots[offset + i])
494 return -EEXIST;
495 }
496
497 for (i = 1; i < n; i++) {
498 rcu_assign_pointer(node->slots[offset + i], slot);
499 node->count++;
500 }
501 }
488 /* Insert pointers to the canonical entry */
489 if ((shift - order) > 0) {
490 int i, n = 1 << (shift - order);
491 offset = offset & ~(n - 1);
492 slot = ptr_to_indirect(&node->slots[offset]);
493 for (i = 0; i < n; i++) {
494 if (node->slots[offset + i])
495 return -EEXIST;
496 }
497
498 for (i = 1; i < n; i++) {
499 rcu_assign_pointer(node->slots[offset + i], slot);
500 node->count++;
501 }
502 }
503#endif
502
503 if (nodep)
504 *nodep = node;
505 if (slotp)
506 *slotp = node ? node->slots + offset : (void **)&root->rnode;
507 return 0;
508}
509

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

1464 deleted = true;
1465
1466 node = parent;
1467 } while (node);
1468
1469 return deleted;
1470}
1471
504
505 if (nodep)
506 *nodep = node;
507 if (slotp)
508 *slotp = node ? node->slots + offset : (void **)&root->rnode;
509 return 0;
510}
511

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

1466 deleted = true;
1467
1468 node = parent;
1469 } while (node);
1470
1471 return deleted;
1472}
1473
1474static inline void delete_sibling_entries(struct radix_tree_node *node,
1475 void *ptr, unsigned offset)
1476{
1477#ifdef CONFIG_RADIX_TREE_MULTIORDER
1478 int i;
1479 for (i = 1; offset + i < RADIX_TREE_MAP_SIZE; i++) {
1480 if (node->slots[offset + i] != ptr)
1481 break;
1482 node->slots[offset + i] = NULL;
1483 node->count--;
1484 }
1485#endif
1486}
1487
1472/**
1473 * radix_tree_delete_item - delete an item from a radix tree
1474 * @root: radix tree root
1475 * @index: index key
1476 * @item: expected item
1477 *
1478 * Remove @item at @index from the radix tree rooted at @root.
1479 *
1480 * Returns the address of the deleted item, or NULL if it was not present
1481 * or the entry at the given @index was not @item.
1482 */
1483void *radix_tree_delete_item(struct radix_tree_root *root,
1484 unsigned long index, void *item)
1485{
1486 struct radix_tree_node *node;
1488/**
1489 * radix_tree_delete_item - delete an item from a radix tree
1490 * @root: radix tree root
1491 * @index: index key
1492 * @item: expected item
1493 *
1494 * Remove @item at @index from the radix tree rooted at @root.
1495 *
1496 * Returns the address of the deleted item, or NULL if it was not present
1497 * or the entry at the given @index was not @item.
1498 */
1499void *radix_tree_delete_item(struct radix_tree_root *root,
1500 unsigned long index, void *item)
1501{
1502 struct radix_tree_node *node;
1487 unsigned int offset, i;
1503 unsigned int offset;
1488 void **slot;
1489 void *entry;
1490 int tag;
1491
1492 entry = __radix_tree_lookup(root, index, &node, &slot);
1493 if (!entry)
1494 return NULL;
1495

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

1508 * Clear all tags associated with the item to be deleted.
1509 * This way of doing it would be inefficient, but seldom is any set.
1510 */
1511 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
1512 if (tag_get(node, tag, offset))
1513 radix_tree_tag_clear(root, index, tag);
1514 }
1515
1504 void **slot;
1505 void *entry;
1506 int tag;
1507
1508 entry = __radix_tree_lookup(root, index, &node, &slot);
1509 if (!entry)
1510 return NULL;
1511

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

1524 * Clear all tags associated with the item to be deleted.
1525 * This way of doing it would be inefficient, but seldom is any set.
1526 */
1527 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
1528 if (tag_get(node, tag, offset))
1529 radix_tree_tag_clear(root, index, tag);
1530 }
1531
1516 /* Delete any sibling slots pointing to this slot */
1517 for (i = 1; offset + i < RADIX_TREE_MAP_SIZE; i++) {
1518 if (node->slots[offset + i] != ptr_to_indirect(slot))
1519 break;
1520 node->slots[offset + i] = NULL;
1521 node->count--;
1522 }
1532 delete_sibling_entries(node, ptr_to_indirect(slot), offset);
1523 node->slots[offset] = NULL;
1524 node->count--;
1525
1526 __radix_tree_delete_node(root, node);
1527
1528 return entry;
1529}
1530EXPORT_SYMBOL(radix_tree_delete_item);

--- 86 unchanged lines hidden --- 		1533 node->slots[offset] = NULL;
1534 node->count--;
1535
1536 __radix_tree_delete_node(root, node);
1537
1538 return entry;
1539}
1540EXPORT_SYMBOL(radix_tree_delete_item);

--- 86 unchanged lines hidden ---