1 /*
2 * filelist.c
3 *
4 * Copyright (c) 2012-2018 Pacman Development Team <pacman-dev@archlinux.org>
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <limits.h>
21 #include <string.h>
22 #include <sys/stat.h>
23
24 /* libalpm */
25 #include "filelist.h"
26 #include "util.h"
27
28 /* Returns the difference of the provided two lists of files.
29 * Pre-condition: both lists are sorted!
30 * When done, free the list but NOT the contained data.
31 */
_alpm_filelist_difference(alpm_filelist_t * filesA,alpm_filelist_t * filesB)32 alpm_list_t *_alpm_filelist_difference(alpm_filelist_t *filesA,
33 alpm_filelist_t *filesB)
34 {
35 alpm_list_t *ret = NULL;
36 size_t ctrA = 0, ctrB = 0;
37
38 while(ctrA < filesA->count && ctrB < filesB->count) {
39 char *strA = filesA->files[ctrA].name;
40 char *strB = filesB->files[ctrB].name;
41
42 int cmp = strcmp(strA, strB);
43 if(cmp < 0) {
44 /* item only in filesA, qualifies as a difference */
45 ret = alpm_list_add(ret, strA);
46 ctrA++;
47 } else if(cmp > 0) {
48 ctrB++;
49 } else {
50 ctrA++;
51 ctrB++;
52 }
53 }
54
55 /* ensure we have completely emptied pA */
56 while(ctrA < filesA->count) {
57 ret = alpm_list_add(ret, filesA->files[ctrA].name);
58 ctrA++;
59 }
60
61 return ret;
62 }
63
_alpm_filelist_pathcmp(const char * p1,const char * p2)64 static int _alpm_filelist_pathcmp(const char *p1, const char *p2)
65 {
66 while(*p1 && *p1 == *p2) {
67 p1++;
68 p2++;
69 }
70
71 /* skip trailing '/' */
72 if(*p1 == '\0' && *p2 == '/') {
73 p2++;
74 } else if(*p2 == '\0' && *p1 == '/') {
75 p1++;
76 }
77
78 return *p1 - *p2;
79 }
80
81 /* Returns the intersection of the provided two lists of files.
82 * Pre-condition: both lists are sorted!
83 * When done, free the list but NOT the contained data.
84 */
_alpm_filelist_intersection(alpm_filelist_t * filesA,alpm_filelist_t * filesB)85 alpm_list_t *_alpm_filelist_intersection(alpm_filelist_t *filesA,
86 alpm_filelist_t *filesB)
87 {
88 alpm_list_t *ret = NULL;
89 size_t ctrA = 0, ctrB = 0;
90 alpm_file_t *arrA = filesA->files, *arrB = filesB->files;
91
92 while(ctrA < filesA->count && ctrB < filesB->count) {
93 const char *strA = arrA[ctrA].name, *strB = arrB[ctrB].name;
94 int cmp = _alpm_filelist_pathcmp(strA, strB);
95 if(cmp < 0) {
96 ctrA++;
97 } else if(cmp > 0) {
98 ctrB++;
99 } else {
100 /* when not directories, item in both qualifies as an intersect */
101 if(strA[strlen(strA) - 1] != '/' || strB[strlen(strB) - 1] != '/') {
102 ret = alpm_list_add(ret, arrA[ctrA].name);
103 }
104 ctrA++;
105 ctrB++;
106 }
107 }
108
109 return ret;
110 }
111
112 /* Helper function for comparing files list entries
113 */
_alpm_files_cmp(const void * f1,const void * f2)114 static int _alpm_files_cmp(const void *f1, const void *f2)
115 {
116 const alpm_file_t *file1 = f1;
117 const alpm_file_t *file2 = f2;
118 return strcmp(file1->name, file2->name);
119 }
120
alpm_filelist_contains(alpm_filelist_t * filelist,const char * path)121 alpm_file_t SYMEXPORT *alpm_filelist_contains(alpm_filelist_t *filelist,
122 const char *path)
123 {
124 alpm_file_t key;
125
126 if(!filelist) {
127 return NULL;
128 }
129
130 key.name = (char *)path;
131
132 return bsearch(&key, filelist->files, filelist->count,
133 sizeof(alpm_file_t), _alpm_files_cmp);
134 }
135
_alpm_filelist_sort(alpm_filelist_t * filelist)136 void _alpm_filelist_sort(alpm_filelist_t *filelist)
137 {
138 size_t i;
139 for(i = 1; i < filelist->count; i++) {
140 if(strcmp(filelist->files[i - 1].name, filelist->files[i].name) > 0) {
141 /* filelist is not pre-sorted */
142 qsort(filelist->files, filelist->count,
143 sizeof(alpm_file_t), _alpm_files_cmp);
144 return;
145 }
146 }
147 }
148