src/dirpool.c

   1 /*
   2  * Copyright (c) 2008, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 #include <stdio.h>
   9 #include <string.h>
  10
  11 #include "pool.h"
  12 #include "util.h"
  13
  14 #define DIR_BLOCK 127
  15
  16 typedef struct _Dirpool {
  17   Id *dirs;
  18   int ndirs;
  19   Id *dirtraverse;
  20 } Dirpool;
  21
  22 void
  23 dirpool_create(Dirpool *dp)
  24 {
  25   memset(dp, 0, sizeof(*dp));
  26 }
  27
  28 void
  29 dirpool_make_dirtraverse(Dirpool *dp)
  30 {
  31   Id parent, i, *dirtraverse;
  32   if (!dp->ndirs)
  33     return;
  34   dp->dirs = sat_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
  35   dirtraverse = sat_calloc_block(dp->ndirs, sizeof(Id), DIR_BLOCK);
  36   for (parent = 0, i = 0; i < dp->ndirs; i++)
  37     {
  38       if (dp->dirs[i] > 0)
  39         continue;
  40       parent = -dp->dirs[i];
  41       dirtraverse[i] = dirtraverse[parent];
  42       dirtraverse[parent] = i + 1;
  43     }
  44   dp->dirtraverse = dirtraverse;
  45 }
  46
  47 Id
  48 dirpool_add_dir(Dirpool *dp, Id parent, Id comp, int create)
  49 {
  50   Id did, d, ds, *dirtraverse;
  51
  52   if (!dp->ndirs)
  53     {
  54       dp->ndirs = 2;
  55       dp->dirs = sat_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
  56       dp->dirs[0] = 0;
  57       dp->dirs[1] = 1;  /* "" */
  58     }
  59   if (parent == 0 && comp == 1)
  60     return 1;
  61   if (!dp->dirtraverse)
  62     dirpool_make_dirtraverse(dp);
  63   dirtraverse = dp->dirtraverse;
  64   ds = dirtraverse[parent];
  65   while (ds)
  66     {
  67       /* ds: first component in this block
  68        * ds-1: parent link */
  69       for (d = ds--; d < dp->ndirs; d++)
  70         {
  71           if (dp->dirs[d] == comp)
  72             return d;
  73           if (dp->dirs[d] <= 0)
  74             break;
  75         }
  76       if (ds)
  77         ds = dp->dirtraverse[ds];
  78     }
  79   if (!create)
  80     return 0;
  81   /* a new one, find last parent */
  82   for (did = dp->ndirs - 1; did > 0; did--)
  83     if (dp->dirs[did] <= 0)
  84       break;
  85   if (dp->dirs[did] != -parent)
  86     {
  87       /* make room for parent entry */
  88       dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
  89       dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
  90       /* new parent block, link in */
  91       dp->dirs[dp->ndirs] = -parent;
  92       dp->dirtraverse[dp->ndirs] = dp->dirtraverse[parent];
  93       dp->dirtraverse[parent] = ++dp->ndirs;
  94     }
  95   /* make room for new entry */
  96   dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
  97   dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
  98   dp->dirs[dp->ndirs] = comp;
  99   dp->dirtraverse[dp->ndirs] = 0;
 100   return dp->ndirs++;
 101 }