From cvs-return-4053-apmail-apr-cvs-archive=apr.apache.org@apr.apache.org Wed Aug 28 14:54:13 2002 Return-Path: Delivered-To: apmail-apr-cvs-archive@apr.apache.org Received: (qmail 36118 invoked by uid 500); 28 Aug 2002 14:54:13 -0000 Mailing-List: contact cvs-help@apr.apache.org; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Reply-To: dev@apr.apache.org Delivered-To: mailing list cvs@apr.apache.org Received: (qmail 36107 invoked from network); 28 Aug 2002 14:54:12 -0000 Date: 28 Aug 2002 14:54:12 -0000 Message-ID: <20020828145412.80083.qmail@icarus.apache.org> From: fanf@apache.org To: apr-cvs@apache.org Subject: cvs commit: apr/include apr_ring.h X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N fanf 2002/08/28 07:54:12 Modified: include apr_ring.h Log: Explain the workings of the ring sentinel. They'll never let me into the Magic Circle. Revision Changes Path 1.7 +53 -2 apr/include/apr_ring.h Index: apr_ring.h =================================================================== RCS file: /home/cvs/apr/include/apr_ring.h,v retrieving revision 1.6 retrieving revision 1.7 diff -u -r1.6 -r1.7 --- apr_ring.h 3 Jul 2002 00:15:07 -0000 1.6 +++ apr_ring.h 28 Aug 2002 14:54:12 -0000 1.7 @@ -96,8 +96,10 @@ * char *bar; * }; * - * An element struct may be put on more than one ring if it has - * more than one APR_RING_ENTRY field. + * + * An element struct may be put on more than one ring if it has more + * than one APR_RING_ENTRY field. Each APR_RING_ENTRY has a corresponding + * APR_RING_HEAD declaration. * * @warning For strict C standards compliance you should put the APR_RING_ENTRY * first in the element struct unless the head is always part of a larger @@ -139,6 +141,55 @@ * the ring's head. The head itself isn't an element, but in order to * get rid of all the special cases when dealing with the ends of the * ring, we play typecasting games to make it look like one. + * + * Here is a diagram to illustrate the arrangements of the next and + * prev pointers of each element in a single ring. Note that they point + * to the start of each element, not to the APR_RING_ENTRY structure. + * + * 
  + *     +->+------+<-+  +->+------+<-+  +->+------+<-+
  + *     |  |struct|  |  |  |struct|  |  |  |struct|  |
  + *    /   | elem |   \/   | elem |   \/   | elem |  \
  + * ...    |      |   /\   |      |   /\   |      |   ...
  + *        +------+  |  |  +------+  |  |  +------+
  + *   ...--|prev  |  |  +--|ring  |  |  +--|prev  |
  + *        |  next|--+     | entry|--+     |  next|--...
  + *        +------+        +------+        +------+
  + *        | etc. |        | etc. |        | etc. |
  + *        :      :        :      :        :      :
  + *
+ * + * The APR_RING_HEAD is nothing but a bare APR_RING_ENTRY. The prev + * and next pointers in the first and last elements don't actually + * point to the head, they point to a phantom place called the + * sentinel. Its value is such that last->next->next == first because + * the offset from the sentinel to the head's next pointer is the same + * as the offset from the start of an element to its next pointer. + * This also works in the opposite direction. + * + * 
  + *        last                            first
  + *     +->+------+<-+  +->sentinel<-+  +->+------+<-+
  + *     |  |struct|  |  |            |  |  |struct|  |
  + *    /   | elem |   \/              \/   | elem |  \
  + * ...    |      |   /\              /\   |      |   ...
  + *        +------+  |  |  +------+  |  |  +------+
  + *   ...--|prev  |  |  +--|ring  |  |  +--|prev  |
  + *        |  next|--+     |  head|--+     |  next|--...
  + *        +------+        +------+        +------+
  + *        | etc. |                        | etc. |
  + *        :      :                        :      :
  + *
+ * + * Note that the offset mentioned above is different for each kind of + * ring that the element may be on, and each kind of ring has a unique + * name for its APR_RING_ENTRY in each element, and has its own type + * for its APR_RING_HEAD. + * + * Note also that if the offset is non-zero (which is required if an + * element has more than one APR_RING_ENTRY), the unreality of the + * sentinel may have bad implications on very perverse implementations + * of C -- see the warning in APR_RING_ENTRY. * * @param hp The head of the ring * @param elem The name of the element struct