Re: [PATCH v2 1/4] Documentation/assoc_array.txt: convert to ReST markup

[Mauro Carvalho Chehab]

Em Fri, 25 Nov 2016 11:02:39 +0100
Silvio Fricke <silvio.fricke@xxxxxxxxx> escreveu:

> ... and move to Documentation/core-api folder.
> 
> Signed-off-by: Silvio Fricke <silvio.fricke@xxxxxxxxx>
> ---
>  Documentation/assoc_array.txt => Documentation/core-api/assoc_array.rst | 617 ++++++++++++++++++++++++++++++++++--------------------------------------
>  Documentation/core-api/index.rst                                        |   1 +-
>  2 files changed, 297 insertions(+), 321 deletions(-)
> 
> diff --git a/Documentation/assoc_array.txt b/Documentation/core-api/assoc_array.rst
> similarity index 46%
> rename from Documentation/assoc_array.txt
> rename to Documentation/core-api/assoc_array.rst
> index 2f2c6cd..67a3a50 100644
> --- a/Documentation/assoc_array.txt
> +++ b/Documentation/core-api/assoc_array.rst
> @@ -1,67 +1,46 @@
> -		   ========================================
> -		   GENERIC ASSOCIATIVE ARRAY IMPLEMENTATION
> -		   ========================================
> +========================================
> +Generic Associative Array Implementation
> +========================================
>  
> -Contents:
> -
> - - Overview.
> -
> - - The public API.
> -   - Edit script.
> -   - Operations table.
> -   - Manipulation functions.
> -   - Access functions.
> -   - Index key form.
> -
> - - Internal workings.
> -   - Basic internal tree layout.
> -   - Shortcuts.
> -   - Splitting and collapsing nodes.
> -   - Non-recursive iteration.
> -   - Simultaneous alteration and iteration.
> -
> -
> -========
> -OVERVIEW
> +Overview
>  ========
>  
>  This associative array implementation is an object container with the following
>  properties:
>  
> - (1) Objects are opaque pointers.  The implementation does not care where they
> -     point (if anywhere) or what they point to (if anything).
> -
> -     [!] NOTE: Pointers to objects _must_ be zero in the least significant bit.
> +1. Objects are opaque pointers.  The implementation does not care where they
> +   point (if anywhere) or what they point to (if anything).

> +   **NOTE: Pointers to objects _must_ be zero in the least significant bit.**

Instead, use:

.. note:: Pointers to objects **must** be zero in the least significant bit.

There's no underline on ReST. We're converting underlines to bold.


>  
> - (2) Objects do not need to contain linkage blocks for use by the array.  This
> -     permits an object to be located in multiple arrays simultaneously.
> -     Rather, the array is made up of metadata blocks that point to objects.
> +2. Objects do not need to contain linkage blocks for use by the array.  This
> +   permits an object to be located in multiple arrays simultaneously.
> +   Rather, the array is made up of metadata blocks that point to objects.
>  
> - (3) Objects require index keys to locate them within the array.
> +3. Objects require index keys to locate them within the array.
>  
> - (4) Index keys must be unique.  Inserting an object with the same key as one
> -     already in the array will replace the old object.
> +4. Index keys must be unique.  Inserting an object with the same key as one
> +   already in the array will replace the old object.
>  
> - (5) Index keys can be of any length and can be of different lengths.
> +5. Index keys can be of any length and can be of different lengths.
>  
> - (6) Index keys should encode the length early on, before any variation due to
> -     length is seen.
> +6. Index keys should encode the length early on, before any variation due to
> +   length is seen.
>  
> - (7) Index keys can include a hash to scatter objects throughout the array.
> +7. Index keys can include a hash to scatter objects throughout the array.
>  
> - (8) The array can iterated over.  The objects will not necessarily come out in
> -     key order.
> +8. The array can iterated over.  The objects will not necessarily come out in
> +   key order.
>  
> - (9) The array can be iterated over whilst it is being modified, provided the
> -     RCU readlock is being held by the iterator.  Note, however, under these
> -     circumstances, some objects may be seen more than once.  If this is a
> -     problem, the iterator should lock against modification.  Objects will not
> -     be missed, however, unless deleted.
> +9. The array can be iterated over whilst it is being modified, provided the
> +   RCU readlock is being held by the iterator.  Note, however, under these
> +   circumstances, some objects may be seen more than once.  If this is a
> +   problem, the iterator should lock against modification.  Objects will not
> +   be missed, however, unless deleted.
>  
> -(10) Objects in the array can be looked up by means of their index key.
> +10. Objects in the array can be looked up by means of their index key.
>  
> -(11) Objects can be looked up whilst the array is being modified, provided the
> -     RCU readlock is being held by the thread doing the look up.
> +11. Objects can be looked up whilst the array is being modified, provided the
> +    RCU readlock is being held by the thread doing the look up.
>  
>  The implementation uses a tree of 16-pointer nodes internally that are indexed
>  on each level by nibbles from the index key in the same manner as in a radix
> @@ -71,25 +50,24 @@ pack leaf object pointers into spare space in the node rather than making an
>  extra branch until as such time an object needs to be added to a full node.
>  
>  
> -==============
> -THE PUBLIC API
> +The Public Api
>  ==============

Better to keep API in uppercase.

>  
> -The public API can be found in <linux/assoc_array.h>.  The associative array is
> -rooted on the following structure:
> +The public API can be found in ``<linux/assoc_array.h>``.  The associative
> +array is rooted on the following structure::
>  
> -	struct assoc_array {
> -		...
> -	};
> +    struct assoc_array {
> +            ...
> +    };
>  
> -The code is selected by enabling CONFIG_ASSOCIATIVE_ARRAY.
> +The code is selected by enabling ``CONFIG_ASSOCIATIVE_ARRAY``.

I would add the command line command used to enable it, e. g.:

The code is selected by enabling ``CONFIG_ASSOCIATIVE_ARRAY`` with::

	./scripts/config -e ASSOCIATIVE_ARRAY


>  
>  
> -EDIT SCRIPT
> +Edit Script
>  -----------
>  
>  The insertion and deletion functions produce an 'edit script' that can later be
> -applied to effect the changes without risking ENOMEM.  This retains the
> +applied to effect the changes without risking ``ENOMEM``. This retains the
>  preallocated metadata blocks that will be installed in the internal tree and
>  keeps track of the metadata blocks that will be removed from the tree when the
>  script is applied.
> @@ -99,246 +77,245 @@ script has been applied so that they can be freed later.  The freeing is done
>  after an RCU grace period has passed - thus allowing access functions to
>  proceed under the RCU read lock.
>  
> -The script appears as outside of the API as a pointer of the type:
> +The script appears as outside of the API as a pointer of the type::
>  
> -	struct assoc_array_edit;
> +    struct assoc_array_edit;
>  
>  There are two functions for dealing with the script:
>  
> - (1) Apply an edit script.
> +1. Apply an edit script. ::
>  
> -	void assoc_array_apply_edit(struct assoc_array_edit *edit);
> +    void assoc_array_apply_edit(struct assoc_array_edit *edit);
>  
> -     This will perform the edit functions, interpolating various write barriers
> -     to permit accesses under the RCU read lock to continue.  The edit script
> -     will then be passed to call_rcu() to free it and any dead stuff it points
> -     to.
> +This will perform the edit functions, interpolating various write barriers
> +to permit accesses under the RCU read lock to continue.  The edit script
> +will then be passed to ``call_rcu()`` to free it and any dead stuff it points
> +to.
>  
> - (2) Cancel an edit script.
> +2. Cancel an edit script. ::
>  
> -	void assoc_array_cancel_edit(struct assoc_array_edit *edit);
> +    void assoc_array_cancel_edit(struct assoc_array_edit *edit);
>  
> -     This frees the edit script and all preallocated memory immediately.  If
> -     this was for insertion, the new object is _not_ released by this function,
> -     but must rather be released by the caller.
> +This frees the edit script and all preallocated memory immediately. If
> +this was for insertion, the new object is _not_ released by this function,
> +but must rather be released by the caller.
>  
>  These functions are guaranteed not to fail.
>  
>  
> -OPERATIONS TABLE
> +Operations Table
>  ----------------
>  
> -Various functions take a table of operations:
> +Various functions take a table of operations::
>  
> -	struct assoc_array_ops {
> -		...
> -	};
> +    struct assoc_array_ops {
> +            ...
> +    };
>  
>  This points to a number of methods, all of which need to be provided:
>  
> - (1) Get a chunk of index key from caller data:
> +1. Get a chunk of index key from caller data::
>  
> -	unsigned long (*get_key_chunk)(const void *index_key, int level);
> +    unsigned long (*get_key_chunk)(const void *index_key, int level);
>  
> -     This should return a chunk of caller-supplied index key starting at the
> -     *bit* position given by the level argument.  The level argument will be a
> -     multiple of ASSOC_ARRAY_KEY_CHUNK_SIZE and the function should return
> -     ASSOC_ARRAY_KEY_CHUNK_SIZE bits.  No error is possible.
> +This should return a chunk of caller-supplied index key starting at the
> +*bit* position given by the level argument.  The level argument will be a
> +multiple of ``ASSOC_ARRAY_KEY_CHUNK_SIZE`` and the function should return
> +``ASSOC_ARRAY_KEY_CHUNK_SIZE bits``.  No error is possible.
>  
>  
> - (2) Get a chunk of an object's index key.
> +2. Get a chunk of an object's index key. ::

Better to remove the dot here, E. g:

2. Get a chunk of an object's index key::

>  
> -	unsigned long (*get_object_key_chunk)(const void *object, int level);
> +    unsigned long (*get_object_key_chunk)(const void *object, int level);
>  
> -     As the previous function, but gets its data from an object in the array
> -     rather than from a caller-supplied index key.
> +As the previous function, but gets its data from an object in the array
> +rather than from a caller-supplied index key.
>  
>  
> - (3) See if this is the object we're looking for.
> +3. See if this is the object we're looking for. ::

Same here and on other similar places

>  
> -	bool (*compare_object)(const void *object, const void *index_key);
> +    bool (*compare_object)(const void *object, const void *index_key);
>  
> -     Compare the object against an index key and return true if it matches and
> -     false if it doesn't.
> +Compare the object against an index key and return ``true`` if it matches and
> +``false`` if it doesn't.
>  
>  
> - (4) Diff the index keys of two objects.
> +4. Diff the index keys of two objects. ::
>  
> -	int (*diff_objects)(const void *object, const void *index_key);
> +    int (*diff_objects)(const void *object, const void *index_key);
>  
> -     Return the bit position at which the index key of the specified object
> -     differs from the given index key or -1 if they are the same.
> +Return the bit position at which the index key of the specified object
> +differs from the given index key or -1 if they are the same.
>  
>  
> - (5) Free an object.
> +5. Free an object. ::
>  
> -	void (*free_object)(void *object);
> +    void (*free_object)(void *object);
>  
> -     Free the specified object.  Note that this may be called an RCU grace
> -     period after assoc_array_apply_edit() was called, so synchronize_rcu() may
> -     be necessary on module unloading.
> +Free the specified object.  Note that this may be called an RCU grace period
> +after ``assoc_array_apply_edit()`` was called, so ``synchronize_rcu()`` may be
> +necessary on module unloading.
>  
>  
> -MANIPULATION FUNCTIONS
> +Manipulation Functions
>  ----------------------
>  
>  There are a number of functions for manipulating an associative array:
>  
> - (1) Initialise an associative array.
> +1. Initialise an associative array. ::
>  
> -	void assoc_array_init(struct assoc_array *array);
> +    void assoc_array_init(struct assoc_array *array);
>  
> -     This initialises the base structure for an associative array.  It can't
> -     fail.
> +This initialises the base structure for an associative array.  It can't fail.
>  
>  
> - (2) Insert/replace an object in an associative array.
> +2. Insert/replace an object in an associative array. ::
>  
> -	struct assoc_array_edit *
> -	assoc_array_insert(struct assoc_array *array,
> -			   const struct assoc_array_ops *ops,
> -			   const void *index_key,
> -			   void *object);
> +    struct assoc_array_edit *
> +    assoc_array_insert(struct assoc_array *array,
> +                       const struct assoc_array_ops *ops,
> +                       const void *index_key,
> +                       void *object);
>  
> -     This inserts the given object into the array.  Note that the least
> -     significant bit of the pointer must be zero as it's used to type-mark
> -     pointers internally.
> +This inserts the given object into the array.  Note that the least
> +significant bit of the pointer must be zero as it's used to type-mark
> +pointers internally.
>  
> -     If an object already exists for that key then it will be replaced with the
> -     new object and the old one will be freed automatically.
> +If an object already exists for that key then it will be replaced with the
> +new object and the old one will be freed automatically.
>  
> -     The index_key argument should hold index key information and is
> -     passed to the methods in the ops table when they are called.
> +The ``index_key`` argument should hold index key information and is
> +passed to the methods in the ops table when they are called.
>  
> -     This function makes no alteration to the array itself, but rather returns
> -     an edit script that must be applied.  -ENOMEM is returned in the case of
> -     an out-of-memory error.
> +This function makes no alteration to the array itself, but rather returns
> +an edit script that must be applied.  ``-ENOMEM`` is returned in the case of
> +an out-of-memory error.
>  
> -     The caller should lock exclusively against other modifiers of the array.
> +The caller should lock exclusively against other modifiers of the array.
>  
>  
> - (3) Delete an object from an associative array.
> +3. Delete an object from an associative array. ::
>  
> -	struct assoc_array_edit *
> -	assoc_array_delete(struct assoc_array *array,
> -			   const struct assoc_array_ops *ops,
> -			   const void *index_key);
> +    struct assoc_array_edit *
> +    assoc_array_delete(struct assoc_array *array,
> +                       const struct assoc_array_ops *ops,
> +                       const void *index_key);
>  
> -     This deletes an object that matches the specified data from the array.
> +This deletes an object that matches the specified data from the array.
>  
> -     The index_key argument should hold index key information and is
> -     passed to the methods in the ops table when they are called.
> +The ``index_key`` argument should hold index key information and is
> +passed to the methods in the ops table when they are called.
>  
> -     This function makes no alteration to the array itself, but rather returns
> -     an edit script that must be applied.  -ENOMEM is returned in the case of
> -     an out-of-memory error.  NULL will be returned if the specified object is
> -     not found within the array.
> +This function makes no alteration to the array itself, but rather returns
> +an edit script that must be applied.  ``-ENOMEM`` is returned in the case of
> +an out-of-memory error.  ``NULL`` will be returned if the specified object is
> +not found within the array.
>  
> -     The caller should lock exclusively against other modifiers of the array.
> +The caller should lock exclusively against other modifiers of the array.
>  
>  
> - (4) Delete all objects from an associative array.
> +4. Delete all objects from an associative array. ::
>  
> -	struct assoc_array_edit *
> -	assoc_array_clear(struct assoc_array *array,
> -			  const struct assoc_array_ops *ops);
> +    struct assoc_array_edit *
> +    assoc_array_clear(struct assoc_array *array,
> +                      const struct assoc_array_ops *ops);
>  
> -     This deletes all the objects from an associative array and leaves it
> -     completely empty.
> +This deletes all the objects from an associative array and leaves it
> +completely empty.
>  
> -     This function makes no alteration to the array itself, but rather returns
> -     an edit script that must be applied.  -ENOMEM is returned in the case of
> -     an out-of-memory error.
> +This function makes no alteration to the array itself, but rather returns
> +an edit script that must be applied.  ``-ENOMEM`` is returned in the case of
> +an out-of-memory error.
>  
> -     The caller should lock exclusively against other modifiers of the array.
> +The caller should lock exclusively against other modifiers of the array.
>  
>  
> - (5) Destroy an associative array, deleting all objects.
> +5. Destroy an associative array, deleting all objects. ::
>  
> -	void assoc_array_destroy(struct assoc_array *array,
> -				 const struct assoc_array_ops *ops);
> +    void assoc_array_destroy(struct assoc_array *array,
> +                             const struct assoc_array_ops *ops);
>  
> -     This destroys the contents of the associative array and leaves it
> -     completely empty.  It is not permitted for another thread to be traversing
> -     the array under the RCU read lock at the same time as this function is
> -     destroying it as no RCU deferral is performed on memory release -
> -     something that would require memory to be allocated.
> +This destroys the contents of the associative array and leaves it
> +completely empty.  It is not permitted for another thread to be traversing
> +the array under the RCU read lock at the same time as this function is
> +destroying it as no RCU deferral is performed on memory release -
> +something that would require memory to be allocated.
>  
> -     The caller should lock exclusively against other modifiers and accessors
> -     of the array.
> +The caller should lock exclusively against other modifiers and accessors
> +of the array.
>  
>  
> - (6) Garbage collect an associative array.
> +6. Garbage collect an associative array. ::
>  
> -	int assoc_array_gc(struct assoc_array *array,
> -			   const struct assoc_array_ops *ops,
> -			   bool (*iterator)(void *object, void *iterator_data),
> -			   void *iterator_data);
> +    int assoc_array_gc(struct assoc_array *array,
> +                       const struct assoc_array_ops *ops,
> +                       bool (*iterator)(void *object, void *iterator_data),
> +                       void *iterator_data);
>  
> -     This iterates over the objects in an associative array and passes each one
> -     to iterator().  If iterator() returns true, the object is kept.  If it
> -     returns false, the object will be freed.  If the iterator() function
> -     returns true, it must perform any appropriate refcount incrementing on the
> -     object before returning.
> +This iterates over the objects in an associative array and passes each one to
> +``iterator()``.  If ``iterator()`` returns ``true``, the object is kept.  If it
> +returns ``false``, the object will be freed.  If the ``iterator()`` function
> +returns ``true``, it must perform any appropriate refcount incrementing on the
> +object before returning.
>  
> -     The internal tree will be packed down if possible as part of the iteration
> -     to reduce the number of nodes in it.
> +The internal tree will be packed down if possible as part of the iteration
> +to reduce the number of nodes in it.
>  
> -     The iterator_data is passed directly to iterator() and is otherwise
> -     ignored by the function.
> +The ``iterator_data`` is passed directly to ``iterator()`` and is otherwise
> +ignored by the function.
>  
> -     The function will return 0 if successful and -ENOMEM if there wasn't
> -     enough memory.
> +The function will return ``0`` if successful and ``-ENOMEM`` if there wasn't
> +enough memory.
>  
> -     It is possible for other threads to iterate over or search the array under
> -     the RCU read lock whilst this function is in progress.  The caller should
> -     lock exclusively against other modifiers of the array.
> +It is possible for other threads to iterate over or search the array under
> +the RCU read lock whilst this function is in progress.  The caller should
> +lock exclusively against other modifiers of the array.
>  
>  
> -ACCESS FUNCTIONS
> +Access Functions
>  ----------------
>  
>  There are two functions for accessing an associative array:
>  
> - (1) Iterate over all the objects in an associative array.
> +1. Iterate over all the objects in an associative array. ::
>  
> -	int assoc_array_iterate(const struct assoc_array *array,
> -				int (*iterator)(const void *object,
> -						void *iterator_data),
> -				void *iterator_data);
> +    int assoc_array_iterate(const struct assoc_array *array,
> +                            int (*iterator)(const void *object,
> +                                            void *iterator_data),
> +                            void *iterator_data);
>  
> -     This passes each object in the array to the iterator callback function.
> -     iterator_data is private data for that function.
> +This passes each object in the array to the iterator callback function.
> +``iterator_data`` is private data for that function.
>  
> -     This may be used on an array at the same time as the array is being
> -     modified, provided the RCU read lock is held.  Under such circumstances,
> -     it is possible for the iteration function to see some objects twice.  If
> -     this is a problem, then modification should be locked against.  The
> -     iteration algorithm should not, however, miss any objects.
> +This may be used on an array at the same time as the array is being
> +modified, provided the RCU read lock is held.  Under such circumstances,
> +it is possible for the iteration function to see some objects twice.  If
> +this is a problem, then modification should be locked against.  The
> +iteration algorithm should not, however, miss any objects.
>  
> -     The function will return 0 if no objects were in the array or else it will
> -     return the result of the last iterator function called.  Iteration stops
> -     immediately if any call to the iteration function results in a non-zero
> -     return.
> +The function will return ``0`` if no objects were in the array or else it will
> +return the result of the last iterator function called.  Iteration stops
> +immediately if any call to the iteration function results in a non-zero
> +return.
>  
>  
> - (2) Find an object in an associative array.
> +2. Find an object in an associative array. ::
>  
> -	void *assoc_array_find(const struct assoc_array *array,
> -			       const struct assoc_array_ops *ops,
> -			       const void *index_key);
> +    void *assoc_array_find(const struct assoc_array *array,
> +                           const struct assoc_array_ops *ops,
> +                           const void *index_key);
>  
> -     This walks through the array's internal tree directly to the object
> -     specified by the index key..
> +This walks through the array's internal tree directly to the object
> +specified by the index key..
>  
> -     This may be used on an array at the same time as the array is being
> -     modified, provided the RCU read lock is held.
> +This may be used on an array at the same time as the array is being
> +modified, provided the RCU read lock is held.
>  
> -     The function will return the object if found (and set *_type to the object
> -     type) or will return NULL if the object was not found.
> +The function will return the object if found (and set ``*_type`` to the object
> +type) or will return ``NULL`` if the object was not found.
>  
>  
> -INDEX KEY FORM
> +Index Key Form
>  --------------
>  
>  The index key can be of any form, but since the algorithms aren't told how long
> @@ -364,8 +341,7 @@ unlikely that more than one word of any particular index key will have to be
>  used.
>  
>  
> -=================
> -INTERNAL WORKINGS
> +Internal Workings
>  =================
>  
>  The associative array data structure has an internal tree.  This tree is
> @@ -373,82 +349,80 @@ constructed of two types of metadata blocks: nodes and shortcuts.
>  
>  A node is an array of slots.  Each slot can contain one of four things:
>  
> - (*) A NULL pointer, indicating that the slot is empty.
> -
> - (*) A pointer to an object (a leaf).
> -
> - (*) A pointer to a node at the next level.
> -
> - (*) A pointer to a shortcut.
> +* A NULL pointer, indicating that the slot is empty.
> +* A pointer to an object (a leaf).
> +* A pointer to a node at the next level.
> +* A pointer to a shortcut.
>  
>  
> -BASIC INTERNAL TREE LAYOUT
> +Basic Internal Tree Layout
>  --------------------------
>  
>  Ignoring shortcuts for the moment, the nodes form a multilevel tree.  The index
>  key space is strictly subdivided by the nodes in the tree and nodes occur on
> -fixed levels.  For example:
> -
> - Level:	0		1		2		3
> -	===============	===============	===============	===============
> -							NODE D
> -			NODE B		NODE C	+------>+---+
> -		+------>+---+	+------>+---+	|	| 0 |
> -	NODE A	|	| 0 |	|	| 0 |	|	+---+
> -	+---+	|	+---+	|	+---+	|	:   :
> -	| 0 |	|	:   :	|	:   :	|	+---+
> -	+---+	|	+---+	|	+---+	|	| f |
> -	| 1 |---+	| 3 |---+	| 7 |---+	+---+
> -	+---+		+---+		+---+
> -	:   :		:   :		| 8 |---+
> -	+---+		+---+		+---+	|	NODE E
> -	| e |---+	| f |		:   :   +------>+---+
> -	+---+	|	+---+		+---+		| 0 |
> -	| f |	|			| f |		+---+
> -	+---+	|			+---+		:   :
> -		|	NODE F				+---+
> -		+------>+---+				| f |
> -			| 0 |		NODE G		+---+
> -			+---+	+------>+---+
> -			:   :	|	| 0 |
> -			+---+	|	+---+
> -			| 6 |---+	:   :
> -			+---+		+---+
> -			:   :		| f |
> -			+---+		+---+
> -			| f |
> -			+---+
> +fixed levels.  For example::
> +
> + Level: 0               1               2               3
> +        =============== =============== =============== ===============
> +                                                        NODE D
> +                        NODE B          NODE C  +------>+---+
> +                +------>+---+   +------>+---+   |       | 0 |
> +        NODE A  |       | 0 |   |       | 0 |   |       +---+
> +        +---+   |       +---+   |       +---+   |       :   :
> +        | 0 |   |       :   :   |       :   :   |       +---+
> +        +---+   |       +---+   |       +---+   |       | f |
> +        | 1 |---+       | 3 |---+       | 7 |---+       +---+
> +        +---+           +---+           +---+
> +        :   :           :   :           | 8 |---+
> +        +---+           +---+           +---+   |       NODE E
> +        | e |---+       | f |           :   :   +------>+---+
> +        +---+   |       +---+           +---+           | 0 |
> +        | f |   |                       | f |           +---+
> +        +---+   |                       +---+           :   :
> +                |       NODE F                          +---+
> +                +------>+---+                           | f |
> +                        | 0 |           NODE G          +---+
> +                        +---+   +------>+---+
> +                        :   :   |       | 0 |
> +                        +---+   |       +---+
> +                        | 6 |---+       :   :
> +                        +---+           +---+
> +                        :   :           | f |
> +                        +---+           +---+
> +                        | f |
> +                        +---+
>  
>  In the above example, there are 7 nodes (A-G), each with 16 slots (0-f).
> -Assuming no other meta data nodes in the tree, the key space is divided thusly:
> -
> -	KEY PREFIX	NODE
> -	==========	====
> -	137*		D
> -	138*		E
> -	13[0-69-f]*	C
> -	1[0-24-f]*	B
> -	e6*		G
> -	e[0-57-f]*	F
> -	[02-df]*	A
> +Assuming no other meta data nodes in the tree, the key space is divided
> +thusly::
> +
> +    KEY PREFIX      NODE
> +    ==========      ====
> +    137*            D
> +    138*            E
> +    13[0-69-f]*     C
> +    1[0-24-f]*      B
> +    e6*             G
> +    e[0-57-f]*      F
> +    [02-df]*        A
>  
>  So, for instance, keys with the following example index keys will be found in
> -the appropriate nodes:
> -
> -	INDEX KEY	PREFIX	NODE
> -	===============	=======	====
> -	13694892892489	13	C
> -	13795289025897	137	D
> -	13889dde88793	138	E
> -	138bbb89003093	138	E
> -	1394879524789	12	C
> -	1458952489	1	B
> -	9431809de993ba	-	A
> -	b4542910809cd	-	A
> -	e5284310def98	e	F
> -	e68428974237	e6	G
> -	e7fffcbd443	e	F
> -	f3842239082	-	A
> +the appropriate nodes::
> +
> +    INDEX KEY       PREFIX  NODE
> +    =============== ======= ====
> +    13694892892489  13      C
> +    13795289025897  137     D
> +    13889dde88793   138     E
> +    138bbb89003093  138     E
> +    1394879524789   12      C
> +    1458952489      1       B
> +    9431809de993ba  -       A
> +    b4542910809cd   -       A
> +    e5284310def98   e       F
> +    e68428974237    e6      G
> +    e7fffcbd443     e       F
> +    f3842239082     -       A
>  
>  To save memory, if a node can hold all the leaves in its portion of keyspace,
>  then the node will have all those leaves in it and will not have any metadata
> @@ -462,23 +436,23 @@ metadata pointer.  If the metadata pointer is there, any leaf whose key matches
>  the metadata key prefix must be in the subtree that the metadata pointer points
>  to.
>  
> -In the above example list of index keys, node A will contain:
> +In the above example list of index keys, node A will contain::
>  
> -	SLOT	CONTENT		INDEX KEY (PREFIX)
> -	====	===============	==================
> -	1	PTR TO NODE B	1*
> -	any	LEAF		9431809de993ba
> -	any	LEAF		b4542910809cd
> -	e	PTR TO NODE F	e*
> -	any	LEAF		f3842239082
> +    SLOT    CONTENT         INDEX KEY (PREFIX)
> +    ====    =============== ==================
> +    1       PTR TO NODE B   1*
> +    any     LEAF            9431809de993ba
> +    any     LEAF            b4542910809cd
> +    e       PTR TO NODE F   e*
> +    any     LEAF            f3842239082
>  
> -and node B:
> +and node B::
>  
> -	3	PTR TO NODE C	13*
> -	any	LEAF		1458952489
> +    3	PTR TO NODE C	13*
> +    any	LEAF		1458952489
>  
>  
> -SHORTCUTS
> +Shortcuts
>  ---------
>  
>  Shortcuts are metadata records that jump over a piece of keyspace.  A shortcut
> @@ -486,12 +460,13 @@ is a replacement for a series of single-occupancy nodes ascending through the
>  levels.  Shortcuts exist to save memory and to speed up traversal.
>  
>  It is possible for the root of the tree to be a shortcut - say, for example,
> -the tree contains at least 17 nodes all with key prefix '1111'.  The insertion
> -algorithm will insert a shortcut to skip over the '1111' keyspace in a single
> -bound and get to the fourth level where these actually become different.
> +the tree contains at least 17 nodes all with key prefix ``1111``.  The
> +insertion algorithm will insert a shortcut to skip over the ``1111`` keyspace
> +in a single bound and get to the fourth level where these actually become
> +different.
>  
>  
> -SPLITTING AND COLLAPSING NODES
> +Splitting And Collapsing Nodes
>  ------------------------------
>  
>  Each node has a maximum capacity of 16 leaves and metadata pointers.  If the
> @@ -508,7 +483,7 @@ fewer, then the subtree will be collapsed down to a single node - and this will
>  ripple towards the root if possible.
>  
>  
> -NON-RECURSIVE ITERATION
> +Non-Recursive Iteration
>  -----------------------
>  
>  Each node and shortcut contains a back pointer to its parent and the number of
> @@ -519,55 +494,55 @@ make sure progress is made without the need for a stack.
>  The backpointers, however, make simultaneous alteration and iteration tricky.
>  
>  
> -SIMULTANEOUS ALTERATION AND ITERATION
> +Simultaneous Alteration And Iteration
>  -------------------------------------
>  
>  There are a number of cases to consider:
>  
> - (1) Simple insert/replace.  This involves simply replacing a NULL or old
> -     matching leaf pointer with the pointer to the new leaf after a barrier.
> -     The metadata blocks don't change otherwise.  An old leaf won't be freed
> -     until after the RCU grace period.
> +1. Simple insert/replace.  This involves simply replacing a NULL or old
> +   matching leaf pointer with the pointer to the new leaf after a barrier.
> +   The metadata blocks don't change otherwise.  An old leaf won't be freed
> +   until after the RCU grace period.
>  
> - (2) Simple delete.  This involves just clearing an old matching leaf.  The
> -     metadata blocks don't change otherwise.  The old leaf won't be freed until
> -     after the RCU grace period.
> +2. Simple delete.  This involves just clearing an old matching leaf.  The
> +   metadata blocks don't change otherwise.  The old leaf won't be freed until
> +   after the RCU grace period.
>  
> - (3) Insertion replacing part of a subtree that we haven't yet entered.  This
> -     may involve replacement of part of that subtree - but that won't affect
> -     the iteration as we won't have reached the pointer to it yet and the
> -     ancestry blocks are not replaced (the layout of those does not change).
> +3. Insertion replacing part of a subtree that we haven't yet entered.  This
> +   may involve replacement of part of that subtree - but that won't affect
> +   the iteration as we won't have reached the pointer to it yet and the
> +   ancestry blocks are not replaced (the layout of those does not change).
>  
> - (4) Insertion replacing nodes that we're actively processing.  This isn't a
> -     problem as we've passed the anchoring pointer and won't switch onto the
> -     new layout until we follow the back pointers - at which point we've
> -     already examined the leaves in the replaced node (we iterate over all the
> -     leaves in a node before following any of its metadata pointers).
> +4. Insertion replacing nodes that we're actively processing.  This isn't a
> +   problem as we've passed the anchoring pointer and won't switch onto the
> +   new layout until we follow the back pointers - at which point we've
> +   already examined the leaves in the replaced node (we iterate over all the
> +   leaves in a node before following any of its metadata pointers).
>  
> -     We might, however, re-see some leaves that have been split out into a new
> -     branch that's in a slot further along than we were at.
> +   We might, however, re-see some leaves that have been split out into a new
> +   branch that's in a slot further along than we were at.
>  
> - (5) Insertion replacing nodes that we're processing a dependent branch of.
> -     This won't affect us until we follow the back pointers.  Similar to (4).
> +5. Insertion replacing nodes that we're processing a dependent branch of.
> +   This won't affect us until we follow the back pointers.  Similar to (4).
>  
> - (6) Deletion collapsing a branch under us.  This doesn't affect us because the
> -     back pointers will get us back to the parent of the new node before we
> -     could see the new node.  The entire collapsed subtree is thrown away
> -     unchanged - and will still be rooted on the same slot, so we shouldn't
> -     process it a second time as we'll go back to slot + 1.
> +6. Deletion collapsing a branch under us.  This doesn't affect us because the
> +   back pointers will get us back to the parent of the new node before we
> +   could see the new node.  The entire collapsed subtree is thrown away
> +   unchanged - and will still be rooted on the same slot, so we shouldn't
> +   process it a second time as we'll go back to slot + 1.
>  
>  Note:

Please use:

.. note::

>  
> - (*) Under some circumstances, we need to simultaneously change the parent
> -     pointer and the parent slot pointer on a node (say, for example, we
> -     inserted another node before it and moved it up a level).  We cannot do
> -     this without locking against a read - so we have to replace that node too.
> +* Under some circumstances, we need to simultaneously change the parent

... and remove the asterisk.

> +  pointer and the parent slot pointer on a node (say, for example, we
> +  inserted another node before it and moved it up a level).  We cannot do
> +  this without locking against a read - so we have to replace that node too.
>  
> -     However, when we're changing a shortcut into a node this isn't a problem
> -     as shortcuts only have one slot and so the parent slot number isn't used
> -     when traversing backwards over one.  This means that it's okay to change
> -     the slot number first - provided suitable barriers are used to make sure
> -     the parent slot number is read after the back pointer.
> +  However, when we're changing a shortcut into a node this isn't a problem
> +  as shortcuts only have one slot and so the parent slot number isn't used
> +  when traversing backwards over one.  This means that it's okay to change
> +  the slot number first - provided suitable barriers are used to make sure
> +  the parent slot number is read after the back pointer.
>  
>  Obsolete blocks and leaves are freed up after an RCU grace period has passed,
>  so as long as anyone doing walking or iteration holds the RCU read lock, the
> diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst
> index f7ef7fd..480d9a3 100644
> --- a/Documentation/core-api/index.rst
> +++ b/Documentation/core-api/index.rst
> @@ -7,6 +7,7 @@ Kernel and driver related documentation.
>  .. toctree::
>     :maxdepth: 1
>  
> +   assoc_array
>     workqueue
>  
>  .. only::  subproject



Thanks,
Mauro