While trying to regenerate the testsuite I noticed that non-unique
[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       /* XXX I think this is broken.  A lone '0' will be interpreted as
202          zero plus end-of-array, which stores another zero.  */
203       write_u8(fp, 0);
204       return;
205     }
206   for (;;)
207     {
208       id = *ids++;
209       if (needid)
210         id = needid[ISRELDEP(id) ? RELOFF(id) : id].need;
211       if (id >= 64)
212         id = (id & 63) | ((id & ~63) << 1);
213       if (!*ids)
214         {
215           write_id(fp, id);
216           return;
217         }
218       write_id(fp, id | 64);
219     }
220 }
221
222 static int
223 cmp_ids (const void *pa, const void *pb)
224 {
225   Id a = *(Id *)pa;
226   Id b = *(Id *)pb;
227   return a - b;
228 }
229
230 static void
231 write_idarray_sort(FILE *fp, Pool *pool, NeedId *needid, Id *ids)
232 {
233   int len, i;
234   if (!ids)
235     return;
236   if (!*ids)
237     {
238       /* XXX I think this is broken.  A lone '0' will be interpreted as
239          zero plus end-of-array, which stores another zero.  */
240       write_u8 (fp, 0);
241       return;
242     }
243   /* If we ever share idarrays we can't do this in-place.  */
244   for (len = 0; ids[len]; len++)
245     {
246       Id id = ids[len];
247       if (needid)
248         ids[len] = needid[ISRELDEP(id) ? RELOFF(id) : id].need;
249     }
250
251   /* That bloody solvable:prereqmarker needs to stay in position :-(  */
252   Id prereq = SOLVABLE_PREREQMARKER;
253   if (needid)
254     prereq = needid[prereq].need;
255   for (i = 0; i < len; i++)
256     if (ids[i] == prereq)
257       break;
258   if (i > 1)
259     qsort (ids, i, sizeof (Id), cmp_ids);
260   if ((len - i) > 2)
261     qsort (ids + i + 1, len - i - 1, sizeof (Id), cmp_ids);
262
263   Id old = 0;
264   for (i = 0; i < len; i++)
265     /* Ugly PREREQ handling.  A "difference" of 0 is the prereq marker,
266        hence all real differences are offsetted by 1.  Otherwise we would
267        have to handle negative differences, which would cost code space for
268        the encoding of the sign.  We loose the exact mapping of prereq here,
269        but we know the result, so we can recover from that in the reader.  */
270     if (ids[i] == prereq)
271       old = ids[i] = 0;
272     else
273       {
274         ids[i] -= old;
275         old = ids[i] + old;
276         /* XXX If difference is zero we have multiple equal elements,
277            we might want to skip writing them out.  */
278         ids[i]++;
279       }
280
281   /* The differencing above produces many runs of ones and twos.  I tried
282      fairly elaborate schemes to RLE those, but they give only very mediocre
283      improvements in compression, as coding the escapes costs quite some
284      space.  Even if they are coded only as bits in IDs.  The best improvement
285      was about 2.7% for the whole .solv file.  It's probably better to
286      invest some complexity into sharing idarrays, than RLEing.  */
287   for (i = 0; i < len - 1; i++)
288     {
289       Id id = ids[i];
290       if (id >= 64)
291         id = (id & 63) | ((id & ~63) << 1);
292       write_id(fp, id | 64);
293     }
294   old = ids[i];
295   if (old >= 64)
296     old = (old & 63) | ((old & ~63) << 1);
297   write_id(fp, old);
298 }
299
300 /*
301  * Repo
302  */
303
304 void
305 repo_write(Repo *repo, FILE *fp)
306 {
307   Pool *pool = repo->pool;
308   int i, n;
309   Solvable *s;
310   NeedId *needid;
311   int nstrings, nrels, nkeys, nschemata;
312   unsigned int sizeid;
313   unsigned int solv_flags;
314   Reldep *ran;
315   Id *idarraydata;
316
317   int idsizes[RPM_RPMDBID + 1];
318   int id2key[RPM_RPMDBID + 1];
319   int nsolvables;
320
321   Id *schemadata, *schemadatap, *schema, *sp;
322   Id schemaid;
323   int schemadatalen;
324   Id *solvschema;       /* schema of our solvables */
325   Id lastschema[256];
326   Id lastschemakey[256];
327
328   nsolvables = 0;
329   idarraydata = repo->idarraydata;
330
331   needid = (NeedId *)xcalloc(pool->ss.nstrings + pool->nrels, sizeof(*needid));
332
333   memset(idsizes, 0, sizeof(idsizes));
334
335   for (i = repo->start, s = pool->solvables + i; i < repo->end; i++, s++)
336     {
337       if (s->repo != repo)
338         continue;
339       nsolvables++;
340       needid[s->name].need++;
341       needid[s->arch].need++;
342       needid[s->evr].need++;
343       if (s->vendor)
344         {
345           needid[s->vendor].need++;
346           idsizes[SOLVABLE_VENDOR] = 1;
347         }
348       if (s->provides)
349         idsizes[SOLVABLE_PROVIDES]    += incneedid(pool, idarraydata + s->provides, needid);
350       if (s->requires)
351         idsizes[SOLVABLE_REQUIRES]    += incneedid(pool, idarraydata + s->requires, needid);
352       if (s->conflicts)
353         idsizes[SOLVABLE_CONFLICTS]   += incneedid(pool, idarraydata + s->conflicts, needid);
354       if (s->obsoletes)
355         idsizes[SOLVABLE_OBSOLETES]   += incneedid(pool, idarraydata + s->obsoletes, needid);
356       if (s->recommends)
357         idsizes[SOLVABLE_RECOMMENDS]  += incneedid(pool, idarraydata + s->recommends, needid);
358       if (s->suggests)
359         idsizes[SOLVABLE_SUGGESTS]    += incneedid(pool, idarraydata + s->suggests, needid);
360       if (s->supplements)
361         idsizes[SOLVABLE_SUPPLEMENTS] += incneedid(pool, idarraydata + s->supplements, needid);
362       if (s->enhances)
363         idsizes[SOLVABLE_ENHANCES]    += incneedid(pool, idarraydata + s->enhances, needid);
364       if (s->freshens)
365         idsizes[SOLVABLE_FRESHENS]    += incneedid(pool, idarraydata + s->freshens, needid);
366     }
367   if (nsolvables != repo->nsolvables)
368     abort();
369
370   idsizes[SOLVABLE_NAME] = 1;
371   idsizes[SOLVABLE_ARCH] = 1;
372   idsizes[SOLVABLE_EVR] = 1;
373   if (repo->rpmdbid)
374     idsizes[RPM_RPMDBID] = 1;
375
376   for (i = SOLVABLE_NAME; i <= RPM_RPMDBID; i++)
377     {
378       if (idsizes[i])
379         needid[i].need++;
380     }
381
382   needid[0].need = 0;
383   needid[pool->ss.nstrings].need = 0;
384   for (i = 0; i < pool->ss.nstrings + pool->nrels; i++)
385     needid[i].map = i;
386
387   cmp_pool = pool;
388   qsort(needid + 1, pool->ss.nstrings - 1, sizeof(*needid), needid_cmp_need_s);
389   qsort(needid + pool->ss.nstrings, pool->nrels, sizeof(*needid), needid_cmp_need);
390
391   sizeid = 0;
392   for (i = 1; i < pool->ss.nstrings; i++)
393     {
394       if (!needid[i].need)
395         break;
396       needid[i].need = 0;
397       sizeid += strlen(pool->ss.stringspace + pool->ss.strings[needid[i].map]) + 1;
398     }
399
400   nstrings = i;
401   for (i = 0; i < nstrings; i++)
402     needid[needid[i].map].need = i;
403
404   for (i = 0; i < pool->nrels; i++)
405     {
406       if (!needid[pool->ss.nstrings + i].need)
407         break;
408       else
409         needid[pool->ss.nstrings + i].need = 0;
410     }
411
412   nrels = i;
413   for (i = 0; i < nrels; i++)
414     {
415       needid[needid[pool->ss.nstrings + i].map].need = nstrings + i;
416     }
417
418   /* find the keys we need */
419   nkeys = 1;
420   memset(id2key, 0, sizeof(id2key));
421   for (i = SOLVABLE_NAME; i <= RPM_RPMDBID; i++)
422     if (idsizes[i])
423       id2key[i] = nkeys++;
424
425   /* find the schemata we need */
426   solvschema = xcalloc(repo->nsolvables, sizeof(Id));
427
428   memset(lastschema, 0, sizeof(lastschema));
429   memset(lastschemakey, 0, sizeof(lastschemakey));
430   schemadata = xmalloc(256 * sizeof(Id));
431   schemadatalen = 256;
432   schemadatap = schemadata;
433   *schemadatap++ = 0;
434   schemadatalen--;
435   nschemata = 0;
436   for (i = repo->start, s = pool->solvables + i, n = 0; i < repo->end; i++, s++)
437     {
438       unsigned int h;
439       Id *sp;
440
441       if (s->repo != repo)
442         continue;
443       if (schemadatalen < 32)
444         {
445           int l = schemadatap - schemadata;
446           fprintf(stderr, "growing schemadata\n");
447           schemadata = xrealloc(schemadata, (schemadatap - schemadata + 256) * sizeof(Id));
448           schemadatalen = 256;
449           schemadatap = schemadata + l;
450         }
451       schema = schemadatap;
452       *schema++ = SOLVABLE_NAME;
453       *schema++ = SOLVABLE_ARCH;
454       *schema++ = SOLVABLE_EVR;
455       if (s->vendor)
456         *schema++ = SOLVABLE_VENDOR;
457       if (s->provides)
458         *schema++ = SOLVABLE_PROVIDES;
459       if (s->obsoletes)
460         *schema++ = SOLVABLE_OBSOLETES;
461       if (s->conflicts)
462         *schema++ = SOLVABLE_CONFLICTS;
463       if (s->requires)
464         *schema++ = SOLVABLE_REQUIRES;
465       if (s->recommends)
466         *schema++ = SOLVABLE_RECOMMENDS;
467       if (s->suggests)
468         *schema++ = SOLVABLE_SUGGESTS;
469       if (s->supplements)
470         *schema++ = SOLVABLE_SUPPLEMENTS;
471       if (s->enhances)
472         *schema++ = SOLVABLE_ENHANCES;
473       if (s->freshens)
474         *schema++ = SOLVABLE_FRESHENS;
475       if (repo->rpmdbid)
476         *schema++ = RPM_RPMDBID;
477       *schema++ = 0;
478       for (sp = schemadatap, h = 0; *sp; )
479         h = h * 7 + *sp++;
480       h &= 255;
481       if (lastschema[h] && !memcmp(schemadata + lastschema[h], schemadatap, (schema - schemadatap) * sizeof(Id)))
482         {
483           solvschema[n++] = lastschemakey[h];
484           continue;
485         }
486       schemaid = 0;
487       for (sp = schemadata + 1; sp < schemadatap; )
488         {
489           if (!memcmp(sp, schemadatap, (schema - schemadatap) * sizeof(Id)))
490             break;
491           while (*sp++)
492             ;
493           schemaid++;
494         }
495       if (sp >= schemadatap)
496         {
497           if (schemaid != nschemata)
498             abort();
499           lastschema[h] = schemadatap - schemadata;
500           lastschemakey[h] = schemaid;
501           schemadatalen -= schema - schemadatap;
502           schemadatap = schema;
503           nschemata++;
504         }
505       solvschema[n++] = schemaid;
506     }
507   /* convert all schemas to keys */
508   for (sp = schemadata; sp < schemadatap; sp++)
509     *sp = id2key[*sp];
510
511   /* write file header */
512   write_u32(fp, 'S' << 24 | 'O' << 16 | 'L' << 8 | 'V');
513   write_u32(fp, SOLV_VERSION_2);
514
515   /* write counts */
516   write_u32(fp, nstrings);
517   write_u32(fp, nrels);
518   write_u32(fp, nsolvables);
519   write_u32(fp, nkeys);
520   write_u32(fp, nschemata);
521   write_u32(fp, 0);     /* no info block */
522   solv_flags = 0;
523   solv_flags |= SOLV_FLAG_PREFIX_POOL;
524 #if 0
525   solv_flags |= SOLV_FLAG_VERTICAL;
526 #endif
527   write_u32(fp, solv_flags);
528
529   /* Build the prefix-encoding of the string pool.  We need to know
530      the size of that before writing it to the file, so we have to
531      build a separate buffer for that.  As it's temporarily possible
532      that this actually is an expansion we can't easily reuse the 
533      stringspace for this.  The max expansion per string is 1 byte,
534      so it will fit into sizeid+nstrings bytes.  */
535   char *prefix = xmalloc (sizeid + nstrings);
536   char *pp = prefix;
537   char *old_str = "";
538   for (i = 1; i < nstrings; i++)
539     {
540       char *str = pool->ss.stringspace + pool->ss.strings[needid[i].map];
541       int same;
542       size_t len;
543       for (same = 0; same < 255; same++)
544         if (old_str[same] != str[same])
545           break;
546       *pp++ = same;
547       len = strlen (str + same) + 1;
548       memcpy (pp, str + same, len);
549       pp += len;
550       old_str = str;
551     }
552
553   /*
554    * write strings
555    */
556   write_u32(fp, sizeid);
557   write_u32(fp, pp - prefix);
558   if (fwrite(prefix, pp - prefix, 1, fp) != 1)
559     {
560       perror("write error");
561       exit(1);
562     }
563   xfree (prefix);
564
565   /*
566    * write RelDeps
567    */
568   for (i = 0; i < nrels; i++)
569     {
570       ran = pool->rels + (needid[pool->ss.nstrings + i].map - pool->ss.nstrings);
571       write_id(fp, needid[ISRELDEP(ran->name) ? RELOFF(ran->name) : ran->name].need);
572       write_id(fp, needid[ISRELDEP(ran->evr) ? RELOFF(ran->evr) : ran->evr].need);
573       write_u8( fp, ran->flags);
574     }
575
576   /*
577    * write keys
578    */
579   for (i = SOLVABLE_NAME; i <= RPM_RPMDBID; i++)
580     {
581       if (!idsizes[i])
582         continue;
583       write_id(fp, needid[i].need);
584       if (i >= SOLVABLE_PROVIDES && i <= SOLVABLE_FRESHENS)
585         write_id(fp, TYPE_REL_IDARRAY);
586       else if (i == RPM_RPMDBID)
587         write_id(fp, TYPE_U32);
588       else
589         write_id(fp, TYPE_ID);
590       write_id(fp, idsizes[i]);
591     }
592
593   /*
594    * write schemata
595    */
596   write_id(fp, schemadatap - schemadata - 1);
597   for (sp = schemadata + 1; sp < schemadatap; )
598     {
599       write_idarray(fp, pool, 0, sp);
600       while (*sp++)
601         ;
602     }
603   
604 #if 0
605   if (1)
606     {
607       Id id, key;
608
609       for (i = 0; i < nsolvables; i++)
610         write_id(fp, solvschema[i]);
611       unsigned char *used = xmalloc(nschemata);
612       for (id = SOLVABLE_NAME; id <= RPM_RPMDBID; id++)
613         {
614           key = id2key[id];
615           memset(used, 0, nschemata);
616           for (sp = schemadata + 1, i = 0; sp < schemadatap; sp++)
617             {
618               if (*sp == 0)
619                 i++;
620               else if (*sp == key)
621                 used[i] = 1;
622             }
623           for (i = repo->start, s = pool->solvables + i, n = 0; i < repo->end; i++, s++)
624             {
625               if (s->repo != repo)
626                 continue;
627               if (!used[solvschema[n++]])
628                 continue;
629               switch(id)
630                 {
631                 case SOLVABLE_NAME:
632                   write_id(fp, needid[s->name].need);
633                   break;
634                 case SOLVABLE_ARCH:
635                   write_id(fp, needid[s->arch].need);
636                   break;
637                 case SOLVABLE_EVR:
638                   write_id(fp, needid[s->evr].need);
639                   break;
640                 case SOLVABLE_VENDOR:
641                   write_id(fp, needid[s->vendor].need);
642                   break;
643                 case RPM_RPMDBID:
644                   write_u32(fp, repo->rpmdbid[i - repo->start]);
645                   break;
646                 case SOLVABLE_PROVIDES:
647                   write_idarray(fp, pool, needid, idarraydata + s->provides);
648                   break;
649                 case SOLVABLE_OBSOLETES:
650                   write_idarray(fp, pool, needid, idarraydata + s->obsoletes);
651                   break;
652                 case SOLVABLE_CONFLICTS:
653                   write_idarray(fp, pool, needid, idarraydata + s->conflicts);
654                   break;
655                 case SOLVABLE_REQUIRES:
656                   write_idarray(fp, pool, needid, idarraydata + s->requires);
657                   break;
658                 case SOLVABLE_RECOMMENDS:
659                   write_idarray(fp, pool, needid, idarraydata + s->recommends);
660                   break;
661                 case SOLVABLE_SUPPLEMENTS:
662                   write_idarray(fp, pool, needid, idarraydata + s->supplements);
663                   break;
664                 case SOLVABLE_SUGGESTS:
665                   write_idarray(fp, pool, needid, idarraydata + s->suggests);
666                   break;
667                 case SOLVABLE_ENHANCES:
668                   write_idarray(fp, pool, needid, idarraydata + s->enhances);
669                   break;
670                 case SOLVABLE_FRESHENS:
671                   write_idarray(fp, pool, needid, idarraydata + s->freshens);
672                   break;
673                 }
674             }
675         }
676       xfree(used);
677       xfree(needid);
678       xfree(solvschema);
679       xfree(schemadata);
680       return;
681     }
682   
683 #endif
684
685   /*
686    * write Solvables
687    */
688   for (i = repo->start, s = pool->solvables + i, n = 0; i < repo->end; i++, s++)
689     {
690       if (s->repo != repo)
691         continue;
692       /* keep in sync with schema generation! */
693       write_id(fp, solvschema[n++]);
694       write_id(fp, needid[s->name].need);
695       write_id(fp, needid[s->arch].need);
696       write_id(fp, needid[s->evr].need);
697       if (s->vendor)
698         write_id(fp, needid[s->vendor].need);
699       if (s->provides)
700         write_idarray_sort(fp, pool, needid, idarraydata + s->provides);
701       if (s->obsoletes)
702         write_idarray_sort(fp, pool, needid, idarraydata + s->obsoletes);
703       if (s->conflicts)
704         write_idarray_sort(fp, pool, needid, idarraydata + s->conflicts);
705       if (s->requires)
706         write_idarray_sort(fp, pool, needid, idarraydata + s->requires);
707       if (s->recommends)
708         write_idarray_sort(fp, pool, needid, idarraydata + s->recommends);
709       if (s->suggests)
710         write_idarray_sort(fp, pool, needid, idarraydata + s->suggests);
711       if (s->supplements)
712         write_idarray_sort(fp, pool, needid, idarraydata + s->supplements);
713       if (s->enhances)
714         write_idarray_sort(fp, pool, needid, idarraydata + s->enhances);
715       if (s->freshens)
716         write_idarray_sort(fp, pool, needid, idarraydata + s->freshens);
717       if (repo->rpmdbid)
718         write_u32(fp, repo->rpmdbid[i - repo->start]);
719     }
720
721   xfree(needid);
722   xfree(solvschema);
723   xfree(schemadata);
724 }
725
726 // EOF