dpkg.c

这是一个SIGMA方案的PMP播放器的UCLINUX程序,可播放DVD,VCD,CD MP3...有很好的参考价值.

/*
 *  Mini dpkg implementation for busybox.
 *  This is not meant as a replacemnt for dpkg
 *
 *  Written By Glenn McGrath with the help of others
 *  Copyright (C) 2001 by Glenn McGrath
 * 		
 *  Started life as a busybox implementation of udpkg
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  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 Library 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/*
 * Known difference between busybox dpkg and the official dpkg that i dont
 * consider important, its worth keeping a note of differences anyway, just to
 * make it easier to maintain.
 *  - The first value for the Confflile: field isnt placed on a new line.
 *  - The <package>.control file is extracted and kept in the info dir.
 *  - When installing a package the Status: field is placed at the end of the
 *      section, rather than just after the Package: field.
 *  - Packages with previously unknown status are inserted at the begining of
 *      the status file
 *
 * Bugs that need to be fixed
 *  - (unknown, please let me know when you find any)
 *
 */

#include <getopt.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "unarchive.h"
#include "busybox.h"

/* NOTE: If you vary HASH_PRIME sizes be aware,
 * 1) Tweaking these will have a big effect on how much memory this program uses.
 * 2) For computational efficiency these hash tables should be at least 20%
 *    larger than the maximum number of elements stored in it.
 * 3) All _HASH_PRIME's must be a prime number or chaos is assured, if your looking
 *    for a prime, try http://www.utm.edu/research/primes/lists/small/10000.txt
 * 4) If you go bigger than 15 bits you may get into trouble (untested) as its
 *    sometimes cast to an unsigned int, if you go to 16 bit you will overlap
 *    int's and chaos is assured, 16381 is the max prime for 14 bit field
 */

/* NAME_HASH_PRIME, Stores package names and versions, 
 * I estimate it should be at least 50% bigger than PACKAGE_HASH_PRIME,
 * as there a lot of duplicate version numbers */
#define NAME_HASH_PRIME 16381
char *name_hashtable[NAME_HASH_PRIME + 1];

/* PACKAGE_HASH_PRIME, Maximum number of unique packages,
 * It must not be smaller than STATUS_HASH_PRIME,
 * Currently only packages from status_hashtable are stored in here, but in
 * future this may be used to store packages not only from a status file,
 * but an available_hashtable, and even multiple packages files.
 * Package can be stored more than once if they have different versions.
 * e.g. The same package may have different versions in the status file
 *      and available file */
#define PACKAGE_HASH_PRIME 10007
typedef struct edge_s {
	unsigned int operator:3;
	unsigned int type:4;
	unsigned int name:14;
	unsigned int version:14;
} edge_t;

typedef struct common_node_s {
	unsigned int name:14;
	unsigned int version:14;
	unsigned int num_of_edges:14;
	edge_t **edge;
} common_node_t;
common_node_t *package_hashtable[PACKAGE_HASH_PRIME + 1];

/* Currently it doesnt store packages that have state-status of not-installed
 * So it only really has to be the size of the maximum number of packages
 * likely to be installed at any one time, so there is a bit of leaway here */
#define STATUS_HASH_PRIME 8191
typedef struct status_node_s {
	unsigned int package:14;	/* has to fit PACKAGE_HASH_PRIME */
	unsigned int status:14;		/* has to fit STATUS_HASH_PRIME */
} status_node_t;
status_node_t *status_hashtable[STATUS_HASH_PRIME + 1];

/* Even numbers are for 'extras', like ored dependecies or null */
enum edge_type_e {
	EDGE_NULL = 0,
	EDGE_PRE_DEPENDS = 1,
	EDGE_OR_PRE_DEPENDS = 2,
	EDGE_DEPENDS = 3,
	EDGE_OR_DEPENDS = 4,
	EDGE_REPLACES = 5,
	EDGE_PROVIDES = 7,
	EDGE_CONFLICTS = 9,
	EDGE_SUGGESTS = 11,
	EDGE_RECOMMENDS = 13,
	EDGE_ENHANCES = 15
};
enum operator_e {
	VER_NULL = 0,
	VER_EQUAL = 1,
	VER_LESS = 2,
	VER_LESS_EQUAL = 3,
	VER_MORE = 4,
	VER_MORE_EQUAL = 5,
	VER_ANY = 6
};

enum dpkg_opt_e {
	dpkg_opt_purge = 1,
	dpkg_opt_remove = 2,
	dpkg_opt_unpack = 4,
	dpkg_opt_configure = 8,
	dpkg_opt_install = 16,
	dpkg_opt_package_name = 32,
	dpkg_opt_filename = 64,
	dpkg_opt_list_installed = 128,
	dpkg_opt_force_ignore_depends = 256
};

typedef struct deb_file_s {
	char *control_file;
	char *filename;
	unsigned int package:14;
} deb_file_t;


void make_hash(const char *key, unsigned int *start, unsigned int *decrement, const int hash_prime)
{
	unsigned long int hash_num = key[0];
	int len = strlen(key);
	int i;

	/* Maybe i should have uses a "proper" hashing algorithm here instead
	 * of making one up myself, seems to be working ok though. */
	for(i = 1; i < len; i++) {
		/* shifts the ascii based value and adds it to previous value
		 * shift amount is mod 24 because long int is 32 bit and data
		 * to be shifted is 8, dont want to shift data to where it has
		 * no effect*/
		hash_num += ((key[i] + key[i-1]) << ((key[i] * i) % 24)); 
	}
	*start = (unsigned int) hash_num % hash_prime;
	*decrement = (unsigned int) 1 + (hash_num % (hash_prime - 1));
}

/* this adds the key to the hash table */
int search_name_hashtable(const char *key)
{
	unsigned int probe_address = 0;
	unsigned int probe_decrement = 0;
//	char *temp;

	make_hash(key, &probe_address, &probe_decrement, NAME_HASH_PRIME);
	while(name_hashtable[probe_address] != NULL) {
		if (strcmp(name_hashtable[probe_address], key) == 0) {
			return(probe_address);
		} else {
			probe_address -= probe_decrement;
			if ((int)probe_address < 0) {
				probe_address += NAME_HASH_PRIME;
			}
		}
	}
	name_hashtable[probe_address] = xstrdup(key);
	return(probe_address);
}

/* this DOESNT add the key to the hashtable
 * TODO make it consistent with search_name_hashtable
 */
unsigned int search_status_hashtable(const char *key)
{
	unsigned int probe_address = 0;
	unsigned int probe_decrement = 0;

	make_hash(key, &probe_address, &probe_decrement, STATUS_HASH_PRIME);
	while(status_hashtable[probe_address] != NULL) {
		if (strcmp(key, name_hashtable[package_hashtable[status_hashtable[probe_address]->package]->name]) == 0) {
			break;
		} else {
			probe_address -= probe_decrement;
			if ((int)probe_address < 0) {
				probe_address += STATUS_HASH_PRIME;
			}
		}
	}
	return(probe_address);
}

/* Need to rethink version comparison, maybe the official dpkg has something i can use ? */
int version_compare_part(const char *version1, const char *version2)
{
	int upstream_len1 = 0;
	int upstream_len2 = 0;
	char *name1_char;
	char *name2_char;
	int len1 = 0;
	int len2 = 0;
	int tmp_int;
	int ver_num1;
	int ver_num2;
	int ret;

	if (version1 == NULL) {
		version1 = xstrdup("");
	}
	if (version2 == NULL) {
		version2 = xstrdup("");
	}
	upstream_len1 = strlen(version1);
	upstream_len2 = strlen(version2);

	while ((len1 < upstream_len1) || (len2 < upstream_len2)) {
		/* Compare non-digit section */
		tmp_int = strcspn(&version1[len1], "0123456789");
		name1_char = xstrndup(&version1[len1], tmp_int);
		len1 += tmp_int;
		tmp_int = strcspn(&version2[len2], "0123456789");
		name2_char = xstrndup(&version2[len2], tmp_int);
		len2 += tmp_int;
		tmp_int = strcmp(name1_char, name2_char);
		free(name1_char);
		free(name2_char);
		if (tmp_int != 0) {
			ret = tmp_int;
			goto cleanup_version_compare_part;
		}

		/* Compare digits */
		tmp_int = strspn(&version1[len1], "0123456789");
		name1_char = xstrndup(&version1[len1], tmp_int);
		len1 += tmp_int;
		tmp_int = strspn(&version2[len2], "0123456789");
		name2_char = xstrndup(&version2[len2], tmp_int);
		len2 += tmp_int;
		ver_num1 = atoi(name1_char);
		ver_num2 = atoi(name2_char);
		free(name1_char);
		free(name2_char);
		if (ver_num1 < ver_num2) {
			ret = -1;
			goto cleanup_version_compare_part;
		}
		else if (ver_num1 > ver_num2) {
			ret = 1;
			goto cleanup_version_compare_part;
		}
	}
	ret = 0;
cleanup_version_compare_part:
	return(ret);
}

/* if ver1 < ver2 return -1,
 * if ver1 = ver2 return 0,
 * if ver1 > ver2 return 1,
 */
int version_compare(const unsigned int ver1, const unsigned int ver2)
{
	char *ch_ver1 = name_hashtable[ver1];
	char *ch_ver2 = name_hashtable[ver2];

	char epoch1, epoch2;
	char *deb_ver1, *deb_ver2;
	char *ver1_ptr, *ver2_ptr;
	char *upstream_ver1;
	char *upstream_ver2;
	int result;

	/* Compare epoch */
	if (ch_ver1[1] == ':') {
		epoch1 = ch_ver1[0];
		ver1_ptr = strchr(ch_ver1, ':') + 1;
	} else {
		epoch1 = '0';
		ver1_ptr = ch_ver1;
	}
	if (ch_ver2[1] == ':') {
		epoch2 = ch_ver2[0];
		ver2_ptr = strchr(ch_ver2, ':') + 1;
	} else {
		epoch2 = '0';
		ver2_ptr = ch_ver2;
	}
	if (epoch1 < epoch2) {
		return(-1);
	}
	else if (epoch1 > epoch2) {
		return(1);
	}

	/* Compare upstream version */
	upstream_ver1 = xstrdup(ver1_ptr);
	upstream_ver2 = xstrdup(ver2_ptr);

	/* Chop off debian version, and store for later use */
	deb_ver1 = strrchr(upstream_ver1, '-');
	deb_ver2 = strrchr(upstream_ver2, '-');
	if (deb_ver1) {
		deb_ver1[0] = '\0';
		deb_ver1++;
	}
	if (deb_ver2) {
		deb_ver2[0] = '\0';
		deb_ver2++;
	}
	result = version_compare_part(upstream_ver1, upstream_ver2);

	free(upstream_ver1);
	free(upstream_ver2);

	if (result != 0) {
		return(result);
	}

	/* Compare debian versions */
	return(version_compare_part(deb_ver1, deb_ver2));
}

int test_version(const unsigned int version1, const unsigned int version2, const unsigned int operator)
{
	const int version_result = version_compare(version1, version2);
	switch(operator) {
		case (VER_ANY):
			return(TRUE);
		case (VER_EQUAL):
			if (version_result == 0) {
				return(TRUE);
			}
			break;
		case (VER_LESS):
			if (version_result < 0) {
				return(TRUE);
			}
			break;
		case (VER_LESS_EQUAL):
			if (version_result <= 0) {
				return(TRUE);
			}
			break;
		case (VER_MORE):
			if (version_result > 0) {
				return(TRUE);
			}
			break;
		case (VER_MORE_EQUAL):
			if (version_result >= 0) {
				return(TRUE);
			}
			break;
	}
	return(FALSE);
}


int search_package_hashtable(const unsigned int name, const unsigned int version, const unsigned int operator)
{
	unsigned int probe_address = 0;
	unsigned int probe_decrement = 0;

	make_hash(name_hashtable[name], &probe_address, &probe_decrement, PACKAGE_HASH_PRIME);
	while(package_hashtable[probe_address] != NULL) {
		if (package_hashtable[probe_address]->name == name) {
			if (operator == VER_ANY) {
				return(probe_address);
			}
			if (test_version(package_hashtable[probe_address]->version, version, operator)) {
				return(probe_address);
			}
		}
		probe_address -= probe_decrement;
		if ((int)probe_address < 0) {
			probe_address += PACKAGE_HASH_PRIME;
		}
	}
	return(probe_address);