home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Usenet 1994 October
/
usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso
/
unix
/
volume27
/
queue
/
part01
next >
Wrap
Text File
|
1993-12-21
|
64KB
|
1,548 lines
Newsgroups: comp.sources.unix
From: bostic@cs.berkeley.edu (Keith Bostic)
Subject: v27i173: queue - implementations of lists, tail queues, and circular queues, Part01/01
Message-id: <1.756504644.8164@gw.home.vix.com>
Sender: unix-sources-moderator@gw.home.vix.com
Approved: vixie@gw.home.vix.com
Submitted-By: bostic@cs.berkeley.edu (Keith Bostic)
Posting-Number: Volume 27, Issue 173
Archive-Name: queue/part01
Here's the final versions of the queue stuff that we talked
about. Paul, consider it a submission for unix.sources, if
you like.
--keith
[ from the manpage...
DESCRIPTION
These macros define and operate on three types of data structures: lists,
tail queues, and circular queues. All three structures support the fol-
lowing functionality:
1. Insertion of a new entry at the head of the list.
2. Insertion of a new entry after any element in the list.
3. Removal of any entry in the list.
4. Forward traversal through the list.
--vix ]
# This is a shell archive. Save it in a file, remove anything before
# this line, and then unpack it by entering "sh file". Note, it may
# create directories; files and directories will be owned by you and
# have default permissions.
#
# This archive contains:
#
# queue.0
# queue.0.ps
# queue.3
# queue.h
#
echo x - queue.0
sed 's/^X//' >queue.0 << 'END-of-queue.0'
XQUEUE(3) BSD Programmer's Manual QUEUE(3)
X
XNNAAMMEE
X LLIISSTT__EENNTTRRYY, LLIISSTT__HHEEAADD, LLIISSTT__IINNIITT, LLIISSTT__IINNSSEERRTT__AAFFTTEERR, LLIISSTT__IINNSSEERRTT__HHEEAADD,
X LLIISSTT__RREEMMOOVVEE, TTAAIILLQQ__EENNTTRRYY, TTAAIILLQQ__HHEEAADD, TTAAIILLQQ__IINNIITT, TTAAIILLQQ__IINNSSEERRTT__AAFFTTEERR,
X TTAAIILLQQ__IINNSSEERRTT__HHEEAADD, TTAAIILLQQ__IINNSSEERRTT__TTAAIILL, TTAAIILLQQ__RREEMMOOVVEE, CCIIRRCCLLEEQQ__EENNTTRRYY,
X CCIIRRCCLLEEQQ__HHEEAADD, CCIIRRCCLLEEQQ__IINNIITT, CCIIRRCCLLEEQQ__IINNSSEERRTT__AAFFTTEERR, CCIIRRCCLLEEQQ__IINNSSEERRTT__BBEEFFOORREE,
X CCIIRRCCLLEEQQ__IINNSSEERRTT__HHEEAADD, CCIIRRCCLLEEQQ__IINNSSEERRTT__TTAAIILL, CCIIRRCCLLEEQQ__RREEMMOOVVEE - implementa-
X tions of lists, tail queues, and circular queues
X
XSSYYNNOOPPSSIISS
X ##iinncclluuddee <<ssyyss//qquueeuuee..hh>>
X
X
X LLIISSTT__EENNTTRRYY(_T_Y_P_E);
X
X LLIISSTT__HHEEAADD(_H_E_A_D_N_A_M_E, _T_Y_P_E);
X
X LLIISSTT__IINNIITT(_L_I_S_T___H_E_A_D _*_h_e_a_d);
X
X LLIISSTT__IINNSSEERRTT__AAFFTTEERR(_L_I_S_T___E_N_T_R_Y _*_l_i_s_t_e_l_m, _T_Y_P_E _*_e_l_m, _L_I_S_T___E_N_T_R_Y _N_A_M_E);
X
X LLIISSTT__IINNSSEERRTT__HHEEAADD(_L_I_S_T___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _L_I_S_T___E_N_T_R_Y _N_A_M_E);
X
X LLIISSTT__RREEMMOOVVEE(_T_Y_P_E _*_e_l_m, _L_I_S_T___E_N_T_R_Y _N_A_M_E);
X
X
X TTAAIILLQQ__EENNTTRRYY(_T_Y_P_E);
X
X TTAAIILLQQ__HHEEAADD(_H_E_A_D_N_A_M_E, _T_Y_P_E);
X
X TTAAIILLQQ__IINNIITT(_T_A_I_L_Q___H_E_A_D _*_h_e_a_d);
X
X TTAAIILLQQ__IINNSSEERRTT__AAFFTTEERR(_T_A_I_L_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_l_i_s_t_e_l_m, _T_Y_P_E _*_e_l_m,
X _T_A_I_L_Q___E_N_T_R_Y _N_A_M_E);
X
X TTAAIILLQQ__IINNSSEERRTT__HHEEAADD(_T_A_I_L_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _T_A_I_L_Q___E_N_T_R_Y _N_A_M_E);
X
X TTAAIILLQQ__IINNSSEERRTT__TTAAIILL(_T_A_I_L_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _T_A_I_L_Q___E_N_T_R_Y _N_A_M_E);
X
X TTAAIILLQQ__RREEMMOOVVEE(_T_A_I_L_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _T_A_I_L_Q___E_N_T_R_Y _N_A_M_E);
X
X
X CCIIRRCCLLEEQQ__EENNTTRRYY(_T_Y_P_E);
X
X CCIIRRCCLLEEQQ__HHEEAADD(_H_E_A_D_N_A_M_E, _T_Y_P_E);
X
X CCIIRRCCLLEEQQ__IINNIITT(_C_I_R_C_L_E_Q___H_E_A_D _*_h_e_a_d);
X
X CCIIRRCCLLEEQQ__IINNSSEERRTT__AAFFTTEERR(_C_I_R_C_L_E_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_l_i_s_t_e_l_m, _T_Y_P_E _*_e_l_m,
X _C_I_R_C_L_E_Q___E_N_T_R_Y _N_A_M_E);
X
X CCIIRRCCLLEEQQ__IINNSSEERRTT__BBEEFFOORREE(_C_I_R_C_L_E_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_l_i_s_t_e_l_m, _T_Y_P_E _*_e_l_m,
X _C_I_R_C_L_E_Q___E_N_T_R_Y _N_A_M_E);
X
X CCIIRRCCLLEEQQ__IINNSSEERRTT__HHEEAADD(_C_I_R_C_L_E_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _C_I_R_C_L_E_Q___E_N_T_R_Y _N_A_M_E);
X
X CCIIRRCCLLEEQQ__IINNSSEERRTT__TTAAIILL(_C_I_R_C_L_E_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _C_I_R_C_L_E_Q___E_N_T_R_Y _N_A_M_E);
X
X CCIIRRCCLLEEQQ__RREEMMOOVVEE(_C_I_R_C_L_E_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _C_I_R_C_L_E_Q___E_N_T_R_Y _N_A_M_E);
X
XDDEESSCCRRIIPPTTIIOONN
X These macros define and operate on three types of data structures: lists,
X tail queues, and circular queues. All three structures support the fol-
X
X lowing functionality:
X 1. Insertion of a new entry at the head of the list.
X 2. Insertion of a new entry after any element in the list.
X 3. Removal of any entry in the list.
X 4. Forward traversal through the list.
X
X Lists are the simplest of the three data structures and support only the
X above functionality.
X
X Tail queues add the following functionality:
X 1. Entries can be added at the end of a list.
X However:
X 1. All list insertions and removals must specify the head of the
X list.
X 2. Each head entry requires two pointers rather than one.
X 3. Code size is about 15% greater and operations run about 20%
X slower than lists.
X
X Circular queues add the following functionality:
X 1. Entries can be added at the end of a list.
X 2. Entries can be added before another entry.
X 3. They may be traversed backwards, from tail to head.
X However:
X 1. All list insertions and removals must specify the head of the
X list.
X 2. Each head entry requires two pointers rather than one.
X 3. The termination condition for traversal is more complex.
X 4. Code size is about 40% greater and operations run about 45%
X slower than lists.
X
X In the macro definitions, _T_Y_P_E is the name of a user defined structure,
X that must contain a field of type LIST_ENTRY, TAILQ_ENTRY, or
X CIRCLEQ_ENTRY, named _N_A_M_E. The argument _H_E_A_D_N_A_M_E is the name of a user
X defined structure that must be declared using the macros LIST_HEAD,
X TAILQ_HEAD, or CIRCLEQ_HEAD. See the examples below for further explana-
X tion of how these macros are used.
X
XLLIISSTTSS
X A list is headed by a structure defined by the LLIISSTT__HHEEAADD macro. This
X structure contains a single pointer to the first element on the list.
X The elements are doubly linked so that an arbitrary element can be re-
X moved without traversing the list. New elements can be added to the list
X after an existing element or at the head of the list. A _L_I_S_T___H_E_A_D struc-
X ture is declared as follows:
X
X LIST_HEAD(HEADNAME, TYPE) head;
X
X where _H_E_A_D_N_A_M_E is the name of the structure to be defined, and _T_Y_P_E is
X the type of the elements to be linked into the list. A pointer to the
X head of the list can later be declared as:
X
X struct HEADNAME *headp;
X
X (The names head and headp are user selectable.)
X
X The macro LLIISSTT__EENNTTRRYY declares a structure that connects the elements in
X the list.
X
X The macro LLIISSTT__IINNIITT initializes the list referenced by _h_e_a_d.
X
X The macro LLIISSTT__IINNSSEERRTT__HHEEAADD inserts the new element _e_l_m at the head of the
X list.
X
X The macro LLIISSTT__IINNSSEERRTT__AAFFTTEERR inserts the new element _e_l_m after the element
X _l_i_s_t_e_l_m.
X
X
X The macro LLIISSTT__RREEMMOOVVEE removes the element _e_l_m from the list.
X
XLLIISSTT EEXXAAMMPPLLEE
X LIST_HEAD(listhead, entry) head;
X struct listhead *headp; /* List head. */
X struct entry {
X ...
X LIST_ENTRY(entry) entries; /* List. */
X ...
X } *n1, *n2, *np;
X
X LIST_INIT(&head); /* Initialize the list. */
X
X n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
X LIST_INSERT_HEAD(&head, n1, entries);
X
X n2 = malloc(sizeof(struct entry)); /* Insert after. */
X LIST_INSERT_AFTER(n1, n2, entries);
X /* Forward traversal. */
X for (np = head.lh_first; np != NULL; np = np->entries.le_next)
X np-> ...
X
X while (head.lh_first != NULL) /* Delete. */
X LIST_REMOVE(head.lh_first, entries);
X
XTTAAIILL QQUUEEUUEESS
X A tail queue is headed by a structure defined by the TTAAIILLQQ__HHEEAADD macro.
X This structure contains a pair of pointers, one to the first element in
X the tail queue and the other to the last element in the tail queue. The
X elements are doubly linked so that an arbitrary element can be removed
X without traversing the tail queue. New elements can be added to the tail
X queue after an existing element, at the head of the tail queue, or at the
X end of the tail queue. A _T_A_I_L_Q___H_E_A_D structure is declared as follows:
X
X TAILQ_HEAD(HEADNAME, TYPE) head;
X
X where HEADNAME is the name of the structure to be defined, and TYPE is
X the type of the elements to be linked into the tail queue. A pointer to
X the head of the tail queue can later be declared as:
X
X struct HEADNAME *headp;
X
X (The names head and headp are user selectable.)
X
X The macro TTAAIILLQQ__EENNTTRRYY declares a structure that connects the elements in
X the tail queue.
X
X The macro TTAAIILLQQ__IINNIITT initializes the tail queue referenced by _h_e_a_d.
X
X The macro TTAAIILLQQ__IINNSSEERRTT__HHEEAADD inserts the new element _e_l_m at the head of
X the tail queue.
X
X The macro TTAAIILLQQ__IINNSSEERRTT__TTAAIILL inserts the new element _e_l_m at the end of the
X tail queue.
X
X The macro TTAAIILLQQ__IINNSSEERRTT__AAFFTTEERR inserts the new element _e_l_m after the ele-
X ment _l_i_s_t_e_l_m.
X
X The macro TTAAIILLQQ__RREEMMOOVVEE removes the element _e_l_m from the tail queue.
X
XTTAAIILL QQUUEEUUEE EEXXAAMMPPLLEE
X TAILQ_HEAD(tailhead, entry) head;
X struct tailhead *headp; /* Tail queue head. */
X struct entry {
X ...
X TAILQ_ENTRY(entry) entries; /* Tail queue. */
X ...
X } *n1, *n2, *np;
X
X TAILQ_INIT(&head); /* Initialize the queue. */
X
X n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
X TAILQ_INSERT_HEAD(&head, n1, entries);
X
X n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
X TAILQ_INSERT_TAIL(&head, n1, entries);
X
X n2 = malloc(sizeof(struct entry)); /* Insert after. */
X TAILQ_INSERT_AFTER(&head, n1, n2, entries);
X /* Forward traversal. */
X for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next)
X np-> ...
X /* Delete. */
X while (head.tqh_first != NULL)
X TAILQ_REMOVE(&head, head.tqh_first, entries);
X
XCCIIRRCCUULLAARR QQUUEEUUEESS
X A circular queue is headed by a structure defined by the CCIIRRCCLLEEQQ__HHEEAADD
X macro. This structure contains a pair of pointers, one to the first ele-
X ment in the circular queue and the other to the last element in the cir-
X cular queue. The elements are doubly linked so that an arbitrary element
X can be removed without traversing the queue. New elements can be added
X to the queue after an existing element, before an existing element, at
X the head of the queue, or at the end of the queue. A _C_I_R_C_L_E_Q___H_E_A_D struc-
X ture is declared as follows:
X
X CIRCLEQ_HEAD(HEADNAME, TYPE) head;
X
X where HEADNAME is the name of the structure to be defined, and TYPE is
X the type of the elements to be linked into the circular queue. A pointer
X to the head of the circular queue can later be declared as:
X
X struct HEADNAME *headp;
X
X (The names head and headp are user selectable.)
X
X The macro CCIIRRCCLLEEQQ__EENNTTRRYY declares a structure that connects the elements
X in the circular queue.
X
X The macro CCIIRRCCLLEEQQ__IINNIITT initializes the circular queue referenced by _h_e_a_d.
X
X The macro CCIIRRCCLLEEQQ__IINNSSEERRTT__HHEEAADD inserts the new element _e_l_m at the head of
X the circular queue.
X
X The macro CCIIRRCCLLEEQQ__IINNSSEERRTT__TTAAIILL inserts the new element _e_l_m at the end of
X the circular queue.
X
X The macro CCIIRRCCLLEEQQ__IINNSSEERRTT__AAFFTTEERR inserts the new element _e_l_m after the ele-
X ment _l_i_s_t_e_l_m.
X
X The macro CCIIRRCCLLEEQQ__IINNSSEERRTT__BBEEFFOORREE inserts the new element _e_l_m before the
X element _l_i_s_t_e_l_m.
X
X The macro CCIIRRCCLLEEQQ__RREEMMOOVVEE removes the element _e_l_m from the circular queue.
X
XCCIIRRCCUULLAARR QQUUEEUUEE EEXXAAMMPPLLEE
X CIRCLEQ_HEAD(circleq, entry) head;
X struct circleq *headp; /* Circular queue head. */
X struct entry {
X ...
X CIRCLEQ_ENTRY entries; /* Circular queue. */
X ...
X } *n1, *n2, *np;
X
X CIRCLEQ_INIT(&head); /* Initialize the circular queue. */
X
X n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
X CIRCLEQ_INSERT_HEAD(&head, n1, entries);
X
X n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
X CIRCLEQ_INSERT_TAIL(&head, n1, entries);
X
X n2 = malloc(sizeof(struct entry)); /* Insert after. */
X CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
X
X n2 = malloc(sizeof(struct entry)); /* Insert before. */
X CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
X /* Forward traversal. */
X for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next)
X np-> ...
X /* Reverse traversal. */
X for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
X np-> ...
X /* Delete. */
X while (head.cqh_first != (void *)&head)
X CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
X
XHHIISSTTOORRYY
X The qquueeuuee functions first appeared in 4.4BSD.
X
X4th Berkeley Distribution December 13, 1993 5
END-of-queue.0
echo x - queue.0.ps
sed 's/^X//' >queue.0.ps << 'END-of-queue.0.ps'
X%!PS-Adobe-3.0
X%%Creator: groff version 1.08
X%%DocumentNeededResources: font Times-Roman
X%%+ font Times-Bold
X%%+ font Courier-Bold
X%%+ font Courier-Oblique
X%%+ font Symbol
X%%+ font Courier
X%%DocumentSuppliedResources: procset grops 1.08 0
X%%Pages: 5
X%%PageOrder: Ascend
X%%Orientation: Portrait
X%%EndComments
X%%BeginProlog
X%%BeginResource: procset grops 1.08 0
X/setpacking where{
Xpop
Xcurrentpacking
Xtrue setpacking
X}if
X/grops 120 dict dup begin
X/SC 32 def
X/A/show load def
X/B{0 SC 3 -1 roll widthshow}bind def
X/C{0 exch ashow}bind def
X/D{0 exch 0 SC 5 2 roll awidthshow}bind def
X/E{0 rmoveto show}bind def
X/F{0 rmoveto 0 SC 3 -1 roll widthshow}bind def
X/G{0 rmoveto 0 exch ashow}bind def
X/H{0 rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
X/I{0 exch rmoveto show}bind def
X/J{0 exch rmoveto 0 SC 3 -1 roll widthshow}bind def
X/K{0 exch rmoveto 0 exch ashow}bind def
X/L{0 exch rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
X/M{rmoveto show}bind def
X/N{rmoveto 0 SC 3 -1 roll widthshow}bind def
X/O{rmoveto 0 exch ashow}bind def
X/P{rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
X/Q{moveto show}bind def
X/R{moveto 0 SC 3 -1 roll widthshow}bind def
X/S{moveto 0 exch ashow}bind def
X/T{moveto 0 exch 0 SC 5 2 roll awidthshow}bind def
X/SF{
Xfindfont exch
X[exch dup 0 exch 0 exch neg 0 0]makefont
Xdup setfont
X[exch/setfont cvx]cvx bind def
X}bind def
X/MF{
Xfindfont
X[5 2 roll
X0 3 1 roll
Xneg 0 0]makefont
Xdup setfont
X[exch/setfont cvx]cvx bind def
X}bind def
X/level0 0 def
X/RES 0 def
X/PL 0 def
X/LS 0 def
X/PLG{
Xgsave newpath clippath pathbbox grestore
Xexch pop add exch pop
X}bind def
X/BP{
X/level0 save def
X1 setlinecap
X1 setlinejoin
X72 RES div dup scale
XLS{
X90 rotate
X}{
X0 PL translate
X}ifelse
X1 -1 scale
X}bind def
X/EP{
Xlevel0 restore
Xshowpage
X}bind def
X/DA{
Xnewpath arcn stroke
X}bind def
X/SN{
Xtransform
X.25 sub exch .25 sub exch
Xround .25 add exch round .25 add exch
Xitransform
X}bind def
X/DL{
XSN
Xmoveto
XSN
Xlineto stroke
X}bind def
X/DC{
Xnewpath 0 360 arc closepath
X}bind def
X/TM matrix def
X/DE{
XTM currentmatrix pop
Xtranslate scale newpath 0 0 .5 0 360 arc closepath
XTM setmatrix
X}bind def
X/RC/rcurveto load def
X/RL/rlineto load def
X/ST/stroke load def
X/MT/moveto load def
X/CL/closepath load def
X/FL{
Xcurrentgray exch setgray fill setgray
X}bind def
X/BL/fill load def
X/LW/setlinewidth load def
X/RE{
Xfindfont
Xdup maxlength 1 index/FontName known not{1 add}if dict begin
X{
X1 index/FID ne{def}{pop pop}ifelse
X}forall
X/Encoding exch def
Xdup/FontName exch def
Xcurrentdict end definefont pop
X}bind def
X/DEFS 0 def
X/EBEGIN{
Xmoveto
XDEFS begin
X}bind def
X/EEND/end load def
X/CNT 0 def
X/level1 0 def
X/PBEGIN{
X/level1 save def
Xtranslate
Xdiv 3 1 roll div exch scale
Xneg exch neg exch translate
X0 setgray
X0 setlinecap
X1 setlinewidth
X0 setlinejoin
X10 setmiterlimit
X[]0 setdash
X/setstrokeadjust where{
Xpop
Xfalse setstrokeadjust
X}if
X/setoverprint where{
Xpop
Xfalse setoverprint
X}if
Xnewpath
X/CNT countdictstack def
Xuserdict begin
X/showpage{}def
X}bind def
X/PEND{
Xclear
Xcountdictstack CNT sub{end}repeat
Xlevel1 restore
X}bind def
Xend def
X/setpacking where{
Xpop
Xsetpacking
X}if
X%%EndResource
X%%IncludeResource: font Times-Roman
X%%IncludeResource: font Times-Bold
X%%IncludeResource: font Courier-Bold
X%%IncludeResource: font Courier-Oblique
X%%IncludeResource: font Symbol
X%%IncludeResource: font Courier
Xgrops begin/DEFS 1 dict def DEFS begin/u{.001 mul}bind def end/RES 72 def/PL
X792 def/LS false def/ENC0[/asciicircum/asciitilde/Scaron/Zcaron/scaron/zcaron
X/Ydieresis/trademark/quotesingle/.notdef/.notdef/.notdef/.notdef/.notdef
X/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
X/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/space
X/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright/parenleft
X/parenright/asterisk/plus/comma/hyphen/period/slash/zero/one/two/three/four
X/five/six/seven/eight/nine/colon/semicolon/less/equal/greater/question/at/A/B/C
X/D/E/F/G/H/I/J/K/L/M/N/O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash
X/bracketright/circumflex/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q
X/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/tilde/.notdef/quotesinglbase
X/guillemotleft/guillemotright/bullet/florin/fraction/perthousand/dagger
X/daggerdbl/endash/emdash/ff/fi/fl/ffi/ffl/dotlessi/dotlessj/grave/hungarumlaut
X/dotaccent/breve/caron/ring/ogonek/quotedblleft/quotedblright/oe/lslash
X/quotedblbase/OE/Lslash/.notdef/exclamdown/cent/sterling/currency/yen/brokenbar
X/section/dieresis/copyright/ordfeminine/guilsinglleft/logicalnot/minus
X/registered/macron/degree/plusminus/twosuperior/threesuperior/acute/mu
X/paragraph/periodcentered/cedilla/onesuperior/ordmasculine/guilsinglright
X/onequarter/onehalf/threequarters/questiondown/Agrave/Aacute/Acircumflex/Atilde
X/Adieresis/Aring/AE/Ccedilla/Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute
X/Icircumflex/Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis
X/multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute/Thorn/germandbls
X/agrave/aacute/acircumflex/atilde/adieresis/aring/ae/ccedilla/egrave/eacute
X/ecircumflex/edieresis/igrave/iacute/icircumflex/idieresis/eth/ntilde/ograve
X/oacute/ocircumflex/otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex
X/udieresis/yacute/thorn/ydieresis]def/Courier@0 ENC0/Courier RE
X/Courier-Oblique@0 ENC0/Courier-Oblique RE/Courier-Bold@0 ENC0/Courier-Bold RE
X/Times-Bold@0 ENC0/Times-Bold RE/Times-Roman@0 ENC0/Times-Roman RE
X%%EndProlog
X%%Page: 1 1
X%%BeginPageSetup
XBP
X%%EndPageSetup
X/F0 10/Times-Roman@0 SF -.1(QU)72 48 S -.834(EUE \( 3 \)).1 F(BSD Programmer')
X250.17 48 Q 2.5(sM)-.55 G 125.232(anual Q)340.17 48 R -.834(UEUE \( 3 \))-.1 F
X/F1 10/Times-Bold@0 SF -.2(NA)72 108 S(ME).2 E/F2 10/Courier-Bold@0 SF
X(LIST_ENTRY)102 120 Q F0(,)A F2(LIST_HEAD)179.375 120 Q F0(,)A F2(LIST_INIT)
X250.75 120 Q F0(,)A F2(LIST_INSERT_AFTER)322.125 120 Q F0(,)A F2
X(LIST_INSERT_HEAD)441.5 120 Q F0(,)A F2(LIST_REMOVE)102 132 Q F0(,)A F2
X(TAILQ_ENTRY)186.875 132 Q F0(,)A F2(TAILQ_HEAD)271.75 132 Q F0(,)A F2
X(TAILQ_INIT)350.625 132 Q F0(,)A F2(TAILQ_INSERT_AFTER)429.5 132 Q F0(,)A F2
X(TAILQ_INSERT_HEAD)102 144 Q F0(,)A F2(TAILQ_INSERT_TAIL)231.167 144 Q F0(,)A
XF2(TAILQ_REMOVE)360.334 144 Q F0(,)A F2(CIRCLEQ_ENTRY)459.5 144 Q F0(,)A F2
X(CIRCLEQ_HEAD)102 156 Q F0(,)A F2(CIRCLEQ_INIT)189.166 156 Q F0(,)A F2
X(CIRCLEQ_INSERT_AFTER)276.333 156 Q F0(,)A F2(CIRCLEQ_INSERT_BEFORE)411.5 156 Q
XF0(,)A F2(CIRCLEQ_INSERT_HEAD)102 168 Q F0(,)A F2(CIRCLEQ_INSERT_TAIL)3.624 E
XF0(,)A F2(CIRCLEQ_REMOVE)3.624 E F0 3.623<ad69>3.623 G 1.123
X(mplementations of lists,)441.914 168 R(tail queues, and circular queues)102
X180 Q F1(SYNOPSIS)72 204 Q F2(#include <sys/queue.h>)102 216 Q(LIST_ENTRY)102
X246 Q F0(\()A/F3 10/Courier-Oblique@0 SF(TYPE)A F0(\);)A F2(LIST_HEAD)102 264 Q
XF0(\()A F3(HEADNAME)A F0(,)1.666 E F3(TYPE)4.166 E F0(\);)A F2(LIST_INIT)102
X282 Q F0(\()A F3(LIST_HEAD)A/F4 10/Symbol SF(*)6 E F3(head)A F0(\);)A F2
X(LIST_INSERT_AFTER)102 300 Q F0(\()A F3(LIST_ENTRY)A F4(*)6 E F3(listelm)A F0
X(,)1.666 E F3(TYPE)4.166 E F4(*)6 E F3(elm)A F0(,)1.666 E F3(LIST_ENTRY NAME)
X4.166 E F0(\);)A F2(LIST_INSERT_HEAD)102 318 Q F0(\()A F3(LIST_HEAD)A F4(*)6 E
XF3(head)A F0(,)1.666 E F3(TYPE)4.166 E F4(*)6 E F3(elm)A F0(,)1.666 E F3
X(LIST_ENTRY NAME)4.166 E F0(\);)A F2(LIST_REMOVE)102 336 Q F0(\()A F3(TYPE)A F4
X(*)6 E F3(elm)A F0(,)1.666 E F3(LIST_ENTRY NAME)4.166 E F0(\);)A F2
X(TAILQ_ENTRY)102 366 Q F0(\()A F3(TYPE)A F0(\);)A F2(TAILQ_HEAD)102 384 Q F0
X(\()A F3(HEADNAME)A F0(,)1.666 E F3(TYPE)4.166 E F0(\);)A F2(TAILQ_INIT)102 402
XQ F0(\()A F3(TAILQ_HEAD)A F4(*)6 E F3(head)A F0(\);)A F2(TAILQ_INSERT_AFTER)102
X420 Q F0(\()A F3(TAILQ_HEAD)A F4(*)6 E F3(head)A F0(,)1.666 E F3(TYPE)4.166 E
XF4(*)6 E F3(listelm)A F0(,)1.666 E F3(TYPE)4.166 E F4(*)6 E F3(elm)A F0(,)1.666
XE F3(TAILQ_ENTRY NAME)151.666 432 Q F0(\);)A F2(TAILQ_INSERT_HEAD)102 450 Q F0
X(\()A F3(TAILQ_HEAD)A F4(*)6 E F3(head)A F0(,)1.666 E F3(TYPE)4.166 E F4(*)6 E
XF3(elm)A F0(,)1.666 E F3(TAILQ_ENTRY NAME)4.166 E F0(\);)A F2
X(TAILQ_INSERT_TAIL)102 468 Q F0(\()A F3(TAILQ_HEAD)A F4(*)6 E F3(head)A F0(,)
X1.666 E F3(TYPE)4.166 E F4(*)6 E F3(elm)A F0(,)1.666 E F3(TAILQ_ENTRY NAME)
X4.166 E F0(\);)A F2(TAILQ_REMOVE)102 486 Q F0(\()A F3(TAILQ_HEAD)A F4(*)6 E F3
X(head)A F0(,)1.666 E F3(TYPE)4.166 E F4(*)6 E F3(elm)A F0(,)1.666 E F3
X(TAILQ_ENTRY NAME)4.166 E F0(\);)A F2(CIRCLEQ_ENTRY)102 516 Q F0(\()A F3(TYPE)A
XF0(\);)A F2(CIRCLEQ_HEAD)102 534 Q F0(\()A F3(HEADNAME)A F0(,)1.666 E F3(TYPE)
X4.166 E F0(\);)A F2(CIRCLEQ_INIT)102 552 Q F0(\()A F3(CIRCLEQ_HEAD)A F4(*)6 E
XF3(head)A F0(\);)A F2(CIRCLEQ_INSERT_AFTER)102 570 Q F0(\()A F3(CIRCLEQ_HEAD)A
XF4(*)6 E F3(head)A F0(,)1.666 E F3(TYPE)4.166 E F4(*)6 E F3(listelm)A F0(,)
X1.666 E F3(TYPE)4.166 E F4(*)6 E F3(elm)A F0(,)1.666 E F3(CIRCLEQ_ENTRY NAME)
X151.666 582 Q F0(\);)A F2(CIRCLEQ_INSERT_BEFORE)102 600 Q F0(\()A F3
X(CIRCLEQ_HEAD)A F4(*)6 E F3(head)A F0(,)1.666 E F3(TYPE)4.166 E F4(*)6 E F3
X(listelm)A F0(,)1.666 E F3(TYPE)4.166 E F4(*)6 E F3(elm)A F0(,)1.666 E F3
X(CIRCLEQ_ENTRY NAME)151.666 612 Q F0(\);)A F2(CIRCLEQ_INSERT_HEAD)102 630 Q F0
X(\()A F3(CIRCLEQ_HEAD)A F4(*)6 E F3(head)A F0(,)1.666 E F3(TYPE)4.166 E F4(*)6
XE F3(elm)A F0(,)1.666 E F3(CIRCLEQ_ENTRY NAME)4.166 E F0(\);)A F2
X(CIRCLEQ_INSERT_TAIL)102 648 Q F0(\()A F3(CIRCLEQ_HEAD)A F4(*)6 E F3(head)A F0
X(,)1.666 E F3(TYPE)4.166 E F4(*)6 E F3(elm)A F0(,)1.666 E F3
X(CIRCLEQ_ENTRY NAME)4.166 E F0(\);)A F2(CIRCLEQ_REMOVE)102 666 Q F0(\()A F3
X(CIRCLEQ_HEAD)A F4(*)6 E F3(head)A F0(,)1.666 E F3(TYPE)4.166 E F4(*)6 E F3
X(elm)A F0(,)1.666 E F3(CIRCLEQ_ENTRY NAME)4.166 E F0(\);)A(4th Berk)72 750 Q
X(ele)-.1 E 2.5(yD)-.15 G(istrib)132.85 750 Q 90.435(ution December)-.2 F
X(13, 1993)2.5 E(1)535 750 Q EP
X%%Page: 2 2
X%%BeginPageSetup
XBP
X%%EndPageSetup
X/F0 10/Times-Roman@0 SF -.1(QU)72 48 S -.834(EUE \( 3 \)).1 F(BSD Programmer')
X250.17 48 Q 2.5(sM)-.55 G 125.232(anual Q)340.17 48 R -.834(UEUE \( 3 \))-.1 F
X/F1 10/Times-Bold@0 SF(DESCRIPTION)72 96 Q F0 .264(These macros de\214ne and o\
Xperate on three types of data structures: lists, tail queues, and circular que\
Xues.)102 108 R(All)5.263 E(three structures support the follo)102 120 Q
X(wing functionality:)-.25 E 10(1. Insertion)132 132 R(of a ne)2.5 E 2.5(we)-.25
XG(ntry at the head of the list.)231.17 132 Q 10(2. Insertion)132 144 R(of a ne)
X2.5 E 2.5(we)-.25 G(ntry after an)231.17 144 Q 2.5(ye)-.15 G
X(lement in the list.)291.83 144 Q 10(3. Remo)132 156 R -.25(va)-.15 G 2.5(lo)
X.25 G 2.5(fa)195.21 156 S .3 -.15(ny e)205.48 156 T(ntry in the list.).15 E 10
X(4. F)132 168 R(orw)-.15 E(ard tra)-.1 E -.15(ve)-.2 G(rsal through the list.)
X.15 E
X(Lists are the simplest of the three data structures and support only the abo)
X102 186 Q .3 -.15(ve f)-.15 H(unctionality).15 E(.)-.65 E -.8(Ta)102 204 S
X(il queues add the follo).8 E(wing functionality:)-.25 E 10(1. Entries)132 216
XR(can be added at the end of a list.)2.5 E(Ho)102 228 Q(we)-.25 E -.15(ve)-.25
XG(r:).15 E 10(1. All)132 240 R(list insertions and remo)2.5 E -.25(va)-.15 G
X(ls must specify the head of the list.).25 E 10(2. Each)132 252 R
X(head entry requires tw)2.5 E 2.5(op)-.1 G(ointers rather than one.)276.03 252
XQ 10(3. Code)132 264 R
X(size is about 15% greater and operations run about 20% slo)2.5 E
X(wer than lists.)-.25 E(Circular queues add the follo)102 282 Q
X(wing functionality:)-.25 E 10(1. Entries)132 294 R
X(can be added at the end of a list.)2.5 E 10(2. Entries)132 306 R
X(can be added before another entry)2.5 E(.)-.65 E 10(3. The)132 318 R 2.5(ym)
X-.15 G(ay be tra)182.68 318 Q -.15(ve)-.2 G(rsed backw).15 E
X(ards, from tail to head.)-.1 E(Ho)102 330 Q(we)-.25 E -.15(ve)-.25 G(r:).15 E
X10(1. All)132 342 R(list insertions and remo)2.5 E -.25(va)-.15 G
X(ls must specify the head of the list.).25 E 10(2. Each)132 354 R
X(head entry requires tw)2.5 E 2.5(op)-.1 G(ointers rather than one.)276.03 354
XQ 10(3. The)132 366 R(termination condition for tra)2.5 E -.15(ve)-.2 G
X(rsal is more comple).15 E(x.)-.15 E 10(4. Code)132 378 R
X(size is about 40% greater and operations run about 45% slo)2.5 E
X(wer than lists.)-.25 E 1.455(In the macro de\214nitions,)102 396 R/F2 10
X/Courier-Oblique@0 SF(TYPE)3.955 E F0 1.456(is the name of a user de\214ned st\
Xructure, that must contain a \214eld of type)3.956 F/F3 10/Courier@0 SF
X(LIST_ENTRY)102 408 Q F0(,)A F3(TAILQ_ENTRY)4.498 E F0 4.498(,o)C(r)246.996 408
XQ F3(CIRCLEQ_ENTRY)4.498 E F0 4.498(,n)C(amed)344.822 408 Q F2(NAME)4.498 E F0
X4.498(.T)C 1.998(he ar)408.088 408 R(gument)-.18 E F2(HEADNAME)4.498 E F0 1.998
X(is the)4.498 F 1.141
X(name of a user de\214ned structure that must be declared using the macros)102
X420 R F3(LIST_HEAD)3.642 E F0(,)A F3(TAILQ_HEAD)3.642 E F0 3.642(,o)C(r)536.67
X420 Q F3(CIRCLEQ_HEAD)102 432 Q F0 2.5(.S)C(ee the e)184.56 432 Q(xamples belo)
X-.15 E 2.5(wf)-.25 G(or further e)280.8 432 Q(xplanation of ho)-.15 E 2.5(wt)
X-.25 G(hese macros are used.)403.43 432 Q F1(LISTS)72 456 Q F0 2.664(Al)102 468
XS .164(ist is headed by a structure de\214ned by the)114.664 468 R/F4 10
X/Courier-Bold@0 SF(LIST_HEAD)2.663 E F0 2.663(macro. This)2.663 F .163
X(structure contains a single pointer to)2.663 F 1.149
X(the \214rst element on the list.)102 480 R 1.149(The elements are doubly link)
X6.149 F 1.15(ed so that an arbitrary element can be remo)-.1 F -.15(ve)-.15 G
X(d).15 E .441(without tra)102 492 R -.15(ve)-.2 G .441(rsing the list.).15 F
X(Ne)5.441 E 2.941(we)-.25 G .441(lements can be added to the list after an e)
X239.425 492 R .441(xisting element or at the head of)-.15 F(the list.)102 504 Q
X(A)5 E F2(LIST_HEAD)2.5 E F0(structure is declared as follo)2.5 E(ws:)-.25 E F3
X(LIST_HEAD\(HEADNAME, TYPE\) head;)132 522 Q F0(where)102 546 Q F2(HEADNAME)
X3.622 E F0 1.122(is the name of the structure to be de\214ned, and)3.622 F F2
X(TYPE)3.623 E F0 1.123(is the type of the elements to be)3.623 F(link)102 558 Q
X(ed into the list.)-.1 E 2.5(Ap)5 G
X(ointer to the head of the list can later be declared as:)196.63 558 Q F3
X(struct HEADNAME)132 576 Q/F5 10/Symbol SF(*)6 E F3(headp;)A F0(\(The names)102
X600 Q F3(head)2.5 E F0(and)2.5 E F3(headp)2.5 E F0(are user selectable.\))2.5 E
X(The macro)102 618 Q F4(LIST_ENTRY)2.5 E F0
X(declares a structure that connects the elements in the list.)2.5 E(The macro)
X102 636 Q F4(LIST_INIT)2.5 E F0(initializes the list referenced by)2.5 E F2
X(head)2.5 E F0(.)A(The macro)102 654 Q F4(LIST_INSERT_HEAD)2.5 E F0
X(inserts the ne)2.5 E 2.5(we)-.25 G(lement)312.72 654 Q F2(elm)2.5 E F0
X(at the head of the list.)2.5 E(The macro)102 672 Q F4(LIST_INSERT_AFTER)2.5 E
XF0(inserts the ne)2.5 E 2.5(we)-.25 G(lement)318.72 672 Q F2(elm)2.5 E F0
X(after the element)2.5 E F2(listelm)2.5 E F0(.)A(The macro)102 690 Q F4
X(LIST_REMOVE)2.5 E F0(remo)2.5 E -.15(ve)-.15 G 2.5(st).15 G(he element)254.9
X690 Q F2(elm)2.5 E F0(from the list.)2.5 E(4th Berk)72 750 Q(ele)-.1 E 2.5(yD)
X-.15 G(istrib)132.85 750 Q 90.435(ution December)-.2 F(13, 1993)2.5 E(2)535 750
XQ EP
X%%Page: 3 3
X%%BeginPageSetup
XBP
X%%EndPageSetup
X/F0 10/Times-Roman@0 SF -.1(QU)72 48 S -.834(EUE \( 3 \)).1 F(BSD Programmer')
X250.17 48 Q 2.5(sM)-.55 G 125.232(anual Q)340.17 48 R -.834(UEUE \( 3 \))-.1 F
X/F1 10/Times-Bold@0 SF 1.666(LIST EXAMPLE)72 96 R/F2 10/Courier@0 SF
X(LIST_HEAD\(listhead, entry\) head;)102 126 Q(struct listhead)102 138 Q/F3 10
X/Symbol SF(*)6 E F2 82(headp; /)B F3(*)A F2(List head.)6 E F3(*)6 E F2(/)A
X(struct entry {)102 150 Q(...)147 162 Q(LIST_ENTRY\(entry\) entries;)147 174 Q
X(/)327 174 Q F3(*)A F2(List.)6 E F3(*)6 E F2(/)A(...)147 186 Q(})102 198 Q F3
X(*)6 E F2(n1,)A F3(*)6 E F2(n2,)A F3(*)6 E F2(np;)A 117(LIST_INIT\(&head\); /)
X102 222 R F3(*)A F2(Initialize the list.)6 E F3(*)6 E F2(/)A
X(n1 = malloc\(sizeof\(struct entry\)\);)102 246 Q(/)327 246 Q F3(*)A F2
X(Insert at the head.)6 E F3(*)6 E F2(/)A
X(LIST_INSERT_HEAD\(&head, n1, entries\);)102 258 Q
X(n2 = malloc\(sizeof\(struct entry\)\);)102 282 Q(/)327 282 Q F3(*)A F2
X(Insert after.)6 E F3(*)6 E F2(/)A(LIST_INSERT_AFTER\(n1, n2, entries\);)102
X294 Q(/)327 306 Q F3(*)A F2(Forward traversal.)6 E F3(*)6 E F2(/)A
X(for \(np = head.lh_first; np != NULL; np = np->entries.le_next\))102 318 Q
X(np-> ...)147 330 Q(while \(head.lh_first != NULL\))102 354 Q(/)327 354 Q F3(*)
XA F2(Delete.)6 E F3(*)6 E F2(/)A(LIST_REMOVE\(head.lh_first, entries\);)147 366
XQ F1 -.9(TA)72 390 S 1.666(IL Q).9 F(UEUES)-.1 E F0 2.98(At)102 402 S .48
X(ail queue is headed by a structure de\214ned by the)114.98 402 R/F4 10
X/Courier-Bold@0 SF(TAILQ_HEAD)2.979 E F0 2.979(macro. This)2.979 F .479
X(structure contains a pair of)2.979 F .227(pointers, one to the \214rst elemen\
Xt in the tail queue and the other to the last element in the tail queue.)102
X414 R .228(The ele-)5.228 F .387(ments are doubly link)102 426 R .387
X(ed so that an arbitrary element can be remo)-.1 F -.15(ve)-.15 G 2.887(dw).15
XG .387(ithout tra)390.075 426 R -.15(ve)-.2 G .387(rsing the tail queue.).15 F
X(Ne)5.387 E(w)-.25 E .45(elements can be added to the tail queue after an e)102
X438 R .451(xisting element, at the head of the tail queue, or at the end)-.15 F
X(of the tail queue.)102 450 Q(A)5 E/F5 10/Courier-Oblique@0 SF(TAILQ_HEAD)2.5 E
XF0(structure is declared as follo)2.5 E(ws:)-.25 E F2
X(TAILQ_HEAD\(HEADNAME, TYPE\) head;)132 468 Q F0(where)102 492 Q F2(HEADNAME)
X3.623 E F0 1.123(is the name of the structure to be de\214ned, and)3.623 F F2
X(TYPE)3.622 E F0 1.122(is the type of the elements to be)3.622 F(link)102 504 Q
X(ed into the tail queue.)-.1 E 2.5(Ap)5 G
X(ointer to the head of the tail queue can later be declared as:)223.56 504 Q F2
X(struct HEADNAME)132 522 Q F3(*)6 E F2(headp;)A F0(\(The names)102 546 Q F2
X(head)2.5 E F0(and)2.5 E F2(headp)2.5 E F0(are user selectable.\))2.5 E
X(The macro)102 564 Q F4(TAILQ_ENTRY)2.5 E F0
X(declares a structure that connects the elements in the tail queue.)2.5 E
X(The macro)102 582 Q F4(TAILQ_INIT)2.5 E F0
X(initializes the tail queue referenced by)2.5 E F5(head)2.5 E F0(.)A(The macro)
X102 600 Q F4(TAILQ_INSERT_HEAD)2.5 E F0(inserts the ne)2.5 E 2.5(we)-.25 G
X(lement)318.72 600 Q F5(elm)2.5 E F0(at the head of the tail queue.)2.5 E
X(The macro)102 618 Q F4(TAILQ_INSERT_TAIL)2.5 E F0(inserts the ne)2.5 E 2.5(we)
X-.25 G(lement)318.72 618 Q F5(elm)2.5 E F0(at the end of the tail queue.)2.5 E
X(The macro)102 636 Q F4(TAILQ_INSERT_AFTER)2.5 E F0(inserts the ne)2.5 E 2.5
X(we)-.25 G(lement)324.72 636 Q F5(elm)2.5 E F0(after the element)2.5 E F5
X(listelm)2.5 E F0(.)A(The macro)102 654 Q F4(TAILQ_REMOVE)2.5 E F0(remo)2.5 E
X-.15(ve)-.15 G 2.5(st).15 G(he element)260.9 654 Q F5(elm)2.5 E F0
X(from the tail queue.)2.5 E F1 -.9(TA)72 678 S 1.666(IL Q).9 F 1.666
X(UEUE EXAMPLE)-.1 F F0(4th Berk)72 750 Q(ele)-.1 E 2.5(yD)-.15 G(istrib)132.85
X750 Q 90.435(ution December)-.2 F(13, 1993)2.5 E(3)535 750 Q EP
X%%Page: 4 4
X%%BeginPageSetup
XBP
X%%EndPageSetup
X/F0 10/Times-Roman@0 SF -.1(QU)72 48 S -.834(EUE \( 3 \)).1 F(BSD Programmer')
X250.17 48 Q 2.5(sM)-.55 G 125.232(anual Q)340.17 48 R -.834(UEUE \( 3 \))-.1 F
X/F1 10/Courier@0 SF(TAILQ_HEAD\(tailhead, entry\) head;)102 96 Q
X(struct tailhead)102 108 Q/F2 10/Symbol SF(*)6 E F1 82(headp; /)B F2(*)A F1
X(Tail queue head.)6 E F2(*)6 E F1(/)A(struct entry {)102 120 Q(...)147 132 Q
X(TAILQ_ENTRY\(entry\) entries;)147 144 Q(/)327 144 Q F2(*)A F1(Tail queue.)6 E
XF2(*)6 E F1(/)A(...)147 156 Q(})102 168 Q F2(*)6 E F1(n1,)A F2(*)6 E F1(n2,)A
XF2(*)6 E F1(np;)A 111(TAILQ_INIT\(&head\); /)102 192 R F2(*)A F1
X(Initialize the queue.)6 E F2(*)6 E F1(/)A
X(n1 = malloc\(sizeof\(struct entry\)\);)102 216 Q(/)327 216 Q F2(*)A F1
X(Insert at the head.)6 E F2(*)6 E F1(/)A
X(TAILQ_INSERT_HEAD\(&head, n1, entries\);)102 228 Q
X(n1 = malloc\(sizeof\(struct entry\)\);)102 252 Q(/)327 252 Q F2(*)A F1
X(Insert at the tail.)6 E F2(*)6 E F1(/)A
X(TAILQ_INSERT_TAIL\(&head, n1, entries\);)102 264 Q
X(n2 = malloc\(sizeof\(struct entry\)\);)102 288 Q(/)327 288 Q F2(*)A F1
X(Insert after.)6 E F2(*)6 E F1(/)A
X(TAILQ_INSERT_AFTER\(&head, n1, n2, entries\);)102 300 Q(/)327 312 Q F2(*)A F1
X(Forward traversal.)6 E F2(*)6 E F1(/)A
X(for \(np = head.tqh_first; np != NULL; np = np->entries.tqe_next\))102 324 Q
X(np-> ...)147 336 Q(/)327 348 Q F2(*)A F1(Delete.)6 E F2(*)6 E F1(/)A
X(while \(head.tqh_first != NULL\))102 360 Q
X(TAILQ_REMOVE\(&head, head.tqh_first, entries\);)147 372 Q/F3 10/Times-Bold@0
XSF 1.666(CIRCULAR Q)72 396 R(UEUES)-.1 E F0 2.984(Ac)102 408 S .484
X(ircular queue is headed by a structure de\214ned by the)116.644 408 R/F4 10
X/Courier-Bold@0 SF(CIRCLEQ_HEAD)2.985 E F0 2.985(macro. This)2.985 F .485
X(structure contains a)2.985 F .358(pair of pointers, one to the \214rst elemen\
Xt in the circular queue and the other to the last element in the circular)102
X420 R 3.33(queue. The)102 432 R .83(elements are doubly link)3.33 F .83
X(ed so that an arbitrary element can be remo)-.1 F -.15(ve)-.15 G 3.33(dw).15 G
X.83(ithout tra)458.14 432 R -.15(ve)-.2 G .83(rsing the).15 F 2.796(queue. Ne)
X102 444 R 2.796(we)-.25 G .296(lements can be added to the queue after an e)
X159.542 444 R .295(xisting element, before an e)-.15 F .295
X(xisting element, at the)-.15 F(head of the queue, or at the end of the queue.)
X102 456 Q(A)5 E/F5 10/Courier-Oblique@0 SF(CIRCLEQ_HEAD)2.5 E F0
X(structure is declared as follo)2.5 E(ws:)-.25 E F1
X(CIRCLEQ_HEAD\(HEADNAME, TYPE\) head;)132 474 Q F0(where)102 498 Q F1(HEADNAME)
X3.622 E F0 1.122(is the name of the structure to be de\214ned, and)3.622 F F1
X(TYPE)3.623 E F0 1.123(is the type of the elements to be)3.623 F(link)102 510 Q
X(ed into the circular queue.)-.1 E 2.5(Ap)5 G
X(ointer to the head of the circular queue can later be declared as:)241.32 510
XQ F1(struct HEADNAME)132 528 Q F2(*)6 E F1(headp;)A F0(\(The names)102 552 Q F1
X(head)2.5 E F0(and)2.5 E F1(headp)2.5 E F0(are user selectable.\))2.5 E
X(The macro)102 570 Q F4(CIRCLEQ_ENTRY)2.5 E F0
X(declares a structure that connects the elements in the circular queue.)2.5 E
X(The macro)102 588 Q F4(CIRCLEQ_INIT)2.5 E F0
X(initializes the circular queue referenced by)2.5 E F5(head)2.5 E F0(.)A
X(The macro)102 606 Q F4(CIRCLEQ_INSERT_HEAD)2.5 E F0(inserts the ne)2.5 E 2.5
X(we)-.25 G(lement)330.72 606 Q F5(elm)2.5 E F0
X(at the head of the circular queue.)2.5 E(The macro)102 624 Q F4
X(CIRCLEQ_INSERT_TAIL)2.5 E F0(inserts the ne)2.5 E 2.5(we)-.25 G(lement)330.72
X624 Q F5(elm)2.5 E F0(at the end of the circular queue.)2.5 E(The macro)102 642
XQ F4(CIRCLEQ_INSERT_AFTER)2.5 E F0(inserts the ne)2.5 E 2.5(we)-.25 G(lement)
X336.72 642 Q F5(elm)2.5 E F0(after the element)2.5 E F5(listelm)2.5 E F0(.)A
X(The macro)102 660 Q F4(CIRCLEQ_INSERT_BEFORE)2.5 E F0(inserts the ne)2.5 E 2.5
X(we)-.25 G(lement)342.72 660 Q F5(elm)2.5 E F0(before the element)2.5 E F5
X(listelm)2.5 E F0(.)A(The macro)102 678 Q F4(CIRCLEQ_REMOVE)2.5 E F0(remo)2.5 E
X-.15(ve)-.15 G 2.5(st).15 G(he element)272.9 678 Q F5(elm)2.5 E F0
X(from the circular queue.)2.5 E(4th Berk)72 750 Q(ele)-.1 E 2.5(yD)-.15 G
X(istrib)132.85 750 Q 90.435(ution December)-.2 F(13, 1993)2.5 E(4)535 750 Q EP
X%%Page: 5 5
X%%BeginPageSetup
XBP
X%%EndPageSetup
X/F0 10/Times-Roman@0 SF -.1(QU)72 48 S -.834(EUE \( 3 \)).1 F(BSD Programmer')
X250.17 48 Q 2.5(sM)-.55 G 125.232(anual Q)340.17 48 R -.834(UEUE \( 3 \))-.1 F
X/F1 10/Times-Bold@0 SF 1.666(CIRCULAR Q)72 96 R 1.666(UEUE EXAMPLE)-.1 F/F2 10
X/Courier@0 SF(CIRCLEQ_HEAD\(circleq, entry\) head;)102 126 Q(struct circleq)102
X138 Q/F3 10/Symbol SF(*)6 E F2 88(headp; /)B F3(*)A F2(Circular queue head.)6 E
XF3(*)6 E F2(/)A(struct entry {)102 150 Q(...)147 162 Q(CIRCLEQ_ENTRY entries;)
X147 174 Q(/)327 174 Q F3(*)A F2(Circular queue.)6 E F3(*)6 E F2(/)A(...)147 186
XQ(})102 198 Q F3(*)6 E F2(n1,)A F3(*)6 E F2(n2,)A F3(*)6 E F2(np;)A 99
X(CIRCLEQ_INIT\(&head\); /)102 222 R F3(*)A F2(Initialize the circular queue.)6
XE F3(*)6 E F2(/)A(n1 = malloc\(sizeof\(struct entry\)\);)102 246 Q(/)327 246 Q
XF3(*)A F2(Insert at the head.)6 E F3(*)6 E F2(/)A
X(CIRCLEQ_INSERT_HEAD\(&head, n1, entries\);)102 258 Q
X(n1 = malloc\(sizeof\(struct entry\)\);)102 282 Q(/)327 282 Q F3(*)A F2
X(Insert at the tail.)6 E F3(*)6 E F2(/)A
X(CIRCLEQ_INSERT_TAIL\(&head, n1, entries\);)102 294 Q
X(n2 = malloc\(sizeof\(struct entry\)\);)102 318 Q(/)327 318 Q F3(*)A F2
X(Insert after.)6 E F3(*)6 E F2(/)A
X(CIRCLEQ_INSERT_AFTER\(&head, n1, n2, entries\);)102 330 Q
X(n2 = malloc\(sizeof\(struct entry\)\);)102 354 Q(/)327 354 Q F3(*)A F2
X(Insert before.)6 E F3(*)6 E F2(/)A
X(CIRCLEQ_INSERT_BEFORE\(&head, n1, n2, entries\);)102 366 Q(/)327 378 Q F3(*)A
XF2(Forward traversal.)6 E F3(*)6 E F2(/)A
X(for \(np = head.cqh_first; np != \(void)102 390 Q F3(*)6 E F2
X(\)&head; np = np->entries.cqe_next\))A(np-> ...)147 402 Q(/)327 414 Q F3(*)A
XF2(Reverse traversal.)6 E F3(*)6 E F2(/)A
X(for \(np = head.cqh_last; np != \(void)102 426 Q F3(*)6 E F2
X(\)&head; np = np->entries.cqe_prev\))A(np-> ...)147 438 Q(/)327 450 Q F3(*)A
XF2(Delete.)6 E F3(*)6 E F2(/)A(while \(head.cqh_first != \(void)102 462 Q F3(*)
X6 E F2(\)&head\))A(CIRCLEQ_REMOVE\(&head, head.cqh_first, entries\);)147 474 Q
XF1(HIST)72 498 Q(OR)-.18 E(Y)-.35 E F0(The)102 510 Q/F4 10/Courier-Bold@0 SF
X(queue)2.5 E F0(functions \214rst appeared in 4.4BSD.)2.5 E(4th Berk)72 750 Q
X(ele)-.1 E 2.5(yD)-.15 G(istrib)132.85 750 Q 90.435(ution December)-.2 F
X(13, 1993)2.5 E(5)535 750 Q EP
X%%Trailer
Xend
X%%EOF
END-of-queue.0.ps
echo x - queue.3
sed 's/^X//' >queue.3 << 'END-of-queue.3'
X.\" Copyright (c) 1993 The Regents of the University of California.
X.\" All rights reserved.
X.\"
X.\" Redistribution and use in source and binary forms, with or without
X.\" modification, are permitted provided that the following conditions
X.\" are met:
X.\" 1. Redistributions of source code must retain the above copyright
X.\" notice, this list of conditions and the following disclaimer.
X.\" 2. Redistributions in binary form must reproduce the above copyright
X.\" notice, this list of conditions and the following disclaimer in the
X.\" documentation and/or other materials provided with the distribution.
X.\" 3. All advertising materials mentioning features or use of this software
X.\" must display the following acknowledgement:
X.\" This product includes software developed by the University of
X.\" California, Berkeley and its contributors.
X.\" 4. Neither the name of the University nor the names of its contributors
X.\" may be used to endorse or promote products derived from this software
X.\" without specific prior written permission.
X.\"
X.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
X.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
X.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
X.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
X.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
X.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
X.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
X.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
X.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
X.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
X.\" SUCH DAMAGE.
X.\"
X.\" @(#)queue.3 8.1 (Berkeley) 12/13/93
X.\"
X.Dd "December 13, 1993"
X.Dt QUEUE 3
X.Os BSD 4
X.Sh NAME
X.Nm LIST_ENTRY ,
X.Nm LIST_HEAD ,
X.Nm LIST_INIT ,
X.Nm LIST_INSERT_AFTER ,
X.Nm LIST_INSERT_HEAD ,
X.Nm LIST_REMOVE ,
X.Nm TAILQ_ENTRY ,
X.Nm TAILQ_HEAD ,
X.Nm TAILQ_INIT ,
X.Nm TAILQ_INSERT_AFTER ,
X.Nm TAILQ_INSERT_HEAD ,
X.Nm TAILQ_INSERT_TAIL ,
X.Nm TAILQ_REMOVE ,
X.Nm CIRCLEQ_ENTRY ,
X.Nm CIRCLEQ_HEAD ,
X.Nm CIRCLEQ_INIT ,
X.Nm CIRCLEQ_INSERT_AFTER ,
X.Nm CIRCLEQ_INSERT_BEFORE ,
X.Nm CIRCLEQ_INSERT_HEAD ,
X.Nm CIRCLEQ_INSERT_TAIL ,
X.Nm CIRCLEQ_REMOVE
X.Nd implementations of lists, tail queues, and circular queues
X.Sh SYNOPSIS
X.Fd #include <sys/queue.h>
X.sp
X.Fn LIST_ENTRY "TYPE"
X.Fn LIST_HEAD "HEADNAME" "TYPE"
X.Fn LIST_INIT "LIST_HEAD *head"
X.Fn LIST_INSERT_AFTER "LIST_ENTRY *listelm" "TYPE *elm" "LIST_ENTRY NAME"
X.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
X.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
X.sp
X.Fn TAILQ_ENTRY "TYPE"
X.Fn TAILQ_HEAD "HEADNAME" "TYPE"
X.Fn TAILQ_INIT "TAILQ_HEAD *head"
X.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
X.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
X.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
X.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
X.sp
X.Fn CIRCLEQ_ENTRY "TYPE"
X.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
X.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
X.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
X.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
X.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
X.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
X.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
X.Sh DESCRIPTION
XThese macros define and operate on three types of data structures:
Xlists, tail queues, and circular queues.
XAll three structures support the following functionality:
X.Bl -enum -compact -offset indent
X.It
XInsertion of a new entry at the head of the list.
X.It
XInsertion of a new entry after any element in the list.
X.It
XRemoval of any entry in the list.
X.It
XForward traversal through the list.
X.El
X.Pp
XLists are the simplest of the three data structures and support
Xonly the above functionality.
X.Pp
XTail queues add the following functionality:
X.Bl -enum -compact -offset indent
X.It
XEntries can be added at the end of a list.
X.El
XHowever:
X.Bl -enum -compact -offset indent
X.It
XAll list insertions and removals must specify the head of the list.
X.It
XEach head entry requires two pointers rather than one.
X.It
XCode size is about 15% greater and operations run about 20% slower
Xthan lists.
X.El
X.Pp
XCircular queues add the following functionality:
X.Bl -enum -compact -offset indent
X.It
XEntries can be added at the end of a list.
X.It
XEntries can be added before another entry.
X.It
XThey may be traversed backwards, from tail to head.
X.El
XHowever:
X.Bl -enum -compact -offset indent
X.It
XAll list insertions and removals must specify the head of the list.
X.It
XEach head entry requires two pointers rather than one.
X.It
XThe termination condition for traversal is more complex.
X.It
XCode size is about 40% greater and operations run about 45% slower
Xthan lists.
X.El
X.Pp
XIn the macro definitions,
X.Fa TYPE
Xis the name of a user defined structure,
Xthat must contain a field of type
X.Li LIST_ENTRY ,
X.Li TAILQ_ENTRY ,
Xor
X.Li CIRCLEQ_ENTRY ,
Xnamed
X.Fa NAME .
XThe argument
X.Fa HEADNAME
Xis the name of a user defined structure that must be declared
Xusing the macros
X.Li LIST_HEAD ,
X.Li TAILQ_HEAD ,
Xor
X.Li CIRCLEQ_HEAD .
XSee the examples below for further explanation of how these
Xmacros are used.
X.Sh LISTS
XA list is headed by a structure defined by the
X.Nm LIST_HEAD
Xmacro.
XThis structure contains a single pointer to the first element
Xon the list.
XThe elements are doubly linked so that an arbitrary element can be
Xremoved without traversing the list.
XNew elements can be added to the list after an existing element or
Xat the head of the list.
XA
X.Fa LIST_HEAD
Xstructure is declared as follows:
X.Bd -literal -offset indent
XLIST_HEAD(HEADNAME, TYPE) head;
X.Ed
X.sp
Xwhere
X.Fa HEADNAME
Xis the name of the structure to be defined, and
X.Fa TYPE
Xis the type of the elements to be linked into the list.
XA pointer to the head of the list can later be declared as:
X.Bd -literal -offset indent
Xstruct HEADNAME *headp;
X.Ed
X.sp
X(The names
X.Li head
Xand
X.Li headp
Xare user selectable.)
X.Pp
XThe macro
X.Nm LIST_ENTRY
Xdeclares a structure that connects the elements in
Xthe list.
X.Pp
XThe macro
X.Nm LIST_INIT
Xinitializes the list referenced by
X.Fa head .
X.Pp
XThe macro
X.Nm LIST_INSERT_HEAD
Xinserts the new element
X.Fa elm
Xat the head of the list.
X.Pp
XThe macro
X.Nm LIST_INSERT_AFTER
Xinserts the new element
X.Fa elm
Xafter the element
X.Fa listelm .
X.Pp
XThe macro
X.Nm LIST_REMOVE
Xremoves the element
X.Fa elm
Xfrom the list.
X.Sh LIST EXAMPLE
X.Bd -literal
XLIST_HEAD(listhead, entry) head;
Xstruct listhead *headp; /* List head. */
Xstruct entry {
X ...
X LIST_ENTRY(entry) entries; /* List. */
X ...
X} *n1, *n2, *np;
X
XLIST_INIT(&head); /* Initialize the list. */
X
Xn1 = malloc(sizeof(struct entry)); /* Insert at the head. */
XLIST_INSERT_HEAD(&head, n1, entries);
X
Xn2 = malloc(sizeof(struct entry)); /* Insert after. */
XLIST_INSERT_AFTER(n1, n2, entries);
X /* Forward traversal. */
Xfor (np = head.lh_first; np != NULL; np = np->entries.le_next)
X np-> ...
X
Xwhile (head.lh_first != NULL) /* Delete. */
X LIST_REMOVE(head.lh_first, entries);
X.Ed
X.Sh TAIL QUEUES
XA tail queue is headed by a structure defined by the
X.Nm TAILQ_HEAD
Xmacro.
XThis structure contains a pair of pointers,
Xone to the first element in the tail queue and the other to
Xthe last element in the tail queue.
XThe elements are doubly linked so that an arbitrary element can be
Xremoved without traversing the tail queue.
XNew elements can be added to the tail queue after an existing element,
Xat the head of the tail queue, or at the end of the tail queue.
XA
X.Fa TAILQ_HEAD
Xstructure is declared as follows:
X.Bd -literal -offset indent
XTAILQ_HEAD(HEADNAME, TYPE) head;
X.Ed
X.sp
Xwhere
X.Li HEADNAME
Xis the name of the structure to be defined, and
X.Li TYPE
Xis the type of the elements to be linked into the tail queue.
XA pointer to the head of the tail queue can later be declared as:
X.Bd -literal -offset indent
Xstruct HEADNAME *headp;
X.Ed
X.sp
X(The names
X.Li head
Xand
X.Li headp
Xare user selectable.)
X.Pp
XThe macro
X.Nm TAILQ_ENTRY
Xdeclares a structure that connects the elements in
Xthe tail queue.
X.Pp
XThe macro
X.Nm TAILQ_INIT
Xinitializes the tail queue referenced by
X.Fa head .
X.Pp
XThe macro
X.Nm TAILQ_INSERT_HEAD
Xinserts the new element
X.Fa elm
Xat the head of the tail queue.
X.Pp
XThe macro
X.Nm TAILQ_INSERT_TAIL
Xinserts the new element
X.Fa elm
Xat the end of the tail queue.
X.Pp
XThe macro
X.Nm TAILQ_INSERT_AFTER
Xinserts the new element
X.Fa elm
Xafter the element
X.Fa listelm .
X.Pp
XThe macro
X.Nm TAILQ_REMOVE
Xremoves the element
X.Fa elm
Xfrom the tail queue.
X.Sh TAIL QUEUE EXAMPLE
X.Bd -literal
XTAILQ_HEAD(tailhead, entry) head;
Xstruct tailhead *headp; /* Tail queue head. */
Xstruct entry {
X ...
X TAILQ_ENTRY(entry) entries; /* Tail queue. */
X ...
X} *n1, *n2, *np;
X
XTAILQ_INIT(&head); /* Initialize the queue. */
X
Xn1 = malloc(sizeof(struct entry)); /* Insert at the head. */
XTAILQ_INSERT_HEAD(&head, n1, entries);
X
Xn1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
XTAILQ_INSERT_TAIL(&head, n1, entries);
X
Xn2 = malloc(sizeof(struct entry)); /* Insert after. */
XTAILQ_INSERT_AFTER(&head, n1, n2, entries);
X /* Forward traversal. */
Xfor (np = head.tqh_first; np != NULL; np = np->entries.tqe_next)
X np-> ...
X /* Delete. */
Xwhile (head.tqh_first != NULL)
X TAILQ_REMOVE(&head, head.tqh_first, entries);
X.Ed
X.Sh CIRCULAR QUEUES
XA circular queue is headed by a structure defined by the
X.Nm CIRCLEQ_HEAD
Xmacro.
XThis structure contains a pair of pointers,
Xone to the first element in the circular queue and the other to the
Xlast element in the circular queue.
XThe elements are doubly linked so that an arbitrary element can be
Xremoved without traversing the queue.
XNew elements can be added to the queue after an existing element,
Xbefore an existing element, at the head of the queue, or at the end
Xof the queue.
XA
X.Fa CIRCLEQ_HEAD
Xstructure is declared as follows:
X.Bd -literal -offset indent
XCIRCLEQ_HEAD(HEADNAME, TYPE) head;
X.Ed
X.sp
Xwhere
X.Li HEADNAME
Xis the name of the structure to be defined, and
X.Li TYPE
Xis the type of the elements to be linked into the circular queue.
XA pointer to the head of the circular queue can later be declared as:
X.Bd -literal -offset indent
Xstruct HEADNAME *headp;
X.Ed
X.sp
X(The names
X.Li head
Xand
X.Li headp
Xare user selectable.)
X.Pp
XThe macro
X.Nm CIRCLEQ_ENTRY
Xdeclares a structure that connects the elements in
Xthe circular queue.
X.Pp
XThe macro
X.Nm CIRCLEQ_INIT
Xinitializes the circular queue referenced by
X.Fa head .
X.Pp
XThe macro
X.Nm CIRCLEQ_INSERT_HEAD
Xinserts the new element
X.Fa elm
Xat the head of the circular queue.
X.Pp
XThe macro
X.Nm CIRCLEQ_INSERT_TAIL
Xinserts the new element
X.Fa elm
Xat the end of the circular queue.
X.Pp
XThe macro
X.Nm CIRCLEQ_INSERT_AFTER
Xinserts the new element
X.Fa elm
Xafter the element
X.Fa listelm .
X.Pp
XThe macro
X.Nm CIRCLEQ_INSERT_BEFORE
Xinserts the new element
X.Fa elm
Xbefore the element
X.Fa listelm .
X.Pp
XThe macro
X.Nm CIRCLEQ_REMOVE
Xremoves the element
X.Fa elm
Xfrom the circular queue.
X.Sh CIRCULAR QUEUE EXAMPLE
X.Bd -literal
XCIRCLEQ_HEAD(circleq, entry) head;
Xstruct circleq *headp; /* Circular queue head. */
Xstruct entry {
X ...
X CIRCLEQ_ENTRY entries; /* Circular queue. */
X ...
X} *n1, *n2, *np;
X
XCIRCLEQ_INIT(&head); /* Initialize the circular queue. */
X
Xn1 = malloc(sizeof(struct entry)); /* Insert at the head. */
XCIRCLEQ_INSERT_HEAD(&head, n1, entries);
X
Xn1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
XCIRCLEQ_INSERT_TAIL(&head, n1, entries);
X
Xn2 = malloc(sizeof(struct entry)); /* Insert after. */
XCIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
X
Xn2 = malloc(sizeof(struct entry)); /* Insert before. */
XCIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
X /* Forward traversal. */
Xfor (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next)
X np-> ...
X /* Reverse traversal. */
Xfor (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
X np-> ...
X /* Delete. */
Xwhile (head.cqh_first != (void *)&head)
X CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
X.Ed
X.Sh HISTORY
XThe
X.Nm queue
Xfunctions first appeared in 4.4BSD.
END-of-queue.3
echo x - queue.h
sed 's/^X//' >queue.h << 'END-of-queue.h'
X/*
X * Copyright (c) 1991, 1993
X * The Regents of the University of California. All rights reserved.
X *
X * Redistribution and use in source and binary forms, with or without
X * modification, are permitted provided that the following conditions
X * are met:
X * 1. Redistributions of source code must retain the above copyright
X * notice, this list of conditions and the following disclaimer.
X * 2. Redistributions in binary form must reproduce the above copyright
X * notice, this list of conditions and the following disclaimer in the
X * documentation and/or other materials provided with the distribution.
X * 3. All advertising materials mentioning features or use of this software
X * must display the following acknowledgement:
X * This product includes software developed by the University of
X * California, Berkeley and its contributors.
X * 4. Neither the name of the University nor the names of its contributors
X * may be used to endorse or promote products derived from this software
X * without specific prior written permission.
X *
X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
X * SUCH DAMAGE.
X *
X * @(#)queue.h 8.3 (Berkeley) 12/13/93
X */
X
X#ifndef _QUEUE_H_
X#define _QUEUE_H_
X
X/*
X * This file defines three types of data structures: lists, tail queues,
X * and circular queues.
X *
X * A list is headed by a single forward pointer (or an array of forward
X * pointers for a hash table header). The elements are doubly linked
X * so that an arbitrary element can be removed without a need to
X * traverse the list. New elements can be added to the list after
X * an existing element or at the head of the list. A list may only be
X * traversed in the forward direction.
X *
X * A tail queue is headed by a pair of pointers, one to the head of the
X * list and the other to the tail of the list. The elements are doubly
X * linked so that an arbitrary element can be removed without a need to
X * traverse the list. New elements can be added to the list after
X * an existing element, at the head of the list, or at the end of the
X * list. A tail queue may only be traversed in the forward direction.
X *
X * A circle queue is headed by a pair of pointers, one to the head of the
X * list and the other to the tail of the list. The elements are doubly
X * linked so that an arbitrary element can be removed without a need to
X * traverse the list. New elements can be added to the list before or after
X * an existing element, at the head of the list, or at the end of the list.
X * A circle queue may be traversed in either direction, but has a more
X * complex end of list detection.
X *
X * For details on the use of these macros, see the queue(3) manual page.
X */
X
X/*
X * List definitions.
X */
X#define LIST_HEAD(name, type) \
Xstruct name { \
X struct type *lh_first; /* first element */ \
X}
X
X#define LIST_ENTRY(type) \
Xstruct { \
X struct type *le_next; /* next element */ \
X struct type **le_prev; /* address of previous next element */ \
X}
X
X/*
X * List functions.
X */
X#define LIST_INIT(head) { \
X (head)->lh_first = NULL; \
X}
X
X#define LIST_INSERT_AFTER(listelm, elm, field) { \
X if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
X (listelm)->field.le_next->field.le_prev = \
X &(elm)->field.le_next; \
X (listelm)->field.le_next = (elm); \
X (elm)->field.le_prev = &(listelm)->field.le_next; \
X}
X
X#define LIST_INSERT_HEAD(head, elm, field) { \
X if (((elm)->field.le_next = (head)->lh_first) != NULL) \
X (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
X (head)->lh_first = (elm); \
X (elm)->field.le_prev = &(head)->lh_first; \
X}
X
X#define LIST_REMOVE(elm, field) { \
X if ((elm)->field.le_next != NULL) \
X (elm)->field.le_next->field.le_prev = \
X (elm)->field.le_prev; \
X *(elm)->field.le_prev = (elm)->field.le_next; \
X}
X
X/*
X * Tail queue definitions.
X */
X#define TAILQ_HEAD(name, type) \
Xstruct name { \
X struct type *tqh_first; /* first element */ \
X struct type **tqh_last; /* addr of last next element */ \
X}
X
X#define TAILQ_ENTRY(type) \
Xstruct { \
X struct type *tqe_next; /* next element */ \
X struct type **tqe_prev; /* address of previous next element */ \
X}
X
X/*
X * Tail queue functions.
X */
X#define TAILQ_INIT(head) { \
X (head)->tqh_first = NULL; \
X (head)->tqh_last = &(head)->tqh_first; \
X}
X
X#define TAILQ_INSERT_HEAD(head, elm, field) { \
X if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
X (elm)->field.tqe_next->field.tqe_prev = \
X &(elm)->field.tqe_next; \
X else \
X (head)->tqh_last = &(elm)->field.tqe_next; \
X (head)->tqh_first = (elm); \
X (elm)->field.tqe_prev = &(head)->tqh_first; \
X}
X
X#define TAILQ_INSERT_TAIL(head, elm, field) { \
X (elm)->field.tqe_next = NULL; \
X (elm)->field.tqe_prev = (head)->tqh_last; \
X *(head)->tqh_last = (elm); \
X (head)->tqh_last = &(elm)->field.tqe_next; \
X}
X
X#define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \
X if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
X (elm)->field.tqe_next->field.tqe_prev = \
X &(elm)->field.tqe_next; \
X else \
X (head)->tqh_last = &(elm)->field.tqe_next; \
X (listelm)->field.tqe_next = (elm); \
X (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
X}
X
X#define TAILQ_REMOVE(head, elm, field) { \
X if (((elm)->field.tqe_next) != NULL) \
X (elm)->field.tqe_next->field.tqe_prev = \
X (elm)->field.tqe_prev; \
X else \
X (head)->tqh_last = (elm)->field.tqe_prev; \
X *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
X}
X
X/*
X * Circular queue definitions.
X */
X#define CIRCLEQ_HEAD(name, type) \
Xstruct name { \
X struct type *cqh_first; /* first element */ \
X struct type *cqh_last; /* last element */ \
X}
X
X#define CIRCLEQ_ENTRY(type) \
Xstruct { \
X struct type *cqe_next; /* next element */ \
X struct type *cqe_prev; /* previous element */ \
X}
X
X/*
X * Circular queue functions.
X */
X#define CIRCLEQ_INIT(head) { \
X (head)->cqh_first = (void *)(head); \
X (head)->cqh_last = (void *)(head); \
X}
X
X#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \
X (elm)->field.cqe_next = (listelm)->field.cqe_next; \
X (elm)->field.cqe_prev = (listelm); \
X if ((listelm)->field.cqe_next == (void *)(head)) \
X (head)->cqh_last = (elm); \
X else \
X (listelm)->field.cqe_next->field.cqe_prev = (elm); \
X (listelm)->field.cqe_next = (elm); \
X}
X
X#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \
X (elm)->field.cqe_next = (listelm); \
X (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
X if ((listelm)->field.cqe_prev == (void *)(head)) \
X (head)->cqh_first = (elm); \
X else \
X (listelm)->field.cqe_prev->field.cqe_next = (elm); \
X (listelm)->field.cqe_prev = (elm); \
X}
X
X#define CIRCLEQ_INSERT_HEAD(head, elm, field) { \
X (elm)->field.cqe_next = (head)->cqh_first; \
X (elm)->field.cqe_prev = (void *)(head); \
X if ((head)->cqh_last == (void *)(head)) \
X (head)->cqh_last = (elm); \
X else \
X (head)->cqh_first->field.cqe_prev = (elm); \
X (head)->cqh_first = (elm); \
X}
X
X#define CIRCLEQ_INSERT_TAIL(head, elm, field) { \
X (elm)->field.cqe_next = (void *)(head); \
X (elm)->field.cqe_prev = (head)->cqh_last; \
X if ((head)->cqh_first == (void *)(head)) \
X (head)->cqh_first = (elm); \
X else \
X (head)->cqh_last->field.cqe_next = (elm); \
X (head)->cqh_last = (elm); \
X}
X
X#define CIRCLEQ_REMOVE(head, elm, field) { \
X if ((elm)->field.cqe_next == (void *)(head)) \
X (head)->cqh_last = (elm)->field.cqe_prev; \
X else \
X (elm)->field.cqe_next->field.cqe_prev = \
X (elm)->field.cqe_prev; \
X if ((elm)->field.cqe_prev == (void *)(head)) \
X (head)->cqh_first = (elm)->field.cqe_next; \
X else \
X (elm)->field.cqe_prev->field.cqe_next = \
X (elm)->field.cqe_next; \
X}
X#endif /* !_QUEUE_H_ */
END-of-queue.h
exit
