Stripe_w/queue.h

   1
   2 /********************************************************************/
   3 /*   STRIPE: converting a polygonal model to triangle strips
   4      Francine Evans, 1996.
   5      SUNY @ Stony Brook
   6      Advisors: Steven Skiena and Amitabh Varshney
   7 */
   8 /********************************************************************/
   9
  10 /*---------------------------------------------------------------------*/
  11 /*   STRIPE:queue.h
  12 -----------------------------------------------------------------------*/
  13
  14 #ifndef QUEUE_INCLUDED
  15 #define QUEUE_INCLUDED
  16
  17 /*        %%s  Node      */
  18 /*****************************************************************
  19      This structure is used to store the List linkage information of a
  20 ListInfo structure.  It contains all the necessary information for the
  21 List functions to function properly.  This structure must be the first
  22 one defined in any block of memory to be linked with the List functions.
  23 for an example of the used of The Node structure look in the files
  24 ipd2dms.c and ipd2man.h
  25 ******************************************************************/
  26 #include <stdio.h>
  27 #define FALSE 0
  28 #define TRUE  1
  29 typedef struct
  30 {
  31      void  *Next;
  32      void  *Previous;
  33 }
  34      Node, * PNODE;
  35
  36 /*****************************************************************
  37      Next     :  is a pointer to the next structure in this List.
  38      Previous :  is a pointer to the previous structure in this List.
  39      priority :  this is the priority of this structure in the List.  The
  40                  highest priority is 0.  This field is only used by the
  41                  functions EnQue and DeQue.
  42 ******************************************************************/
  43 /*        %%e       */
  44
  45
  46 /*        %%s  ListInfo      */
  47
  48 /*****************************************************************
  49       This is the general means of linking application defined information into
  50 Lists and queues.  All structures must begin with the Node Structure.  All
  51 other data in the structure is user definable.
  52 ******************************************************************/
  53
  54 typedef struct List
  55 {
  56      Node     ListNode;       /*  link to the next Listinfo Structure  */
  57      /*  user definable data  */
  58 }    ListInfo, *PLISTINFO;
  59
  60 /*****************************************************************
  61      ListNode  :  this is the required node structure for the List
  62                   mainpulation functions.  This must be the first
  63                   element of a user definable structure.
  64
  65      In order for an application to use the List routines, it must define
  66 a structure with all the needed information.  The first element in the
  67 user definable structure must be a Node structure.  The Node structure
  68 contains all the necessary information for the List routines to do their
  69 magic.  For an example of a user defined List structure see the file
  70 ipd2i.h.  The User definable structure can be passed to any List function
  71 that excepts a pointer to a ListInfo structure.
  72
  73 example:
  74
  75 typedef  mstruct
  76 {
  77      Node   ListNode;
  78      int    a,b,c,d,e,f,g;
  79 }
  80      mystruct;
  81
  82      the user definable portion of the above structure is represented by
  83 the integers a,b,c,d,e,f,g.  When passing this structure to a List
  84 function a cast of (ListInfo *) must be made to satisify the "C" complier.
  85 ******************************************************************/
  86 /*        %%e       */
  87
  88
  89 /*        %%s ListHead        */
  90 /*****************************************************************
  91      ListHead is used as a header to a List.  LHeaders[0] points to the
  92 head of the List.  LHeaders[1] points the tail of the list.  When
  93 accessing these variables use the defines  LISTHEAD, LISTTAIL.
  94 ******************************************************************/
  95
  96 typedef struct LHead
  97 {
  98      PLISTINFO  LHeaders[2];
  99      int         NumList;
 100 }
 101 ListHead, *PLISTHEAD;
 102
 103 /*****************************************************************
 104      LHeaders   :  this is an array of two pointers to ListInfo structures.
 105                    This information is used to point to the head and tail of
 106                    a list.
 107      NumList    :  this integer hold the number of structures linked into this
 108                    list.
 109
 110 ListHead #define:
 111
 112      LISTHEAD  :  when Peeking down a list this specifies you should
 113                   start at the Head of the list and search downward.
 114
 115      LISTTAIL  :  when Peeking down a list this specifies you should
 116                   start at the tail of the list and search foward.
 117  ******************************************************************/
 118
 119 #define  LISTHEAD  0
 120
 121 #define  LISTTAIL  1
 122 /*        %%e       */
 123
 124 typedef int BOOL;
 125 typedef void * PVOID;
 126
 127 #define PEEKFROMHEAD( lh, ind )     ( PeekList( (lh), LISTHEAD, (ind) ) )
 128 #define PEEKFROMTAIL( lh, ind )     ( PeekList( (lh), LISTTAIL, (ind) ) )
 129 #define EMPTYLIST( lh )             ( ( (lh)->LHeaders[LISTHEAD] == NULL ) )
 130
 131 /*   General utility routines   */
 132 /*        %%s QueRoutines          */
 133 BOOL    InitList      ( PLISTHEAD );
 134
 135 /*****************************************************************
 136      InitList :  Initialize a new list structure for use with the List
 137                  routines
 138
 139      INPUTS   :  LHead : a pointer to a ListHead structure.
 140      OUTPUT   :  a boolean value TRUE if no errors occured FALSE
 141                  otherwise
 142 ******************************************************************/
 143
 144
 145 PLISTINFO  PeekList      ( PLISTHEAD, int, int   );
 146
 147 /*****************************************************************
 148      PeekList :  This funciton peeks down a list for the N'th element
 149                  from the HEAD or TAIL of the list
 150
 151      INPUTS   :  LHead    :  a pointer to a List head structure.
 152                  from     :  can either search from the HEAD or TAIL
 153                              of the list
 154                  where    :  how many nodes from the begining should the
 155                              List routines look.
 156      OUTPUT   :  a pointer to a ListInfo structure identified by
 157                  from/where or NULL if an error occurred.
 158 ******************************************************************/
 159
 160
 161 PLISTINFO   RemoveList( PLISTHEAD LHead, PLISTINFO LInfo );
 162
 163
 164 /*****************************************************************
 165      RemoveList: Remove a ListInfo structure from a List.
 166
 167      INPUTS    : LHead  :  a pointer to a ListHead structure.
 168                  LInfo  :  a pointer to the ListInfo structure to remove
 169                            from the list.
 170      OUTPUT    : a pointer to the ListInfo structure that was removed or
 171                  NULL if an error occurred.
 172 ******************************************************************/
 173
 174 BOOL  InsertNode( PLISTHEAD LHead, int nPos, PLISTINFO LInfo );
 175
 176 /*****************************************************************
 177      InsertNode: add a node to a list after a given node
 178
 179      INPUTS    : LHead : a pointer to a ListHead structure.
 180                  nPos  : the position to insert the node into
 181                  LInfo : a pointer to the new node to add to the list.
 182      OUTPUT: a boolean value TRUE if all goes well false otherwise
 183 *****************************************************************/
 184
 185 BOOL   AddHead       ( PLISTHEAD, PLISTINFO );
 186
 187 /*****************************************************************
 188      AddHead   : add a ListInfo structure to the HEAD of a list.
 189
 190      INPUTS    : LHead  : a pointer to a ListHead structure of the list
 191                           to add to.
 192                  LInfo  : a pointer to the ListInfo structure to add to
 193                           the list.
 194      OUTPUT    : A boolean value TRUE if no errors occurred FALSE
 195                  otherwise.
 196 ******************************************************************/
 197
 198
 199 BOOL     AddTail       ( PLISTHEAD, PLISTINFO );
 200
 201 /*****************************************************************
 202      AddTail   : Add a ListInfo structure to the TAIL of a list.
 203
 204      INPUTS    : LHead  : a pointer to a ListHead structure of the List
 205                           to add to.
 206                  LInfo  : a pointer to the ListInfo structure to add to
 207                           the List.
 208      OUTPUT    : a boolean value TRUE if no errors occurred FALSE
 209                  otherwise.
 210 ******************************************************************/
 211
 212
 213 PLISTINFO  RemTail       ( PLISTHEAD );
 214
 215 /*****************************************************************
 216      RemTail   : Remove a ListInfo structure from the TAIL of a List.
 217
 218      INPUTS    : LHead  : a pointer to a ListHead structure of the List
 219                           to remove from.
 220      OUTPUT    : a pointer to the ListInfo structure that was removed
 221                  or NULL if an error occurred.
 222 ******************************************************************/
 223
 224
 225 PLISTINFO  RemHead       ( PLISTHEAD );
 226
 227 /*****************************************************************
 228      RemHead   : Remove a ListInfo structure from the Head of a List.
 229
 230      INPUTS    : LHead  : a pointer to a ListHead structure of the List
 231                           to remove from.
 232      OUTPUT    : a pointer to the ListInfo structure that was removed or
 233                  NULL if an error occurred.
 234 ******************************************************************/
 235
 236 PLISTINFO  SearchList(
 237                         PLISTHEAD lpListHead,
 238                         PVOID lpSKey,
 239                         int ( * CompareCallBack) ( PVOID, PVOID ) );
 240
 241 /*****************************************************************
 242   SearchList:
 243         Try to find a specific node in the queue whose key matches with
 244    searching key. Return the pointer to that node if found, return NULL
 245    otherwise
 246
 247    Input:
 248      lpHashTbl       => a far pointer to the hash table
 249      lpKey           => a far poniter to searching key
 250      CompareCallBack => comparision function
 251
 252    Output: a far pointer to the node to be found
 253
 254  ******************************************************************/
 255
 256 #define           NumOnList(lh) ( ((lh)->NumList)        )
 257
 258 /*****************************************************************
 259      NumOnList: Returns the number of Nodes linked to a ListHead
 260                 structure.  This number is maintained by the List
 261                 routines.
 262 ******************************************************************/
 263
 264 #define           GetNextNode(pli) ( ((pli)->ListNode.Next) )
 265
 266 /********************************************************
 267      GetNextNode: This macro returns the Next Structure in this list.
 268                   This macro will return NULL if no more structures are
 269                   in the List.
 270 *********************************************************/
 271
 272 #define           GetPrevNode(pli) ( ((pli)->ListNode.Previous) )
 273
 274 /********************************************************
 275      GetPrevNode: This macro returns the Previous Structure in this list.
 276                   This macro will reutrn NULL if no more structures are
 277                   in the List.
 278 ********************************************************/
 279 /*        %%e       */
 280
 281 #endif
 282
 283