filelist.c 17.5 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
/*  This file is part of "reprepro"
 *  Copyright (C) 2006,2007 Bernhard R. Link
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License version 2 as
 *  published by the Free Software Foundation.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02111-1301  USA
 */
16 17 18
#include <config.h>

#include <malloc.h>
19
#include <stdlib.h>
20 21 22 23 24
#include <assert.h>
#include <string.h>
#include <stdio.h>

#include "error.h"
25 26 27
#include "database_p.h"
#include "files.h"
#include "debfile.h"
28 29 30 31 32 33 34 35 36
#include "filelist.h"

struct filelist_package {
	struct filelist_package *next;
	char name[];
};

struct dirlist;
struct filelist {
Bernhard Link's avatar
Bernhard Link committed
37 38
	struct filelist *nextl;
	struct filelist *nextr;
39
	int balance;
40 41 42 43 44
	char *name;
	size_t count;
	const char *packages[];
};
struct dirlist {
45 46 47 48 49
	struct dirlist *nextl;
	struct dirlist *nextr;
	int balance;
	/*@dependant@*/ struct dirlist *parent;
	struct dirlist *subdirs;
50 51
	struct filelist *files;
	/*@dependant@*/struct filelist *lastfile;
52 53
 	size_t len;
	char name[];
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
};

struct filelist_list {
	struct dirlist *root;
	struct filelist_package *packages;
};

retvalue filelist_init(struct filelist_list **list) {
	struct filelist_list *filelist;

	filelist = calloc(1,sizeof(struct filelist_list));
	if( filelist == NULL )
		return RET_ERROR_OOM;
	filelist->root = calloc(1,sizeof(struct dirlist));
	if( filelist->root == NULL ) {
		free(filelist);
		return RET_ERROR_OOM;
	}
	*list = filelist;
	return RET_OK;
};
Bernhard Link's avatar
Bernhard Link committed
75 76 77 78 79 80 81 82
static void files_free(/*@only@*/struct filelist *list) {
	if( list == NULL )
		return;
	files_free(list->nextl);
	files_free(list->nextr);
	free(list->name);
	free(list);
}
83
static void dirlist_free(/*@only@*/struct dirlist *list) {
84 85 86 87 88 89 90
	if( list == NULL )
		return;
	files_free(list->files);
	dirlist_free(list->subdirs);
	dirlist_free(list->nextl);
	dirlist_free(list->nextr);
	free(list);
91 92 93 94 95 96 97 98 99 100 101 102 103 104
}
void filelist_free(struct filelist_list *list) {

	if( list == NULL )
		return;
	dirlist_free(list->root);
	while( list->packages != NULL ) {
		struct filelist_package *package = list->packages;
		list->packages = package->next;
		free(package);
	}
	free(list);
};

105
static retvalue filelist_newpackage(struct filelist_list *filelist, const char *name, const char *section, const struct filelist_package **pkg) {
106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
	struct filelist_package *p;
	size_t name_len = strlen(name);
	size_t section_len = strlen(section);

	p = malloc(sizeof(struct filelist_package)+name_len+section_len+2);
	if( p == NULL )
		return RET_ERROR_OOM;
	p->next = filelist->packages;
	memcpy(p->name, section, section_len);
	p->name[section_len] = '/';
	memcpy(p->name+section_len+1, name, name_len+1);
	filelist->packages = p;
	*pkg = p;
	return RET_OK;
};

122
static bool findfile(struct dirlist *parent, const char *packagename, const char *basefilename, size_t namelen) {
123 124 125
	struct filelist *file, *n, *last;
	struct filelist **stack[128];
	int stackpointer = 0;
126

127 128
	stack[stackpointer++] = &parent->files;
	file = parent->files;
129 130

	while( file != NULL ) {
131 132
		int c = strncmp(basefilename, file->name, namelen);
		if( c == 0 && file->name[namelen] == '\0' ) {
133 134
			n = realloc(file,sizeof(struct filelist)+
					(file->count+1)*sizeof(const char*));
135 136 137
			if( n == NULL )
				return false;
			n->packages[n->count++] = packagename;
138
			*(stack[--stackpointer]) = n;
139
			return true;
140
		} else if ( c > 0 ) {
141 142
			stack[stackpointer++] = &file->nextr;
			file = file->nextr;
Bernhard Link's avatar
Bernhard Link committed
143
		} else  {
144 145
			stack[stackpointer++] = &file->nextl;
			file = file->nextl;
Bernhard Link's avatar
Bernhard Link committed
146
		}
147 148
	}
	n = malloc(sizeof(struct filelist)+sizeof(const char*));
149 150 151
	if( n == NULL )
		return false;
	n->name = strndup(basefilename, namelen);
Bernhard Link's avatar
Bernhard Link committed
152 153
	n->nextl = NULL;
	n->nextr = NULL;
154
	n->balance = 0;
155
	n->count = 1;
156
	n->packages[0] = packagename;
157 158
	if( n->name == NULL ) {
		free(n);
159
		return false;
160
	}
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189
	*(stack[--stackpointer]) = n;
	while( stackpointer > 0 ) {
		file = *(stack[--stackpointer]);
		if( file->nextl == n ) {
			file->balance--;
			if( file->balance > -1 )
				break;
			if( file->balance == -1 ) {
				n = file;
				continue;
			}
			if( n->balance == -1 ) {
				file->nextl = n->nextr;
				file->balance = 0;
				n->nextr = file;
				n->balance = 0;
				*(stack[stackpointer]) = n;
				break;
			} else {
				last = n->nextr;
				file->nextl = last->nextr;
				*(stack[stackpointer]) = last;
				last->nextr = file;
				n->nextr = last->nextl;
				last->nextl = n;
				if( last->balance == 0 ) {
					file->balance = 0;
					n->balance = 0;
				} else if( last->balance < 0 ) {
190
					file->balance = 1;
191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
					n->balance = 0;
				} else {
					file->balance = 0;
					n->balance = -1;
				}
				last->balance = 0;
				break;
			}
		} else {
			file->balance++;
			if( file->balance < 1 )
				break;
			if( file->balance == 1 ) {
				n = file;
				continue;
			}
			if( n->balance == 1 ) {
				file->nextr = n->nextl;
				file->balance = 0;
				n->nextl = file;
				n->balance = 0;
				*(stack[stackpointer]) = n;
				break;
			} else {
				last = n->nextl;
				file->nextr = last->nextl;
				*(stack[stackpointer]) = last;
				last->nextl = file;
				n->nextl = last->nextr;
				last->nextr = n;
				if( last->balance == 0 ) {
					file->balance = 0;
					n->balance = 0;
				} else if( last->balance > 0 ) {
					file->balance = -1;
					n->balance = 0;
				} else {
					file->balance = 0;
229
					n->balance = 1;
230 231 232 233 234 235
				}
				last->balance = 0;
				break;
			}
		}
	}
236
	return true;
237 238
}

239
typedef const unsigned char cuchar;
240

241
static struct dirlist *finddir(struct dirlist *dir, cuchar *name, size_t namelen) {
242 243 244
	struct dirlist *d, *this, *parent, *h;
	struct dirlist **stack[128];
	int stackpointer = 0;
245

246 247 248 249
	stack[stackpointer++] = &dir->subdirs;
	d = dir->subdirs;

	while( d != NULL ) {
250 251
		int c;

252 253
		if( namelen < d->len ) {
			c = memcmp(name, d->name, namelen);
254 255 256 257 258 259 260
			if( c <= 0 ) {
				stack[stackpointer++] = &d->nextl;
				d = d->nextl;
			} else {
				stack[stackpointer++] = &d->nextr;
				d = d->nextr;
			}
261 262 263 264 265
		} else {
			c = memcmp(name, d->name, d->len);
			if( c == 0 && d->len == namelen ) {
				return d;
			} else if( c >= 0) {
266 267 268 269 270 271
				stack[stackpointer++] = &d->nextr;
				d = d->nextr;
			} else {
				stack[stackpointer++] = &d->nextl;
				d = d->nextl;
			}
272
		}
273
	}
274
	/* not found, create it and rebalance */
275 276 277
	d = malloc(sizeof(struct dirlist) + namelen );
	if( d == NULL )
		return d;
278
	d->subdirs = NULL;
279 280 281 282
	d->nextl = NULL;
	d->nextr = NULL;
	d->balance = 0;
	d->parent = dir;
283 284 285
	d->files = NULL;
	d->len = namelen;
	memcpy(d->name, name, namelen);
286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315
	*(stack[--stackpointer]) = d;
	this = d;
	while( stackpointer > 0 ) {
		parent = *(stack[--stackpointer]);
		if( parent->nextl == this ) {
			parent->balance--;
			if( parent->balance > -1 )
				break;
			if( parent->balance == -1 ) {
				this = parent;
				continue;
			}
			if( this->balance == -1 ) {
				parent->nextl = this->nextr;
				parent->balance = 0;
				this->nextr = parent;
				this->balance = 0;
				*(stack[stackpointer]) = this;
				break;
			} else {
				h = this->nextr;
				parent->nextl = h->nextr;
				*(stack[stackpointer]) = h;
				h->nextr = parent;
				this->nextr = h->nextl;
				h->nextl = this;
				if( h->balance == 0 ) {
					parent->balance = 0;
					this->balance = 0;
				} else if( h->balance < 0 ) {
316
					parent->balance = 1;
317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354
					this->balance = 0;
				} else {
					parent->balance = 0;
					this->balance = -1;
				}
				h->balance = 0;
				break;
			}
		} else {
			parent->balance++;
			if( parent->balance < 1 )
				break;
			if( parent->balance == 1 ) {
				this = parent;
				continue;
			}
			if( this->balance == 1 ) {
				parent->nextr = this->nextl;
				parent->balance = 0;
				this->nextl = parent;
				this->balance = 0;
				*(stack[stackpointer]) = this;
				break;
			} else {
				h = this->nextl;
				parent->nextr = h->nextl;
				*(stack[stackpointer]) = h;
				h->nextl = parent;
				this->nextl = h->nextr;
				h->nextr = this;
				if( h->balance == 0 ) {
					parent->balance = 0;
					this->balance = 0;
				} else if( h->balance > 0 ) {
					parent->balance = -1;
					this->balance = 0;
				} else {
					parent->balance = 0;
355
					this->balance = 1;
356 357 358 359 360 361
				}
				h->balance = 0;
				break;
			}
		}
	}
362
	return d;
363 364
}

365
static retvalue filelist_addfiles(struct filelist_list *list, const struct filelist_package *package, const char *filekey, const char *datastart, size_t size) {
366 367 368 369
	struct dirlist *curdir = list->root;
	const unsigned char *data = (const unsigned char *)datastart;

	while( *data != '\0' ) {
370 371
		int d;

372
		if( (size_t)(data - (const unsigned char *)datastart) >= size-1 ) {
373 374 375 376 377 378
			/* This might not catch everything, but we are only
			 * accessing it readonly */
			fprintf(stderr, "Corrupted file list data for %s\n",
					filekey);
			return RET_ERROR;
		}
379
		d = *(data++);
380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418
		if( d == 1 ) {
			size_t len = 0;
			while( *data == 255 ) {
				data++;
				len += 255;
			}
			if( *data == 0 ) {
				fprintf(stderr,
					"Corrupted file list data for %s\n",
					filekey);
				return RET_ERROR;
			}
			len += *(data++);
			if( !findfile(curdir, package->name, (const char*)data, len) )
				return RET_ERROR_OOM;
			 data += len;
		} else if( d == 2 ) {
			size_t len = 0;
			while( *data == 255 ) {
				data++;
				len += 255;
			}
			if( *data == 0 ) {
				fprintf(stderr,
					"Corrupted file list data for %s\n",
					filekey);
				return RET_ERROR;
			}
			len += *(data++);
			curdir = finddir(curdir, data, len);
			if( curdir == NULL )
				return RET_ERROR_OOM;
			data += len;
		} else {
			d -= 2;
			while( d-- > 0 && curdir->parent != NULL )
				curdir = curdir->parent;
		}
	}
419 420 421 422 423 424 425
	if( (size_t)(data - (const unsigned char *)datastart) != size-1 ) {
		fprintf(stderr, "Corrupted file list data for %s (format suggest %llu, is %llu)\n",
				filekey,
				(unsigned long long)(data - (const unsigned char *)datastart),
				(unsigned long long)(size-1));
		return RET_ERROR;
	}
426 427 428 429
	return RET_OK;
}

retvalue filelist_addpackage(struct filelist_list *list, struct database *database, const char *packagename, const char *section, const char *filekey) {
430
	const struct filelist_package *package IFSTUPIDCC(=NULL);
431 432 433
	char *debfilename, *contents = NULL;
	retvalue r;
	const char *c;
434
	size_t len;
435 436 437 438 439 440

	r = filelist_newpackage(list, packagename, section, &package);
	assert( r != RET_NOTHING );
	if( RET_WAS_ERROR(r) )
		return r;

441
	r = table_gettemprecord(database->contents, filekey, &c, &len);
442 443 444 445 446 447 448
	if( r == RET_NOTHING ) {
		if( verbose > 3 )
			printf("Reading filelist for %s\n", filekey);
		debfilename = files_calcfullfilename(database, filekey);
		if( debfilename == NULL ) {
			return RET_ERROR_OOM;
		}
449 450
		r = getfilelist(&contents, &len, debfilename);
		len--;
451 452 453 454
		free(debfilename);
		c = contents;
	}
	if( RET_IS_OK(r) ) {
455
		r = filelist_addfiles(list, package, filekey, c, len + 1);
456
		if( contents != NULL )
457
			r = table_adduniqsizedrecord(database->contents, filekey,
458
					contents, len + 1, true, false);
459 460 461 462
	}
	free(contents);
	return r;
}
463

464
retvalue fakefilelist(struct database *database, const char *filekey) {
465
	return table_adduniqsizedrecord(database->contents, filekey,
466
			"", 1, true, false);
467 468 469
}

static const char header[] = "FILE                                                    LOCATION\n";
470
static const char separator_chars[] = "\t    ";
471 472 473 474

static void filelist_writefiles(char *dir, size_t len,
		struct filelist *files, struct filetorelease *file) {
	unsigned int i;
475
	bool first;
476

Bernhard Link's avatar
Bernhard Link committed
477 478 479
	if( files == NULL )
		return;
	filelist_writefiles(dir,len,files->nextl,file);
480 481
		(void)release_writedata(file,dir,len);
		(void)release_writestring(file,files->name);
482 483
		(void)release_writedata(file, separator_chars,
				sizeof(separator_chars) - 1);
484
		first = true;
485 486 487
		for( i = 0 ; i < files->count ; i ++ ) {
			if( !first )
				(void)release_writestring(file,",");
488
			first = false;
489 490 491
			(void)release_writestring(file,files->packages[i]);
		}
		(void)release_writestring(file,"\n");
Bernhard Link's avatar
Bernhard Link committed
492
	filelist_writefiles(dir,len,files->nextr,file);
493 494
}

495
static retvalue filelist_writedirs(char **buffer_p, size_t *size_p, size_t ofs, struct dirlist *dir, struct filetorelease *file) {
496

497 498 499 500 501 502 503 504 505 506
	if( dir->nextl != NULL ) {
		retvalue r;
		r = filelist_writedirs(buffer_p, size_p, ofs, dir->nextl, file);
		if( RET_WAS_ERROR(r) )
			return r;
	}
	{	size_t len = dir->len;
		register retvalue r;

		if( ofs+len+2 >= *size_p ) {
507 508
			char *n;

509
			*size_p += 1024*(1+(len/1024));
510
			n = realloc(*buffer_p, *size_p);
511 512
			if( n == NULL ) {
				free(*buffer_p);
513 514
				*buffer_p = NULL;
				return RET_ERROR_OOM;
515 516 517
			}
			*buffer_p = n;
		}
518 519
		memcpy((*buffer_p) + ofs, dir->name, len);
		(*buffer_p)[ofs + len] = '/';
520
		// TODO: output files and directories sorted together instead
521 522 523 524 525 526 527 528
		filelist_writefiles(*buffer_p, ofs+len+1, dir->files, file);
		if( dir->subdirs == NULL )
			r = RET_OK;
		else
			r = filelist_writedirs(buffer_p, size_p, ofs+len+1,
					dir->subdirs, file);
		if( dir->nextr == NULL )
			return r;
529 530 531
		if( RET_WAS_ERROR(r) )
			return r;
	}
532
	return filelist_writedirs(buffer_p, size_p, ofs, dir->nextr, file);
533 534 535 536 537 538 539 540 541 542 543 544 545
}

retvalue filelist_write(struct filelist_list *list, struct filetorelease *file) {
	size_t size = 1024;
	char *buffer = malloc(size);
	retvalue r;

	if( buffer == NULL )
		return RET_ERROR_OOM;

	(void)release_writedata(file,header,sizeof(header)-1);
	buffer[0] = '\0';
	filelist_writefiles(buffer,0,list->root->files,file);
546 547 548 549 550
	if( list->root->subdirs != NULL )
		r = filelist_writedirs(&buffer, &size, 0,
				list->root->subdirs, file);
	else
		r = RET_OK;
551 552 553
	free(buffer);
	return r;
}
554

555 556
/* helpers for filelist generators to get the preprocessed form */

557 558 559 560 561
retvalue filelistcompressor_setup(/*@out@*/struct filelistcompressor *c) {
	c->size = 2000; c->len = 0;
	c->filelist = malloc(c->size);
	if( c->filelist == NULL )
		return RET_ERROR_OOM;
562
	c->dirdepth = 0;
563 564 565
	return RET_OK;
}

566 567
static inline bool filelistcompressor_space(struct filelistcompressor *c, size_t len) {
	if( c->len + len + 2 >= c->size ) {
568 569 570
		char *n;

		if( c->size > 1024*1024*1024 ) {
Bernhard Link's avatar
Bernhard Link committed
571
			fprintf(stderr, "Ridiculously long file list!\n");
572
			return false;
573
		}
574
		c->size = c->len + len + 2048;
575 576
		n = realloc(c->filelist, c->size);
		if( n == NULL )
577
			return false;
578
		c->filelist = n;
579 580 581
	}
	return true;
}
582

583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637
retvalue filelistcompressor_add(struct filelistcompressor *c, const char *name, size_t name_len) {
	unsigned int depth;
	const char *separator;

	/* check if it is already in the current dir or a subdir of that: */
	if( name_len > 0 && *name == '.' ) {
		name++; name_len--;
	}
	while( name_len > 0 && *name == '/' ) {
		name++; name_len--;
	}
	for( depth = 0; depth < c->dirdepth ; depth++ ) {
		const unsigned char *u =(unsigned char *)c->filelist
						+ c->offsets[depth];
		size_t dir_len = 0;
		while( *u == 255 ) {
			dir_len += 255;
			u++;
		}
		dir_len += *(u++);
		if( dir_len >= name_len )
			break;
		if( memcmp(u, name, dir_len) != 0 || name[dir_len] != '/' )
			break;
		name += dir_len + 1;
		name_len -= dir_len + 1;
	}
	if( depth < c->dirdepth ) {
		if( !filelistcompressor_space(c, 1) )
			return RET_ERROR_OOM;
		c->filelist[c->len++] = (unsigned char)2 +
						c->dirdepth - depth;
		c->dirdepth = depth;
	}
	while( (separator = memchr(name, '/', name_len)) != NULL ) {
		size_t dirlen = separator - name;
		/* ignore files within directories with more than 255 chars */
		if( dirlen >= 255 )
			return RET_NOTHING;
		/* ignore too deep paths */
		if( c->dirdepth > 252 )
			return RET_NOTHING;
		/* add directory */
		if( !filelistcompressor_space(c, 2 + dirlen) )
			return RET_ERROR_OOM;
		c->filelist[c->len++] = 2;
		c->offsets[c->dirdepth++] = c->len;
		c->filelist[c->len++] = dirlen;
		memcpy(c->filelist + c->len, name, dirlen);
		c->len += dirlen;
		name += dirlen+1;
		name_len -= dirlen+1;
		while( name_len > 0 && *name == '/' ) {
			name++; name_len--;
		}
638
	}
639 640 641 642 643 644 645 646 647
	if( name_len >= 255 )
		return RET_NOTHING;
	/* all directories created, now only the file is left */
	if( !filelistcompressor_space(c, 2 + name_len) )
		return RET_ERROR_OOM;
	c->filelist[c->len++] = 1;
	c->filelist[c->len++] = name_len;
	memcpy(c->filelist + c->len, name, name_len);
	c->len += name_len;
648 649 650
	return RET_OK;
}

651
retvalue filelistcompressor_finish(struct filelistcompressor *c, /*@out@*/char **list,/*@out@*/size_t *size) {
652 653 654 655 656 657 658
	char *l;

	l = realloc(c->filelist, c->len+1);
	if( l == NULL ) {
		free(c->filelist);
		return RET_ERROR_OOM;
	}
659
	c->filelist[c->len] = '\0';
660
	*list = l;
661
	*size = c->len+1;
662 663 664 665 666 667 668
	return RET_OK;
}

void filelistcompressor_cancel(struct filelistcompressor *c) {
	free(c->filelist);
}

669 670 671 672 673 674 675
retvalue filelists_translate(struct table *oldtable, struct table *newtable) {
	retvalue r;
	struct cursor *cursor;
	const char *filekey, *olddata;
	size_t olddata_len, newdata_size;
	char *newdata;

676
	r = table_newglobalcursor(oldtable, &cursor);
677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699
	if( !RET_IS_OK(r) )
		return r;
	while( cursor_nexttempdata(oldtable, cursor, &filekey,
				&olddata, &olddata_len) ) {
		const char *p;
		size_t l;
		struct filelistcompressor c;

		r = filelistcompressor_setup(&c);
		if( RET_WAS_ERROR(r) )
			break;
		for( p = olddata ; (l = strlen(p)) != 0 ; p += l + 1 ) {
			r = filelistcompressor_add(&c, p, l);
			if( RET_WAS_ERROR(r) )
				break;
		}
		if( RET_WAS_ERROR(r) ) {
			filelistcompressor_cancel(&c);
			break;
		}
		r = filelistcompressor_finish(&c, &newdata, &newdata_size);
		if( !RET_IS_OK(r) )
			break;
700
		r = table_adduniqsizedrecord(newtable, filekey,
701
				newdata, newdata_size, false, false);
702 703 704 705 706 707 708 709 710 711 712 713 714 715
		free(newdata);
		if( RET_WAS_ERROR(r) )
			break;

	}
	if( RET_WAS_ERROR(r) ) {
		(void)cursor_close(oldtable, cursor);
		return r;
	}
	r = cursor_close(oldtable, cursor);
	if( RET_WAS_ERROR(r) )
		return r;
	return RET_OK;
}