Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754268AbcKYNEc (ORCPT ); Fri, 25 Nov 2016 08:04:32 -0500 Received: from ec2-52-27-115-49.us-west-2.compute.amazonaws.com ([52.27.115.49]:59328 "EHLO osg.samsung.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1751764AbcKYNEY (ORCPT ); Fri, 25 Nov 2016 08:04:24 -0500 Date: Fri, 25 Nov 2016 11:03:25 -0200 From: Mauro Carvalho Chehab To: Silvio Fricke Cc: linux-doc@vger.kernel.org, Jonathan Corbet , Ming Lei , "Luis R . Rodriguez" , Mauro Carvalho Chehab , linux-kernel@vger.kernel.org Subject: Re: [PATCH v2 1/4] Documentation/assoc_array.txt: convert to ReST markup Message-ID: <20161125110325.6eb186c7@vento.lan> In-Reply-To: References: Organization: Samsung X-Mailer: Claws Mail 3.14.0 (GTK+ 2.24.31; x86_64-redhat-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 38304 Lines: 901 Em Fri, 25 Nov 2016 11:02:39 +0100 Silvio Fricke escreveu: > ... and move to Documentation/core-api folder. > > Signed-off-by: Silvio Fricke > --- > 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 . The associative array is > -rooted on the following structure: > +The public API can be found in ````. 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