Function report

Linux Kernel

v5.5.9

Brick Technologies Co., Ltd

Source Code:lib\assoc_array.c Create Date:2022-07-28 06:54:40
Last Modify:2020-03-12 14:18:49 Copyright©Brick
home page Tree
Annotation kernel can get tool activityDownload SCCTChinese

Name:assoc_array_gc - Garbage collect an associative array

Proto:int assoc_array_gc(struct assoc_array *array, const struct assoc_array_ops *ops, bool (*iterator)(void *object, void *iterator_data), void *iterator_data)

Type:int

Parameter:

TypeParameterName
struct assoc_array *array
const struct assoc_array_ops *ops
bool (*iterator
void *iterator_data
1467  pr_devel("-->%s()\n", __func__)
1469  If Not The node at the root of the tree Then Return 0
1472  edit = kzalloc - allocate memory. The memory is set to zero.*@size: how many bytes of memory are required.*@flags: the type of memory to allocate (see kmalloc).
1473  If Not edit Then Return -ENOMEM
1475  array = array
1476  ops = ops
1477  ops_for_excised_subtree = ops
1478  ptr = The node at the root of the tree
1479  excised_subtree = The node at the root of the tree
1481  new_root = new_parent = NULL
1482  new_ptr_pp = new_root
1483  cursor = The node at the root of the tree
1485  descend :
1489  If assoc_array_ptr_is_shortcut(cursor) Then
1490  shortcut = assoc_array_ptr_to_shortcut(cursor)
1491  keylen = und_up - round up to next specified power of 2*@x: the value to round*@y: multiple to round up to (must be a power of 2)* Rounds @x up to next multiple of @y (which must be a power of 2).* To perform arbitrary rounding up, use roundup() below.(skip_to_level, Key data retrieved in chunks of this size )
1492  keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT
1493  new_s = kmalloc(sizeof(structassoc_array_shortcut) + keylen * sizeof(unsignedlong), GFP_KERNEL)
1495  If Not new_s Then Go to enomem
1497  pr_devel("dup shortcut %p -> %p\n", shortcut, new_s)
1498  No 3D Now!(new_s, shortcut, (sizeof(structassoc_array_shortcut) + keylen * sizeof(unsignedlong)))
1500  back_pointer = new_parent
1501  parent_slot = parent_slot
1502  new_ptr_pp = new_parent = assoc_array_shortcut_to_ptr(new_s)
1503  new_ptr_pp = next_node
1504  cursor = next_node
1508  node = assoc_array_ptr_to_node(cursor)
1509  new_n = kzalloc - allocate memory. The memory is set to zero.*@size: how many bytes of memory are required.*@flags: the type of memory to allocate (see kmalloc).
1510  If Not new_n Then Go to enomem
1512  pr_devel("dup node %p -> %p\n", node, new_n)
1513  back_pointer = new_parent
1514  parent_slot = parent_slot
1515  new_ptr_pp = new_parent = assoc_array_node_to_ptr(new_n)
1516  new_ptr_pp = NULL
1517  slot = 0
1519  continue_node :
1521  When slot < Number of slots per node cycle
1522  ptr = slots[slot]
1523  If Not ptr Then Continue
1526  If assoc_array_ptr_is_leaf(ptr) Then
1527  If iterator(assoc_array_ptr_to_leaf(ptr), iterator_data) Then slots[slot] = ptr
1533  Continue
1536  new_ptr_pp = slots[slot]
1537  cursor = ptr
1538  Go to descend
1541  pr_devel("-- compress node %p --\n", new_n)
1546  nr_leaves_on_branch = 0
1547  nr_free = 0
1548  When slot < Number of slots per node cycle
1549  ptr = slots[slot]
1550  If Not ptr Then nr_free++
1552  Else if assoc_array_ptr_is_leaf(ptr) Then nr_leaves_on_branch++
1555  pr_devel("free=%d, leaves=%lu\n", nr_free, nr_leaves_on_branch)
1558  next_slot = 0
1559  When slot < Number of slots per node cycle
1563  ptr = slots[slot]
1564  If Not ptr || assoc_array_ptr_is_leaf(ptr) Then Continue
1567  s = NULL
1568  If assoc_array_ptr_is_shortcut(ptr) Then
1569  s = assoc_array_ptr_to_shortcut(ptr)
1570  ptr = next_node
1573  child = assoc_array_ptr_to_node(ptr)
1574  nr_leaves_on_branch += nr_leaves_on_branch
1576  If nr_leaves_on_branch <= nr_free + 1 Then
1578  pr_devel("[%d] fold node %lu/%d [nx %d]\n", slot, nr_leaves_on_branch, nr_free + 1, next_slot)
1585  BUG_ON(s)
1587  slots[slot] = NULL
1588  nr_free++
1589  If slot < next_slot Then next_slot = slot
1591  When i < Number of slots per node cycle
1592  p = slots[i]
1593  If Not p Then Continue
1595  BUG_ON(assoc_array_ptr_is_meta(p))
1596  When slots[next_slot] cycle
1597  next_slot++
1598  BUG_ON(next_slot >= Number of slots per node )
1599  slots[next_slot++] = p
1600  nr_free--
1602  kfree(child)
1603  Else
1604  pr_devel("[%d] retain node %lu/%d [nx %d]\n", slot, nr_leaves_on_branch, nr_free + 1, next_slot)
1610  pr_devel("after: %lu\n", nr_leaves_on_branch)
1612  nr_leaves_on_tree = nr_leaves_on_branch
1615  If nr_free == Number of slots per node - 1 Then
1616  When slot < Number of slots per node cycle If ptr = slots[slot] Then
1618  Break
1620  If assoc_array_ptr_is_meta(ptr) && assoc_array_ptr_is_shortcut(ptr) Then
1622  pr_devel("excise node %p with 1 shortcut\n", new_n)
1623  new_s = assoc_array_ptr_to_shortcut(ptr)
1624  new_parent = back_pointer
1625  slot = parent_slot
1626  kfree(new_n)
1627  If Not new_parent Then
1628  back_pointer = NULL
1629  parent_slot = 0
1630  new_root = ptr
1631  Go to gc_complete
1634  If assoc_array_ptr_is_shortcut(new_parent) Then
1636  s = assoc_array_ptr_to_shortcut(new_parent)
1639  pr_devel("excise preceding shortcut\n")
1641  new_parent = back_pointer = back_pointer
1642  slot = parent_slot = parent_slot
1643  kfree(s)
1644  If Not new_parent Then
1645  back_pointer = NULL
1646  parent_slot = 0
1647  new_root = ptr
1648  Go to gc_complete
1652  back_pointer = new_parent
1653  parent_slot = slot
1654  new_n = assoc_array_ptr_to_node(new_parent)
1655  slots[slot] = ptr
1656  Go to ascend_old_tree
1663  ptr = back_pointer
1664  If Not ptr Then Go to gc_complete
1667  If assoc_array_ptr_is_shortcut(ptr) Then
1668  new_s = assoc_array_ptr_to_shortcut(ptr)
1669  new_parent = back_pointer
1670  slot = parent_slot
1672  If nr_leaves_on_branch <= Number of slots per node Then
1675  pr_devel("excise shortcut\n")
1676  back_pointer = new_parent
1677  parent_slot = slot
1678  kfree(new_s)
1679  If Not new_parent Then
1684  n = assoc_array_ptr_to_node(new_parent)
1685  slots[slot] = assoc_array_node_to_ptr(new_n)
1687  Else
1688  new_parent = ptr
1690  new_n = assoc_array_ptr_to_node(new_parent)
1692  ascend_old_tree :
1693  ptr = back_pointer
1694  If assoc_array_ptr_is_shortcut(ptr) Then
1695  shortcut = assoc_array_ptr_to_shortcut(ptr)
1696  slot = parent_slot
1697  cursor = back_pointer
1698  If Not cursor Then Go to gc_complete
1700  Else
1701  slot = parent_slot
1702  cursor = ptr
1704  BUG_ON(!cursor)
1705  node = assoc_array_ptr_to_node(cursor)
1706  slot++
1707  Go to continue_node
1709  gc_complete :
1710  to = new_root
1711  assoc_array_apply_edit - Apply an edit script to an associative array*@edit: The script to apply.* Apply an edit script to an associative array to effect an insertion,* deletion or clearance. As the edit script includes preallocated memory,
1712  nr_leaves_on_tree = nr_leaves_on_tree
1713  Return 0
1715  enomem :
1716  pr_devel("enomem\n")
1717  Destructively iterate over an associative array. The caller must prevent* other simultaneous accesses.
1718  kfree(edit)
1719  Return -ENOMEM