Source Code 1994 March

home *** CD-ROM | disk | FTP | other *** search

/ Source Code 1994 March / Source_Code_CD-ROM_Walnut_Creek_March_1994.iso / compsrcs / unix / volume27 / queue / part01 < prev next >

Wrap

Text File | 1993-12-21 | 62.5 KB | 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