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