source/texk/kpathsea/str-llist.c

   1 /* str-llist.c: implementation of a linked list of strings.
   2
   3    Copyright 1993, 2008 Karl Berry.
   4
   5    This library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    This library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public License
  16    along with this library; if not, see <http://www.gnu.org/licenses/>.  */
  17
  18 #include <kpathsea/config.h>
  19
  20 #include <kpathsea/str-llist.h>
  21
  22
  23 /* Add the new string STR to the end of the list L.  */
  24
  25 void
  26 str_llist_add (str_llist_type *l,  string str)
  27 {
  28   str_llist_elt_type *e;
  29   str_llist_elt_type *new_elt = XTALLOC1 (str_llist_elt_type);
  30
  31   /* The new element will be at the end of the list.  */
  32   STR_LLIST (*new_elt) = str;
  33   STR_LLIST_MOVED (*new_elt) = false;
  34   STR_LLIST_NEXT (*new_elt) = NULL;
  35
  36   /* Find the current end of the list.  */
  37   for (e = *l; e && STR_LLIST_NEXT (*e); e = STR_LLIST_NEXT (*e))
  38     ;
  39
  40   if (!e)
  41     *l = new_elt;
  42   else
  43     STR_LLIST_NEXT (*e) = new_elt;
  44 }
  45 \f
  46 /* Move an element towards the top. The idea is that when a file is
  47    found in a given directory, later files will likely be in that same
  48    directory, and looking for the file in all the directories in between
  49    is thus a waste.  */
  50
  51 void
  52 str_llist_float (str_llist_type *l,  str_llist_elt_type *mover)
  53 {
  54   str_llist_elt_type *last_moved, *unmoved;
  55
  56   /* If we've already moved this element, never mind.  */
  57   if (STR_LLIST_MOVED (*mover))
  58     return;
  59
  60   /* Find the first unmoved element (to insert before).  We're
  61      guaranteed this will terminate, since MOVER itself is currently
  62      unmoved, and it must be in L (by hypothesis).  */
  63   for (last_moved = NULL, unmoved = *l; STR_LLIST_MOVED (*unmoved);
  64        last_moved = unmoved, unmoved = STR_LLIST_NEXT (*unmoved))
  65     ;
  66
  67   /* If we are the first unmoved element, nothing to relink.  */
  68   if (unmoved != mover)
  69     { /* Remember `mover's current successor, so we can relink `mover's
  70          predecessor to it.  */
  71       str_llist_elt_type *before_mover;
  72       str_llist_elt_type *after_mover = STR_LLIST_NEXT (*mover);
  73
  74       /* Find `mover's predecessor.  */
  75       for (before_mover = unmoved; STR_LLIST_NEXT (*before_mover) != mover;
  76            before_mover = STR_LLIST_NEXT (*before_mover))
  77         ;
  78
  79       /* `before_mover' now links to `after_mover'.  */
  80       STR_LLIST_NEXT (*before_mover) = after_mover;
  81
  82       /* Insert `mover' before `unmoved' and after `last_moved' (or at
  83          the head of the list).  */
  84       STR_LLIST_NEXT (*mover) = unmoved;
  85       if (!last_moved)
  86         *l = mover;
  87       else
  88         STR_LLIST_NEXT (*last_moved) = mover;
  89     }
  90
  91   /* We've moved it.  */
  92   STR_LLIST_MOVED (*mover) = true;
  93 }