satsolver 0.16.3
|
00001 /* 00002 * Copyright (c) 2008, Novell Inc. 00003 * 00004 * This program is licensed under the BSD license, read LICENSE.BSD 00005 * for further information 00006 */ 00007 00008 #include <stdio.h> 00009 #include <string.h> 00010 00011 #include "pool.h" 00012 #include "util.h" 00013 #include "dirpool.h" 00014 00015 #define DIR_BLOCK 127 00016 00017 void 00018 dirpool_init(Dirpool *dp) 00019 { 00020 memset(dp, 0, sizeof(*dp)); 00021 } 00022 00023 void 00024 dirpool_free(Dirpool *dp) 00025 { 00026 sat_free(dp->dirs); 00027 sat_free(dp->dirtraverse); 00028 } 00029 00030 void 00031 dirpool_make_dirtraverse(Dirpool *dp) 00032 { 00033 Id parent, i, *dirtraverse; 00034 if (!dp->ndirs) 00035 return; 00036 dp->dirs = sat_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK); 00037 dirtraverse = sat_calloc_block(dp->ndirs, sizeof(Id), DIR_BLOCK); 00038 for (parent = 0, i = 0; i < dp->ndirs; i++) 00039 { 00040 if (dp->dirs[i] > 0) 00041 continue; 00042 parent = -dp->dirs[i]; 00043 dirtraverse[i] = dirtraverse[parent]; 00044 dirtraverse[parent] = i + 1; 00045 } 00046 dp->dirtraverse = dirtraverse; 00047 } 00048 00049 Id 00050 dirpool_add_dir(Dirpool *dp, Id parent, Id comp, int create) 00051 { 00052 Id did, d, ds, *dirtraverse; 00053 00054 if (!dp->ndirs) 00055 { 00056 if (!create) 00057 return 0; 00058 dp->ndirs = 2; 00059 dp->dirs = sat_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK); 00060 dp->dirs[0] = 0; 00061 dp->dirs[1] = 1; /* "" */ 00062 } 00063 if (parent == 0 && comp == 1) 00064 return 1; 00065 if (!dp->dirtraverse) 00066 dirpool_make_dirtraverse(dp); 00067 dirtraverse = dp->dirtraverse; 00068 ds = dirtraverse[parent]; 00069 while (ds) 00070 { 00071 /* ds: first component in this block 00072 * ds-1: parent link */ 00073 for (d = ds--; d < dp->ndirs; d++) 00074 { 00075 if (dp->dirs[d] == comp) 00076 return d; 00077 if (dp->dirs[d] <= 0) 00078 break; 00079 } 00080 if (ds) 00081 ds = dp->dirtraverse[ds]; 00082 } 00083 if (!create) 00084 return 0; 00085 /* a new one, find last parent */ 00086 for (did = dp->ndirs - 1; did > 0; did--) 00087 if (dp->dirs[did] <= 0) 00088 break; 00089 if (dp->dirs[did] != -parent) 00090 { 00091 /* make room for parent entry */ 00092 dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK); 00093 dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK); 00094 /* new parent block, link in */ 00095 dp->dirs[dp->ndirs] = -parent; 00096 dp->dirtraverse[dp->ndirs] = dp->dirtraverse[parent]; 00097 dp->dirtraverse[parent] = ++dp->ndirs; 00098 } 00099 /* make room for new entry */ 00100 dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK); 00101 dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK); 00102 dp->dirs[dp->ndirs] = comp; 00103 dp->dirtraverse[dp->ndirs] = 0; 00104 return dp->ndirs++; 00105 }