QUEUE(3) NetBSD Programmer's Manual QUEUE(3) NNAAMMEE LLIISSTT__EENNTTRRYY, LLIISSTT__HHEEAADD, LLIISSTT__IINNIITT, LLIISSTT__IINNSSEERRTT__AAFFTTEERR, LLIISSTT__IINNSSEERRTT__BBEEFFOORREE, LLIISSTT__IINNSSEERRTT__HHEEAADD, LLIISSTT__RREEMMOOVVEE, TTAAIILLQQ__EENNTTRRYY, TTAAIILLQQ__HHEEAADD, TTAAIILLQQ__IINNIITT, TTAAIILLQQ__IINNSSEERRTT__AAFFTTEERR, TTAAIILLQQ__IINNSSEERRTT__BBEEFFOORREE, TTAAIILLQQ__IINNSSEERRTT__HHEEAADD, TTAAIILLQQ__IINNSSEERRTT__TTAAIILL, TTAAIILLQQ__RREEMMOOVVEE, CCIIRRCCLLEEQQ__EENNTTRRYY, CCIIRRCCLLEEQQ__HHEEAADD, CCIIRRCCLLEEQQ__IINNIITT, CCIIRRCCLLEEQQ__IINNSSEERRTT__AAFFTTEERR, CCIIRRCCLLEEQQ__IINNSSEERRTT__BBEEFFOORREE, CCIIRRCCLLEEQQ__IINNSSEERRTT__HHEEAADD, CCIIRRCCLLEEQQ__IINNSSEERRTT__TTAAIILL, CCIIRRCCLLEEQQ__RREEMMOOVVEE - implementa- tions of lists, tail queues, and circular queues SSYYNNOOPPSSIISS ##iinncclluuddee <> LLIISSTT__EENNTTRRYY(_T_Y_P_E) LLIISSTT__HHEEAADD(_H_E_A_D_N_A_M_E, _T_Y_P_E) LLIISSTT__IINNIITT(_L_I_S_T___H_E_A_D _*_h_e_a_d) LLIISSTT__IINNSSEERRTT__AAFFTTEERR(_T_Y_P_E _*_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) LLIISSTT__IINNSSEERRTT__BBEEFFOORREE(_T_Y_P_E _*_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) 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) LLIISSTT__RREEMMOOVVEE(_T_Y_P_E _*_e_l_m, _L_I_S_T___E_N_T_R_Y _N_A_M_E) TTAAIILLQQ__EENNTTRRYY(_T_Y_P_E) TTAAIILLQQ__HHEEAADD(_H_E_A_D_N_A_M_E, _T_Y_P_E) TTAAIILLQQ__IINNIITT(_T_A_I_L_Q___H_E_A_D _*_h_e_a_d) 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, _T_A_I_L_Q___E_N_T_R_Y _N_A_M_E) TTAAIILLQQ__IINNSSEERRTT__BBEEFFOORREE(_T_Y_P_E _*_l_i_s_t_e_l_m, _T_Y_P_E _*_e_l_m, _T_A_I_L_Q___E_N_T_R_Y _N_A_M_E) 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) 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) 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) CCIIRRCCLLEEQQ__EENNTTRRYY(_T_Y_P_E) CCIIRRCCLLEEQQ__HHEEAADD(_H_E_A_D_N_A_M_E, _T_Y_P_E) CCIIRRCCLLEEQQ__IINNIITT(_C_I_R_C_L_E_Q___H_E_A_D _*_h_e_a_d) 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, _C_I_R_C_L_E_Q___E_N_T_R_Y _N_A_M_E) 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, _C_I_R_C_L_E_Q___E_N_T_R_Y _N_A_M_E) 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) 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) 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) DDEESSCCRRIIPPTTIIOONN 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 before or after any element in the list. 3. Removal of any entry in the list. 4. Forward traversal through the list. Lists are the simplest of the three data structures and support only the above functionality. Tail queues add the following functionality: 1. Entries can be added at the end of a list. However: 1. All list insertions and removals, except insertion before an- other element, must specify the head of the list. 2. Each head entry requires two pointers rather than one. 3. Code size is about 15% greater and operations run about 20% slower than lists. Circular queues add the following functionality: 1. Entries can be added at the end of a list. 2. They may be traversed backwards, from tail to head. However: 1. All list insertions and removals must specify the head of the list. 2. Each head entry requires two pointers rather than one. 3. The termination condition for traversal is more complex. 4. Code size is about 40% greater and operations run about 45% slower than lists. In the macro definitions, _T_Y_P_E is the name of a user defined structure, that must contain a field of type LIST_ENTRY, TAILQ_ENTRY, or CIRCLEQ_ENTRY, named _N_A_M_E. The argument _H_E_A_D_N_A_M_E is the name of a user defined structure that must be declared using the macros LIST_HEAD, TAILQ_HEAD, or CIRCLEQ_HEAD. See the examples below for further explana- tion of how these macros are used. LLIISSTTSS A list is headed by a structure defined by the LLIISSTT__HHEEAADD macro. This structure contains a single pointer to the first element on the list. The elements are doubly linked so that an arbitrary element can be re- moved without traversing the list. New elements can be added to the list after an existing element, before an existing element, or at the head of the list. A _L_I_S_T___H_E_A_D structure is declared as follows: LIST_HEAD(HEADNAME, TYPE) head; where _H_E_A_D_N_A_M_E is the name of the structure to be defined, and _T_Y_P_E is the type of the elements to be linked into the list. A pointer to the head of the list can later be declared as: struct HEADNAME *headp; (The names head and headp are user selectable.) The macro LLIISSTT__EENNTTRRYY declares a structure that connects the elements in the list. The macro LLIISSTT__IINNIITT initializes the list referenced by _h_e_a_d. The macro LLIISSTT__IINNSSEERRTT__HHEEAADD inserts the new element _e_l_m at the head of the list. The macro LLIISSTT__IINNSSEERRTT__AAFFTTEERR inserts the new element _e_l_m after the element _l_i_s_t_e_l_m. The macro LLIISSTT__IINNSSEERRTT__BBEEFFOORREE inserts the new element _e_l_m before the ele- ment _l_i_s_t_e_l_m. The macro LLIISSTT__RREEMMOOVVEE removes the element _e_l_m from the list. LLIISSTT EEXXAAMMPPLLEE LIST_HEAD(listhead, entry) head; struct listhead *headp; /* List head. */ struct entry { ... LIST_ENTRY(entry) entries; /* List. */ ... } *n1, *n2, *np; LIST_INIT(&head); /* Initialize the list. */ n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ LIST_INSERT_HEAD(&head, n1, entries); n2 = malloc(sizeof(struct entry)); /* Insert after. */ LIST_INSERT_AFTER(n1, n2, entries); n2 = malloc(sizeof(struct entry)); /* Insert before. */ LIST_INSERT_BEFORE(n1, n2, entries); /* Forward traversal. */ for (np = head.lh_first; np != NULL; np = np->entries.le_next) np-> ... while (head.lh_first != NULL) /* Delete. */ LIST_REMOVE(head.lh_first, entries); TTAAIILL QQUUEEUUEESS A tail queue is headed by a structure defined by the TTAAIILLQQ__HHEEAADD macro. This structure contains a pair of pointers, one to the first element in the tail queue and the other to the last element in the tail queue. The elements are doubly linked so that an arbitrary element can be removed without traversing the tail queue. New elements can be added to the queue after an existing element, before an existing element, at the head of the queue, or at the end the queue. A _T_A_I_L_Q___H_E_A_D structure is de- clared as follows: TAILQ_HEAD(HEADNAME, TYPE) head; where HEADNAME is the name of the structure to be defined, and TYPE is the type of the elements to be linked into the tail queue. A pointer to the head of the tail queue can later be declared as: struct HEADNAME *headp; (The names head and headp are user selectable.) The macro TTAAIILLQQ__EENNTTRRYY declares a structure that connects the elements in the tail queue. The macro TTAAIILLQQ__IINNIITT initializes the tail queue referenced by _h_e_a_d. The macro TTAAIILLQQ__IINNSSEERRTT__HHEEAADD inserts the new element _e_l_m at the head of the tail queue. The macro TTAAIILLQQ__IINNSSEERRTT__TTAAIILL inserts the new element _e_l_m at the end of the tail queue. The macro TTAAIILLQQ__IINNSSEERRTT__AAFFTTEERR inserts the new element _e_l_m after the ele- ment _l_i_s_t_e_l_m. The macro TTAAIILLQQ__IINNSSEERRTT__BBEEFFOORREE inserts the new element _e_l_m before the ele- ment _l_i_s_t_e_l_m. The macro TTAAIILLQQ__RREEMMOOVVEE removes the element _e_l_m from the tail queue. TTAAIILL QQUUEEUUEE EEXXAAMMPPLLEE TAILQ_HEAD(tailhead, entry) head; struct tailhead *headp; /* Tail queue head. */ struct entry { ... TAILQ_ENTRY(entry) entries; /* Tail queue. */ ... } *n1, *n2, *np; TAILQ_INIT(&head); /* Initialize the queue. */ n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ TAILQ_INSERT_HEAD(&head, n1, entries); n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ TAILQ_INSERT_TAIL(&head, n1, entries); n2 = malloc(sizeof(struct entry)); /* Insert after. */ TAILQ_INSERT_AFTER(&head, n1, n2, entries); n2 = malloc(sizeof(struct entry)); /* Insert before. */ TAILQ_INSERT_BEFORE(n1, n2, entries); /* Forward traversal. */ for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next) np-> ... /* Delete. */ while (head.tqh_first != NULL) TAILQ_REMOVE(&head, head.tqh_first, entries); CCIIRRCCUULLAARR QQUUEEUUEESS A circular queue is headed by a structure defined by the CCIIRRCCLLEEQQ__HHEEAADD macro. This structure contains a pair of pointers, one to the first ele- ment in the circular queue and the other to the last element in the cir- cular queue. The elements are doubly linked so that an arbitrary element can be removed without traversing the queue. New elements can be added to the queue after an existing element, before an existing element, at 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- ture is declared as follows: CIRCLEQ_HEAD(HEADNAME, TYPE) head; where HEADNAME is the name of the structure to be defined, and TYPE is the type of the elements to be linked into the circular queue. A pointer to the head of the circular queue can later be declared as: struct HEADNAME *headp; (The names head and headp are user selectable.) The macro CCIIRRCCLLEEQQ__EENNTTRRYY declares a structure that connects the elements in the circular queue. The macro CCIIRRCCLLEEQQ__IINNIITT initializes the circular queue referenced by _h_e_a_d. The macro CCIIRRCCLLEEQQ__IINNSSEERRTT__HHEEAADD inserts the new element _e_l_m at the head of the circular queue. The macro CCIIRRCCLLEEQQ__IINNSSEERRTT__TTAAIILL inserts the new element _e_l_m at the end of the circular queue. The macro CCIIRRCCLLEEQQ__IINNSSEERRTT__AAFFTTEERR inserts the new element _e_l_m after the ele- ment _l_i_s_t_e_l_m. The macro CCIIRRCCLLEEQQ__IINNSSEERRTT__BBEEFFOORREE inserts the new element _e_l_m before the element _l_i_s_t_e_l_m. The macro CCIIRRCCLLEEQQ__RREEMMOOVVEE removes the element _e_l_m from the circular queue. CCIIRRCCUULLAARR QQUUEEUUEE EEXXAAMMPPLLEE CIRCLEQ_HEAD(circleq, entry) head; struct circleq *headp; /* Circular queue head. */ struct entry { ... CIRCLEQ_ENTRY entries; /* Circular queue. */ ... } *n1, *n2, *np; CIRCLEQ_INIT(&head); /* Initialize the circular queue. */ n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ CIRCLEQ_INSERT_HEAD(&head, n1, entries); n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ CIRCLEQ_INSERT_TAIL(&head, n1, entries); n2 = malloc(sizeof(struct entry)); /* Insert after. */ CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); n2 = malloc(sizeof(struct entry)); /* Insert before. */ CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); /* Forward traversal. */ for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next) np-> ... /* Reverse traversal. */ for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev) np-> ... /* Delete. */ while (head.cqh_first != (void *)&head) CIRCLEQ_REMOVE(&head, head.cqh_first, entries); HHIISSTTOORRYY The qquueeuuee functions first appeared in 4.4BSD. 4th Berkeley Distribution December 18, 1995 5