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()
824 		edit->set[0].ptr = &edit->array->root;  in assoc_array_insert_mid_shortcut()
945  * assoc_array_insert - Script insertion of an object into an associative array
946  * @array: The array to insert into.
952  * object in an associative array.  This results in an edit script that can
963 struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,  in assoc_array_insert()  argument
983 	edit->array = array;  in assoc_array_insert()
988 	switch (assoc_array_walk(array, ops, index_key, &result)) {  in assoc_array_insert()
1060  * assoc_array_delete - Script deletion of an object from an associative array
1061  * @array: The array to search.
1066  * associative array.  This results in an edit script that can either be
1078 struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,  in assoc_array_delete()  argument
1095 	edit->array = array;  in assoc_array_delete()
1099 	switch (assoc_array_walk(array, ops, index_key, &result)) {  in assoc_array_delete()
1125 	BUG_ON(array->nr_leaves_on_tree <= 0);  in assoc_array_delete()
1136 	 * internal array.  in assoc_array_delete()
1138 	if (array->nr_leaves_on_tree == 1) {  in assoc_array_delete()
1139 		edit->set[1].ptr = &array->root;  in assoc_array_delete()
1142 		edit->excised_subtree = array->root;  in assoc_array_delete()
1230 				edit->set[1].ptr = &array->root;  in assoc_array_delete()
1257  * assoc_array_clear - Script deletion of all objects from an associative array
1258  * @array: The array to clear.
1262  * from an associative array.  This results in an edit script that can either
1266  * deleted, NULL if there are no objects in the array or -ENOMEM.
1274 struct assoc_array_edit *assoc_array_clear(struct assoc_array *array,  in assoc_array_clear()  argument
1281 	if (!array->root)  in assoc_array_clear()
1287 	edit->array = array;  in assoc_array_clear()
1289 	edit->set[1].ptr = &array->root;  in assoc_array_clear()
1291 	edit->excised_subtree = array->root;  in assoc_array_clear()
1333  * assoc_array_apply_edit - Apply an edit script to an associative array
1336  * Apply an edit script to an associative array to effect an insertion,
1342  * accesses on the array to continue to do so under the RCU read lock whilst
1373 	if (edit->array->root == NULL) {  in assoc_array_apply_edit()
1374 		edit->array->nr_leaves_on_tree = 0;  in assoc_array_apply_edit()
1393 		edit->array->nr_leaves_on_tree += edit->adjust_count_by;  in assoc_array_apply_edit()
1404  * any changes to the associative array it was intended for.
1430  * assoc_array_gc - Garbage collect an associative array.
1431  * @array: The array to clean.
1436  * Collect garbage from an associative array and pack down the internal tree to
1440  * array.  If it returns false, the object is discard and if it returns true,
1445  * latter case, the array is not changed.
1453 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()
1718 	array->nr_leaves_on_tree = nr_leaves_on_tree;  in assoc_array_gc()