Author: mlschroe Date: Fri Jan 25 18:50:39 2008 New Revision: 8373 URL: http://svn.opensuse.org/viewcvs/zypp?rev=8373&view=rev Log: - add dirpool support Added: trunk/sat-solver/src/dirpool.c trunk/sat-solver/src/dirpool.h Added: trunk/sat-solver/src/dirpool.c URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/dirpool.c?rev=8373&view=auto ============================================================================== --- trunk/sat-solver/src/dirpool.c (added) +++ trunk/sat-solver/src/dirpool.c Fri Jan 25 18:50:39 2008 @@ -0,0 +1,104 @@ +/* + * Copyright (c) 2008, Novell Inc. + * + * This program is licensed under the BSD license, read LICENSE.BSD + * for further information + */ + +#include +#include + +#include "pool.h" +#include "util.h" + +#define DIR_BLOCK 127 + +typedef struct _Dirpool { + Id *dirs; + int ndirs; + Id *dirtraverse; +} Dirpool; + +void +dirpool_create(Dirpool *dp) +{ + memset(dp, 0, sizeof(*dp)); +} + +void +dirpool_make_dirtraverse(Dirpool *dp) +{ + Id parent, i, *dirtraverse; + if (!dp->ndirs) + return; + dp->dirs = sat_realloc2(dp->dirs, (dp->ndirs + DIR_BLOCK) &~ DIR_BLOCK, sizeof(Id)); + dirtraverse = sat_calloc((dp->ndirs + DIR_BLOCK) &~ DIR_BLOCK, sizeof(Id)); + for (parent = 0, i = 0; i < dp->ndirs; i++) + { + if (dp->dirs[i] > 0) + continue; + parent = -dp->dirs[i]; + dirtraverse[i] = dirtraverse[parent]; + dirtraverse[parent] = i + 1; + } + dp->dirtraverse = dirtraverse; +} + +Id +dirpool_add_dir(Dirpool *dp, Id parent, Id comp) +{ + Id did, d, ds, *dirtraverse; + + if (!dp->ndirs) + { + dp->dirs = sat_malloc2(DIR_BLOCK, sizeof(Id)); + dp->ndirs = 2; + dp->dirs[0] = 0; + dp->dirs[1] = 1; /* "" */ + } + if (parent == 0 && comp == 1) + return 1; + if (!dp->dirtraverse) + dirpool_make_dirtraverse(dp); + dirtraverse = dp->dirtraverse; + ds = dirtraverse[parent]; + while (ds) + { + /* ds: first component in this block + * ds-1: parent link */ + for (d = ds--; d < dp->ndirs; d++) + { + if (dp->dirs[d] == comp) + return d; + if (dp->dirs[d] <= 0) + break; + } + if (ds) + ds = dp->dirtraverse[ds]; + } + /* a new one, find last parent */ + for (did = dp->ndirs - 1; did > 0; did--) + if (dp->dirs[did] <= 0) + break; + if (dp->dirs[did] != -parent) + { + if ((dp->ndirs & DIR_BLOCK) == 0) + { + dp->dirs = sat_realloc2(dp->dirs, dp->ndirs + DIR_BLOCK, sizeof(Id)); + dp->dirtraverse = sat_realloc2(dp->dirtraverse, dp->ndirs + DIR_BLOCK, sizeof(Id)); + } + /* new parent block, link in */ + dp->dirs[dp->ndirs] = -parent; + dp->dirtraverse[dp->ndirs] = dp->dirtraverse[parent]; + dp->dirtraverse[parent] = ++dp->ndirs; + } + if ((dp->ndirs & DIR_BLOCK) == 0) + { + dp->dirs = sat_realloc2(dp->dirs, dp->ndirs + DIR_BLOCK, sizeof(Id)); + dp->dirtraverse = sat_realloc2(dp->dirtraverse, dp->ndirs + DIR_BLOCK, sizeof(Id)); + } + dp->dirs[dp->ndirs] = comp; + dp->dirtraverse[dp->ndirs] = 0; + return dp->ndirs++; +} + Added: trunk/sat-solver/src/dirpool.h URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/dirpool.h?rev=8373&view=auto ============================================================================== --- trunk/sat-solver/src/dirpool.h (added) +++ trunk/sat-solver/src/dirpool.h Fri Jan 25 18:50:39 2008 @@ -0,0 +1,70 @@ +/* + * Copyright (c) 2007, Novell Inc. + * + * This program is licensed under the BSD license, read LICENSE.BSD + * for further information + */ +#ifndef SATSOLVER_DIRPOOL_H +#define SATSOLVER_DIRPOOL_H + + +#include "pooltypes.h" +#include "util.h" + +#define DIR_BLOCK 127 + +typedef struct _Dirpool { + Id *dirs; + int ndirs; + Id *dirtraverse; +} Dirpool; + +void dirpool_create(Dirpool *dp); +void dirpool_make_dirtraverse(Dirpool *dp); +Id dirpool_add_dir(Dirpool *dp, Id parent, Id comp); + +static inline Id dirpool_parent(Dirpool *dp, Id did) +{ + if (!did) + return 0; + while (dp->dirs[--did] > 0) + ; + return -dp->dirs[did]; +} + +static inline Id +dirpool_sibling(Dirpool *dp, Id did) +{ + if (did + 1 <= dp->ndirs && dp->dirs[did + 1] > 0) + return did + 1; + while (dp->dirs[--did] > 0) + ; + /* need to special case did == 0 to prevent looping */ + if (!did) + return 0; + if (!dp->dirtraverse) + dirpool_make_dirtraverse(dp); + return dp->dirtraverse[did]; +} + +static inline Id +dirpool_child(Dirpool *dp, Id did) +{ + if (!dp->dirtraverse) + dirpool_make_dirtraverse(dp); + return dp->dirtraverse[did]; +} + +static inline void +dirpool_free_dirtraverse(Dirpool *dp) +{ + dp->dirtraverse = sat_free(dp->dirtraverse); +} + +static inline Id +dirpool_compid(Dirpool *dp, Id did) +{ + return dp->dirs[did]; +} + +#endif /* SATSOLVER_DIRPOOL_H */ -- To unsubscribe, e-mail: zypp-commit+unsubscribe@opensuse.org For additional commands, e-mail: zypp-commit+help@opensuse.org