subsys/win32k/freetype/src/base/ftlist.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftlist.c                                                               */
   4 /*                                                                         */
   5 /*    Generic list support for FreeType (body).                            */
   6 /*                                                                         */
   7 /*  Copyright 1996-2000 by                                                 */
   8 /*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
   9 /*                                                                         */
  10 /*  This file is part of the FreeType project, and may only be used,       */
  11 /*  modified, and distributed under the terms of the FreeType project      */
  12 /*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
  13 /*  this file you indicate that you have read the license and              */
  14 /*  understand and accept it fully.                                        */
  15 /*                                                                         */
  16 /***************************************************************************/
  17
  18   /*************************************************************************/
  19   /*                                                                       */
  20   /*  This file implements functions relative to list processing.  Its     */
  21   /*  data structures are defined in `freetype/internal/ftlist.h'.         */
  22   /*                                                                       */
  23   /*************************************************************************/
  24
  25
  26 #include <freetype/internal/ftlist.h>
  27 #include <freetype/internal/ftdebug.h>
  28 #include <freetype/internal/ftobjs.h>
  29
  30
  31   /*************************************************************************/
  32   /*                                                                       */
  33   /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
  34   /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
  35   /* messages during execution.                                            */
  36   /*                                                                       */
  37 #undef  FT_COMPONENT
  38 #define FT_COMPONENT  trace_list
  39
  40
  41   /*************************************************************************/
  42   /*                                                                       */
  43   /* <Function>                                                            */
  44   /*    FT_List_Find                                                       */
  45   /*                                                                       */
  46   /* <Description>                                                         */
  47   /*    Finds the list node for a given listed object.                     */
  48   /*                                                                       */
  49   /* <Input>                                                               */
  50   /*    list :: A pointer to the parent list.                              */
  51   /*    data :: The address of the listed object.                          */
  52   /*                                                                       */
  53   /* <Return>                                                              */
  54   /*    List node.  NULL if it wasn't found.                               */
  55   /*                                                                       */
  56   BASE_FUNC( FT_ListNode )  FT_List_Find( FT_List  list,
  57                                           void*    data )
  58   {
  59     FT_ListNode  cur;
  60
  61
  62     cur = list->head;
  63     while ( cur )
  64     {
  65       if ( cur->data == data )
  66         return cur;
  67
  68       cur = cur->next;
  69     }
  70
  71     return (FT_ListNode)0;
  72   }
  73
  74
  75   /*************************************************************************/
  76   /*                                                                       */
  77   /* <Function>                                                            */
  78   /*    FT_List_Add                                                        */
  79   /*                                                                       */
  80   /* <Description>                                                         */
  81   /*    Appends an element to the end of a list.                           */
  82   /*                                                                       */
  83   /* <InOut>                                                               */
  84   /*    list :: A pointer to the parent list.                              */
  85   /*    node :: The node to append.                                        */
  86   /*                                                                       */
  87   BASE_FUNC( void )  FT_List_Add( FT_List      list,
  88                                   FT_ListNode  node )
  89   {
  90     FT_ListNode  before = list->tail;
  91
  92
  93     node->next = 0;
  94     node->prev = before;
  95
  96     if ( before )
  97       before->next = node;
  98     else
  99       list->head = node;
 100
 101     list->tail = node;
 102   }
 103
 104
 105   /*************************************************************************/
 106   /*                                                                       */
 107   /* <Function>                                                            */
 108   /*    FT_List_Insert                                                     */
 109   /*                                                                       */
 110   /* <Description>                                                         */
 111   /*    Inserts an element at the head of a list.                          */
 112   /*                                                                       */
 113   /* <InOut>                                                               */
 114   /*    list :: A pointer to parent list.                                  */
 115   /*    node :: The node to insert.                                        */
 116   /*                                                                       */
 117   BASE_FUNC( void )  FT_List_Insert( FT_List      list,
 118                                      FT_ListNode  node )
 119   {
 120     FT_ListNode  after = list->head;
 121
 122
 123     node->next = after;
 124     node->prev = 0;
 125
 126     if ( !after )
 127       list->tail = node;
 128     else
 129       after->prev = node;
 130
 131     list->head = node;
 132   }
 133
 134
 135   /*************************************************************************/
 136   /*                                                                       */
 137   /* <Function>                                                            */
 138   /*    FT_List_Remove                                                     */
 139   /*                                                                       */
 140   /* <Description>                                                         */
 141   /*    Removes a node from a list.  This function doesn't check whether   */
 142   /*    the node is in the list!                                           */
 143   /*                                                                       */
 144   /* <Input>                                                               */
 145   /*    node :: The node to remove.                                        */
 146   /*                                                                       */
 147   /* <InOut>                                                               */
 148   /*    list :: A pointer to the parent list.                              */
 149   /*                                                                       */
 150   BASE_FUNC( void )  FT_List_Remove( FT_List      list,
 151                                      FT_ListNode  node )
 152   {
 153     FT_ListNode  before, after;
 154
 155
 156     before = node->prev;
 157     after  = node->next;
 158
 159     if ( before )
 160       before->next = after;
 161     else
 162       list->head = after;
 163
 164     if ( after )
 165       after->prev = before;
 166     else
 167       list->tail = before;
 168   }
 169
 170
 171   /*************************************************************************/
 172   /*                                                                       */
 173   /* <Function>                                                            */
 174   /*    FT_List_Up                                                         */
 175   /*                                                                       */
 176   /* <Description>                                                         */
 177   /*    Moves a node to the head/top of a list.  Used to maintain LRU      */
 178   /*    lists.                                                             */
 179   /*                                                                       */
 180   /* <InOut>                                                               */
 181   /*    list :: A pointer to the parent list.                              */
 182   /*    node :: The node to move.                                          */
 183   /*                                                                       */
 184   BASE_FUNC( void )  FT_List_Up( FT_List      list,
 185                                  FT_ListNode  node )
 186   {
 187     FT_ListNode  before, after;
 188
 189
 190     before = node->prev;
 191     after  = node->next;
 192
 193     /* check whether we are already on top of the list */
 194     if ( !before )
 195       return;
 196
 197     before->next = after;
 198
 199     if ( after )
 200       after->prev = before;
 201     else
 202       list->tail = before;
 203
 204     node->prev       = 0;
 205     node->next       = list->head;
 206     list->head->prev = node;
 207     list->head       = node;
 208   }
 209
 210
 211   /*************************************************************************/
 212   /*                                                                       */
 213   /* <Function>                                                            */
 214   /*    FT_List_Iterate                                                    */
 215   /*                                                                       */
 216   /* <Description>                                                         */
 217   /*    Parses a list and calls a given iterator function on each element. */
 218   /*    Note that parsing is stopped as soon as one of the iterator calls  */
 219   /*    returns a non-zero value.                                          */
 220   /*                                                                       */
 221   /* <Input>                                                               */
 222   /*    list     :: A handle to the list.                                  */
 223   /*    iterator :: An interator function, called on each node of the      */
 224   /*                list.                                                  */
 225   /*    user     :: A user-supplied field which is passed as the second    */
 226   /*                argument to the iterator.                              */
 227   /*                                                                       */
 228   /* <Return>                                                              */
 229   /*    The result (a FreeType error code) of the last iterator call.      */
 230   /*                                                                       */
 231   BASE_FUNC( FT_Error )  FT_List_Iterate( FT_List            list,
 232                                           FT_List_Iterator   iterator,
 233                                           void*              user )
 234   {
 235     FT_ListNode  cur   = list->head;
 236     FT_Error     error = FT_Err_Ok;
 237
 238
 239     while ( cur )
 240     {
 241       FT_ListNode  next = cur->next;
 242
 243
 244       error = iterator( cur, user );
 245       if ( error )
 246         break;
 247
 248       cur = next;
 249     }
 250
 251     return error;
 252   }
 253
 254
 255   /*************************************************************************/
 256   /*                                                                       */
 257   /* <Function>                                                            */
 258   /*    FT_List_Finalize                                                   */
 259   /*                                                                       */
 260   /* <Description>                                                         */
 261   /*    Destroys all elements in the list as well as the list itself.      */
 262   /*                                                                       */
 263   /* <Input>                                                               */
 264   /*    list    :: A handle to the list.                                   */
 265   /*                                                                       */
 266   /*    destroy :: A list destructor that will be applied to each element  */
 267   /*               of the list.                                            */
 268   /*                                                                       */
 269   /*    memory  :: The current memory object which handles deallocation.   */
 270   /*                                                                       */
 271   /*    user    :: A user-supplied field which is passed as the last       */
 272   /*               argument to the destructor.                             */
 273   /*                                                                       */
 274   BASE_FUNC( void )  FT_List_Finalize( FT_List             list,
 275                                        FT_List_Destructor  destroy,
 276                                        FT_Memory           memory,
 277                                        void*               user )
 278   {
 279     FT_ListNode  cur;
 280
 281
 282     cur = list->head;
 283     while ( cur )
 284     {
 285       FT_ListNode  next = cur->next;
 286       void*        data = cur->data;
 287
 288
 289       if ( destroy )
 290         destroy( memory, data, user );
 291
 292       FREE( cur );
 293       cur = next;
 294     }
 295
 296     list->head = 0;
 297     list->tail = 0;
 298   }
 299
 300
 301 /* END */