prefix-code the string store, difference-code the dependency idarrays.
[platform/upstream/libsolv.git] / tools / repo_write.c
1 /*
2  * Copyright (c) 2007, Novell Inc.
3  *
4  * This program is licensed under the BSD license, read LICENSE.BSD
5  * for further information
6  */
7
8 /*
9  * repo_write.c
10  * 
11  * Write Repo data out to binary file
12  * 
13  * See doc/README.format for a description 
14  * of the binary file format
15  * 
16  */
17
18 #include <sys/types.h>
19 #include <limits.h>
20 #include <fcntl.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <assert.h>
25
26 #include "pool.h"
27 #include "util.h"
28 #include "repo_write.h"
29
30 /* #define IGNORE_NEED_FREQUENCY */
31
32 /*------------------------------------------------------------------*/
33 /* Id map optimizations */
34
35 typedef struct needid {
36   Id need;
37   Id map;
38 } NeedId;
39
40
41 #define RELOFF(id) (pool->ss.nstrings + GETRELID(id))
42
43 /*
44  * increment need Id
45  * idarray: array of Ids, ID_NULL terminated
46  * needid: array of Id->NeedId
47  * 
48  * return count
49  * 
50  */
51
52 static int
53 incneedid(Pool *pool, Id *idarray, NeedId *needid)
54 {
55   if (!idarray)
56     return 0;
57
58   Id id;
59   int n = 0;
60
61   while ((id = *idarray++) != 0)
62     {
63       n++;
64       while (ISRELDEP(id))
65         {
66           Reldep *rd = GETRELDEP(pool, id);
67           needid[RELOFF(id)].need++;
68           if (ISRELDEP(rd->evr))
69             {
70               Id ida[2];
71               ida[0] = rd->evr;
72               ida[1] = 0;
73               incneedid(pool, ida, needid);
74             }
75           else
76             needid[rd->evr].need++;
77           id = rd->name;
78         }
79       needid[id].need++;
80     }
81   return n + 1;
82 }
83
84
85 /*
86  * 
87  */
88
89 static int
90 needid_cmp_need(const void *ap, const void *bp)
91 {
92   const NeedId *a = ap;
93   const NeedId *b = bp;
94   int r;
95   r = b->need - a->need;
96   if (r)
97     return r;
98   return a->map - b->map;
99 }
100
101 static Pool *cmp_pool;
102 static int
103 needid_cmp_need_s(const void *ap, const void *bp)
104 {
105   const NeedId *a = ap;
106   const NeedId *b = bp;
107   if (a == b)
108     return 0;
109 #ifdef IGNORE_NEED_FREQUENCY
110   if (a->need == 0)
111     return 1;
112   else if (b->need == 0)
113     return -1;
114 #else
115   int r;
116   r = b->need - a->need;
117   if (r)
118     return r;
119 #endif
120   char *as = cmp_pool->ss.stringspace + cmp_pool->ss.strings[a->map];
121   char *bs = cmp_pool->ss.stringspace + cmp_pool->ss.strings[b->map];
122   size_t alen = strlen (as);
123   size_t blen = strlen (bs);
124   return memcmp (as, bs, alen < blen ? alen + 1 : blen + 1);
125 }
126
127
128 /*------------------------------------------------------------------*/
129 /* output routines */
130
131 /*
132  * unsigned 32-bit
133  */
134
135 static void
136 write_u32(FILE *fp, unsigned int x)
137 {
138   if (putc(x >> 24, fp) == EOF ||
139       putc(x >> 16, fp) == EOF ||
140       putc(x >> 8, fp) == EOF ||
141       putc(x, fp) == EOF)
142     {
143       perror("write error");
144       exit(1);
145     }
146 }
147
148
149 /*
150  * unsigned 8-bit
151  */
152
153 static void
154 write_u8(FILE *fp, unsigned int x)
155 {
156   if (putc(x, fp) == EOF)
157     {
158       perror("write error");
159       exit(1);
160     }
161 }
162
163
164 /*
165  * Id
166  */
167
168 static void
169 write_id(FILE *fp, Id x)
170 {
171   if (x >= (1 << 14))
172     {
173       if (x >= (1 << 28))
174         putc((x >> 28) | 128, fp);
175       if (x >= (1 << 21))
176         putc((x >> 21) | 128, fp);
177       putc((x >> 14) | 128, fp);
178     }
179   if (x >= (1 << 7))
180     putc((x >> 7) | 128, fp);
181   if (putc(x & 127, fp) == EOF)
182     {
183       perror("write error");
184       exit(1);
185     }
186 }
187
188
189 /*
190  * Array of Ids
191  */
192
193 static void
194 write_idarray(FILE *fp, Pool *pool, NeedId *needid, Id *ids)
195 {
196   Id id;
197   if (!ids)
198     return;
199   if (!*ids)
200     {
201       write_u8(fp, 0);
202       return;
203     }
204   for (;;)
205     {
206       id = *ids++;
207       if (needid)
208         id = needid[ISRELDEP(id) ? RELOFF(id) : id].need;
209       if (id >= 64)
210         id = (id & 63) | ((id & ~63) << 1);
211       if (!*ids)
212         {
213           write_id(fp, id);
214           return;
215         }
216       write_id(fp, id | 64);
217     }
218 }
219
220 static int
221 cmp_ids (const void *pa, const void *pb)
222 {
223   Id a = *(Id *)pa;
224   Id b = *(Id *)pb;
225   return a - b;
226 }
227
228 static void
229 write_idarray_sort(FILE *fp, Pool *pool, NeedId *needid, Id *ids)
230 {
231   int len, i;
232   if (!ids)
233     return;
234   if (!*ids)
235     {
236       write_u8 (fp, 0);
237       return;
238     }
239   /* If we ever share idarrays we can't do this in-place.  */
240   for (len = 0; ids[len]; len++)
241     {
242       Id id = ids[len];
243       if (needid)
244         ids[len] = needid[ISRELDEP(id) ? RELOFF(id) : id].need;
245     }
246
247   /* That bloody solvable:prereqmarker needs to stay in position :-(  */
248   Id prereq = SOLVABLE_PREREQMARKER;
249   if (needid)
250     prereq = needid[prereq].need;
251   for (i = 0; i < len; i++)
252     if (ids[i] == prereq)
253       break;
254   if (i > 1)
255     qsort (ids, i, sizeof (Id), cmp_ids);
256   if ((len - i) > 2)
257     qsort (ids + i + 1, len - i - 1, sizeof (Id), cmp_ids);
258
259   Id old = 0;
260   for (i = 0; i < len; i++)
261     /* Ugly PREREQ handling.  A "difference" of 1 is the prereq marker,
262        hence all real differences are offsetted by 1.  Otherwise we would
263        have to handle negative differences, which would cost code space for
264        the encoding of the sign.  We loose the exact mapping of prereq here,
265        but we know the result, so we can recover from that in the reader.  */
266     if (ids[i] == prereq)
267       old = ids[i] = 1;
268     else
269       {
270         ids[i] -= old;
271         old = ids[i] + old;
272         /* difference is zero --> we have multiple equal elements in the list */
273         assert (ids[i] > 0);
274         ids[i]++;
275       }
276
277   /* The differencing above produces many runs of ones and twos.  I tried
278      fairly elaborate schemes to RLE those, but they give only very mediocre
279      improvements in compression, as coding the escapes costs quite some
280      space.  Even if they are coded only as bits in IDs.  The best improvement
281      was about 2.7% for the whole .solv file.  It's probably better to
282      invest some complexity into sharing idarrays, than RLEing.  */
283   for (;;)
284     {
285       Id id = *ids++;
286       if (id >= 64)
287         id = (id & 63) | ((id & ~63) << 1);
288       if (!*ids)
289         {
290           write_id(fp, id);
291           return;
292         }
293       write_id(fp, id | 64);
294     }
295 }
296
297 /*
298  * Repo
299  */
300
301 void
302 repo_write(Repo *repo, FILE *fp)
303 {
304   Pool *pool = repo->pool;
305   int i, n;
306   Solvable *s;
307   NeedId *needid;
308   int nstrings, nrels, nkeys, nschemata;
309   unsigned int sizeid;
310   unsigned int solv_flags;
311   Reldep *ran;
312   Id *idarraydata;
313
314   int idsizes[RPM_RPMDBID + 1];
315   int id2key[RPM_RPMDBID + 1];
316   int nsolvables;
317
318   Id *schemadata, *schemadatap, *schema, *sp;
319   Id schemaid;
320   int schemadatalen;
321   Id *solvschema;       /* schema of our solvables */
322   Id lastschema[256];
323   Id lastschemakey[256];
324
325   nsolvables = 0;
326   idarraydata = repo->idarraydata;
327
328   needid = (NeedId *)xcalloc(pool->ss.nstrings + pool->nrels, sizeof(*needid));
329
330   memset(idsizes, 0, sizeof(idsizes));
331
332   for (i = repo->start, s = pool->solvables + i; i < repo->end; i++, s++)
333     {
334       if (s->repo != repo)
335         continue;
336       nsolvables++;
337       needid[s->name].need++;
338       needid[s->arch].need++;
339       needid[s->evr].need++;
340       if (s->vendor)
341         {
342           needid[s->vendor].need++;
343           idsizes[SOLVABLE_VENDOR] = 1;
344         }
345       if (s->provides)
346         idsizes[SOLVABLE_PROVIDES]    += incneedid(pool, idarraydata + s->provides, needid);
347       if (s->requires)
348         idsizes[SOLVABLE_REQUIRES]    += incneedid(pool, idarraydata + s->requires, needid);
349       if (s->conflicts)
350         idsizes[SOLVABLE_CONFLICTS]   += incneedid(pool, idarraydata + s->conflicts, needid);
351       if (s->obsoletes)
352         idsizes[SOLVABLE_OBSOLETES]   += incneedid(pool, idarraydata + s->obsoletes, needid);
353       if (s->recommends)
354         idsizes[SOLVABLE_RECOMMENDS]  += incneedid(pool, idarraydata + s->recommends, needid);
355       if (s->suggests)
356         idsizes[SOLVABLE_SUGGESTS]    += incneedid(pool, idarraydata + s->suggests, needid);
357       if (s->supplements)
358         idsizes[SOLVABLE_SUPPLEMENTS] += incneedid(pool, idarraydata + s->supplements, needid);
359       if (s->enhances)
360         idsizes[SOLVABLE_ENHANCES]    += incneedid(pool, idarraydata + s->enhances, needid);
361       if (s->freshens)
362         idsizes[SOLVABLE_FRESHENS]    += incneedid(pool, idarraydata + s->freshens, needid);
363     }
364   if (nsolvables != repo->nsolvables)
365     abort();
366
367   idsizes[SOLVABLE_NAME] = 1;
368   idsizes[SOLVABLE_ARCH] = 1;
369   idsizes[SOLVABLE_EVR] = 1;
370   if (repo->rpmdbid)
371     idsizes[RPM_RPMDBID] = 1;
372
373   for (i = SOLVABLE_NAME; i <= RPM_RPMDBID; i++)
374     {
375       if (idsizes[i])
376         needid[i].need++;
377     }
378
379   needid[0].need = 0;
380   needid[pool->ss.nstrings].need = 0;
381   for (i = 0; i < pool->ss.nstrings + pool->nrels; i++)
382     needid[i].map = i;
383
384   cmp_pool = pool;
385   qsort(needid + 1, pool->ss.nstrings - 1, sizeof(*needid), needid_cmp_need_s);
386   qsort(needid + pool->ss.nstrings, pool->nrels, sizeof(*needid), needid_cmp_need);
387
388   sizeid = 0;
389   for (i = 1; i < pool->ss.nstrings; i++)
390     {
391       if (!needid[i].need)
392         break;
393       needid[i].need = 0;
394       sizeid += strlen(pool->ss.stringspace + pool->ss.strings[needid[i].map]) + 1;
395     }
396
397   nstrings = i;
398   for (i = 0; i < nstrings; i++)
399     needid[needid[i].map].need = i;
400
401   for (i = 0; i < pool->nrels; i++)
402     {
403       if (!needid[pool->ss.nstrings + i].need)
404         break;
405       else
406         needid[pool->ss.nstrings + i].need = 0;
407     }
408
409   nrels = i;
410   for (i = 0; i < nrels; i++)
411     {
412       needid[needid[pool->ss.nstrings + i].map].need = nstrings + i;
413     }
414
415   /* find the keys we need */
416   nkeys = 1;
417   memset(id2key, 0, sizeof(id2key));
418   for (i = SOLVABLE_NAME; i <= RPM_RPMDBID; i++)
419     if (idsizes[i])
420       id2key[i] = nkeys++;
421
422   /* find the schemata we need */
423   solvschema = xcalloc(repo->nsolvables, sizeof(Id));
424
425   memset(lastschema, 0, sizeof(lastschema));
426   memset(lastschemakey, 0, sizeof(lastschemakey));
427   schemadata = xmalloc(256 * sizeof(Id));
428   schemadatalen = 256;
429   schemadatap = schemadata;
430   *schemadatap++ = 0;
431   schemadatalen--;
432   nschemata = 0;
433   for (i = repo->start, s = pool->solvables + i, n = 0; i < repo->end; i++, s++)
434     {
435       unsigned int h;
436       Id *sp;
437
438       if (s->repo != repo)
439         continue;
440       if (schemadatalen < 32)
441         {
442           int l = schemadatap - schemadata;
443           fprintf(stderr, "growing schemadata\n");
444           schemadata = xrealloc(schemadata, (schemadatap - schemadata + 256) * sizeof(Id));
445           schemadatalen = 256;
446           schemadatap = schemadata + l;
447         }
448       schema = schemadatap;
449       *schema++ = SOLVABLE_NAME;
450       *schema++ = SOLVABLE_ARCH;
451       *schema++ = SOLVABLE_EVR;
452       if (s->vendor)
453         *schema++ = SOLVABLE_VENDOR;
454       if (s->provides)
455         *schema++ = SOLVABLE_PROVIDES;
456       if (s->obsoletes)
457         *schema++ = SOLVABLE_OBSOLETES;
458       if (s->conflicts)
459         *schema++ = SOLVABLE_CONFLICTS;
460       if (s->requires)
461         *schema++ = SOLVABLE_REQUIRES;
462       if (s->recommends)
463         *schema++ = SOLVABLE_RECOMMENDS;
464       if (s->suggests)
465         *schema++ = SOLVABLE_SUGGESTS;
466       if (s->supplements)
467         *schema++ = SOLVABLE_SUPPLEMENTS;
468       if (s->enhances)
469         *schema++ = SOLVABLE_ENHANCES;
470       if (s->freshens)
471         *schema++ = SOLVABLE_FRESHENS;
472       if (repo->rpmdbid)
473         *schema++ = RPM_RPMDBID;
474       *schema++ = 0;
475       for (sp = schemadatap, h = 0; *sp; )
476         h = h * 7 + *sp++;
477       h &= 255;
478       if (lastschema[h] && !memcmp(schemadata + lastschema[h], schemadatap, (schema - schemadatap) * sizeof(Id)))
479         {
480           solvschema[n++] = lastschemakey[h];
481           continue;
482         }
483       schemaid = 0;
484       for (sp = schemadata + 1; sp < schemadatap; )
485         {
486           if (!memcmp(sp, schemadatap, (schema - schemadatap) * sizeof(Id)))
487             break;
488           while (*sp++)
489             ;
490           schemaid++;
491         }
492       if (sp >= schemadatap)
493         {
494           if (schemaid != nschemata)
495             abort();
496           lastschema[h] = schemadatap - schemadata;
497           lastschemakey[h] = schemaid;
498           schemadatalen -= schema - schemadatap;
499           schemadatap = schema;
500           nschemata++;
501         }
502       solvschema[n++] = schemaid;
503     }
504   /* convert all schemas to keys */
505   for (sp = schemadata; sp < schemadatap; sp++)
506     *sp = id2key[*sp];
507
508   /* write file header */
509   write_u32(fp, 'S' << 24 | 'O' << 16 | 'L' << 8 | 'V');
510   write_u32(fp, SOLV_VERSION_2);
511
512   /* write counts */
513   write_u32(fp, nstrings);
514   write_u32(fp, nrels);
515   write_u32(fp, nsolvables);
516   write_u32(fp, nkeys);
517   write_u32(fp, nschemata);
518   write_u32(fp, 0);     /* no info block */
519   solv_flags = 0;
520   solv_flags |= SOLV_FLAG_PREFIX_POOL;
521 #if 0
522   solv_flags |= SOLV_FLAG_VERTICAL;
523 #endif
524   write_u32(fp, solv_flags);
525
526   /* Build the prefix-encoding of the string pool.  We need to know
527      the size of that before writing it to the file, so we have to
528      build a separate buffer for that.  As it's temporarily possible
529      that this actually is an expansion we can't easily reuse the 
530      stringspace for this.  The max expansion per string is 1 byte,
531      so it will fit into sizeid+nstrings bytes.  */
532   char *prefix = xmalloc (sizeid + nstrings);
533   char *pp = prefix;
534   char *old_str = "";
535   for (i = 1; i < nstrings; i++)
536     {
537       char *str = pool->ss.stringspace + pool->ss.strings[needid[i].map];
538       int same;
539       size_t len;
540       for (same = 0; same < 255; same++)
541         if (old_str[same] != str[same])
542           break;
543       *pp++ = same;
544       len = strlen (str + same) + 1;
545       memcpy (pp, str + same, len);
546       pp += len;
547       old_str = str;
548     }
549
550   /*
551    * write strings
552    */
553   write_u32(fp, sizeid);
554   write_u32(fp, pp - prefix);
555   if (fwrite(prefix, pp - prefix, 1, fp) != 1)
556     {
557       perror("write error");
558       exit(1);
559     }
560   xfree (prefix);
561
562   /*
563    * write RelDeps
564    */
565   for (i = 0; i < nrels; i++)
566     {
567       ran = pool->rels + (needid[pool->ss.nstrings + i].map - pool->ss.nstrings);
568       write_id(fp, needid[ISRELDEP(ran->name) ? RELOFF(ran->name) : ran->name].need);
569       write_id(fp, needid[ISRELDEP(ran->evr) ? RELOFF(ran->evr) : ran->evr].need);
570       write_u8( fp, ran->flags);
571     }
572
573   /*
574    * write keys
575    */
576   for (i = SOLVABLE_NAME; i <= RPM_RPMDBID; i++)
577     {
578       if (!idsizes[i])
579         continue;
580       write_id(fp, needid[i].need);
581       if (i >= SOLVABLE_PROVIDES && i <= SOLVABLE_FRESHENS)
582         write_id(fp, TYPE_REL_IDARRAY);
583       else if (i == RPM_RPMDBID)
584         write_id(fp, TYPE_U32);
585       else
586         write_id(fp, TYPE_ID);
587       write_id(fp, idsizes[i]);
588     }
589
590   /*
591    * write schemata
592    */
593   write_id(fp, schemadatap - schemadata - 1);
594   for (sp = schemadata + 1; sp < schemadatap; )
595     {
596       write_idarray(fp, pool, 0, sp);
597       while (*sp++)
598         ;
599     }
600   
601 #if 0
602   if (1)
603     {
604       Id id, key;
605
606       for (i = 0; i < nsolvables; i++)
607         write_id(fp, solvschema[i]);
608       unsigned char *used = xmalloc(nschemata);
609       for (id = SOLVABLE_NAME; id <= RPM_RPMDBID; id++)
610         {
611           key = id2key[id];
612           memset(used, 0, nschemata);
613           for (sp = schemadata + 1, i = 0; sp < schemadatap; sp++)
614             {
615               if (*sp == 0)
616                 i++;
617               else if (*sp == key)
618                 used[i] = 1;
619             }
620           for (i = repo->start, s = pool->solvables + i, n = 0; i < repo->end; i++, s++)
621             {
622               if (s->repo != repo)
623                 continue;
624               if (!used[solvschema[n++]])
625                 continue;
626               switch(id)
627                 {
628                 case SOLVABLE_NAME:
629                   write_id(fp, needid[s->name].need);
630                   break;
631                 case SOLVABLE_ARCH:
632                   write_id(fp, needid[s->arch].need);
633                   break;
634                 case SOLVABLE_EVR:
635                   write_id(fp, needid[s->evr].need);
636                   break;
637                 case SOLVABLE_VENDOR:
638                   write_id(fp, needid[s->vendor].need);
639                   break;
640                 case RPM_RPMDBID:
641                   write_u32(fp, repo->rpmdbid[i - repo->start]);
642                   break;
643                 case SOLVABLE_PROVIDES:
644                   write_idarray(fp, pool, needid, idarraydata + s->provides);
645                   break;
646                 case SOLVABLE_OBSOLETES:
647                   write_idarray(fp, pool, needid, idarraydata + s->obsoletes);
648                   break;
649                 case SOLVABLE_CONFLICTS:
650                   write_idarray(fp, pool, needid, idarraydata + s->conflicts);
651                   break;
652                 case SOLVABLE_REQUIRES:
653                   write_idarray(fp, pool, needid, idarraydata + s->requires);
654                   break;
655                 case SOLVABLE_RECOMMENDS:
656                   write_idarray(fp, pool, needid, idarraydata + s->recommends);
657                   break;
658                 case SOLVABLE_SUPPLEMENTS:
659                   write_idarray(fp, pool, needid, idarraydata + s->supplements);
660                   break;
661                 case SOLVABLE_SUGGESTS:
662                   write_idarray(fp, pool, needid, idarraydata + s->suggests);
663                   break;
664                 case SOLVABLE_ENHANCES:
665                   write_idarray(fp, pool, needid, idarraydata + s->enhances);
666                   break;
667                 case SOLVABLE_FRESHENS:
668                   write_idarray(fp, pool, needid, idarraydata + s->freshens);
669                   break;
670                 }
671             }
672         }
673       xfree(used);
674       xfree(needid);
675       xfree(solvschema);
676       xfree(schemadata);
677       return;
678     }
679   
680 #endif
681
682   /*
683    * write Solvables
684    */
685   for (i = repo->start, s = pool->solvables + i, n = 0; i < repo->end; i++, s++)
686     {
687       if (s->repo != repo)
688         continue;
689       /* keep in sync with schema generation! */
690       write_id(fp, solvschema[n++]);
691       write_id(fp, needid[s->name].need);
692       write_id(fp, needid[s->arch].need);
693       write_id(fp, needid[s->evr].need);
694       if (s->vendor)
695         write_id(fp, needid[s->vendor].need);
696       if (s->provides)
697         write_idarray_sort(fp, pool, needid, idarraydata + s->provides);
698       if (s->obsoletes)
699         write_idarray_sort(fp, pool, needid, idarraydata + s->obsoletes);
700       if (s->conflicts)
701         write_idarray_sort(fp, pool, needid, idarraydata + s->conflicts);
702       if (s->requires)
703         write_idarray_sort(fp, pool, needid, idarraydata + s->requires);
704       if (s->recommends)
705         write_idarray_sort(fp, pool, needid, idarraydata + s->recommends);
706       if (s->suggests)
707         write_idarray_sort(fp, pool, needid, idarraydata + s->suggests);
708       if (s->supplements)
709         write_idarray_sort(fp, pool, needid, idarraydata + s->supplements);
710       if (s->enhances)
711         write_idarray_sort(fp, pool, needid, idarraydata + s->enhances);
712       if (s->freshens)
713         write_idarray_sort(fp, pool, needid, idarraydata + s->freshens);
714       if (repo->rpmdbid)
715         write_u32(fp, repo->rpmdbid[i - repo->start]);
716     }
717
718   xfree(needid);
719   xfree(solvschema);
720   xfree(schemadata);
721 }
722
723 // EOF