[zypp-commit] r7844 - in /trunk/sat-solver: src/ tools/

Author: matz Date: Fri Nov 16 14:48:23 2007 New Revision: 7844 URL: http://svn.opensuse.org/viewcvs/zypp?rev=7844&view=rev Log: Reduce C&P code by factoring out the uniquifying string pool. Added: trunk/sat-solver/src/strpool.c trunk/sat-solver/src/strpool.h Modified: trunk/sat-solver/src/CMakeLists.txt trunk/sat-solver/src/pool.c trunk/sat-solver/src/pool.h trunk/sat-solver/src/poolid.c trunk/sat-solver/src/poolid_private.h trunk/sat-solver/src/pooltypes.h trunk/sat-solver/src/repo_solv.c trunk/sat-solver/tools/attr_store.c trunk/sat-solver/tools/attr_store_p.h trunk/sat-solver/tools/repo_write.c Modified: trunk/sat-solver/src/CMakeLists.txt URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/CMakeLists.txt?rev=7844&r1=7843&r2=7844&view=diff ============================================================================== --- trunk/sat-solver/src/CMakeLists.txt (original) +++ trunk/sat-solver/src/CMakeLists.txt Fri Nov 16 14:48:23 2007 @@ -1,10 +1,10 @@ -SET(libsatsolver_SRCS bitmap.c poolarch.c poolvendor.c poolid.c +SET(libsatsolver_SRCS bitmap.c poolarch.c poolvendor.c poolid.c strpool.c solver.c repo_solv.c evr.c pool.c queue.c repo.c util.c policy.c ) ADD_LIBRARY(satsolver STATIC ${libsatsolver_SRCS}) -SET(libsatsolver_HEADERS bitmap.h evr.h hash.h policy.h poolarch.h poolvendor.h pool.h poolid.h pooltypes.h queue.h solvable.h solver.h repo.h repo_solv.h util.h ) +SET(libsatsolver_HEADERS bitmap.h evr.h hash.h policy.h poolarch.h poolvendor.h pool.h poolid.h pooltypes.h queue.h solvable.h solver.h repo.h repo_solv.h util.h strpool.h ) SET( CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -g -O3 -Wall -fPIC" ) Modified: trunk/sat-solver/src/pool.c URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/pool.c?rev=7844&r1=7843&r2=7844&view=diff ============================================================================== --- trunk/sat-solver/src/pool.c (original) +++ trunk/sat-solver/src/pool.c Fri Nov 16 14:48:23 2007 @@ -40,7 +40,7 @@ // list of string constants, so we can do pointer/Id instead of string comparison // index into array matches ID_xxx constants in pool.h -static char *initpool_data[] = { +static const char *initpool_data[] = { "<NULL>", // ID_NULL "", // ID_EMPTY "solvable:name", @@ -64,7 +64,8 @@ "system:system", "src", "nosrc", - "noarch" + "noarch", + 0 }; // create pool @@ -72,29 +73,12 @@ Pool * pool_create(void) { - int count, totalsize = 0; Pool *pool; Solvable *s; pool = (Pool *)xcalloc(1, sizeof(*pool)); - // count number and total size of predefined strings - for (count = 0; count < sizeof(initpool_data)/sizeof(*initpool_data); count++) - totalsize += strlen(initpool_data[count]) + 1; - - // alloc appropriate space - pool->stringspace = (char *)xmalloc((totalsize + STRINGSPACE_BLOCK) & ~STRINGSPACE_BLOCK); - pool->strings = (Offset *)xmalloc(((count + STRING_BLOCK) & ~STRING_BLOCK) * sizeof(Offset)); - - // now copy predefined strings into allocated space - pool->sstrings = 0; - for (count = 0; count < sizeof(initpool_data)/sizeof(*initpool_data); count++) - { - strcpy(pool->stringspace + pool->sstrings, initpool_data[count]); - pool->strings[count] = pool->sstrings; - pool->sstrings += strlen(initpool_data[count]) + 1; - } - pool->nstrings = count; + stringpool_init (&pool->ss, initpool_data); // pre-alloc space for a RelDep pool->rels = (Reldep *)xcalloc(1 + REL_BLOCK, sizeof(Reldep)); @@ -124,8 +108,8 @@ pool_freeallrepos(pool, 1); xfree(pool->id2arch); xfree(pool->solvables); - xfree(pool->stringspace); - xfree(pool->strings); + xfree(pool->ss.stringspace); + xfree(pool->ss.strings); xfree(pool->rels); queue_free(&pool->vendormap); for (i = 0; i < DEP2STRBUF; i++) @@ -169,16 +153,16 @@ Offset o; int r; - if (pool->nstrings < 3) + if (pool->ss.nstrings < 3) return; - sorted = xmalloc2(pool->nstrings, sizeof(Id)); - for (id = 0; id < pool->nstrings; id++) + sorted = xmalloc2(pool->ss.nstrings, sizeof(Id)); + for (id = 0; id < pool->ss.nstrings; id++) sorted[id] = id; pool_shrink_whatprovides_sortcmp_data = pool; - qsort(sorted + 1, pool->nstrings - 1, sizeof(Id), pool_shrink_whatprovides_sortcmp); + qsort(sorted + 1, pool->ss.nstrings - 1, sizeof(Id), pool_shrink_whatprovides_sortcmp); last = 0; lastid = 0; - for (i = 1; i < pool->nstrings; i++) + for (i = 1; i < pool->ss.nstrings; i++) { id = sorted[i]; o = pool->whatprovides[id]; @@ -207,7 +191,7 @@ } xfree(sorted); dp = pool->whatprovidesdata + 2; - for (id = 1; id < pool->nstrings; id++) + for (id = 1; id < pool->ss.nstrings; id++) { o = pool->whatprovides[id]; if (o == 0 || o == 1) @@ -262,11 +246,11 @@ if (pool->verbose) printf("number of solvables: %d\n", pool->nsolvables); if (pool->verbose) - printf("number of ids: %d + %d\n", pool->nstrings, pool->nrels); + printf("number of ids: %d + %d\n", pool->ss.nstrings, pool->nrels); pool_freeidhashes(pool); pool_freewhatprovides(pool); - num = pool->nstrings + pool->nrels; + num = pool->ss.nstrings + pool->nrels; whatprovides = (Offset *)xcalloc(num, sizeof(Offset)); /* count providers for each name */ Modified: trunk/sat-solver/src/pool.h URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/pool.h?rev=7844&r1=7843&r2=7844&view=diff ============================================================================== --- trunk/sat-solver/src/pool.h (original) +++ trunk/sat-solver/src/pool.h Fri Nov 16 14:48:23 2007 @@ -22,12 +22,13 @@ #include "repo.h" #include "solvable.h" #include "queue.h" +#include "strpool.h" // see initpool_data[] in pool.c /* well known ids */ -#define ID_NULL 0 -#define ID_EMPTY 1 +#define ID_NULL STRID_NULL +#define ID_EMPTY STRID_EMPTY #define SOLVABLE_NAME 2 #define SOLVABLE_ARCH 3 #define SOLVABLE_EVR 4 @@ -58,19 +59,12 @@ /* how many strings to maintain (round robin) */ #define DEP2STRBUF 16 - //----------------------------------------------- struct _Pool { int verbose; // pool is used everywhere, so put the verbose flag here - Offset *strings; // table of offsets into stringspace, indexed by Id: Id -> Offset - int nstrings; // number of unique strings in stringspace - char *stringspace; // space for all unique strings: stringspace + Offset = string - Offset sstrings; // next free pos in stringspace - - Hashtable stringhashtbl; // hash table: (string ->) Hash -> Id - Hashmask stringhashmask; // modulo value for hash table (size of table - 1) + struct _Stringpool ss; Reldep *rels; // table of rels: Id -> Reldep int nrels; // number of unique rels @@ -135,7 +129,7 @@ #define MAKERELDEP(id) ((id) | 0x80000000) #define ISRELDEP(id) (((id) & 0x80000000) != 0) -#define GETRELID(pool, id) ((pool)->nstrings + ((id) ^ 0x80000000)) /* returns Id */ +#define GETRELID(pool, id) ((pool)->ss.nstrings + ((id) ^ 0x80000000)) /* returns Id */ #define GETRELDEP(pool, id) ((pool)->rels + ((id) ^ 0x80000000)) /* returns Reldep* */ #define REL_GT 1 Modified: trunk/sat-solver/src/poolid.c URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/poolid.c?rev=7844&r1=7843&r2=7844&view=diff ============================================================================== --- trunk/sat-solver/src/poolid.c (original) +++ trunk/sat-solver/src/poolid.c Fri Nov 16 14:48:23 2007 @@ -27,84 +27,15 @@ Id str2id(Pool *pool, const char *str, int create) { - Hashval h; - unsigned int hh; - Hashmask hashmask; - int i, space_needed; - Id id; - Hashtable hashtbl; - - // check string - if (!str) - return ID_NULL; - if (!*str) - return ID_EMPTY; - - hashmask = pool->stringhashmask; - hashtbl = pool->stringhashtbl; - - // expand hashtable if needed - // - // - if (pool->nstrings * 2 > hashmask) - { - xfree(hashtbl); - - // realloc hash table - pool->stringhashmask = hashmask = mkmask(pool->nstrings + STRING_BLOCK); - pool->stringhashtbl = hashtbl = (Hashtable)xcalloc(hashmask + 1, sizeof(Id)); - - // rehash all strings into new hashtable - for (i = 1; i < pool->nstrings; i++) - { - h = strhash(pool->stringspace + pool->strings[i]) & hashmask; - hh = HASHCHAIN_START; - while (hashtbl[h] != ID_NULL) // follow overflow chain - h = HASHCHAIN_NEXT(h, hh, hashmask); - hashtbl[h] = i; - } - } - - // compute hash and check for match - - h = strhash(str) & hashmask; - hh = HASHCHAIN_START; - while ((id = hashtbl[h]) != ID_NULL) // follow hash overflow chain - { - // break if string already hashed - if(!strcmp(pool->stringspace + pool->strings[id], str)) - break; - h = HASHCHAIN_NEXT(h, hh, hashmask); - } - if (id || !create) // exit here if string found - return id; - - pool_freewhatprovides(pool); - - // generate next id and save in table - id = pool->nstrings++; - hashtbl[h] = id; - - // - if ((id & STRING_BLOCK) == 0) - pool->strings = xrealloc(pool->strings, ((pool->nstrings + STRING_BLOCK) & ~STRING_BLOCK) * sizeof(Hashval)); - // 'pointer' into stringspace is Offset of next free pos: sstrings - pool->strings[id] = pool->sstrings; - - space_needed = strlen(str) + 1; - - // resize string buffer if needed - if (((pool->sstrings + space_needed - 1) | STRINGSPACE_BLOCK) != ((pool->sstrings - 1) | STRINGSPACE_BLOCK)) - pool->stringspace = xrealloc(pool->stringspace, (pool->sstrings + space_needed + STRINGSPACE_BLOCK) & ~STRINGSPACE_BLOCK); - // copy new string into buffer - memcpy(pool->stringspace + pool->sstrings, str, space_needed); - // next free pos is behind new string - pool->sstrings += space_needed; - + int old_nstrings = pool->ss.nstrings; + Id id = stringpool_str2id (&pool->ss, str, create); + /* If we changed the ID->string relations we need to get rid of an + eventually existing provides lookup cache. */ + if (old_nstrings != pool->ss.nstrings) + pool_freewhatprovides(pool); return id; } - Id rel2id(Pool *pool, Id name, Id evr, int flags, int create) { @@ -124,7 +55,7 @@ if (pool->nrels * 2 > hashmask) { xfree(pool->relhashtbl); - pool->relhashmask = hashmask = mkmask(pool->nstrings + REL_BLOCK); + pool->relhashmask = hashmask = mkmask(pool->ss.nstrings + REL_BLOCK); pool->relhashtbl = hashtbl = xcalloc(hashmask + 1, sizeof(Id)); // rehash all rels into new hashtable for (i = 1; i < pool->nrels; i++) @@ -179,9 +110,9 @@ Reldep *rd = GETRELDEP(pool, id); if (ISRELDEP(rd->name)) return "REL"; - return pool->stringspace + pool->strings[rd->name]; + return pool->ss.stringspace + pool->ss.strings[rd->name]; } - return pool->stringspace + pool->strings[id]; + return pool->ss.stringspace + pool->ss.strings[id]; } static const char *rels[] = { @@ -235,7 +166,7 @@ rd = GETRELDEP(pool, id); if (ISRELDEP(rd->evr)) return "REL"; - return pool->stringspace + pool->strings[rd->evr]; + return pool->ss.stringspace + pool->ss.strings[rd->evr]; } const char * @@ -247,7 +178,7 @@ int n, l, ls1, ls2, lsr; if (!ISRELDEP(id)) - return pool->stringspace + pool->strings[id]; + return pool->ss.stringspace + pool->ss.strings[id]; rd = GETRELDEP(pool, id); n = pool->dep2strn; @@ -305,8 +236,7 @@ void pool_shrink_strings(Pool *pool) { - pool->stringspace = (char *)xrealloc(pool->stringspace, (pool->sstrings + STRINGSPACE_BLOCK) & ~STRINGSPACE_BLOCK); - pool->strings = (Offset *)xrealloc(pool->strings, ((pool->nstrings + STRING_BLOCK) & ~STRING_BLOCK) * sizeof(Offset)); + stringpool_shrink (&pool->ss); } void @@ -320,9 +250,9 @@ void pool_freeidhashes(Pool *pool) { - pool->stringhashtbl = xfree(pool->stringhashtbl); + pool->ss.stringhashtbl = xfree(pool->ss.stringhashtbl); + pool->ss.stringhashmask = 0; pool->relhashtbl = xfree(pool->relhashtbl); - pool->stringhashmask = 0; pool->relhashmask = 0; } Modified: trunk/sat-solver/src/poolid_private.h URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/poolid_private.h?rev=7844&r1=7843&r2=7844&view=diff ============================================================================== --- trunk/sat-solver/src/poolid_private.h (original) +++ trunk/sat-solver/src/poolid_private.h Fri Nov 16 14:48:23 2007 @@ -15,10 +15,8 @@ // the size of all buffers is incremented in blocks // these are the block values (increment values) for the -// string hashtable, rel hashtable, stringspace buffer and idarray +// rel hashtable // -#define STRING_BLOCK 2047 // hashtable for strings #define REL_BLOCK 1023 // hashtable for relations -#define STRINGSPACE_BLOCK 65535 // string buffer #endif /* POOLID_PRIVATE_H */ Modified: trunk/sat-solver/src/pooltypes.h URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/pooltypes.h?rev=7844&r1=7843&r2=7844&view=diff ============================================================================== --- trunk/sat-solver/src/pooltypes.h (original) +++ trunk/sat-solver/src/pooltypes.h Fri Nov 16 14:48:23 2007 @@ -16,6 +16,9 @@ /* version number for .solv files */ #define SOLV_VERSION 0 +struct _Stringpool; +typedef struct _Stringpool Stringpool; + struct _Pool; typedef struct _Pool Pool; Modified: trunk/sat-solver/src/repo_solv.c URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/repo_solv.c?rev=7844&r1=7843&r2=7844&view=diff ============================================================================== --- trunk/sat-solver/src/repo_solv.c (original) +++ trunk/sat-solver/src/repo_solv.c Fri Nov 16 14:48:23 2007 @@ -230,15 +230,15 @@ */ /* alloc string buffer */ - strsp = (char *)xrealloc(pool->stringspace, pool->sstrings + sizeid + 1); + strsp = (char *)xrealloc(pool->ss.stringspace, pool->ss.sstrings + sizeid + 1); /* alloc string offsets (Id -> Offset into string space) */ - str = (Offset *)xrealloc(pool->strings, (pool->nstrings + numid) * sizeof(Offset)); + str = (Offset *)xrealloc(pool->ss.strings, (pool->ss.nstrings + numid) * sizeof(Offset)); - pool->stringspace = strsp; - pool->strings = str; /* array of offsets into strsp, indexed by Id */ + pool->ss.stringspace = strsp; + pool->ss.strings = str; /* array of offsets into strsp, indexed by Id */ /* point to _BEHIND_ already allocated string/Id space */ - strsp += pool->sstrings; + strsp += pool->ss.sstrings; /* alloc id map for name and rel Ids. this maps ids in the solv files * to the ids in our pool */ @@ -261,7 +261,7 @@ * */ - hashmask = mkmask(pool->nstrings + numid); + hashmask = mkmask(pool->ss.nstrings + numid); #if 0 printf("read %d strings\n", numid); @@ -278,9 +278,9 @@ * fill hashtable with strings already in pool */ - for (i = 1; i < pool->nstrings; i++) /* leave out our dummy zero id */ + for (i = 1; i < pool->ss.nstrings; i++) /* leave out our dummy zero id */ { - h = strhash(pool->stringspace + pool->strings[i]) & hashmask; + h = strhash(pool->ss.stringspace + pool->ss.strings[i]) & hashmask; hh = HASHCHAIN_START; while (hashtbl[h]) h = HASHCHAIN_NEXT(h, hh, hashmask); @@ -315,7 +315,7 @@ id = hashtbl[h]; if (id == 0) break; - if (!strcmp(pool->stringspace + pool->strings[id], sp)) + if (!strcmp(pool->ss.stringspace + pool->ss.strings[id], sp)) break; /* existing string */ h = HASHCHAIN_NEXT(h, hh, hashmask); } @@ -324,12 +324,12 @@ l = strlen(sp) + 1; if (id == ID_NULL) /* end of hash chain -> new string */ { - id = pool->nstrings++; + id = pool->ss.nstrings++; hashtbl[h] = id; - str[id] = pool->sstrings; /* save Offset */ - if (sp != pool->stringspace + pool->sstrings) /* not at end-of-buffer */ - memmove(pool->stringspace + pool->sstrings, sp, l); /* append to pool buffer */ - pool->sstrings += l; + str[id] = pool->ss.sstrings; /* save Offset */ + if (sp != pool->ss.stringspace + pool->ss.sstrings) /* not at end-of-buffer */ + memmove(pool->ss.stringspace + pool->ss.sstrings, sp, l); /* append to pool buffer */ + pool->ss.sstrings += l; } idmap[i] = id; /* repo relative -> pool relative */ sp += l; /* next string */ Added: trunk/sat-solver/src/strpool.c URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/strpool.c?rev=7844&view=auto ============================================================================== --- trunk/sat-solver/src/strpool.c (added) +++ trunk/sat-solver/src/strpool.c Fri Nov 16 14:48:23 2007 @@ -0,0 +1,122 @@ +/* + * Copyright (c) 2007, Novell Inc. + * + * This program is licensed under the BSD license, read LICENSE.BSD + * for further information + */ + +#include +#include "util.h" +#include "strpool.h" + +#define STRING_BLOCK 2047 +#define STRINGSPACE_BLOCK 65535 + +void +stringpool_init (Stringpool *ss, const char *strs[]) +{ + unsigned totalsize = 0; + unsigned count; + // count number and total size of predefined strings + for (count = 0; strs[count]; count++) + totalsize += strlen(strs[count]) + 1; + + // alloc appropriate space + ss->stringspace = (char *)xmalloc((totalsize + STRINGSPACE_BLOCK) & ~STRINGSPACE_BLOCK); + ss->strings = (Offset *)xmalloc(((count + STRING_BLOCK) & ~STRING_BLOCK) * sizeof(Offset)); + + // now copy predefined strings into allocated space + ss->sstrings = 0; + for (count = 0; strs[count]; count++) + { + strcpy(ss->stringspace + ss->sstrings, strs[count]); + ss->strings[count] = ss->sstrings; + ss->sstrings += strlen(strs[count]) + 1; + } + ss->nstrings = count; +} + +Id +stringpool_str2id (Stringpool *ss, const char *str, int create) +{ + Hashval h; + unsigned int hh; + Hashmask hashmask; + int i, space_needed; + Id id; + Hashtable hashtbl; + + // check string + if (!str) + return STRID_NULL; + if (!*str) + return STRID_EMPTY; + + hashmask = ss->stringhashmask; + hashtbl = ss->stringhashtbl; + + // expand hashtable if needed + // + // + if (ss->nstrings * 2 > hashmask) + { + xfree(hashtbl); + + // realloc hash table + ss->stringhashmask = hashmask = mkmask(ss->nstrings + STRING_BLOCK); + ss->stringhashtbl = hashtbl = (Hashtable)xcalloc(hashmask + 1, sizeof(Id)); + + // rehash all strings into new hashtable + for (i = 1; i < ss->nstrings; i++) + { + h = strhash(ss->stringspace + ss->strings[i]) & hashmask; + hh = HASHCHAIN_START; + while (hashtbl[h] != 0) // follow overflow chain + h = HASHCHAIN_NEXT(h, hh, hashmask); + hashtbl[h] = i; + } + } + + // compute hash and check for match + + h = strhash(str) & hashmask; + hh = HASHCHAIN_START; + while ((id = hashtbl[h]) != 0) // follow hash overflow chain + { + // break if string already hashed + if(!strcmp(ss->stringspace + ss->strings[id], str)) + break; + h = HASHCHAIN_NEXT(h, hh, hashmask); + } + if (id || !create) // exit here if string found + return id; + + // generate next id and save in table + id = ss->nstrings++; + hashtbl[h] = id; + + // + if ((id & STRING_BLOCK) == 0) + ss->strings = xrealloc(ss->strings, ((ss->nstrings + STRING_BLOCK) & ~STRING_BLOCK) * sizeof(Hashval)); + // 'pointer' into stringspace is Offset of next free pos: sstrings + ss->strings[id] = ss->sstrings; + + space_needed = strlen(str) + 1; + + // resize string buffer if needed + if (((ss->sstrings + space_needed - 1) | STRINGSPACE_BLOCK) != ((ss->sstrings - 1) | STRINGSPACE_BLOCK)) + ss->stringspace = xrealloc(ss->stringspace, (ss->sstrings + space_needed + STRINGSPACE_BLOCK) & ~STRINGSPACE_BLOCK); + // copy new string into buffer + memcpy(ss->stringspace + ss->sstrings, str, space_needed); + // next free pos is behind new string + ss->sstrings += space_needed; + + return id; +} + +void +stringpool_shrink (Stringpool *ss) +{ + ss->stringspace = (char *)xrealloc(ss->stringspace, (ss->sstrings + STRINGSPACE_BLOCK) & ~STRINGSPACE_BLOCK); + ss->strings = (Offset *)xrealloc(ss->strings, ((ss->nstrings + STRING_BLOCK) & ~STRING_BLOCK) * sizeof(Offset)); +} Added: trunk/sat-solver/src/strpool.h URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/strpool.h?rev=7844&view=auto ============================================================================== --- trunk/sat-solver/src/strpool.h (added) +++ trunk/sat-solver/src/strpool.h Fri Nov 16 14:48:23 2007 @@ -0,0 +1,31 @@ +/* + * Copyright (c) 2007, Novell Inc. + * + * This program is licensed under the BSD license, read LICENSE.BSD + * for further information + */ +#ifndef STRINGPOOL_H +#define STRINGPOOL_H + +#include "pooltypes.h" +#include "hash.h" + +#define STRID_NULL 0 +#define STRID_EMPTY 1 + +struct _Stringpool +{ + Offset *strings; // table of offsets into stringspace, indexed by Id: Id -> Offset + int nstrings; // number of unique strings in stringspace + char *stringspace; // space for all unique strings: stringspace + Offset = string + Offset sstrings; // next free pos in stringspace + + Hashtable stringhashtbl; // hash table: (string ->) Hash -> Id + Hashmask stringhashmask; // modulo value for hash table (size of table - 1) +}; + +void stringpool_init (Stringpool *ss, const char *strs[]); +Id stringpool_str2id (Stringpool *ss, const char *str, int create); +void stringpool_shrink (Stringpool *ss); + +#endif Modified: trunk/sat-solver/tools/attr_store.c URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/tools/attr_store.c?rev=7844&r1=7843&r2=7844&view=diff ============================================================================== --- trunk/sat-solver/tools/attr_store.c (original) +++ trunk/sat-solver/tools/attr_store.c Fri Nov 16 14:48:23 2007 @@ -45,6 +45,11 @@ Attrstore * new_store (Pool *pool) { + static const char *predef_strings[] = { + "<NULL>", + "", + 0 + }; Attrstore *s = calloc (1, sizeof (Attrstore)); s->pool = pool; s->nameids = calloc (128, sizeof (s->nameids[0])); @@ -52,23 +57,7 @@ s->nameids[0] = 0; s->nameids[1] = 1; - int totalsize = strlen ("<NULL>") + 1 + 1; - int count = 2; - - // alloc appropriate space - s->stringspace = (char *)xmalloc((totalsize + STRINGSPACE_BLOCK) & ~STRINGSPACE_BLOCK); - s->strings = (Offset *)xmalloc(((count + STRING_BLOCK) & ~STRING_BLOCK) * sizeof(Offset)); - - // now copy predefined strings into allocated space - s->sstrings = 0; - strcpy (s->stringspace + s->sstrings, "<NULL>"); - s->strings[0] = s->sstrings; - s->sstrings += strlen (s->stringspace + s->strings[0]) + 1; - strcpy (s->stringspace + s->sstrings, ""); - s->strings[1] = s->sstrings; - s->sstrings += strlen (s->stringspace + s->strings[1]) + 1; - - s->nstrings = 2; + stringpool_init (&s->ss, predef_strings); return s; } @@ -76,82 +65,13 @@ LocalId str2localid (Attrstore *s, const char *str, int create) { - Hashval h; - unsigned int hh; - Hashmask hashmask; - int i, space_needed; - LocalId id; - Hashtable hashtbl; - - // check string - if (!str) - return LOCALID_NULL; - if (!*str) - return LOCALID_EMPTY; - - hashmask = s->stringhashmask; - hashtbl = s->stringhashtbl; - - // expand hashtable if needed - if (s->nstrings * 2 > hashmask) - { - xfree(hashtbl); - - // realloc hash table - s->stringhashmask = hashmask = mkmask(s->nstrings + STRING_BLOCK); - s->stringhashtbl = hashtbl = (Hashtable)xcalloc(hashmask + 1, sizeof(Id)); - - // rehash all strings into new hashtable - for (i = 1; i < s->nstrings; i++) - { - h = strhash(s->stringspace + s->strings[i]) & hashmask; - hh = HASHCHAIN_START; - while (hashtbl[h] != 0) - h = HASHCHAIN_NEXT(h, hh, hashmask); - hashtbl[h] = i; - } - } - - // compute hash and check for match - - h = strhash(str) & hashmask; - hh = HASHCHAIN_START; - while ((id = hashtbl[h]) != 0) - { - // break if string already hashed - if(!strcmp(s->stringspace + s->strings[id], str)) - break; - h = HASHCHAIN_NEXT(h, hh, hashmask); - } - if (id || !create) // exit here if string found - return id; - - // generate next id and save in table - id = s->nstrings++; - hashtbl[h] = id; - - if ((id & STRING_BLOCK) == 0) - s->strings = xrealloc(s->strings, ((s->nstrings + STRING_BLOCK) & ~STRING_BLOCK) * sizeof(Hashval)); - // 'pointer' into stringspace is Offset of next free pos: sstrings - s->strings[id] = s->sstrings; - - space_needed = strlen(str) + 1; - - // resize string buffer if needed - if (((s->sstrings + space_needed - 1) | STRINGSPACE_BLOCK) != ((s->sstrings - 1) | STRINGSPACE_BLOCK)) - s->stringspace = xrealloc(s->stringspace, (s->sstrings + space_needed + STRINGSPACE_BLOCK) & ~STRINGSPACE_BLOCK); - // copy new string into buffer - memcpy(s->stringspace + s->sstrings, str, space_needed); - // next free pos is behind new string - s->sstrings += space_needed; - - return id; + return stringpool_str2id (&s->ss, str, create); } const char * localid2str(Attrstore *s, LocalId id) { - return s->stringspace + s->strings[id]; + return s->ss.stringspace + s->ss.strings[id]; } static NameId @@ -712,10 +632,10 @@ /* Remove the hashtable too, it will be build on demand in str2localid the next time we call it, which should not happen while in packed mode. */ - old_mem += (s->stringhashmask + 1) * sizeof (s->stringhashtbl[0]); - free (s->stringhashtbl); - s->stringhashtbl = 0; - s->stringhashmask = 0; + old_mem += (s->ss.stringhashmask + 1) * sizeof (s->ss.stringhashtbl[0]); + free (s->ss.stringhashtbl); + s->ss.stringhashtbl = 0; + s->ss.stringhashmask = 0; fprintf (stderr, "%d\n", old_mem); fprintf (stderr, "%zd\n", s->entries * sizeof(s->ent2attr[0])); @@ -929,7 +849,7 @@ write_u32 (fp, s->entries); write_u32 (fp, s->num_nameids); - write_u32 (fp, s->nstrings); + write_u32 (fp, s->ss.nstrings); for (i = 2; i < s->num_nameids; i++) { const char *str = id2str (s->pool, s->nameids[i]); @@ -940,11 +860,11 @@ } } - for (i = 2, local_ssize = 0; i < (unsigned)s->nstrings; i++) + for (i = 2, local_ssize = 0; i < (unsigned)s->ss.nstrings; i++) local_ssize += strlen (localid2str (s, i)) + 1; write_u32 (fp, local_ssize); - for (i = 2; i < (unsigned)s->nstrings; i++) + for (i = 2; i < (unsigned)s->ss.nstrings; i++) { const char *str = localid2str (s, i); if (fwrite(str, strlen(str) + 1, 1, fp) != 1) @@ -1199,12 +1119,12 @@ } local_ssize = read_u32 (fp); - char *strsp = (char *)xrealloc(s->stringspace, s->sstrings + local_ssize + 1); - Offset *str = (Offset *)xrealloc(s->strings, (nstrings) * sizeof(Offset)); + char *strsp = (char *)xrealloc(s->ss.stringspace, s->ss.sstrings + local_ssize + 1); + Offset *str = (Offset *)xrealloc(s->ss.strings, (nstrings) * sizeof(Offset)); - s->stringspace = strsp; - s->strings = str; - strsp += s->sstrings; + s->ss.stringspace = strsp; + s->ss.strings = str; + strsp += s->ss.sstrings; if (fread(strsp, local_ssize, 1, fp) != 1) { @@ -1216,14 +1136,14 @@ /* Don't build hashtable here, it will be built on demand by str2localid should we call that. */ - strsp = s->stringspace; - s->nstrings = nstrings; + strsp = s->ss.stringspace; + s->ss.nstrings = nstrings; for (i = 0; i < nstrings; i++) { - str[i] = strsp - s->stringspace; + str[i] = strsp - s->ss.stringspace; strsp += strlen (strsp) + 1; } - s->sstrings = strsp - s->stringspace; + s->ss.sstrings = strsp - s->ss.stringspace; s->entries = nentries; Modified: trunk/sat-solver/tools/attr_store_p.h URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/tools/attr_store_p.h?rev=7844&r1=7843&r2=7844&view=diff ============================================================================== --- trunk/sat-solver/tools/attr_store_p.h (original) +++ trunk/sat-solver/tools/attr_store_p.h Fri Nov 16 14:48:23 2007 @@ -63,13 +63,7 @@ unsigned int *mapped; unsigned int nmapped, ncanmap; - Offset *strings; - int nstrings; - char *stringspace; - Offset sstrings; - Hashtable stringhashtbl; - Hashmask stringhashmask; - + Stringpool ss; /* A space efficient in memory representation. It's read-only. */ /* flat_attrs[ent2attr[i]] are the attrs for entity i. */ Modified: trunk/sat-solver/tools/repo_write.c URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/tools/repo_write.c?rev=7844&r1=7843&r2=7844&view=diff ============================================================================== --- trunk/sat-solver/tools/repo_write.c (original) +++ trunk/sat-solver/tools/repo_write.c Fri Nov 16 14:48:23 2007 @@ -207,7 +207,7 @@ nsolvables = 0; idarraydata = repo->idarraydata; - needid = (NeedId *)calloc(pool->nstrings + pool->nrels, sizeof(*needid)); + needid = (NeedId *)calloc(pool->ss.nstrings + pool->nrels, sizeof(*needid)); memset(idsizes, 0, sizeof(idsizes)); @@ -259,20 +259,20 @@ } needid[0].need = 0; - needid[pool->nstrings].need = 0; - for (i = 0; i < pool->nstrings + pool->nrels; i++) + needid[pool->ss.nstrings].need = 0; + for (i = 0; i < pool->ss.nstrings + pool->nrels; i++) needid[i].map = i; - qsort(needid + 1, pool->nstrings - 1, sizeof(*needid), needid_cmp_need); - qsort(needid + pool->nstrings, pool->nrels, sizeof(*needid), needid_cmp_need); + qsort(needid + 1, pool->ss.nstrings - 1, sizeof(*needid), needid_cmp_need); + qsort(needid + pool->ss.nstrings, pool->nrels, sizeof(*needid), needid_cmp_need); sizeid = 0; - for (i = 1; i < pool->nstrings; i++) + for (i = 1; i < pool->ss.nstrings; i++) { if (!needid[i].need) break; needid[i].need = 0; - sizeid += strlen(pool->stringspace + pool->strings[needid[i].map]) + 1; + sizeid += strlen(pool->ss.stringspace + pool->ss.strings[needid[i].map]) + 1; } nstrings = i; @@ -281,16 +281,16 @@ for (i = 0; i < pool->nrels; i++) { - if (!needid[pool->nstrings + i].need) + if (!needid[pool->ss.nstrings + i].need) break; else - needid[pool->nstrings + i].need = 0; + needid[pool->ss.nstrings + i].need = 0; } nrels = i; for (i = 0; i < nrels; i++) { - needid[needid[pool->nstrings + i].map].need = nstrings + i; + needid[needid[pool->ss.nstrings + i].map].need = nstrings + i; } /* write file header */ @@ -308,7 +308,7 @@ */ for (i = 1; i < nstrings; i++) { - char *str = pool->stringspace + pool->strings[needid[i].map]; + char *str = pool->ss.stringspace + pool->ss.strings[needid[i].map]; if (fwrite(str, strlen(str) + 1, 1, fp) != 1) { perror("write error"); @@ -321,7 +321,7 @@ */ for (i = 0; i < nrels; i++) { - ran = pool->rels + (needid[pool->nstrings + i].map - pool->nstrings); + ran = pool->rels + (needid[pool->ss.nstrings + i].map - pool->ss.nstrings); write_id(fp, needid[ISRELDEP(ran->name) ? GETRELID(pool, ran->name) : ran->name].need); write_id(fp, needid[ISRELDEP(ran->evr) ? GETRELID(pool, ran->evr) : ran->evr].need); write_u8( fp, ran->flags); -- To unsubscribe, e-mail: zypp-commit+unsubscribe@opensuse.org For additional commands, e-mail: zypp-commit+help@opensuse.org