|
Packit Service |
dc579d |
/*
|
|
Packit Service |
dc579d |
Copyright (c) 2007-2009, Troy D. Hanson
|
|
Packit Service |
dc579d |
All rights reserved.
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
Redistribution and use in source and binary forms, with or without
|
|
Packit Service |
dc579d |
modification, are permitted provided that the following conditions are met:
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
* Redistributions of source code must retain the above copyright
|
|
Packit Service |
dc579d |
notice, this list of conditions and the following disclaimer.
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
|
|
Packit Service |
dc579d |
IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
|
|
Packit Service |
dc579d |
TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
|
|
Packit Service |
dc579d |
PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
|
|
Packit Service |
dc579d |
OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
|
Packit Service |
dc579d |
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
|
Packit Service |
dc579d |
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
|
|
Packit Service |
dc579d |
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
|
|
Packit Service |
dc579d |
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
|
|
Packit Service |
dc579d |
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
|
|
Packit Service |
dc579d |
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
Packit Service |
dc579d |
*/
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
#ifndef UTLIST_H
|
|
Packit Service |
dc579d |
#define UTLIST_H
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
#define UTLIST_VERSION 1.7
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
/* From: http://uthash.sourceforge.net/utlist.html */
|
|
Packit Service |
dc579d |
/*
|
|
Packit Service |
dc579d |
* This file contains macros to manipulate singly and doubly-linked lists.
|
|
Packit Service |
dc579d |
*
|
|
Packit Service |
dc579d |
* 1. LL_ macros: singly-linked lists.
|
|
Packit Service |
dc579d |
* 2. DL_ macros: doubly-linked lists.
|
|
Packit Service |
dc579d |
* 3. CDL_ macros: circular doubly-linked lists.
|
|
Packit Service |
dc579d |
*
|
|
Packit Service |
dc579d |
* To use singly-linked lists, your structure must have a "next" pointer.
|
|
Packit Service |
dc579d |
* To use doubly-linked lists, your structure must "prev" and "next" pointers.
|
|
Packit Service |
dc579d |
* Either way, the pointer to the head of the list must be initialized to NULL.
|
|
Packit Service |
dc579d |
*
|
|
Packit Service |
dc579d |
* ----------------.EXAMPLE -------------------------
|
|
Packit Service |
dc579d |
* struct item {
|
|
Packit Service |
dc579d |
* int id;
|
|
Packit Service |
dc579d |
* struct item *prev, *next;
|
|
Packit Service |
dc579d |
* }
|
|
Packit Service |
dc579d |
*
|
|
Packit Service |
dc579d |
* struct item *list = NULL:
|
|
Packit Service |
dc579d |
*
|
|
Packit Service |
dc579d |
* int main() {
|
|
Packit Service |
dc579d |
* struct item *item;
|
|
Packit Service |
dc579d |
* ... allocate and populate item ...
|
|
Packit Service |
dc579d |
* DL_APPEND(list, item);
|
|
Packit Service |
dc579d |
* }
|
|
Packit Service |
dc579d |
* --------------------------------------------------
|
|
Packit Service |
dc579d |
*
|
|
Packit Service |
dc579d |
* For doubly-linked lists, the append and delete macros are O(1)
|
|
Packit Service |
dc579d |
* For singly-linked lists, append and delete are O(n) but prepend is O(1)
|
|
Packit Service |
dc579d |
* The sort macro is O(n log(n)) for all types of single/double/circular lists.
|
|
Packit Service |
dc579d |
*/
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
/******************************************************************************
|
|
Packit Service |
dc579d |
* doubly linked list macros (non-circular) *
|
|
Packit Service |
dc579d |
*****************************************************************************/
|
|
Packit Service |
dc579d |
#define DL_PREPEND(head,add) \
|
|
Packit Service |
dc579d |
do { \
|
|
Packit Service |
dc579d |
(add)->next = head; \
|
|
Packit Service |
dc579d |
if (head) { \
|
|
Packit Service |
dc579d |
(add)->prev = (head)->prev; \
|
|
Packit Service |
dc579d |
(head)->prev = (add); \
|
|
Packit Service |
dc579d |
} else { \
|
|
Packit Service |
dc579d |
(add)->prev = (add); \
|
|
Packit Service |
dc579d |
} \
|
|
Packit Service |
dc579d |
(head) = (add); \
|
|
Packit Service |
dc579d |
} while (0)
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
#define DL_APPEND(head,add) \
|
|
Packit Service |
dc579d |
do { \
|
|
Packit Service |
dc579d |
if (head) { \
|
|
Packit Service |
dc579d |
(add)->prev = (head)->prev; \
|
|
Packit Service |
dc579d |
(head)->prev->next = (add); \
|
|
Packit Service |
dc579d |
(head)->prev = (add); \
|
|
Packit Service |
dc579d |
(add)->next = NULL; \
|
|
Packit Service |
dc579d |
} else { \
|
|
Packit Service |
dc579d |
(head)=(add); \
|
|
Packit Service |
dc579d |
(head)->prev = (head); \
|
|
Packit Service |
dc579d |
(head)->next = NULL; \
|
|
Packit Service |
dc579d |
} \
|
|
Packit Service |
dc579d |
} while (0);
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
#define DL_DELETE(head,del) \
|
|
Packit Service |
dc579d |
do { \
|
|
Packit Service |
dc579d |
if ((del)->prev == (del)) { \
|
|
Packit Service |
dc579d |
(head)=NULL; \
|
|
Packit Service |
dc579d |
} else if ((del)==(head)) { \
|
|
Packit Service |
dc579d |
(del)->next->prev = (del)->prev; \
|
|
Packit Service |
dc579d |
(head) = (del)->next; \
|
|
Packit Service |
dc579d |
} else { \
|
|
Packit Service |
dc579d |
(del)->prev->next = (del)->next; \
|
|
Packit Service |
dc579d |
if ((del)->next) { \
|
|
Packit Service |
dc579d |
(del)->next->prev = (del)->prev; \
|
|
Packit Service |
dc579d |
} else { \
|
|
Packit Service |
dc579d |
(head)->prev = (del)->prev; \
|
|
Packit Service |
dc579d |
} \
|
|
Packit Service |
dc579d |
} \
|
|
Packit Service |
dc579d |
} while (0);
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
#define DL_FOREACH(head,el) \
|
|
Packit Service |
dc579d |
for(el=head;el;el=el->next)
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
#define DL_FOREACH_SAFE(head,el,tmp) \
|
|
Packit Service |
dc579d |
for(el=head,tmp=el->next;el;el=tmp,tmp=(el) ? (el->next) : NULL)
|
|
Packit Service |
dc579d |
|
|
Packit Service |
dc579d |
#endif /* UTLIST_H */
|
|
Packit Service |
dc579d |
|