Author: matz Date: Fri Dec 28 01:04:38 2007 New Revision: 8153 URL: http://svn.opensuse.org/viewcvs/zypp?rev=8153&view=rev Log: Memory efficient representation of the dirtree (important for unabridged packages.DU). Store and reread the dirtree (in a hacky way, should use the info block). Make dumpattr show the directory names. On disk the same info as in my 10.3 packages.DU (1.4MB, 330 KB gzipped) only takes 146 KB. Modified: trunk/sat-solver/src/attr_store.c trunk/sat-solver/src/attr_store_p.h trunk/sat-solver/tools/dumpattr.c Modified: trunk/sat-solver/src/attr_store.c URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/attr_store.c?rev=8153&r1=8152&r2=8153&view=diff ============================================================================== --- trunk/sat-solver/src/attr_store.c (original) +++ trunk/sat-solver/src/attr_store.c Fri Dec 28 01:04:38 2007 @@ -96,6 +96,37 @@ stringpool_init (&s->dirtree.ss, ss_init_strs); } +#if 0 +static void +dir_setup_flatsons (Dirtree *d) +{ + if (d->flatsons) + return; + if (!d->nflatdirs) + return; + d->flatsons = xcalloc (d->nflatdirs, sizeof (d->flatsons[0])); + unsigned firstson = -1; + unsigned i; + for (i = 0; i < d->nflatdirs; i++) + if (d->flatdirs[i] & 1) + /* A node, i.e. potential son. */ + { + if (firstson == -1) + firstson = i; + } + else if (d->flatdirs[i] & 2) + /* An intermediate parent pointer. */ + ; + else + /* The final parent pointer. Remember the first son. */ + { + assert (firstson != -1); + d->flatsons[d->flatdirs[i] >> 2] = firstson; + firstson = -1; + } +} +#endif + static unsigned dir_lookup_1 (Attrstore *s, unsigned dir, const char *name, unsigned insert) { @@ -188,17 +219,30 @@ unsigned dir_parent (Attrstore *s, unsigned dir) { - return s->dirtree.dirs[dir].parent; + if (s->dirtree.dirs) + return s->dirtree.dirs[dir].parent; + /* We have the packed representation. */ + unsigned p; + while ((p = s->dirtree.flatdirs[dir]) & 1) + dir++; + return p >> 2; } void dir2str (Attrstore *s, unsigned dir, char **str, unsigned *len) { unsigned l = 0; - Id ids[s->dirtree.dirstack_size + 1]; + Id ids[256]; unsigned i, ii; - for (i = 0; dir > 1; dir = dir_parent (s, dir), i++) - ids[i] = s->dirtree.dirs[dir].name; + if (s->dirtree.dirs) + for (i = 0; i < 256 && dir > 1; dir = dir_parent (s, dir), i++) + ids[i] = s->dirtree.dirs[dir].name; + else + for (i = 0; i < 256 && dir > 1; dir = dir_parent (s, dir), i++) + { + assert (s->dirtree.flatdirs[dir] & 1); + ids[i] = s->dirtree.flatdirs[dir] >> 1; + } ii = i; l = 1; for (i = 0; i < ii; i++) @@ -787,6 +831,47 @@ return s->nkeys++; } +#define DIR_BLOCK 1023 +#define CACHE_LINE 32 +#define CACHE_LINE_ELEMS (CACHE_LINE / sizeof(unsigned)) + +static void +finalize_dirs_rec (Dirtree *d, unsigned dir) +{ + unsigned c, parent; + if (!d->dirs[dir].child) + return; + parent = d->dirmap[dir]; + assert(parent); + parent--; + for (c = d->dirs[dir].child; c; c = d->dirs[c].sibling) + { + unsigned id = d->dirs[c].name; + if ((d->nflatdirs & (CACHE_LINE_ELEMS - 1)) == CACHE_LINE_ELEMS - 1) + add_elem (d->flatdirs, d->nflatdirs, parent * 4 + 2, DIR_BLOCK); + d->dirmap[c] = d->nflatdirs + 1; + add_elem (d->flatdirs, d->nflatdirs, id * 2 + 1, DIR_BLOCK); + } + add_elem (d->flatdirs, d->nflatdirs, parent * 4, DIR_BLOCK); + for (c = d->dirs[dir].child; c; c = d->dirs[c].sibling) + finalize_dirs_rec (d, c); +} + +static void +finalize_dirtree (Dirtree *d) +{ + if (d->nflatdirs || !d->ndirs) + return; + d->dirmap = calloc (d->ndirs, sizeof (d->dirmap[0])); + d->nflatdirs = 0; + d->flatdirs = 0; + d->flatsons = 0; + d->dirmap[1] = d->nflatdirs + 1; + finalize_dirs_rec (d, 1); + xfree (d->dirs); + d->dirs = 0; +} + void attr_store_pack (Attrstore *s) { @@ -794,6 +879,8 @@ unsigned int old_mem = 0; if (s->packed) return; + finalize_dirtree (&s->dirtree); + s->ent2attr = xcalloc (s->entries, sizeof (s->ent2attr[0])); s->flat_attrs = 0; s->attr_next_free = 0; @@ -802,6 +889,8 @@ s->schemata = 0; s->schemaofs = 0; + Id id_diskusage = str2id (s->pool, "diskusage", 0); + add_num (s->flat_attrs, s->attr_next_free, 0, FLAT_ATTR_BLOCK); add_elem (s->schemata, s->szschemata, 0, SCHEMA_BLOCK); add_elem (s->schemaofs, s->nschemata, 0, SCHEMA_BLOCK); @@ -878,7 +967,14 @@ { const int *il = nv[ofs].v.intlist; int len = *il++; - //add_num (s->flat_attrs, s->attr_next_free, len, FLAT_ATTR_BLOCK); + if (s->dirtree.dirmap + && s->keys[nv[ofs].key].name == id_diskusage) + { + unsigned i; + assert (!(len % 3)); + for (i = 1; i <= len; i += 3) + nv[ofs].v.intlist[i] = s->dirtree.dirmap[nv[ofs].v.intlist[i]] - 1; + } old_mem += 4 * (len + 1); while (len--) { @@ -911,6 +1007,8 @@ old_mem += s->entries * sizeof (s->attrs[0]); free (s->attrs); s->attrs = 0; + xfree (s->dirtree.dirmap); + s->dirtree.dirmap = 0; /* 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. */ @@ -1015,6 +1113,7 @@ xfree (s->schemata); s->schemata = 0; s->szschemata = 0; + /* XXX unpack the dirtree */ } static void @@ -1247,6 +1346,28 @@ exit (1); } + /* XXX write the dirtree as info block. */ + write_id (fp, s->dirtree.ndirs); + if (s->dirtree.ndirs) + { + for (i = 1, local_ssize = 0; i < (unsigned)s->dirtree.ss.nstrings; i++) + local_ssize += 1 + strlen (s->dirtree.ss.stringspace + s->dirtree.ss.strings[i]); + + write_u32 (fp, s->dirtree.ss.nstrings); + write_u32 (fp, local_ssize); + for (i = 1; i < (unsigned)s->dirtree.ss.nstrings; i++) + { + const char *str = s->dirtree.ss.stringspace + s->dirtree.ss.strings[i]; + if (fwrite(str, strlen(str) + 1, 1, fp) != 1) + { + perror("write error"); + exit(1); + } + } + write_id (fp, s->dirtree.nflatdirs); + for (i = 0; i < s->dirtree.nflatdirs; i++) + write_id (fp, s->dirtree.flatdirs[i]); + } write_pages (fp, s); } @@ -1483,12 +1604,51 @@ } } +static void +read_stringpool (FILE *fp, Stringpool *ss, unsigned nstrings) +{ + unsigned i; + unsigned local_ssize; + /* Slightly hacky. Our local string pool already contains "<NULL>" and + "". We write out the "" too, so we have to read over it. We write it + out to be compatible with the SOLV file and to not have to introduce + merging and mapping the string IDs. */ + local_ssize = read_u32 (fp) - 1; + char *strsp = (char *)xrealloc(ss->stringspace, ss->sstrings + local_ssize + 1); + Offset *str = (Offset *)xrealloc(ss->strings, nstrings * sizeof(Offset)); + + ss->stringspace = strsp; + ss->strings = str; + strsp += ss->sstrings; + + unsigned char ignore_char = 1; + if (fread(&ignore_char, 1, 1, fp) != 1 + || (local_ssize && fread(strsp, local_ssize, 1, fp) != 1) + || ignore_char != 0) + { + perror ("read error while reading strings"); + exit(1); + } + strsp[local_ssize] = 0; + + /* Don't build hashtable here, it will be built on demand by str2localid + should we call that. */ + + strsp = ss->stringspace; + ss->nstrings = nstrings; + for (i = 0; i < nstrings; i++) + { + str[i] = strsp - ss->stringspace; + strsp += strlen (strsp) + 1; + } + ss->sstrings = strsp - ss->stringspace; +} + Attrstore * attr_store_read (FILE *fp, Pool *pool) { unsigned nentries; unsigned i; - unsigned local_ssize; unsigned nstrings, nschemata; Attrstore *s = new_store (pool); @@ -1520,39 +1680,7 @@ exit (1); } - /* Slightly hacky. Our local string pool already contains "<NULL>" and - "". We write out the "" too, so we have to read over it. We write it - out to be compatible with the SOLV file and to not have to introduce - merging and mapping the string IDs. */ - local_ssize = read_u32 (fp) - 1; - char *strsp = (char *)xrealloc(s->ss.stringspace, s->ss.sstrings + local_ssize + 1); - Offset *str = (Offset *)xrealloc(s->ss.strings, (nstrings) * sizeof(Offset)); - - s->ss.stringspace = strsp; - s->ss.strings = str; - strsp += s->ss.sstrings; - - unsigned char ignore_char = 1; - if (fread(&ignore_char, 1, 1, fp) != 1 - || (local_ssize && fread(strsp, local_ssize, 1, fp) != 1) - || ignore_char != 0) - { - perror ("read error while reading strings"); - exit(1); - } - strsp[local_ssize] = 0; - - /* Don't build hashtable here, it will be built on demand by str2localid - should we call that. */ - - strsp = s->ss.stringspace; - s->ss.nstrings = nstrings; - for (i = 0; i < nstrings; i++) - { - str[i] = strsp - s->ss.stringspace; - strsp += strlen (strsp) + 1; - } - s->ss.sstrings = strsp - s->ss.stringspace; + read_stringpool (fp, &s->ss, nstrings); s->keys = xrealloc (s->keys, ((s->nkeys + KEY_BLOCK) & ~KEY_BLOCK) * sizeof (s->keys[0])); /* s->keys[0] is initialized in new_store. */ @@ -1603,6 +1731,22 @@ exit (1); } + s->dirtree.ndirs = read_id (fp, 0); + if (s->dirtree.ndirs) + { + unsigned ndirs = s->dirtree.ndirs; + setup_dirs (s); + xfree (s->dirtree.dirs); + s->dirtree.dirs = 0; + s->dirtree.ndirs = ndirs; + + nstrings = read_u32 (fp); + read_stringpool (fp, &s->dirtree.ss, nstrings); + s->dirtree.nflatdirs = read_id (fp, 0); + s->dirtree.flatdirs = xmalloc (s->dirtree.nflatdirs * sizeof (s->dirtree.flatdirs[0])); + for (i = 0; i < s->dirtree.nflatdirs; i++) + s->dirtree.flatdirs[i] = read_id (fp, 0); + } read_or_setup_pages (fp, s); s->packed = 1; Modified: trunk/sat-solver/src/attr_store_p.h URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/attr_store_p.h?rev=8153&r1=8152&r2=8153&view=diff ============================================================================== --- trunk/sat-solver/src/attr_store_p.h (original) +++ trunk/sat-solver/src/attr_store_p.h Fri Dec 28 01:04:38 2007 @@ -47,6 +47,18 @@ Id name; } Dir; +typedef struct _Dirtree { + Dir *dirs; + unsigned ndirs; + Stringpool ss; + unsigned *dirstack; + unsigned ndirstack, dirstack_size; + unsigned *flatdirs; + unsigned nflatdirs; + unsigned *flatsons; + unsigned *dirmap; +} Dirtree; + struct _Attrstore { Pool *pool; @@ -65,13 +77,7 @@ Stringpool ss; - struct Dirtree { - Dir *dirs; - unsigned ndirs; - Stringpool ss; - unsigned *dirstack; - unsigned ndirstack, dirstack_size; - } dirtree; + Dirtree dirtree; /* 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/dumpattr.c URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/tools/dumpattr.c?rev=8153&r1=8152&r2=8153&view=diff ============================================================================== --- trunk/sat-solver/tools/dumpattr.c (original) +++ trunk/sat-solver/tools/dumpattr.c Fri Dec 28 01:04:38 2007 @@ -18,6 +18,38 @@ #include "pool.h" #include "attr_store_p.h" +static Id id_diskusage; + +static void +dump_diskusage (Attrstore *s, const unsigned char *numlist) +{ + char sbuf[1024]; + char *buf = sbuf; + unsigned slen = sizeof (sbuf); + fprintf (stdout, "DU\n"); + while (1) + { + unsigned dirid, filesz, filenum; + int val; + get_num (numlist, val); + dirid = (val & 63) | ((val >> 1) & ~63); + if (!(val & 64)) + break; + get_num (numlist, val); + filesz = (val & 63) | ((val >> 1) & ~63); + if (!(val & 64)) + break; + get_num (numlist, val); + filenum = (val & 63) | ((val >> 1) & ~63); + dir2str (s, dirid, &buf, &slen); + fprintf (stdout, " %s %d %d %d\n", buf, dirid, filesz, filenum); + if (!(val & 64)) + break; + } + if (buf != sbuf) + free (buf); +} + static void dump_attrs (Attrstore *s, unsigned int entry) { @@ -43,19 +75,22 @@ fprintf (stdout, "str %s\n", ai.as_string); break; case TYPE_ATTR_INTLIST: - { - fprintf (stdout, "lint\n "); - while (1) - { - int val; - get_num (ai.as_numlist, val); - fprintf (stdout, " %d", (val & 63) | ((val >> 1) & ~63)); - if (!(val & 64)) - break; - } - fprintf (stdout, "\n"); - break; - } + if (ai.name == id_diskusage) + dump_diskusage (s, ai.as_numlist); + else + { + fprintf (stdout, "lint\n "); + while (1) + { + int val; + get_num (ai.as_numlist, val); + fprintf (stdout, " %d", (val & 63) | ((val >> 1) & ~63)); + if (!(val & 64)) + break; + } + fprintf (stdout, "\n"); + } + break; case TYPE_ATTR_LOCALIDS: { fprintf (stdout, "lids"); @@ -93,6 +128,7 @@ unsigned int i; Pool *pool = pool_create (); Attrstore *s = attr_store_read (stdin, pool); + id_diskusage = str2id (pool, "diskusage", 0); /* For now test the packing code. */ attr_store_unpack (s); attr_store_pack (s); -- To unsubscribe, e-mail: zypp-commit+unsubscribe@opensuse.org For additional commands, e-mail: zypp-commit+help@opensuse.org