2 /* Generic associative array implementation.
16  * Iterate over an associative array.  The caller must hold the RCU read lock
111  * assoc_array_iterate - Pass all objects in the array to a callback
112  * @array: The array to iterate over.
116  * Iterate over all the objects in an associative array.  Each one will be
119  * If the array is being modified concurrently with the iteration then it is
120  * possible that some objects in the array will be passed to the iterator
125  * The function will return 0 if no objects were in the array or else it will
133 int assoc_array_iterate(const struct assoc_array *array,  in assoc_array_iterate()  argument
138 	struct assoc_array_ptr *root = READ_ONCE(array->root); /* Address dependency. */  in assoc_array_iterate()
170 assoc_array_walk(const struct assoc_array *array,  in assoc_array_walk()  argument
185 	cursor = READ_ONCE(array->root);  /* Address dependency. */  in assoc_array_walk()
294  * @array: The associative array to search.
298  * Find an object in an associative array by walking through the internal tree
300  * there.  NULL is returned if the requested object was not found in the array.
304 void *assoc_array_find(const struct assoc_array *array,  in assoc_array_find()  argument
314 	if (assoc_array_walk(array, ops, index_key, &result) !=  in assoc_array_find()
340  * Destructively iterate over an associative array.  The caller must prevent
429  * assoc_array_destroy - Destroy an associative array
430  * @array: The array to destroy.
433  * Discard all metadata and free all objects in an associative array.  The
434  * array will be empty and ready to use again upon completion.  This function
441 void assoc_array_destroy(struct assoc_array *array,  in assoc_array_destroy()  argument
444 	assoc_array_destroy_subtree(array->root, ops);  in assoc_array_destroy()
445 	array->root = NULL;  in assoc_array_destroy()
464 	edit->set[0].ptr = &edit->array->root;  in assoc_array_insert_in_empty_tree()
704 		edit->set[0].ptr = &edit->array->root;  in assoc_array_insert_into_terminal_node()
825 		edit->set[0].ptr = &edit->array->root;  in assoc_array_insert_mid_shortcut()
946  * assoc_array_insert - Script insertion of an object into an associative array
947  * @array: The array to insert into.
953  * object in an associative array.  This results in an edit script that can
964 struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,  in assoc_array_insert()  argument
984 	edit->array = array;  in assoc_array_insert()
989 	switch (assoc_array_walk(array, ops, index_key, &result)) {  in assoc_array_insert()
1061  * assoc_array_delete - Script deletion of an object from an associative array
1062  * @array: The array to search.
1067  * associative array.  This results in an edit script that can either be
1079 struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,  in assoc_array_delete()  argument
1096 	edit->array = array;  in assoc_array_delete()
1100 	switch (assoc_array_walk(array, ops, index_key, &result)) {  in assoc_array_delete()
1126 	BUG_ON(array->nr_leaves_on_tree <= 0);  in assoc_array_delete()
1137 	 * internal array.  in assoc_array_delete()
1139 	if (array->nr_leaves_on_tree == 1) {  in assoc_array_delete()
1140 		edit->set[1].ptr = &array->root;  in assoc_array_delete()
1143 		edit->excised_subtree = array->root;  in assoc_array_delete()
1231 				edit->set[1].ptr = &array->root;  in assoc_array_delete()
1258  * assoc_array_clear - Script deletion of all objects from an associative array
1259  * @array: The array to clear.
1263  * from an associative array.  This results in an edit script that can either
1267  * deleted, NULL if there are no objects in the array or -ENOMEM.
1275 struct assoc_array_edit *assoc_array_clear(struct assoc_array *array,  in assoc_array_clear()  argument
1282 	if (!array->root)  in assoc_array_clear()
1288 	edit->array = array;  in assoc_array_clear()
1290 	edit->set[1].ptr = &array->root;  in assoc_array_clear()
1292 	edit->excised_subtree = array->root;  in assoc_array_clear()
1334  * assoc_array_apply_edit - Apply an edit script to an associative array
1337  * Apply an edit script to an associative array to effect an insertion,
1343  * accesses on the array to continue to do so under the RCU read lock whilst
1374 	if (edit->array->root == NULL) {  in assoc_array_apply_edit()
1375 		edit->array->nr_leaves_on_tree = 0;  in assoc_array_apply_edit()
1394 		edit->array->nr_leaves_on_tree += edit->adjust_count_by;  in assoc_array_apply_edit()
1405  * any changes to the associative array it was intended for.
1431  * assoc_array_gc - Garbage collect an associative array.
1432  * @array: The array to clean.
1437  * Collect garbage from an associative array and pack down the internal tree to
1441  * array.  If it returns false, the object is discard and if it returns true,
1446  * latter case, the array is not changed.
1454 int assoc_array_gc(struct assoc_array *array,  in assoc_array_gc()  argument
1469 	if (!array->root)  in assoc_array_gc()
1475 	edit->array = array;  in assoc_array_gc()
1478 	edit->set[0].ptr = &array->root;  in assoc_array_gc()
1479 	edit->excised_subtree = array->root;  in assoc_array_gc()
1483 	cursor = array->root;  in assoc_array_gc()
1712 	array->nr_leaves_on_tree = nr_leaves_on_tree;  in assoc_array_gc()