1f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/************************************************************************** 2f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 3f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA. 4f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * All Rights Reserved. 5f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 6f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Permission is hereby granted, free of charge, to any person obtaining a 7f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * copy of this software and associated documentation files (the 8f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * "Software"), to deal in the Software without restriction, including 9f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * without limitation the rights to use, copy, modify, merge, publish, 10f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * distribute, sub license, and/or sell copies of the Software, and to 11f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * permit persons to whom the Software is furnished to do so, subject to 12f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * the following conditions: 13f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 14f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL 17f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, 18f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 19f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE 20f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * USE OR OTHER DEALINGS IN THE SOFTWARE. 21f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 22f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * The above copyright notice and this permission notice (including the 23f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * next paragraph) shall be included in all copies or substantial portions 24f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * of the Software. 25f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 26f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org **************************************************************************/ 27f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 28f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 29f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \file 30f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * List macros heavily inspired by the Linux kernel 31f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * list handling. No list looping yet. 32f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 33f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Is not threadsafe, so common operations need to 34f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * be protected using an external mutex. 35f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 36f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 37f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#ifndef _U_DOUBLE_LIST_H_ 38f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define _U_DOUBLE_LIST_H_ 39f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 40f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 41f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include <stddef.h> 42f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "pipe/p_compiler.h" 43f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 44f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 45f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstruct list_head 46f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 47f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct list_head *prev; 48f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct list_head *next; 49f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 50f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 51f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstatic INLINE void list_inithead(struct list_head *item) 52f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 53f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->prev = item; 54f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->next = item; 55f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 56f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 57f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstatic INLINE void list_add(struct list_head *item, struct list_head *list) 58f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 59f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->prev = list; 60f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->next = list->next; 61f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org list->next->prev = item; 62f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org list->next = item; 63f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 64f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 65f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstatic INLINE void list_addtail(struct list_head *item, struct list_head *list) 66f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 67f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->next = list; 68f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->prev = list->prev; 69f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org list->prev->next = item; 70f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org list->prev = item; 71f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 72f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 73f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstatic INLINE void list_replace(struct list_head *from, struct list_head *to) 74f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 75f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org to->prev = from->prev; 76f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org to->next = from->next; 77f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org from->next->prev = to; 78f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org from->prev->next = to; 79f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 80f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 81f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstatic INLINE void list_del(struct list_head *item) 82f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 83f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->prev->next = item->next; 84f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->next->prev = item->prev; 85f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->prev = item->next = NULL; 86f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 87f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 88f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstatic INLINE void list_delinit(struct list_head *item) 89f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 90f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->prev->next = item->next; 91f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->next->prev = item->prev; 92f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->next = item; 93f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->prev = item; 94f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 95f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 96f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LIST_INITHEAD(__item) list_inithead(__item) 97f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LIST_ADD(__item, __list) list_add(__item, __list) 98f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LIST_ADDTAIL(__item, __list) list_addtail(__item, __list) 99f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LIST_REPLACE(__from, __to) list_replace(__from, __to) 100f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LIST_DEL(__item) list_del(__item) 101f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LIST_DELINIT(__item) list_delinit(__item) 102f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 103f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LIST_ENTRY(__type, __item, __field) \ 104f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ((__type *)(((char *)(__item)) - offsetof(__type, __field))) 105f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 106f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LIST_IS_EMPTY(__list) \ 107f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ((__list)->next == (__list)) 108f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 109f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 110f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Cast from a pointer to a member of a struct back to the containing struct. 111f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 112f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 'sample' MUST be initialized, or else the result is undefined! 113f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 114f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#ifndef container_of 115f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define container_of(ptr, sample, member) \ 116f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (void *)((char *)(ptr) \ 117f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org - ((char *)&(sample)->member - (char *)(sample))) 118f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#endif 119f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 120f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LIST_FOR_EACH_ENTRY(pos, head, member) \ 121f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (pos = NULL, pos = container_of((head)->next, pos, member); \ 122f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org &pos->member != (head); \ 123f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = container_of(pos->member.next, pos, member)) 124f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 125f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LIST_FOR_EACH_ENTRY_SAFE(pos, storage, head, member) \ 126f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (pos = NULL, pos = container_of((head)->next, pos, member), \ 127f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org storage = container_of(pos->member.next, pos, member); \ 128f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org &pos->member != (head); \ 129f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = storage, storage = container_of(storage->member.next, storage, member)) 130f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 131f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LIST_FOR_EACH_ENTRY_SAFE_REV(pos, storage, head, member) \ 132f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (pos = NULL, pos = container_of((head)->prev, pos, member), \ 133f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org storage = container_of(pos->member.prev, pos, member); \ 134f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org &pos->member != (head); \ 135f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = storage, storage = container_of(storage->member.prev, storage, member)) 136f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 137f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LIST_FOR_EACH_ENTRY_FROM(pos, start, head, member) \ 138f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (pos = NULL, pos = container_of((start), pos, member); \ 139f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org &pos->member != (head); \ 140f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = container_of(pos->member.next, pos, member)) 141f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 142f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LIST_FOR_EACH_ENTRY_FROM_REV(pos, start, head, member) \ 143f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (pos = NULL, pos = container_of((start), pos, member); \ 144f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org &pos->member != (head); \ 145f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = container_of(pos->member.prev, pos, member)) 146f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 147f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#endif /*_U_DOUBLE_LIST_H_*/ 148