usr/src/lib/libast/common/cdt/dtflatten.c

   1 /***********************************************************************
   2 *                                                                      *
   3 *               This software is part of the ast package               *
   4 *          Copyright (c) 1985-2010 AT&T Intellectual Property          *
   5 *                      and is licensed under the                       *
   6 *                  Common Public License, Version 1.0                  *
   7 *                    by AT&T Intellectual Property                     *
   8 *                                                                      *
   9 *                A copy of the License is available at                 *
  10 *            http://www.opensource.org/licenses/cpl1.0.txt             *
  11 *         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
  12 *                                                                      *
  13 *              Information and Software Systems Research               *
  14 *                            AT&T Research                             *
  15 *                           Florham Park NJ                            *
  16 *                                                                      *
  17 *                 Glenn Fowler <gsf@research.att.com>                  *
  18 *                  David Korn <dgk@research.att.com>                   *
  19 *                   Phong Vo <kpv@research.att.com>                    *
  20 *                                                                      *
  21 ***********************************************************************/
  22 #include        "dthdr.h"
  23
  24 /*      Flatten a dictionary into a linked list.
  25 **      This may be used when many traversals are likely.
  26 **
  27 **      Written by Kiem-Phong Vo (5/25/96).
  28 */
  29
  30 #if __STD_C
  31 Dtlink_t* dtflatten(Dt_t* dt)
  32 #else
  33 Dtlink_t* dtflatten(dt)
  34 Dt_t*   dt;
  35 #endif
  36 {
  37         reg Dtlink_t    *t, *r, *list, *last, **s, **ends;
  38
  39         /* already flattened */
  40         if(dt->data->type&DT_FLATTEN )
  41                 return dt->data->here;
  42
  43         list = last = NIL(Dtlink_t*);
  44         if(dt->data->type&(DT_SET|DT_BAG))
  45         {       for(ends = (s = dt->data->htab) + dt->data->ntab; s < ends; ++s)
  46                 {       if((t = *s) )
  47                         {       if(last)
  48                                         last->right = t;
  49                                 else    list = last = t;
  50                                 while(last->right)
  51                                         last = last->right;
  52                                 *s = last;
  53                         }
  54                 }
  55         }
  56         else if(dt->data->type&(DT_LIST|DT_STACK|DT_QUEUE) )
  57                 list = dt->data->head;
  58         else if((r = dt->data->here) ) /*if(dt->data->type&(DT_OSET|DT_OBAG))*/
  59         {       while((t = r->left) )
  60                         RROTATE(r,t);
  61                 for(list = last = r, r = r->right; r; last = r, r = r->right)
  62                 {       if((t = r->left) )
  63                         {       do      RROTATE(r,t);
  64                                 while((t = r->left) );
  65
  66                                 last->right = r;
  67                         }
  68                 }
  69         }
  70
  71         dt->data->here = list;
  72         dt->data->type |= DT_FLATTEN;
  73
  74         return list;
  75 }