/* Copyright 2000-2005 The Apache Software Foundation or its licensors, as
 * applicable.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/**
 * @file apr_buckets.h
 * @brief APR-UTIL Buckets/Bucket Brigades
 */

#ifndef APR_BUCKETS_H
#define APR_BUCKETS_H

#if defined(APR_BUCKET_DEBUG) && !defined(APR_RING_DEBUG)
#define APR_RING_DEBUG
#endif

#include "apu.h"
#include "apr_network_io.h"
#include "apr_file_io.h"
#include "apr_general.h"
#include "apr_mmap.h"
#include "apr_errno.h"
#include "apr_ring.h"
#include "apr.h"
#if APR_HAVE_SYS_UIO_H
#include <sys/uio.h>	/* for struct iovec */
#endif
#if APR_HAVE_STDARG_H
#include <stdarg.h>
#endif

#ifdef __cplusplus
extern "C" {
#endif

/**
 * @defgroup APR_Util_Bucket_Brigades Bucket Brigades
 * @ingroup APR_Util
 * @{ 
 */

/** default bucket buffer size - 8KB minus room for memory allocator headers */
#define APR_BUCKET_BUFF_SIZE 8000

/** Determines how a bucket or brigade should be read */
typedef enum {
    APR_BLOCK_READ,   /**< block until data becomes available */
    APR_NONBLOCK_READ /**< return immediately if no data is available */
} apr_read_type_e;

/**
 * The one-sentence buzzword-laden overview: Bucket brigades represent
 * a complex data stream that can be passed through a layered IO
 * system without unnecessary copying. A longer overview follows...
 *
 * A bucket brigade is a doubly linked list (ring) of buckets, so we
 * aren't limited to inserting at the front and removing at the end.
 * Buckets are only passed around as members of a brigade, although
 * singleton buckets can occur for short periods of time.
 *
 * Buckets are data stores of various types. They can refer to data in
 * memory, or part of a file or mmap area, or the output of a process,
 * etc. Buckets also have some type-dependent accessor functions:
 * read, split, copy, setaside, and destroy.
 *
 * read returns the address and size of the data in the bucket. If the
 * data isn't in memory then it is read in and the bucket changes type
 * so that it can refer to the new location of the data. If all the
 * data doesn't fit in the bucket then a new bucket is inserted into
 * the brigade to hold the rest of it.
 *
 * split divides the data in a bucket into two regions. After a split
 * the original bucket refers to the first part of the data and a new
 * bucket inserted into the brigade after the original bucket refers
 * to the second part of the data. Reference counts are maintained as
 * necessary.
 *
 * setaside ensures that the data in the bucket has a long enough
 * lifetime. Sometimes it is convenient to create a bucket referring
 * to data on the stack in the expectation that it will be consumed
 * (output to the network) before the stack is unwound. If that
 * expectation turns out not to be valid, the setaside function is
 * called to move the data somewhere safer.
 *
 * copy makes a duplicate of the bucket structure as long as it's
 * possible to have multiple references to a single copy of the
 * data itself.  Not all bucket types can be copied.
 *
 * destroy maintains the reference counts on the resources used by a
 * bucket and frees them if necessary.
 *
 * Note: all of the above functions have wrapper macros (apr_bucket_read(),
 * apr_bucket_destroy(), etc), and those macros should be used rather
 * than using the function pointers directly.
 *
 * To write a bucket brigade, they are first made into an iovec, so that we
 * don't write too little data at one time.  Currently we ignore compacting the
 * buckets into as few buckets as possible, but if we really want good
 * performance, then we need to compact the buckets before we convert to an
 * iovec, or possibly while we are converting to an iovec.
 */

/*
 * Forward declaration of the main types.
 */

/** @see apr_bucket_brigade */
typedef struct apr_bucket_brigade apr_bucket_brigade;
/** @see apr_bucket */
typedef struct apr_bucket apr_bucket;
/** @see apr_bucket_alloc_t */
typedef struct apr_bucket_alloc_t apr_bucket_alloc_t;

/** @see apr_bucket_type_t */
typedef struct apr_bucket_type_t apr_bucket_type_t;

/**
 * Basic bucket type
 */
struct apr_bucket_type_t {
    /**
     * The name of the bucket type
     */
    const char *name;
    /** 
     * The number of functions this bucket understands.  Can not be less than
     * five.
     */
    int num_func;
    /**
     * Whether the bucket contains metadata (ie, information that
     * describes the regular contents of the brigade).  The metadata
     * is not returned by apr_bucket_read() and is not indicated by
     * the ->length of the apr_bucket itself.  In other words, an
     * empty bucket is safe to arbitrarily remove if and only if it
     * contains no metadata.  In this sense, "data" is just raw bytes
     * that are the "content" of the brigade and "metadata" describes
     * that data but is not a proper part of it.
     */
    enum {
        /** This bucket type represents actual data to send to the client. */
        APR_BUCKET_DATA = 0,
        /** This bucket type represents metadata. */
        APR_BUCKET_METADATA = 1
    } is_metadata;
    /**
     * Free the private data and any resources used by the bucket (if they
     *  aren't shared with another bucket).  This function is required to be
     *  implemented for all bucket types, though it might be a no-op on some
     *  of them (namely ones that never allocate any private data structures).
     * @param data The private data pointer from the bucket to be destroyed
     */
    void (*destroy)(void *data);

    /**
     * Read the data from the bucket. This is required to be implemented
     *  for all bucket types.
     * @param b The bucket to read from
     * @param str A place to store the data read.  Allocation should only be
     *            done if absolutely necessary. 
     * @param len The amount of data read.
     * @param block Should this read function block if there is more data that
     *              cannot be read immediately.
     */
    apr_status_t (*read)(apr_bucket *b, const char **str, apr_size_t *len, 
                         apr_read_type_e block);
    
    /**
     * Make it possible to set aside the data for at least as long as the
     *  given pool. Buckets containing data that could potentially die before
     *  this pool (e.g. the data resides on the stack, in a child pool of
     *  the given pool, or in a disjoint pool) must somehow copy, shift, or
     *  transform the data to have the proper lifetime.
     * @param e The bucket to convert
     * @remark Some bucket types contain data that will always outlive the
     *         bucket itself. For example no data (EOS and FLUSH), or the data
     *         resides in global, constant memory (IMMORTAL), or the data is on
     *      the heap (HEAP). For these buckets, apr_bucket_setaside_noop can
     *      be used.
     */
    apr_status_t (*setaside)(apr_bucket *e, apr_pool_t *pool);

    /**
     * Split one bucket in two at the specified position by duplicating
     *  the bucket structure (not the data) and modifying any necessary
     *  start/end/offset information.  If it's not possible to do this
     *  for the bucket type (perhaps the length of the data is indeterminate,
     *  as with pipe and socket buckets), then APR_ENOTIMPL is returned.
     * @param e The bucket to split
     * @param point The offset of the first byte in the new bucket
     */
    apr_status_t (*split)(apr_bucket *e, apr_size_t point);

    /**
     * Copy the bucket structure (not the data), assuming that this is
     *  possible for the bucket type. If it's not, APR_ENOTIMPL is returned.
     * @param e The bucket to copy
     * @param c Returns a pointer to the new bucket
     */
    apr_status_t (*copy)(apr_bucket *e, apr_bucket **c);

};

/**
 * apr_bucket structures are allocated on the malloc() heap and
 * their lifetime is controlled by the parent apr_bucket_brigade
 * structure. Buckets can move from one brigade to another e.g. by
 * calling APR_BRIGADE_CONCAT(). In general the data in a bucket has
 * the same lifetime as the bucket and is freed when the bucket is
 * destroyed; if the data is shared by more than one bucket (e.g.
 * after a split) the data is freed when the last bucket goes away.
 */
struct apr_bucket {
    /** Links to the rest of the brigade */
    APR_RING_ENTRY(apr_bucket) link;
    /** The type of bucket.  */
    const apr_bucket_type_t *type;
    /** The length of the data in the bucket.  This could have been implemented
     *  with a function, but this is an optimization, because the most
     *  common thing to do will be to get the length.  If the length is unknown,
     *  the value of this field will be (apr_size_t)(-1).
     */
    apr_size_t length;
    /** The start of the data in the bucket relative to the private base
     *  pointer.  The vast majority of bucket types allow a fixed block of
     *  data to be referenced by multiple buckets, each bucket pointing to
     *  a different segment of the data.  That segment starts at base+start
     *  and ends at base+start+length.  
     *  If the length == (apr_size_t)(-1), then start == -1.
     */
    apr_off_t start;
    /** type-dependent data hangs off this pointer */
    void *data;	
    /**
     * Pointer to function used to free the bucket. This function should
     * always be defined and it should be consistent with the memory
     * function used to allocate the bucket. For example, if malloc() is 
     * used to allocate the bucket, this pointer should point to free().
     * @param e Pointer to the bucket being freed
     */
    void (*free)(void *e);
    /** The freelist from which this bucket was allocated */
    apr_bucket_alloc_t *list;
};

/** A list of buckets */
struct apr_bucket_brigade {
    /** The pool to associate the brigade with.  The data is not allocated out
     *  of the pool, but a cleanup is registered with this pool.  If the 
     *  brigade is destroyed by some mechanism other than pool destruction,
     *  the destroying function is responsible for killing the cleanup.
     */
    apr_pool_t *p;
    /** The buckets in the brigade are on this list. */
    /*
     * The apr_bucket_list structure doesn't actually need a name tag
     * because it has no existence independent of struct apr_bucket_brigade;
     * the ring macros are designed so that you can leave the name tag
     * argument empty in this situation but apparently the Windows compiler
     * doesn't like that.
     */
    APR_RING_HEAD(apr_bucket_list, apr_bucket) list;
    /** The freelist from which this bucket was allocated */
    apr_bucket_alloc_t *bucket_alloc;
};


/**
 * Function called when a brigade should be flushed
 */
typedef apr_status_t (*apr_brigade_flush)(apr_bucket_brigade *bb, void *ctx);

/*
 * define APR_BUCKET_DEBUG if you want your brigades to be checked for
 * validity at every possible instant.  this will slow your code down
 * substantially but is a very useful debugging tool.
 */
#ifdef APR_BUCKET_DEBUG

#define APR_BRIGADE_CHECK_CONSISTENCY(b)				\
        APR_RING_CHECK_CONSISTENCY(&(b)->list, apr_bucket, link)

#define APR_BUCKET_CHECK_CONSISTENCY(e)					\
        APR_RING_CHECK_ELEM_CONSISTENCY((e), apr_bucket, link)

#else
/**
 * checks the ring pointers in a bucket brigade for consistency.  an
 * abort() will be triggered if any inconsistencies are found.
 *   note: this is a no-op unless APR_BUCKET_DEBUG is defined.
 * @param b The brigade
 */
#define APR_BRIGADE_CHECK_CONSISTENCY(b)
/**
 * checks the brigade a bucket is in for ring consistency.  an
 * abort() will be triggered if any inconsistencies are found.
 *   note: this is a no-op unless APR_BUCKET_DEBUG is defined.
 * @param e The bucket
 */
#define APR_BUCKET_CHECK_CONSISTENCY(e)
#endif


/**
 * Wrappers around the RING macros to reduce the verbosity of the code
 * that handles bucket brigades.
 */
/**
 * The magic pointer value that indicates the head of the brigade
 * @remark This is used to find the beginning and end of the brigade, eg:
 * <pre>
 *      while (e != APR_BRIGADE_SENTINEL(b)) {
 *          ...
 *          e = APR_BUCKET_NEXT(e);
 *      }
 * </pre>
 * @param  b The brigade
 * @return The magic pointer value
 */
#define APR_BRIGADE_SENTINEL(b)	APR_RING_SENTINEL(&(b)->list, apr_bucket, link)

/**
 * Determine if the bucket brigade is empty
 * @param b The brigade to check
 * @return true or false
 */
#define APR_BRIGADE_EMPTY(b)	APR_RING_EMPTY(&(b)->list, apr_bucket, link)

/**
 * Return the first bucket in a brigade
 * @param b The brigade to query
 * @return The first bucket in the brigade
 */
#define APR_BRIGADE_FIRST(b)	APR_RING_FIRST(&(b)->list)
/**
 * Return the last bucket in a brigade
 * @param b The brigade to query
 * @return The last bucket in the brigade
 */
#define APR_BRIGADE_LAST(b)	APR_RING_LAST(&(b)->list)

/**
 * Iterate through a bucket brigade
 * @param e The current bucket
 * @param b The brigade to iterate over
 * @remark This is the same as either:
 * <pre>
 *	e = APR_BRIGADE_FIRST(b);
 * 	while (e != APR_BRIGADE_SENTINEL(b)) {
 *	    ...
 * 	    e = APR_BUCKET_NEXT(e);
 * 	}
 *  OR
 * 	for (e = APR_BRIGADE_FIRST(b);
 *           e != APR_BRIGADE_SENTINEL(b);
 *           e = APR_BUCKET_NEXT(e)) {
 *	    ...
 * 	}
 * </pre>
 * @warning Be aware that you cannot change the value of e within
 * the foreach loop, nor can you destroy the bucket it points to.
 * Modifying the prev and next pointers of the bucket is dangerous
 * but can be done if you're careful.  If you change e's value or