mmlist.3

mmstatd包含一个 C库和服务器

.\" $Id: mmlist.3,v 1.4 2003/01/08 20:57:46 mmondor Exp $
.\"
.\" Copyright (C) 2002-2003, Matthew Mondor
.\" 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. All advertising materials mentioning features or use of this software
.\"    must display the following acknowledgement:
.\"      This product includes software written by Matthew Mondor.
.\" 4. The name of Matthew Mondor may not be used to endorse or promote
.\"    products derived from this software without specific prior written
.\"    permission.
.\"
.\" THIS SOFTWARE IS PROVIDED BY MATTHEW MONDOR ``AS IS'' AND ANY EXPRESS 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 MATTHEW MONDOR 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.
.\"
.Dd January 7, 2003
.Os
.Dt MMLIST 3
.Sh NAME
.Nm mmlist
.Nd General purpose doubly linked list library with pool support.
.Sh SYNOPSIS
.Fd #include <sys/types.h>
.Fd #include <mmtypes.h>
.Fd #include <mmlist.h>
.Ft void
.Fn INITLIST "list *list"
.Ft list *
.Fn openlist "void *(*malloc)(size_t)" "void (*free)(void *)" \
"size_t nodelen" "size_t pagesize" "long maxpages"
.Ft list *
.Fn blocklist "void *(*malloc)(size_t)" "void (*free)(void *)" \
"size_t nodelen" "long nodes"
.Ft list *
.Fn closelist "list *list"
.Ft node *
.Fn allocnode "list *list" "bool zero"
.Ft node *
.Fn freenode "node *node"
.Ft void
.Fn APPENDNODE "list *list" "node *node"
.Ft void
.Fn INSERTNODE "list *list" "node *node"
.Ft void
.Fn INSERTNODEAT "list *list" "node *atnode" "node *node"
.Ft void
.Fn SWAPNODE "list *dest" "list *source" "node *node" "bool insert"
.Ft void
.Fn UNLINKNODE "list *list" "node *node"
.Sh DESCRIPTION
This library provides a useful set of functions to manipulate doubly linked
lists. We also optionally allow pre-buffering node pools allowing to very
efficiently allocate/free nodes for a particular list.
All nodes in a pool are
.Ar long
word aligned and are thus suitable for
.Ar long *
referencing. The pools ensure to minimize calls to the supplied allocation
functions (such as
.Xr malloc 3
and
.Xr free 3 ) ,
preparing buffered pages. Even those pages are buffered as required and
statistics are maintained to monitor average current usage so that the
number of pre-buffered pages for a pool remain available even when most
nodes have been freed back. An application can then alternate size properly
in a very fast manner using these pools. Of course the statistics are updated
which will also allow those buffered pages to really be freed back when
it is noticeable that the pool does not grow large again for some while.
.Pp
The following structures and fields of interest which are left for the user
to reference are described below (only fields of user interest are shown),
declared in
.Aq Pa mmfd.h
.Bd -literal -offset indent
typedef struct node {
    struct node *prev, *next;
} node;

typedef struct list {
    struct node *top, *bottom;
    long nodes;
} list;
.Ed
.Pp
A custom node has to be declared as a structure using the node structure as
it's first field, as in the following:
.Bd -literal -offset indent
struct mynode {
    node nod;
    int i;
    /*...other custom fields...*/
};
.Ed
.Pp
.Fn INITLIST
initializes a
.Nm list
object in such a way that it can be used to store nodes. This does not
setup any memory pool and thus
.Fn allocnode
and
.Fn freenode
will not work with this type of list.
.Pp
.Fn openlist
allocates required resources to create a list handle with a node pre-buffering
pool. The supplied
.Fa malloc
and
.Fa free
arguments can either be
.Fn malloc ,
.Fn free
respectively, but custom functions may also be provided.
.Fa nodelen
consists of sizeof(struct mynode) in the previous example and should be
the size of the node which may then later on be allocated using
.Fn allocnode
at will.
.Fa pagesize
specifies the smallest amount of memory, in bytes, which will be initially
prepared to be used as buffered nodes for
.Fn allocnode
calls.
.Fa maxpages
specifies the maximum number of
.Fa pagesize
bytes blocks that will be allocated for this pool/list.
.Fn allocnode
will no longer be able to allocate new nodes if this is reached. 0 may also
be specified for this option to specify that no limit is wanted. Using this
pool mechanism minimizes calls to
.Fn malloc
and optimizes things considerably. Typical
.Fa pagesize
values are 4096, 8192, 16384 or 65536 bytes. Any size may be used as long as
at least two nodes may fit in a page. Note that if no pool is wanted it often
can be useful to simply define a
.Fa list
object and clear it to zeros using
.Fn bzero ,
.Fn memset ,
or
.Fn mm_memclr .
The allocation functions will not be available, and such a list should not
be closed using
.Fn closelist ,
but it will be available to hold nodes.
.Pp
.Fn blocklist
also prepares a list handle to be used by other functions, but allocates in one
block the requested number of maximum nodes to be available for
.Fn allocnode
calls.
.Pp
.Fn closelist
calls the provided
.Fn free
function to free all resources allocated for the specified
.Fa list *
handle. Any
.Fn allocnode
allocated memory is also freed. You should be sure to not have to reference
or use anymore any node that has been allocated for this list using
.Fn allocnode
before calling this function. If needed, custom allocated nodes may be used
instead of pre-buffered ones, and unlinked from the list before it's freed
using
.Fn UNLINKNODE
function, so they then remain useable by other lists.
.Pp
.Fn allocnode
attempts to allocate a pre-buffered node from the pool reserved to the
specified
.Fa list *
and optionally zeros allocated memory like
.Fn calloc
would if
.Fa zero
is TRUE. If required a new page of pre-buffered nodes will be allocated
and prepared, if within allowed page limits, to make other nodes available
for allocation. If the list was created using
.Fn blocklist
function, only a single page is available allowing to allocate the maximum
number of nodes that was specified.
.Pp
.Fn freenode
restores specified
.Fa node *
to the list pool
.Fn allocnode
allocated node from, making it available for re-allocating later. Of course
if all nodes of a particular page have been freed, the page is internally
released into a pool, and eventually back to the system if it is not recycled
soon enough. If the list was created using
.Fn blocklist
function, the buffer will never shrink as it handles a fixed amount of nodes
to be available for allocation.
.Pp
.Fn APPENDNODE
links node pointed to by
.Fa node
after all elements in list specified by
.Fa list
.Pp
.Fn INSERTNODE
links node
.Fa node
before all elements of list
.Fa list
.Pp
.Fn INSERTNODEAT
links node
.Fa node
before node
.Fa atnode
into
.Fa list
.Pp
.Fn SWAPNODE
unlinks node
.Fa node
from
.Fa source
, and appends or inserts it into list
.Fa dest
depending on weither
.Fa insert
is TRUE or FALSE.
.Pp
.Fn UNLINKNODE
unlinks node
.Fa node
from
.Fa list
but does not free the node in any way.
.Sh RETURN VALUES
.Fn openlist
and
.Fn blocklist
return a
.Fa list *
or NULL pointer on error (out of memory).
.Pp
.Fn closelist
always returns a NULL pointer of type
.Fa list *
.Pp
.Fn allocnode
returns a
.Fa node *
or NULL on error (no more memory allowed for this pool, or out of memory).
.Pp
.Fn freenode
always returns a NULL pointer of type
.Fa node *
.Pp
.Fn INITLIST ,
.Fn APPENDNODE ,
.Fn INSERTNODE ,
.Fn INSERTNODEAT ,
.Fn SWAPNODE
and
.Fn UNLINKNODE
don't return anything.
.Sh SEE ALSO
.Xr malloc 3 ,
.Xr free 3
.Sh STANDARDS
None
.Sh HISTORY
mmlist was originally developped on NetBSD 1.5 for the Xisop portable kernel
project from Matthew Mondor, then imported to be used by mmserver, mmftpd and
mmmail daemons.
.Sh AUTHORS
The mmlist library was written by Matthew Mondor and is
Copyright (c) 2001-2003, Matthew Mondor, All rights reserved.
.Sh BUGS
Please report any bug to [e-mail]