2 Copyright (C) 2003, 2010 - Wolfire Games
4 This file is part of Lugaru.
6 Lugaru is free software; you can redistribute it and/or
7 modify it under the terms of the GNU General Public License
8 as published by the Free Software Foundation; either version 2
9 of the License, or (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
15 See the GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
23 * Copyright (c) 1999-2002 Apple Computer, Inc. All rights reserved.
25 * @APPLE_LICENSE_HEADER_START@
27 * Portions Copyright (c) 1999-2002 Apple Computer, Inc. All Rights
28 * Reserved. This file contains Original Code and/or Modifications of
29 * Original Code as defined in and that are subject to the Apple Public
30 * Source License Version 1.1 (the "License"). You may not use this file
31 * except in compliance with the License. Please obtain a copy of the
32 * License at http://www.apple.com/publicsource and read it before using
35 * The Original Code and all software distributed under the License are
36 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
37 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
38 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
39 * FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT. Please see the
40 * License for the specific language governing rights and limitations
43 * @APPLE_LICENSE_HEADER_END@
45 * Modified: $Date: 2002/04/27 20:52:48 $
46 * Revision: $Id: LinkedList.h,v 1.3 2002/04/27 20:52:48 lane Exp $
57 #ifndef __LINKEDLIST__
58 #define __LINKEDLIST__
61 //we cant just use "macintosh_build" - the mac macho_build is designated as "posix_build" but may
62 //include open transport in some cases
63 #ifndef __OPENTRANSPORT__
64 //#if (!macintosh_build)
66 #include <stddef.h> //for OTGetLinkObject replacement
68 #include "OPUtils.h" //for true/false
72 // ECF 010928 win32 syncronization routines for safe critical sections. We can't simply use TryEnterCriticalSection()
73 // to return a true/false value because it's not available in win95 and 98
74 class OSCriticalSection
78 OSCriticalSection() {locked = false; InitializeCriticalSection(&theCriticalSection);}
79 ~OSCriticalSection() {DeleteCriticalSection(&theCriticalSection);}
80 NMBoolean acquire() { if (locked == true) return false; //dont have to wait in this case
81 EnterCriticalSection(&theCriticalSection);
82 if (locked) {LeaveCriticalSection(&theCriticalSection); return false;}
83 else {locked = true; LeaveCriticalSection(&theCriticalSection); return true;}}
84 void release() { EnterCriticalSection(&theCriticalSection);
85 locked = false; LeaveCriticalSection(&theCriticalSection);}
87 CRITICAL_SECTION theCriticalSection;
89 #endif //windows_build
93 class OSCriticalSection
96 OSCriticalSection() {pthread_mutex_init(&theMutex,NULL);}
97 ~OSCriticalSection() {pthread_mutex_destroy(&theMutex);}
98 NMBoolean acquire() { int error = pthread_mutex_trylock(&theMutex);
99 if (error) return false; else return true;}
100 void release() { pthread_mutex_unlock(&theMutex);}
102 pthread_mutex_t theMutex;
105 #endif //(posix_build)
107 /* -------------------------------------------------------------------------
110 ** These are functions to implement a LIFO list that is interrupt-safe.
111 ** The only function which is not is OTReverseList. Normally, you create
112 ** a LIFO list, populate it at interrupt time, and then use OTLIFOStealList
113 ** to atomically remove the list, and OTReverseList to flip the list so that
114 ** it is a FIFO list, which tends to be more useful.
115 ------------------------------------------------------------------------- */
131 OSCriticalSection theLock;
137 void Enqueue(OTLink* link)
139 while (true) {if (theLock.acquire()) break;}
148 while (true) {if (theLock.acquire()) break;}
149 OTLink *origHead = fHead;
150 fHead = fHead->fNext;
158 while (true) {if (theLock.acquire()) break;}
159 OTLink *origHead = fHead;
168 return fHead == NULL;
172 /* -------------------------------------------------------------------------
175 ** An OTList is a non-interrupt-safe list, but has more features than the
176 ** OTLIFO list. It is a standard singly-linked list.
177 ------------------------------------------------------------------------- */
179 typedef struct OTList OTList;
181 typedef NMBoolean (*OTListSearchProcPtr)(const void* ref, OTLink* linkToCheck);
183 // Remove the last link from the list
185 extern OTLink* OTRemoveLast(OTList* pList);
187 // Return the first link from the list
189 extern OTLink* OTGetFirst(OTList* pList);
191 // Return the last link from the list
193 extern OTLink* OTGetLast(OTList* pList);
195 // Return true if the link is present in the list
197 extern NMBoolean OTIsInList(OTList* pList, OTLink* link);
199 // Find a link in the list which matches the search criteria
200 // established by the search proc and the refPtr. This is done
201 // by calling the search proc, passing it the refPtr and each
202 // link in the list, until the search proc returns true.
203 // NULL is returned if the search proc never returned true.
205 extern OTLink* OTFindLink(OTList* pList, OTListSearchProcPtr proc, const void* refPtr);
207 // Remove the specified link from the list, returning true if it was found
209 extern NMBoolean OTRemoveLink(OTList*, OTLink*);
211 // Similar to OTFindLink, but it also removes it from the list.
213 extern OTLink* OTFindAndRemoveLink(OTList* pList, OTListSearchProcPtr proc, const void* refPtr);
215 // Return the "index"th link in the list
217 extern OTLink* OTGetIndexedLink(OTList* pList, size_t index);
227 { return fHead == NULL; }
229 void AddFirst(OTLink* link)
235 void AddLast(OTLink* link)
241 OTLink *current = fHead;
243 while (current->fNext != NULL)
244 current = current->fNext;
246 current->fNext = link;
256 { return OTGetFirst(this); }
259 { return OTGetLast(this); }
261 OTLink* RemoveFirst()
263 OTLink *origHead = fHead;
264 fHead = fHead->fNext;
269 { return OTRemoveLast(this); }
271 NMBoolean IsInList(OTLink* link)
272 { return OTIsInList(this, link); }
274 OTLink* FindLink(OTListSearchProcPtr proc, const void* ref)
275 { return OTFindLink(this, proc, ref); }
277 NMBoolean RemoveLink(OTLink* link)
278 { return OTRemoveLink(this, link); }
280 OTLink* RemoveLink(OTListSearchProcPtr proc, const void* ref)
281 { return OTFindAndRemoveLink(this, proc, ref); }
283 OTLink* GetIndexedLink(size_t index)
284 { return OTGetIndexedLink(this, index); }
288 //FIXME!! this is a recursive function and will crash and burn on large lists
289 static OTLink* OTReverseList(OTLink *headRef)
294 if (headRef == NULL) return NULL;
297 rest = (OTLink *) first->fNext;
299 if (rest == NULL) return headRef;
301 rest = OTReverseList(rest);
303 first->fNext->fNext = first;
310 #define OTGetLinkObject(link, struc, field) \
311 ((struc*)((char*)(link) - offsetof(struc, field)))
313 #endif //!macintosh_build
314 #endif /* __LINKEDLIST__ */