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       dp->ndirs = 2;
  57       dp->dirs = sat_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
  58       dp->dirs[0] = 0;
  59       dp->dirs[1] = 1;  /* "" */
  60     }
  61   if (parent == 0 && comp == 1)
  62     return 1;
  63   if (!dp->dirtraverse)
  64     dirpool_make_dirtraverse(dp);
  65   dirtraverse = dp->dirtraverse;
  66   ds = dirtraverse[parent];
  67   while (ds)
  68     {
  69       /* ds: first component in this block
  70        * ds-1: parent link */
  71       for (d = ds--; d < dp->ndirs; d++)
  72         {
  73           if (dp->dirs[d] == comp)
  74             return d;
  75           if (dp->dirs[d] <= 0)
  76             break;
  77         }
  78       if (ds)
  79         ds = dp->dirtraverse[ds];
  80     }
  81   if (!create)
  82     return 0;
  83   /* a new one, find last parent */
  84   for (did = dp->ndirs - 1; did > 0; did--)
  85     if (dp->dirs[did] <= 0)
  86       break;
  87   if (dp->dirs[did] != -parent)
  88     {
  89       /* make room for parent entry */
  90       dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
  91       dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
  92       /* new parent block, link in */
  93       dp->dirs[dp->ndirs] = -parent;
  94       dp->dirtraverse[dp->ndirs] = dp->dirtraverse[parent];
  95       dp->dirtraverse[parent] = ++dp->ndirs;
  96     }
  97   /* make room for new entry */
  98   dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
  99   dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
 100   dp->dirs[dp->ndirs] = comp;
 101   dp->dirtraverse[dp->ndirs] = 0;
 102   return dp->ndirs++;
 103 }