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 /* directories are stored as components, 18 * components are simple ids from the string pool 19 * /usr/bin -> "", "usr", "bin" 20 * /usr/lib -> "", "usr", "lib" 21 * foo/bar -> "foo", "bar" 22 * /usr/games -> "", "usr", "games" 23 * 24 * all directories are stores in the "dirs" array 25 * dirs[id] > 0 : component string pool id 26 * dirs[id] <= 0 : -(parent directory id) 27 * 28 * Directories with the same parent are stored as 29 * multiple blocks. We need multiple blocks because 30 * we cannot insert entries into old blocks, as that 31 * would shift the ids of already used directories. 32 * Each block starts with (-parent_dirid) and contains 33 * component ids of the directory entries. 34 * (The (-parent_dirid) entry is not a valid directory 35 * id, it's just used internally) 36 * 37 * There is also the aux "dirtraverse" array, which 38 * is created on demand to speed things up a bit. 39 * if dirs[id] > 0, dirtravers[id] points to the first 40 * entry in the last block with parent id. 41 * if dirs[id] <= 0, dirtravers[id] points to the entry 42 * in the previous block with the same parent. 43 * (Thus it acts as a linked list that starts at the 44 * parent dirid and chains all the blocks with that 45 * parent.) 46 * 47 * id dirs[id] dirtraverse[id] 48 * 0 0 8 [no parent, block#0] 49 * 1 "" 3 50 * 2 -1 [parent 1, /, block #0] 51 * 3 "usr" 12 52 * 4 -3 [parent 3, /usr, block #0] 53 * 5 "bin" 54 * 6 "lib" 55 * 7 0 1 [no parent, block#1] 56 * 8 "foo" 10 57 * 9 -8 [parent 8, foo, block #0] 58 * 10 "bar" 59 * 11 -3 5 [parent 3, /usr, block #1] 60 * 12 "games" 61 * 62 * to find all children of dirid 3 ("/usr"), follow the 63 * dirtraverse link to 12 -> "games". Then follow the 64 * dirtraverse link of this block to 5 -> "bin", "lib" 65 */ 66 67 void 68 dirpool_init(Dirpool *dp) 69 { 70 memset(dp, 0, sizeof(*dp)); 71 } 72 73 void 74 dirpool_free(Dirpool *dp) 75 { 76 solv_free(dp->dirs); 77 solv_free(dp->dirtraverse); 78 } 79 80 void 81 dirpool_make_dirtraverse(Dirpool *dp) 82 { 83 Id parent, i, *dirtraverse; 84 if (!dp->ndirs) 85 return; 86 dp->dirs = solv_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK); 87 dirtraverse = solv_calloc_block(dp->ndirs, sizeof(Id), DIR_BLOCK); 88 for (parent = 0, i = 0; i < dp->ndirs; i++) 89 { 90 if (dp->dirs[i] > 0) 91 continue; 92 parent = -dp->dirs[i]; 93 dirtraverse[i] = dirtraverse[parent]; 94 dirtraverse[parent] = i + 1; 95 } 96 dp->dirtraverse = dirtraverse; 97 } 98 99 Id 100 dirpool_add_dir(Dirpool *dp, Id parent, Id comp, int create) 101 { 102 Id did, d, ds, *dirtraverse; 103 104 if (!dp->ndirs) 105 { 106 if (!create) 107 return 0; 108 dp->ndirs = 2; 109 dp->dirs = solv_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK); 110 dp->dirs[0] = 0; 111 dp->dirs[1] = 1; /* "" */ 112 } 113 if (parent == 0 && comp == 1) 114 return 1; 115 if (!dp->dirtraverse) 116 dirpool_make_dirtraverse(dp); 117 /* check all entries with this parent if we 118 * already have this component */ 119 dirtraverse = dp->dirtraverse; 120 ds = dirtraverse[parent]; 121 while (ds) 122 { 123 /* ds: first component in this block 124 * ds-1: parent link */ 125 for (d = ds--; d < dp->ndirs; d++) 126 { 127 if (dp->dirs[d] == comp) 128 return d; 129 if (dp->dirs[d] <= 0) /* reached end of this block */ 130 break; 131 } 132 if (ds) 133 ds = dp->dirtraverse[ds]; 134 } 135 if (!create) 136 return 0; 137 /* a new one, find last parent */ 138 for (did = dp->ndirs - 1; did > 0; did--) 139 if (dp->dirs[did] <= 0) 140 break; 141 if (dp->dirs[did] != -parent) 142 { 143 /* make room for parent entry */ 144 dp->dirs = solv_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK); 145 dp->dirtraverse = solv_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK); 146 /* new parent block, link in */ 147 dp->dirs[dp->ndirs] = -parent; 148 dp->dirtraverse[dp->ndirs] = dp->dirtraverse[parent]; 149 dp->dirtraverse[parent] = ++dp->ndirs; 150 } 151 /* make room for new entry */ 152 dp->dirs = solv_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK); 153 dp->dirtraverse = solv_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK); 154 dp->dirs[dp->ndirs] = comp; 155 dp->dirtraverse[dp->ndirs] = 0; 156 return dp->ndirs++; 157 } 158