rpm  5.2.1
rpmal.c
Go to the documentation of this file.
1 
5 #include "system.h"
6 
7 #include <rpmio.h>
8 #include <rpmiotypes.h> /* XXX fnpyKey */
9 
10 #include <rpmtag.h>
11 #include <rpmtypes.h>
12 
13 #define _RPMDS_INTERNAL
14 #include <rpmds.h>
15 #include <rpmal.h>
16 
17 #include "debug.h"
18 
19 typedef /*@abstract@*/ struct availablePackage_s * availablePackage;
20 
21 /*@access alKey @*/
22 /*@access alNum @*/
23 /*@access rpmal @*/
24 /*@access rpmds @*/
25 /*@access availablePackage @*/
26 
27 /*@access fnpyKey @*/ /* XXX suggestedKeys array */
28 
33 /*@refcounted@*/ /*@null@*/
35 /*@refcounted@*/ /*@null@*/
40 /*@exposed@*/ /*@dependent@*/ /*@null@*/
43 };
44 
45 typedef /*@abstract@*/ struct availableIndexEntry_s * availableIndexEntry;
46 /*@access availableIndexEntry@*/
47 
52 /*@exposed@*/ /*@dependent@*/ /*@null@*/
54 /*@observer@*/
55  const char * entry;
56  unsigned short entryLen;
57  unsigned short entryIx;
60  } type;
61 };
62 
63 typedef /*@abstract@*/ struct availableIndex_s * availableIndex;
64 /*@access availableIndex@*/
65 
70 /*@null@*/
71  availableIndexEntry index;
72  int size;
73  int k;
74 };
75 
76 typedef /*@abstract@*/ struct fileIndexEntry_s * fileIndexEntry;
77 /*@access fileIndexEntry@*/
78 
83 /*@dependent@*/ /*@relnull@*/
84  const char * baseName;
85  size_t baseNameLen;
88 };
89 
90 typedef /*@abstract@*/ struct dirInfo_s * dirInfo;
91 /*@access dirInfo@*/
92 
96 struct dirInfo_s {
97 /*@owned@*/ /*@relnull@*/
98  const char * dirName;
99  size_t dirNameLen;
100 /*@owned@*/
101  fileIndexEntry files;
102  int numFiles;
103 };
104 
108 struct rpmal_s {
109 /*@owned@*/ /*@null@*/
110  availablePackage list;
112  int delta;
113  int size;
114  int alloced;
116  int numDirs;
117 /*@owned@*/ /*@null@*/
118  dirInfo dirs;
119 };
120 
125 static void rpmalFreeIndex(rpmal al)
126  /*@modifies al @*/
127 {
128  availableIndex ai = &al->index;
129  if (ai->size > 0) {
130  ai->index = _free(ai->index);
131  ai->size = 0;
132  }
133 }
134 
135 static inline alNum alKey2Num(/*@unused@*/ /*@null@*/ const rpmal al,
136  /*@null@*/ alKey pkgKey)
137  /*@*/
138 {
139  /*@-nullret -temptrans -retalias @*/
140  union { alKey key; alNum num; } u;
141  u.num = 0;
142  u.key = pkgKey;
143  return u.num;
144  /*@=nullret =temptrans =retalias @*/
145 }
146 
147 static inline alKey alNum2Key(/*@unused@*/ /*@null@*/ const rpmal al,
148  /*@null@*/ alNum pkgNum)
149  /*@*/
150 {
151  /*@-nullret -temptrans -retalias @*/
152  union { alKey key; alNum num; } u;
153  u.key = 0;
154  u.num = pkgNum;
155  return u.key;
156  /*@=nullret =temptrans =retalias @*/
157 }
158 
159 rpmal rpmalCreate(int delta)
160 {
161  rpmal al = xcalloc(1, sizeof(*al));
162  availableIndex ai = &al->index;
163 
164  al->delta = delta;
165  al->size = 0;
166  al->list = xcalloc(al->delta, sizeof(*al->list));
167  al->alloced = al->delta;
168 
169  ai->index = NULL;
170  ai->size = 0;
171 
172  al->numDirs = 0;
173  al->dirs = NULL;
174  return al;
175 }
176 
178 {
179  availablePackage alp;
180  dirInfo die;
181  int i;
182 
183  if (al == NULL)
184  return NULL;
185 
186  if ((alp = al->list) != NULL)
187  for (i = 0; i < al->size; i++, alp++) {
188  (void)rpmdsFree(alp->provides);
189  alp->provides = NULL;
190  alp->fi = rpmfiFree(alp->fi);
191  }
192 
193  if ((die = al->dirs) != NULL)
194  for (i = 0; i < al->numDirs; i++, die++) {
195  die->dirName = _free(die->dirName);
196  die->files = _free(die->files);
197  }
198  al->dirs = _free(al->dirs);
199  al->numDirs = 0;
200 
201  al->list = _free(al->list);
202  al->alloced = 0;
203  rpmalFreeIndex(al);
204  al = _free(al);
205  return NULL;
206 }
207 
214 static int dieCompare(const void * one, const void * two)
215  /*@*/
216 {
217  /*@-castexpose@*/
218  const dirInfo a = (const dirInfo) one;
219  const dirInfo b = (const dirInfo) two;
220  /*@=castexpose@*/
221  int lenchk = (int)a->dirNameLen - (int)b->dirNameLen;
222 
223  if (lenchk || a->dirNameLen == 0)
224  return lenchk;
225 
226  if (a->dirName == NULL || b->dirName == NULL)
227  return lenchk;
228 
229  /* XXX FIXME: this might do "backward" strcmp for speed */
230  return strcmp(a->dirName, b->dirName);
231 }
232 
239 static int fieCompare(const void * one, const void * two)
240  /*@*/
241 {
242  /*@-castexpose@*/
243  const fileIndexEntry a = (const fileIndexEntry) one;
244  const fileIndexEntry b = (const fileIndexEntry) two;
245  /*@=castexpose@*/
246  int lenchk = (int)a->baseNameLen - (int)b->baseNameLen;
247 
248  if (lenchk)
249  return lenchk;
250 
251  if (a->baseName == NULL || b->baseName == NULL)
252  return lenchk;
253 
254  return strcmp(a->baseName, b->baseName);
255 }
256 
257 void rpmalDel(rpmal al, alKey pkgKey)
258 {
259  alNum pkgNum = alKey2Num(al, pkgKey);
260  availablePackage alp;
261  rpmfi fi;
262 
263  if (al == NULL || al->list == NULL)
264  return; /* XXX can't happen */
265 
266  alp = al->list + pkgNum;
267 
268  /* Delete directory/file info entries from added package list. */
269  if ((fi = alp->fi) != NULL)
270  if (rpmfiFC(fi) > 0) {
271  int origNumDirs = al->numDirs;
272  int dx;
273  dirInfo dieNeedle =
274  memset(alloca(sizeof(*dieNeedle)), 0, sizeof(*dieNeedle));
275  dirInfo die;
276  int last;
277  int i;
278 
279  /* XXX FIXME: We ought to relocate the directory list here */
280 
281  if (al->dirs != NULL)
282  for (dx = rpmfiDC(fi) - 1; dx >= 0; dx--)
283  {
284  fileIndexEntry fie;
285 
286  (void) rpmfiSetDX(fi, dx);
287 
288  /*@-assignexpose -dependenttrans -observertrans@*/
289  dieNeedle->dirName = (char *) rpmfiDN(fi);
290  /*@=assignexpose =dependenttrans =observertrans@*/
291  dieNeedle->dirNameLen = (dieNeedle->dirName != NULL
292  ? strlen(dieNeedle->dirName) : 0);
293  die = bsearch(dieNeedle, al->dirs, al->numDirs,
294  sizeof(*dieNeedle), dieCompare);
295  if (die == NULL)
296  continue;
297 
298  last = die->numFiles;
299  fie = die->files + last - 1;
300  for (i = last - 1; i >= 0; i--, fie--) {
301  if (fie->pkgNum != pkgNum)
302  /*@innercontinue@*/ continue;
303  die->numFiles--;
304 
305  if (i < die->numFiles)
306  memmove(fie, fie+1, (die->numFiles - i) * sizeof(*fie));
307  memset(die->files + die->numFiles, 0, sizeof(*fie)); /* overkill */
308 
309  }
310  if (die->numFiles > 0) {
311  if (last > i)
312  die->files = xrealloc(die->files,
313  die->numFiles * sizeof(*die->files));
314  continue;
315  }
316  die->files = _free(die->files);
317  die->dirName = _free(die->dirName);
318  al->numDirs--;
319  if ((die - al->dirs) < al->numDirs)
320  memmove(die, die+1, (al->numDirs - (die - al->dirs)) * sizeof(*die));
321 
322  memset(al->dirs + al->numDirs, 0, sizeof(*al->dirs)); /* overkill */
323  }
324 
325  if (origNumDirs > al->numDirs) {
326  if (al->numDirs > 0)
327  al->dirs = xrealloc(al->dirs, al->numDirs * sizeof(*al->dirs));
328  else
329  al->dirs = _free(al->dirs);
330  }
331  }
332 
333  (void)rpmdsFree(alp->provides);
334  alp->provides = NULL;
335  alp->fi = rpmfiFree(alp->fi);
336 
337  memset(alp, 0, sizeof(*alp)); /* XXX trash and burn */
338  return;
339 }
340 
341 alKey rpmalAdd(rpmal * alistp, alKey pkgKey, fnpyKey key,
342  rpmds provides, rpmfi fi, rpmuint32_t tscolor)
343 {
344  alNum pkgNum;
345  rpmal al;
346  availablePackage alp;
347 
348  /* If list doesn't exist yet, create. */
349  if (*alistp == NULL)
350  *alistp = rpmalCreate(5);
351  al = *alistp;
352  pkgNum = alKey2Num(al, pkgKey);
353 
354  if (pkgNum >= 0 && pkgNum < al->size) {
355  rpmalDel(al, pkgKey);
356  } else {
357  if (al->size == al->alloced) {
358  al->alloced += al->delta;
359  al->list = xrealloc(al->list, sizeof(*al->list) * al->alloced);
360  }
361  pkgNum = al->size++;
362  }
363 
364  if (al->list == NULL)
365  return RPMAL_NOMATCH; /* XXX can't happen */
366 
367  alp = al->list + pkgNum;
368 
369  alp->key = key;
370  alp->tscolor = tscolor;
371 
372 /*@-assignexpose -castexpose @*/
373  alp->provides = rpmdsLink(provides, "Provides (rpmalAdd)");
374  alp->fi = rpmfiLink(fi, "Files (rpmalAdd)");
375 /*@=assignexpose =castexpose @*/
376 
377 /*@-castexpose@*/
378  fi = rpmfiLink(alp->fi, "Files index (rpmalAdd)");
379 /*@=castexpose@*/
380  fi = rpmfiInit(fi, 0);
381  if (rpmfiFC(fi) > 0) {
382  dirInfo dieNeedle =
383  memset(alloca(sizeof(*dieNeedle)), 0, sizeof(*dieNeedle));
384  dirInfo die;
385  int dc = rpmfiDC(fi);
386  int dx;
387  int * dirMapping = alloca(sizeof(*dirMapping) * dc);
388  int * dirUnique = alloca(sizeof(*dirUnique) * dc);
389  const char * DN;
390  int origNumDirs;
391  int first;
392 
393  /* XXX FIXME: We ought to relocate the directory list here */
394 
395  /* XXX enough space for all directories, late realloc to truncate. */
396  al->dirs = xrealloc(al->dirs, (al->numDirs + dc) * sizeof(*al->dirs));
397 
398  /* Only previously allocated dirInfo is sorted and bsearch'able. */
399  origNumDirs = al->numDirs;
400 
401  /* Package dirnames are not currently unique. Create unique mapping. */
402  for (dx = 0; dx < dc; dx++) {
403  int i = 0;
404  (void) rpmfiSetDX(fi, dx);
405  DN = rpmfiDN(fi);
406  if (DN != NULL)
407  for (i = 0; i < dx; i++) {
408  const char * iDN;
409  (void) rpmfiSetDX(fi, i);
410  iDN = rpmfiDN(fi);
411  if (iDN != NULL && !strcmp(DN, iDN))
412  /*@innerbreak@*/ break;
413  }
414  dirUnique[dx] = i;
415  }
416 
417  /* Map package dirs into transaction dirInfo index. */
418  for (dx = 0; dx < dc; dx++) {
419 
420  /* Non-unique package dirs use the 1st entry mapping. */
421  if (dirUnique[dx] < dx) {
422  dirMapping[dx] = dirMapping[dirUnique[dx]];
423  continue;
424  }
425 
426  /* Find global dirInfo mapping for first encounter. */
427  (void) rpmfiSetDX(fi, dx);
428 
429  /*@-assignexpose -dependenttrans -observertrans@*/
430  dieNeedle->dirName = rpmfiDN(fi);
431  /*@=assignexpose =dependenttrans =observertrans@*/
432 
433  dieNeedle->dirNameLen = (dieNeedle->dirName != NULL
434  ? strlen(dieNeedle->dirName) : 0);
435  die = bsearch(dieNeedle, al->dirs, origNumDirs,
436  sizeof(*dieNeedle), dieCompare);
437  if (die) {
438  dirMapping[dx] = die - al->dirs;
439  } else {
440  dirMapping[dx] = al->numDirs;
441  die = al->dirs + al->numDirs;
442  if (dieNeedle->dirName != NULL)
443  die->dirName = xstrdup(dieNeedle->dirName);
444  die->dirNameLen = dieNeedle->dirNameLen;
445  die->files = NULL;
446  die->numFiles = 0;
447 
448  al->numDirs++;
449  }
450  }
451 
452  for (first = rpmfiNext(fi); first >= 0;) {
453  fileIndexEntry fie;
454  int next;
455 
456  /* Find the first file of the next directory. */
457  dx = rpmfiDX(fi);
458  while ((next = rpmfiNext(fi)) >= 0) {
459  if (dx != rpmfiDX(fi))
460  /*@innerbreak@*/ break;
461  }
462  if (next < 0) next = rpmfiFC(fi); /* XXX reset end-of-list */
463 
464  die = al->dirs + dirMapping[dx];
465  die->files = xrealloc(die->files,
466  (die->numFiles + next - first) * sizeof(*die->files));
467 
468  fie = die->files + die->numFiles;
469 
470  /* Rewind to first file, generate file index entry for each file. */
471  fi = rpmfiInit(fi, first);
472  while ((first = rpmfiNext(fi)) >= 0 && first < next) {
473  /*@-assignexpose -dependenttrans -observertrans @*/
474  fie->baseName = rpmfiBN(fi);
475  /*@=assignexpose =dependenttrans =observertrans @*/
476  fie->baseNameLen = (fie->baseName ? strlen(fie->baseName) : 0);
477  fie->pkgNum = pkgNum;
478  fie->ficolor = rpmfiFColor(fi);
479 
480  die->numFiles++;
481  fie++;
482  }
483  qsort(die->files, die->numFiles, sizeof(*die->files), fieCompare);
484  }
485 
486  /* Resize the directory list. If any directories were added, resort. */
487  al->dirs = xrealloc(al->dirs, al->numDirs * sizeof(*al->dirs));
488  if (origNumDirs != al->numDirs)
489  qsort(al->dirs, al->numDirs, sizeof(*al->dirs), dieCompare);
490  }
491  fi = rpmfiUnlink(fi, "Files index (rpmalAdd)");
492 
493  rpmalFreeIndex(al);
494 
495 assert(((alNum)(alp - al->list)) == pkgNum);
496  return ((alKey)(alp - al->list));
497 }
498 
505 static int indexcmp(const void * one, const void * two)
506  /*@*/
507 {
508  /*@-castexpose@*/
509  const availableIndexEntry a = (const availableIndexEntry) one;
510  const availableIndexEntry b = (const availableIndexEntry) two;
511  /*@=castexpose@*/
512  int lenchk;
513 
514  lenchk = a->entryLen - b->entryLen;
515  if (lenchk)
516  return lenchk;
517 
518  return strcmp(a->entry, b->entry);
519 }
520 
521 void rpmalAddProvides(rpmal al, alKey pkgKey, rpmds provides, rpmuint32_t tscolor)
522 {
523  rpmuint32_t dscolor;
524  const char * Name;
525  alNum pkgNum = alKey2Num(al, pkgKey);
526  availableIndex ai = &al->index;
527  availableIndexEntry aie;
528  int ix;
529 
530  if (provides == NULL || pkgNum < 0 || pkgNum >= al->size)
531  return;
532  if (ai->index == NULL || ai->k < 0 || ai->k >= ai->size)
533  return;
534 
535  if (rpmdsInit(provides) != NULL)
536  while (rpmdsNext(provides) >= 0) {
537 
538  if ((Name = provides->N[provides->i]) == NULL)
539  continue; /* XXX can't happen */
540 
541  /* Ignore colored provides not in our rainbow. */
542  dscolor = rpmdsColor(provides);
543  if (tscolor && dscolor && !(tscolor & dscolor))
544  continue;
545 
546  aie = ai->index + ai->k;
547  ai->k++;
548 
549  aie->pkgKey = pkgKey;
550 /*@-assignexpose@*/
551  aie->entry = Name;
552 /*@=assignexpose@*/
553  aie->entryLen = (unsigned short)strlen(Name);
554  ix = rpmdsIx(provides);
555 
556 /* XXX make sure that element index fits in unsigned short */
557 assert(ix < 0x10000);
558 
559  aie->entryIx = ix;
560  aie->type = IET_PROVIDES;
561  }
562 }
563 
565 {
566  availableIndex ai;
567  availablePackage alp;
568  int i;
569 
570  if (al == NULL || al->list == NULL) return;
571  ai = &al->index;
572 
573  ai->size = 0;
574  for (i = 0; i < al->size; i++) {
575  alp = al->list + i;
576  if (alp->provides != NULL)
577  ai->size += rpmdsCount(alp->provides);
578  }
579  if (ai->size == 0) return;
580 
581  ai->index = xrealloc(ai->index, ai->size * sizeof(*ai->index));
582  ai->k = 0;
583  for (i = 0; i < al->size; i++) {
584  alp = al->list + i;
585  rpmalAddProvides(al, alNum2Key(NULL, (alNum)i), alp->provides, alp->tscolor);
586  }
587 
588  /* Reset size to the no. of provides added. */
589  ai->size = ai->k;
590  qsort(ai->index, ai->size, sizeof(*ai->index), indexcmp);
591 }
592 
593 fnpyKey *
594 rpmalAllFileSatisfiesDepend(const rpmal al, const rpmds ds, alKey * keyp)
595 {
596  rpmuint32_t tscolor;
597  rpmuint32_t ficolor;
598  int found = 0;
599  const char * dirName;
600  const char * baseName;
601  dirInfo dieNeedle =
602  memset(alloca(sizeof(*dieNeedle)), 0, sizeof(*dieNeedle));
603  dirInfo die;
604  fileIndexEntry fieNeedle =
605  memset(alloca(sizeof(*fieNeedle)), 0, sizeof(*fieNeedle));
606  fileIndexEntry fie;
607  availablePackage alp;
608  fnpyKey * ret = NULL;
609  const char * fileName;
610 
611  if (keyp) *keyp = RPMAL_NOMATCH;
612 
613  if (al == NULL || (fileName = rpmdsN(ds)) == NULL || *fileName != '/')
614  return NULL;
615 
616  /* Solaris 2.6 bsearch sucks down on this. */
617  if (al->numDirs == 0 || al->dirs == NULL || al->list == NULL)
618  return NULL;
619 
620  { char * t;
621  dirName = t = xstrdup(fileName);
622  if ((t = strrchr(t, '/')) != NULL) {
623  t++; /* leave the trailing '/' */
624  *t = '\0';
625  }
626  }
627 
628  dieNeedle->dirName = (char *) dirName;
629  dieNeedle->dirNameLen = strlen(dirName);
630  die = bsearch(dieNeedle, al->dirs, al->numDirs,
631  sizeof(*dieNeedle), dieCompare);
632  if (die == NULL)
633  goto exit;
634 
635  /* rewind to the first match */
636  while (die > al->dirs && dieCompare(die-1, dieNeedle) == 0)
637  die--;
638 
639  if ((baseName = strrchr(fileName, '/')) == NULL)
640  goto exit;
641  baseName++;
642 
643  for (found = 0, ret = NULL;
644  die < al->dirs + al->numDirs && dieCompare(die, dieNeedle) == 0;
645  die++)
646  {
647 
648 /*@-observertrans@*/
649  fieNeedle->baseName = baseName;
650 /*@=observertrans@*/
651  fieNeedle->baseNameLen = strlen(fieNeedle->baseName);
652  fie = bsearch(fieNeedle, die->files, die->numFiles,
653  sizeof(*fieNeedle), fieCompare);
654  if (fie == NULL)
655  continue; /* XXX shouldn't happen */
656 
657  alp = al->list + fie->pkgNum;
658 
659  /* Ignore colored files not in our rainbow. */
660  tscolor = alp->tscolor;
661  ficolor = fie->ficolor;
662  if (tscolor && ficolor && !(tscolor & ficolor))
663  continue;
664 
665  rpmdsNotify(ds, _("(added files)"), 0);
666 
667  ret = xrealloc(ret, (found+2) * sizeof(*ret));
668  if (ret) /* can't happen */
669  ret[found] = alp->key;
670  if (keyp)
671  *keyp = alNum2Key(al, fie->pkgNum);
672  found++;
673  }
674 
675 exit:
676  dirName = _free(dirName);
677  if (ret)
678  ret[found] = NULL;
679  return ret;
680 }
681 
682 fnpyKey *
683 rpmalAllSatisfiesDepend(const rpmal al, const rpmds ds, alKey * keyp)
684 {
685  availableIndex ai;
686  availableIndexEntry needle;
687  availableIndexEntry match;
688  fnpyKey * ret = NULL;
689  int found = 0;
690  const char * KName;
691  availablePackage alp;
692  int rc;
693 
694  if (keyp) *keyp = RPMAL_NOMATCH;
695 
696  if (al == NULL || ds == NULL || (KName = rpmdsN(ds)) == NULL)
697  return ret;
698 
699  if (*KName == '/') {
700  /* First, look for files "contained" in package ... */
701  ret = rpmalAllFileSatisfiesDepend(al, ds, keyp);
702  if (ret != NULL && *ret != NULL)
703  return ret;
704  ret = _free(ret);
705  /* ... then, look for files "provided" by package. */
706  }
707 
708  ai = &al->index;
709  if (ai->index == NULL || ai->size <= 0)
710  return NULL;
711 
712  needle = memset(alloca(sizeof(*needle)), 0, sizeof(*needle));
713  /*@-assignexpose -temptrans@*/
714  needle->entry = KName;
715  /*@=assignexpose =temptrans@*/
716  needle->entryLen = (unsigned short)strlen(needle->entry);
717 
718  match = bsearch(needle, ai->index, ai->size, sizeof(*ai->index), indexcmp);
719  if (match == NULL)
720  return NULL;
721 
722  /* rewind to the first match */
723  while (match > ai->index && indexcmp(match-1, needle) == 0)
724  match--;
725 
726  if (al->list != NULL) /* XXX always true */
727  for (ret = NULL, found = 0;
728  match < ai->index + ai->size && indexcmp(match, needle) == 0;
729  match++)
730  {
731  alp = al->list + alKey2Num(al, match->pkgKey);
732 
733  rc = 0;
734  if (alp->provides != NULL) /* XXX can't happen */
735  switch (match->type) {
736  case IET_PROVIDES:
737  /* XXX single step on rpmdsNext to regenerate DNEVR string */
738  (void) rpmdsSetIx(alp->provides, match->entryIx - 1);
739  if (rpmdsNext(alp->provides) >= 0)
740  rc = rpmdsCompare(alp->provides, ds);
741 
742  if (rc)
743  rpmdsNotify(ds, _("(added provide)"), 0);
744 
745  /*@switchbreak@*/ break;
746  }
747 
748  if (rc) {
749  ret = xrealloc(ret, (found + 2) * sizeof(*ret));
750  if (ret) /* can't happen */
751  ret[found] = alp->key;
752 /*@-dependenttrans@*/
753  if (keyp)
754  *keyp = match->pkgKey;
755 /*@=dependenttrans@*/
756  found++;
757  }
758  }
759 
760  if (ret)
761  ret[found] = NULL;
762 
763 /*@-nullstate@*/ /* FIX: *keyp may be NULL */
764  return ret;
765 /*@=nullstate@*/
766 }
767 
768 fnpyKey
769 rpmalSatisfiesDepend(const rpmal al, const rpmds ds, alKey * keyp)
770 {
771  fnpyKey * tmp = rpmalAllSatisfiesDepend(al, ds, keyp);
772 
773  if (tmp) {
774  fnpyKey ret = tmp[0];
775  free(tmp);
776  return ret;
777  }
778  return NULL;
779 }