Documentation/core-api/xarray.rst

1 .. SPDX-License-Identifier: GPL-2.0+
15 next or previous entry in a cache-efficient manner.  In contrast to a
17 order to grow the array.  It is more memory-efficient, parallelisable
18 and cache friendly than a doubly-linked list.  It takes advantage of
28 Normal pointers may be stored in the XArray directly.  They must be 4-byte
30 alloc_page().  It isn't true for arbitrary user-space pointers,
31 nor for function pointers.  You can store pointers to statically allocated
54 the range.  Storing to any index will store to all of them.  Multi-index
63 allocated ones.  A freshly-initialised XArray contains a ``NULL``
82 returns ``-EBUSY`` if the entry is not empty.
98 will not need to allocate memory.  The xa_reserve() function
107 If all entries in the array are ``NULL``, the xa_empty() function
116 ------------
129 Setting or clearing a mark on any index of a multi-index entry will
141 ------------------
169 -----------------
184 -------
254         xa_init_flags(&foo->array, XA_FLAGS_LOCK_BH);
261         xa_lock_bh(&foo->array);
262         err = xa_err(__xa_store(&foo->array, index, entry, GFP_KERNEL));
264             foo->count++;
265         xa_unlock_bh(&foo->array);
272         xa_lock(&foo->array);
273         __xa_erase(&foo->array, index);
274         foo->count--;
275         xa_unlock(&foo->array);
312 to use the xa_lock or the RCU lock while doing read-only operations on
315 advanced API is only available to modules with a GPL-compatible license.
350 ----------------
357 .. flat-table::
360    * - Name
361      - Test
362      - Usage
364    * - Node
365      - xa_is_node()
366      - An XArray node.  May be visible when using a multi-index xa_state.
368    * - Sibling
369      - xa_is_sibling()
370      - A non-canonical entry for a multi-index entry.  The value indicates
373    * - Retry
374      - xa_is_retry()
375      - This entry is currently being modified by a thread which has the
380    * - Zero
381      - xa_is_zero()
382      - Zero entries appear as ``NULL`` through the Normal API, but occupy
391 ------------------------
393 The xas_create_range() function allocates all the necessary memory
407 xas_reload() to save a function call.
423 a function call in the majority of cases at the expense of emitting more
426 The xas_find_marked() function is similar.  If the xa_state has
430 function is the equivalent of xas_next_entry().
434 the iteration.  The xas_pause() function exists for this purpose.
446 You can call xas_set_update() to have a callback function
451 Multi-Index Entries
452 -------------------
460 eg indices 64-127 may be tied together, but 2-6 may not be.  This may
464 You can create a multi-index entry by using XA_STATE_ORDER()
466 Calling xas_load() with a multi-index xa_state will walk the
474 If xas_load() encounters a multi-index entry, the xa_index
477 of a multi-index entry, it will not be altered.  Subsequent calls
482 Using xas_next() or xas_prev() with a multi-index xa_state is not
483 supported.  Using either of these functions on a multi-index entry will
486 Storing ``NULL`` into any index of a multi-index entry will set the
487 entry at every index to ``NULL`` and dissolve the tie.  A multi-index
495 .. kernel-doc:: include/linux/xarray.h
496 .. kernel-doc:: lib/xarray.c