httpd-docs mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From f...@locus.apache.org
Subject cvs commit: apache-2.0/src/include ap_ring.h
Date Fri, 08 Sep 2000 02:00:06 GMT
fanf        00/09/07 19:00:06

  Added:       src/include ap_ring.h
  Log:
  Macros for implementing doubly-linked lists that bite their own tails like
  Friedrich August Kekulé's benzene rings.
  
  Revision  Changes    Path
  1.1                  apache-2.0/src/include/ap_ring.h
  
  Index: ap_ring.h
  ===================================================================
  /* ====================================================================
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 2000 The Apache Software Foundation.  All rights
   * reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   *
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   *
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in
   *    the documentation and/or other materials provided with the
   *    distribution.
   *
   * 3. The end-user documentation included with the redistribution,
   *    if any, must include the following acknowledgment:
   *       "This product includes software developed by the
   *        Apache Software Foundation (http://www.apache.org/)."
   *    Alternately, this acknowledgment may appear in the software itself,
   *    if and wherever such third-party acknowledgments normally appear.
   *
   * 4. The names "Apache" and "Apache Software Foundation" must
   *    not be used to endorse or promote products derived from this
   *    software without prior written permission. For written
   *    permission, please contact apache@apache.org.
   *
   * 5. Products derived from this software may not be called "Apache",
   *    nor may "Apache" appear in their name, without prior written
   *    permission of the Apache Software Foundation.
   *
   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   * SUCH DAMAGE.
   * ====================================================================
   *
   * This software consists of voluntary contributions made by many
   * individuals on behalf of the Apache Software Foundation.  For more
   * information on the Apache Software Foundation, please see
   * <http://www.apache.org/>.
   */
  
  /*
   * This code draws heavily from the 4.4BSD <sys/queue.h> macros
   * and Dean Gaudet's "splim/ring.h".
   * <http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/queue.h>
   * <http://www.arctic.org/~dean/splim/>
   *
   * We'd use Dean's code directly if we could guarantee the
   * availability of inline functions.
   */
  
  #ifndef AP_RING_H
  #define AP_RING_H
  
  /*
   * for offsetof()
   */
  #include <stddef.h>
  
  /*
   * A ring is a kind of doubly-linked list.
   */
  
  /*
   * A struct on a ring contains a field linking it to the other
   * elements in the ring, e.g.
   *
   *      struct my_item_t {
   *          AP_RING_ENTRY(my_item_t) link;
   *          int foo;
   *          char *bar;
   *      };
   *
   * A struct may be put on more than one ring if it has more than one
   * AP_RING_ENTRY field.
   */
  #define AP_RING_ENTRY(elem)						\
      struct {								\
  	struct elem *next;						\
  	struct elem *prev;						\
      }
  
  /*
   * Each ring is managed via its head, which is a struct declared like this:
   *
   *      AP_RING_HEAD(my_ring_t, my_item_t);
   *      struct my_ring_t ring, *ringp;
   *
   * This struct looks just like the element link struct so that we can
   * be sure that the typecasting games will work as expected.
   *
   * The first element in the ring is next after the head, and the last
   * element is just before the head.
   */
  #define AP_RING_HEAD(head, elem)					\
      struct head {							\
  	struct elem *next;						\
  	struct elem *prev;						\
      }
  
  /*
   * 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. The sentinel is the
   * magic pointer value that occurs before the first and after the last
   * elements in the ring, computed from the address of the ring's head.
   *
   * Note that for strict C standards compliance you should put the
   * AP_RING_ENTRY first in struct elem_tag unless the head is always
   * part of a larger object with enough earlier fields to accommodate
   * the offsetof() computed below. You can usually ignore this caveat.
   */
  #define AP_RING_SENTINAL(hp, elem, link)				\
      (struct elem *)((char *)(hp) - offsetof(struct elem, link))
  
  /*
   * Accessor macros. Use these rather than footling inside the
   * structures directly so that you can more easily change to a
   * different flavour of list from BSD's <sys/queue.h>.
   */
  #define AP_RING_FIRST(hp)	(hp)->next
  #define AP_RING_LAST(hp)	(hp)->prev
  #define AP_RING_NEXT(ep, link)	(ep)->link.next
  #define AP_RING_PREV(ep, link)	(ep)->link.prev
  
  /*
   * Empty rings and singleton elements.
   */
  #define AP_RING_INIT(hp, elem, link) do {				\
  	AP_RING_FIRST((hp)) = AP_RING_SENTINEL((hp), elem, link);	\
  	AP_RING_LAST((hp))  = AP_RING_SENTINEL((hp), elem, link);	\
      } while (0)
  
  #define AP_RING_EMPTY(hp, elem, link)					\
      (AP_RING_FIRST((hp)) == AP_RING_SENTINEL((hp), elem, link))
  
  #define AP_RING_ELEM_INIT(ep, link) do {				\
  	AP_RING_NEXT((ep), link) = (ep);				\
  	AP_RING_PREV((ep), link) = (ep);				\
      } while (0)
  
  /*
   * Adding elements.
   */
  #define AP_RING_SPLICE_BEFORE(lep, ep1, epN, link) do {			\
  	AP_RING_NEXT((epN), link) = (lep);				\
  	AP_RING_PREV((ep1), link) = AP_RING_PREV((lep), link);		\
  	AP_RING_NEXT(AP_RING_PREV((lep), link), link) = (ep1);		\
  	AP_RING_PREV((lep), link) = (epN);				\
      } while (0)
  
  #define AP_RING_SPLICE_AFTER(lep, ep1, epN, link) do {			\
  	AP_RING_PREV((ep1), link) = (lep);				\
  	AP_RING_NEXT((epN), link) = AP_RING_NEXT((lep), link);		\
  	AP_RING_PREV(AP_RING_NEXT((lep), link), link) = (epN);		\
  	AP_RING_NEXT((lep), link) = (ep1);				\
      } while (0)
  
  #define AP_RING_INSERT_BEFORE(lep, nep, link)				\
  	AP_RING_SPLICE_BEFORE((lep), (nep), (nep), link)
  
  #define AP_RING_INSERT_AFTER(lep, nep, link)				\
  	AP_RING_SPLICE_AFTER((lep), (nep), (nep), link)
  
  /*
   * We could implement these by splicing after and before the sentinel
   * instead of before the first and after the last respectively, but
   * then the caller would have to pass in the element type.
   */
  #define AP_RING_SPLICE_HEAD(hp, ep1, epN, link)				\
  	AP_RING_SPLICE_BEFORE(AP_RING_FIRST((hp)), (ep1), (epN), link)
  
  #define AP_RING_SPLICE_TAIL(hp, ep1, epN, link)				\
  	AP_RING_SPLICE_AFTER(AP_RING_LAST((hp)), (ep1), (epN), link)
  
  #define AP_RING_INSERT_HEAD(lep, nep, link)				\
  	AP_RING_SPLICE_HEAD((lep), (nep), (nep), link)
  
  #define AP_RING_INSERT_TAIL(lep, nep, link)				\
  	AP_RING_SPLICE_TAIL((lep), (nep), (nep), link)
  
  /*
   * Concatenating ring h2 onto the end of ring h1 leaves h2 empty.
   *
   * Doing this without asking for the element type is ugly.
   */
  #define AP_RING_CONCAT(h1, h2, elem, link) do {				\
  	if (!AP_RING_EMPTY((h2), elem, link)) {				\
  	    AP_RING_SPLICE_BEFORE(AP_RING_SENTINEL((h1), elem, link),	\
  				  AP_RING_FIRST((h2)),			\
  				  AP_RING_LAST((h2)), link);		\
  	    AP_RING_INIT((h2), elem, link);				\
  	}								\
      } while (0)
  
  /*
   * Removing elements. Be warned that the unspliced elements are left
   * with dangling pointers at either end!
   */
  #define AP_RING_UNSPLICE(ep1, epN, link) do {				\
  	AP_RING_NEXT(AP_RING_PREV((ep1), link), link) =			\
  		     AP_RING_NEXT((epN), link);				\
  	AP_RING_PREV(AP_RING_NEXT((epN), link), link) =			\
  		     AP_RING_PREV((ep1), link);				\
      } while (0)
  
  #define AP_RING_REMOVE(ep, link)					\
      AP_RING_UNSPLICE((ep), (ep), link)
  
  /*
   * Iteration.
   */
  #define AP_RING_FOREACH(ep, hp, elem, link)				\
      for ((ep)  = AP_RING_FIRST((hp));					\
  	 (ep) != AP_RING_SENTINEL((hp), elem, link);			\
  	 (ep)  = AP_RING_NEXT((ep), link))
  
  #define AP_RING_FOREACH_REVERSE(ep, hp, elem, link)			\
      for ((ep)  = AP_RING_LAST((hp));					\
  	 (ep) != AP_RING_SENTINEL((hp), elem, link);			\
  	 (ep)  = AP_RING_PREV((ep), link))
  
  #endif /* !AP_RING_H */
  
  
  

Mime
View raw message