Source/LinkedList.h

   1 /*
   2 Copyright (C) 2003, 2010 - Wolfire Games
   3
   4 This file is part of Lugaru.
   5
   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.
  10
  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.
  14
  15 See the GNU General Public License for more details.
  16
  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.
  20 */
  21
  22 /*
  23  * Copyright (c) 1999-2002 Apple Computer, Inc. All rights reserved.
  24  *
  25  * @APPLE_LICENSE_HEADER_START@
  26  *
  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
  33  * this file.
  34  *
  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
  41  * under the License.
  42  *
  43  * @APPLE_LICENSE_HEADER_END@
  44  *
  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 $
  47  */
  48
  49
  50 /*
  51         File:           LinkedList.h
  52
  53         Contains:
  54
  55 */
  56
  57 #ifndef __LINKEDLIST__
  58 #define __LINKEDLIST__
  59
  60
  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)
  65
  66 #include <stddef.h>             //for OTGetLinkObject replacement
  67
  68 #include "OPUtils.h"    //for true/false
  69
  70 #if (windows_build)
  71
  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
  75 {
  76         public:
  77                 NMBoolean locked;
  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);}
  86
  87         CRITICAL_SECTION theCriticalSection;
  88 };
  89 #endif //windows_build
  90
  91 #if (posix_build)
  92 #include <pthread.h>
  93 class OSCriticalSection
  94 {
  95         public:
  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);}
 101
 102                 pthread_mutex_t theMutex;
 103 };
 104
 105 #endif //(posix_build)
 106
 107 /*      -------------------------------------------------------------------------
 108         ** OTLIFO
 109         **
 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         ------------------------------------------------------------------------- */
 116
 117         class OTLink;
 118         class OTLIFO;
 119
 120         class OTLink
 121         {
 122                 public:
 123                         OTLink* fNext;
 124                         void    Init()
 125                                                 { fNext = NULL; }
 126         };
 127
 128         class OTLIFO
 129         {
 130                 public:
 131                         OSCriticalSection theLock;
 132                         OTLink* fHead;
 133
 134                         void    Init()
 135                                         { fHead = NULL; }
 136
 137                         void    Enqueue(OTLink* link)
 138                                                         {
 139                                                                 while (true) {if (theLock.acquire()) break;}
 140                                                                 link->fNext = fHead;
 141                                                                 fHead = link;
 142                                                                 theLock.release();
 143                                                         }
 144
 145
 146                         OTLink* Dequeue()
 147                                                         {
 148                                                                 while (true) {if (theLock.acquire()) break;}
 149                                                                 OTLink *origHead = fHead;
 150                                                                 fHead = fHead->fNext;
 151                                                                 theLock.release();
 152                                                                 return origHead;
 153                                                         }
 154
 155
 156                         OTLink* StealList()
 157                                                         {
 158                                                                 while (true) {if (theLock.acquire()) break;}
 159                                                                 OTLink *origHead = fHead;
 160                                                                 fHead = NULL;
 161                                                                 theLock.release();
 162                                                                 return origHead;
 163                                                         }
 164
 165
 166                         NMBoolean       IsEmpty()
 167                                                         {
 168                                                                 return fHead == NULL;
 169                                                         }
 170         };
 171
 172 /*      -------------------------------------------------------------------------
 173         ** OTList
 174         **
 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         ------------------------------------------------------------------------- */
 178
 179         typedef struct OTList   OTList;
 180
 181                 typedef NMBoolean (*OTListSearchProcPtr)(const void* ref, OTLink* linkToCheck);
 182                 //
 183                 // Remove the last link from the list
 184                 //
 185         extern OTLink*          OTRemoveLast(OTList* pList);
 186                 //
 187                 // Return the first link from the list
 188                 //
 189         extern OTLink*          OTGetFirst(OTList* pList);
 190                 //
 191                 // Return the last link from the list
 192                 //
 193         extern OTLink*          OTGetLast(OTList* pList);
 194                 //
 195                 // Return true if the link is present in the list
 196                 //
 197         extern NMBoolean                OTIsInList(OTList* pList, OTLink* link);
 198                 //
 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.
 204                 //
 205         extern OTLink*          OTFindLink(OTList* pList, OTListSearchProcPtr proc, const void* refPtr);
 206                 //
 207                 // Remove the specified link from the list, returning true if it was found
 208                 //
 209         extern NMBoolean                OTRemoveLink(OTList*, OTLink*);
 210                 //
 211                 // Similar to OTFindLink, but it also removes it from the list.
 212                 //
 213         extern OTLink*          OTFindAndRemoveLink(OTList* pList, OTListSearchProcPtr proc, const void* refPtr);
 214                 //
 215                 // Return the "index"th link in the list
 216                 //
 217         extern OTLink*          OTGetIndexedLink(OTList* pList, size_t index);
 218
 219         struct OTList
 220         {
 221                 OTLink*         fHead;
 222
 223                 void            Init()
 224                                                 { fHead = NULL; }
 225
 226                 NMBoolean               IsEmpty()
 227                                                 { return fHead == NULL; }
 228
 229                 void            AddFirst(OTLink* link)
 230                                                         {
 231                                                                 link->fNext = fHead;
 232                                                                 fHead = link;
 233                                                         }
 234
 235                 void            AddLast(OTLink* link)
 236                                                         {
 237                                                                 if (fHead == NULL)
 238                                                                         fHead = link->fNext;
 239                                                                 else
 240                                                                 {
 241                                                                         OTLink *current = fHead;
 242
 243                                                                         while (current->fNext != NULL)
 244                                                                                 current = current->fNext;
 245
 246                                                                         current->fNext = link;
 247                                                                 }
 248
 249
 250                                                                 link->fNext = fHead;
 251                                                                 fHead = link;
 252                                                         }
 253
 254
 255                 OTLink*         GetFirst()
 256                                                 { return OTGetFirst(this); }
 257
 258                 OTLink*         GetLast()
 259                                                 { return OTGetLast(this); }
 260
 261                 OTLink*         RemoveFirst()
 262                                                         {
 263                                                                 OTLink *origHead = fHead;
 264                                                                 fHead = fHead->fNext;
 265                                                                 return origHead;
 266                                                         }
 267
 268                 OTLink*         RemoveLast()
 269                                                 { return OTRemoveLast(this); }
 270
 271                 NMBoolean               IsInList(OTLink* link)
 272                                                 { return OTIsInList(this, link); }
 273
 274                 OTLink*         FindLink(OTListSearchProcPtr proc, const void* ref)
 275                                                 { return OTFindLink(this, proc, ref); }
 276
 277                 NMBoolean               RemoveLink(OTLink* link)
 278                                                 { return OTRemoveLink(this, link); }
 279
 280                 OTLink*         RemoveLink(OTListSearchProcPtr proc, const void* ref)
 281                                                 { return OTFindAndRemoveLink(this, proc, ref); }
 282
 283                 OTLink*         GetIndexedLink(size_t index)
 284                                                 { return OTGetIndexedLink(this, index); }
 285         };
 286
 287
 288 //FIXME!!  this is a recursive function and will crash and burn on large lists
 289 static OTLink* OTReverseList(OTLink *headRef)
 290 {
 291         OTLink  *first;
 292         OTLink  *rest;
 293
 294         if (headRef == NULL) return NULL;
 295
 296         first = headRef;
 297         rest = (OTLink *) first->fNext;
 298
 299         if (rest == NULL) return headRef;
 300
 301         rest = OTReverseList(rest);
 302
 303         first->fNext->fNext = first;
 304         first->fNext = NULL;
 305
 306         return rest;
 307 }
 308
 309
 310         #define OTGetLinkObject(link, struc, field)     \
 311                 ((struc*)((char*)(link) - offsetof(struc, field)))
 312
 313 #endif //!macintosh_build
 314 #endif  /* __LINKEDLIST__ */
 315
 316