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 #include "dirpool.h"
  14
  15 #define DIR_BLOCK 127
  16
  17 void
  18 dirpool_init(Dirpool *dp)
  19 {
  20   memset(dp, 0, sizeof(*dp));
  21 }
  22
  23 void
  24 dirpool_free(Dirpool *dp)
  25 {
  26   sat_free(dp->dirs);
  27   sat_free(dp->dirtraverse);
  28 }
  29
  30 void
  31 dirpool_make_dirtraverse(Dirpool *dp)
  32 {
  33   Id parent, i, *dirtraverse;
  34   if (!dp->ndirs)
  35     return;
  36   dp->dirs = sat_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
  37   dirtraverse = sat_calloc_block(dp->ndirs, sizeof(Id), DIR_BLOCK);
  38   for (parent = 0, i = 0; i < dp->ndirs; i++)
  39     {
  40       if (dp->dirs[i] > 0)
  41         continue;
  42       parent = -dp->dirs[i];
  43       dirtraverse[i] = dirtraverse[parent];
  44       dirtraverse[parent] = i + 1;
  45     }
  46   dp->dirtraverse = dirtraverse;
  47 }
  48
  49 Id
  50 dirpool_add_dir(Dirpool *dp, Id parent, Id comp, int create)
  51 {
  52   Id did, d, ds, *dirtraverse;
  53
  54   if (!dp->ndirs)
  55     {
  56       if (!create)
  57         return 0;
  58       dp->ndirs = 2;
  59       dp->dirs = sat_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
  60       dp->dirs[0] = 0;
  61       dp->dirs[1] = 1;  /* "" */
  62     }
  63   if (parent == 0 && comp == 1)
  64     return 1;
  65   if (!dp->dirtraverse)
  66     dirpool_make_dirtraverse(dp);
  67   dirtraverse = dp->dirtraverse;
  68   ds = dirtraverse[parent];
  69   while (ds)
  70     {
  71       /* ds: first component in this block
  72        * ds-1: parent link */
  73       for (d = ds--; d < dp->ndirs; d++)
  74         {
  75           if (dp->dirs[d] == comp)
  76             return d;
  77           if (dp->dirs[d] <= 0)
  78             break;
  79         }
  80       if (ds)
  81         ds = dp->dirtraverse[ds];
  82     }
  83   if (!create)
  84     return 0;
  85   /* a new one, find last parent */
  86   for (did = dp->ndirs - 1; did > 0; did--)
  87     if (dp->dirs[did] <= 0)
  88       break;
  89   if (dp->dirs[did] != -parent)
  90     {
  91       /* make room for parent entry */
  92       dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
  93       dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
  94       /* new parent block, link in */
  95       dp->dirs[dp->ndirs] = -parent;
  96       dp->dirtraverse[dp->ndirs] = dp->dirtraverse[parent];
  97       dp->dirtraverse[parent] = ++dp->ndirs;
  98     }
  99   /* make room for new entry */
 100   dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
 101   dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
 102   dp->dirs[dp->ndirs] = comp;
 103   dp->dirtraverse[dp->ndirs] = 0;
 104   return dp->ndirs++;
 105 }