adb: improve sorting features, sort installed-db package listing

3 files changed, 155 insertions, 55 deletions

diff --git a/src/adb.c b/src/adb.c
index 2237a67..848322e 100644
--- a/src/adb.c
+++ b/src/adb.c
@@ -60,55 +60,73 @@ void adb_reset(struct adb *db)
 	db->adb.len = 0;
 }
 
-int adb_m_map(struct adb *db, int fd, uint32_t expected_schema, struct adb_trust *t)
+static int __adb_m_parse(struct adb *db, struct adb_trust *t)
 {
-	struct stat st;
-	struct adb_header *hdr;
-	struct adb_block *blk;
 	struct adb_verify_ctx vfy = {};
+	struct adb_block *blk;
+	int r = -EBADMSG;
 	int trusted = t ? 0 : 1;
 
-	if (fstat(fd, &st) != 0) return -errno;
-	if (st.st_size < sizeof *hdr) return -EIO;
-
-	memset(db, 0, sizeof *db);
-	db->mmap.ptr = mmap(NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
-	db->mmap.len = st.st_size;
-	if (db->mmap.ptr == MAP_FAILED) return -errno;
-
-	hdr = (struct adb_header *) db->mmap.ptr;
-	if (hdr->magic != htole32(ADB_FORMAT_MAGIC)) goto bad_msg;
-	if (expected_schema && expected_schema != le32toh(hdr->schema)) goto bad_msg;
-
-	db->hdr = *hdr;
-	db->data = APK_BLOB_PTR_LEN(db->mmap.ptr + sizeof *hdr, db->mmap.len - sizeof *hdr);
 	adb_foreach_block(blk, db->data) {
 		apk_blob_t b = APK_BLOB_PTR_LEN((char*)(blk+1), ADB_BLOCK_SIZE(blk));
 		switch (ADB_BLOCK_TYPE(blk)) {
 		case ADB_BLOCK_ADB:
-			if (!APK_BLOB_IS_NULL(db->adb)) goto bad_msg;
+			if (!APK_BLOB_IS_NULL(db->adb)) break;
 			db->adb = b;
 			break;
 		case ADB_BLOCK_SIG:
-			if (APK_BLOB_IS_NULL(db->adb)) goto bad_msg;
+			if (APK_BLOB_IS_NULL(db->adb)) break;
 			if (!trusted &&
 			    adb_trust_verify_signature(t, db, &vfy, b) == 0)
 				trusted = 1;
 			break;
 		default:
-			if (APK_BLOB_IS_NULL(db->adb)) goto bad_msg;
+			if (APK_BLOB_IS_NULL(db->adb)) break;
 			break;
 		}
 	}
-	if (!trusted) blk = ERR_PTR(-ENOKEY);
-	if (IS_ERR(blk)) goto err;
-	return 0;
+	if (IS_ERR(blk)) r = PTR_ERR(blk);
+	else if (!trusted) r = -ENOKEY;
+	else if (db->adb.ptr) r = 0;
 
-bad_msg:
-	blk = ERR_PTR(-EBADMSG);
+	if (r != 0) {
+		db->adb = APK_BLOB_NULL;
+	}
+	return r;
+}
+
+int adb_m_blob(struct adb *db, apk_blob_t blob, struct adb_trust *t)
+{
+	*db = (struct adb) { .data = blob };
+	return __adb_m_parse(db, t);
+}
+
+int adb_m_map(struct adb *db, int fd, uint32_t expected_schema, struct adb_trust *t)
+{
+	struct stat st;
+	struct adb_header *hdr;
+	int r = -EBADMSG;
+
+	if (fstat(fd, &st) != 0) return -errno;
+	if (st.st_size < sizeof *hdr) return -EIO;
+
+	memset(db, 0, sizeof *db);
+	db->mmap.ptr = mmap(NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
+	db->mmap.len = st.st_size;
+	if (db->mmap.ptr == MAP_FAILED) return -errno;
+
+	hdr = (struct adb_header *) db->mmap.ptr;
+	if (hdr->magic != htole32(ADB_FORMAT_MAGIC)) goto err;
+	if (expected_schema && expected_schema != le32toh(hdr->schema)) goto err;
+
+	db->hdr = *hdr;
+	db->data = APK_BLOB_PTR_LEN(db->mmap.ptr + sizeof *hdr, db->mmap.len - sizeof *hdr);
+	r = __adb_m_parse(db, t);
+	if (r) goto err;
+	return 0;
 err:
 	adb_free(db);
-	return PTR_ERR(blk);
+	return r;
 }
 
 int adb_w_init_dynamic(struct adb *db, uint32_t schema, void *buckets, size_t num_buckets)
@@ -265,6 +283,28 @@ struct adb_obj *adb_ro_obj(const struct adb_obj *o, unsigned i, struct adb_obj *
 	return adb_r_obj(o->db, adb_ro_val(o, i), no, schema);
 }
 
+int adb_ro_cmp(const struct adb_obj *o1, const struct adb_obj *o2, unsigned i)
+{
+	assert(o1->schema->kind == ADB_KIND_OBJECT);
+	assert(o1->schema == o2->schema);
+	assert(i > 0 && i < o1->schema->num_fields);
+
+	switch (*o1->schema->fields[i-1].kind) {
+	case ADB_KIND_BLOB:
+	case ADB_KIND_INT:
+		return container_of(o1->schema->fields[i-1].kind, struct adb_scalar_schema, kind)->compare(
+			o1->db, adb_ro_val(o1, i),
+			o2->db, adb_ro_val(o2, i));
+	case ADB_KIND_OBJECT: {
+		struct adb_obj so1, so2;
+		adb_ro_obj(o1, i, &so1);
+		adb_ro_obj(o2, i, &so2);
+		return so1.schema->compare(&so1, &so2);
+		}
+	}
+	assert(0);
+}
+
 static struct adb *__db1, *__db2;
 static const struct adb_object_schema *__schema;
 
@@ -276,6 +316,17 @@ static int wacmp(const void *p1, const void *p2)
 	return o1.schema->compare(&o1, &o2);
 }
 
+static int wadbcmp(const void *p1, const void *p2)
+{
+	struct adb a1, a2;
+	struct adb_obj o1, o2;
+	adb_m_blob(&a1, adb_r_blob(__db1, *(adb_val_t *)p1), 0);
+	adb_m_blob(&a2, adb_r_blob(__db2, *(adb_val_t *)p2), 0);
+	adb_r_rootobj(&a1, &o1, __schema);
+	adb_r_rootobj(&a2, &o2, __schema);
+	return __schema->compare(&o1, &o2);
+}
+
 int adb_ra_find(struct adb_obj *arr, int cur, struct adb *db, adb_val_t val)
 {
 	adb_val_t *ndx;
@@ -635,23 +686,27 @@ adb_val_t adb_wo_int(struct adb_obj *o, unsigned i, uint32_t v)
 
 adb_val_t adb_wo_blob(struct adb_obj *o, unsigned i, apk_blob_t b)
 {
+	assert(o->schema->kind == ADB_KIND_OBJECT);
 	return adb_wo_val(o, i, adb_w_blob(o->db, b));
 }
 
 adb_val_t adb_wo_obj(struct adb_obj *o, unsigned i, struct adb_obj *no)
 {
+	assert(o->schema->kind == ADB_KIND_OBJECT);
 	assert(o->db == no->db);
 	return adb_wo_val(o, i, adb_w_obj(no));
 }
 
 adb_val_t adb_wo_arr(struct adb_obj *o, unsigned i, struct adb_obj *no)
 {
+	assert(o->schema->kind == ADB_KIND_OBJECT || o->schema->kind == ADB_KIND_ARRAY);
 	assert(o->db == no->db);
 	return adb_wo_val(o, i, adb_w_arr(no));
 }
 
 adb_val_t adb_wa_append(struct adb_obj *o, adb_val_t v)
 {
+	assert(o->schema->kind == ADB_KIND_ARRAY);
 	if (o->num >= o->obj[ADBI_NUM_ENTRIES]) return adb_w_error(o->db, E2BIG);
 	if (ADB_IS_ERROR(v)) return adb_w_error(o->db, ADB_VAL_VALUE(v));
 	o->obj[o->num++] = v;
@@ -660,20 +715,33 @@ adb_val_t adb_wa_append(struct adb_obj *o, adb_val_t v)
 
 adb_val_t adb_wa_append_obj(struct adb_obj *o, struct adb_obj *no)
 {
+	assert(o->schema->kind == ADB_KIND_ARRAY);
 	assert(o->db == no->db);
 	return adb_wa_append(o, adb_w_obj(no));
 }
 
 adb_val_t adb_wa_append_fromstring(struct adb_obj *o, apk_blob_t b)
 {
+	assert(o->schema->kind == ADB_KIND_ARRAY);
 	return adb_wa_append(o, adb_w_fromstring(o->db, o->schema->fields[0].kind, b));
 }
 
 void adb_wa_sort(struct adb_obj *arr)
 {
+	assert(arr->schema->kind == ADB_KIND_ARRAY);
 	__db1 = __db2 = arr->db;
-	__schema = container_of(arr->schema->fields[0].kind, struct adb_object_schema, kind);
-	qsort(&arr->obj[ADBI_FIRST], adb_ra_num(arr), sizeof(arr->obj[0]), wacmp);
+	switch (*arr->schema->fields[0].kind) {
+	case ADB_KIND_OBJECT:
+		__schema = container_of(arr->schema->fields[0].kind, struct adb_object_schema, kind);
+		qsort(&arr->obj[ADBI_FIRST], adb_ra_num(arr), sizeof(arr->obj[0]), wacmp);
+		break;
+	case ADB_KIND_ADB:
+		__schema = container_of(arr->schema->fields[0].kind, struct adb_adb_schema, kind)->schema;
+		qsort(&arr->obj[ADBI_FIRST], adb_ra_num(arr), sizeof(arr->obj[0]), wadbcmp);
+		break;
+	default:
+		assert(1);
+	}
 }
 
 void adb_wa_sort_unique(struct adb_obj *arr)
diff --git a/src/adb.h b/src/adb.h
index 576f13f..851aece 100644
--- a/src/adb.h
+++ b/src/adb.h
@@ -102,7 +102,7 @@ struct adb_object_schema {
 	apk_blob_t (*tostring)(struct adb_obj *, char *, size_t);
 	int (*fromstring)(struct adb_obj *, apk_blob_t);
 	uint32_t (*get_default_int)(unsigned i);
-	int (*compare)(struct adb_obj *, struct adb_obj *);
+	int (*compare)(const struct adb_obj *, const struct adb_obj *);
 	void (*pre_commit)(struct adb_obj *);
 
 	struct {
@@ -116,13 +116,13 @@ struct adb_scalar_schema {
 
 	apk_blob_t (*tostring)(struct adb*, adb_val_t, char *, size_t);
 	adb_val_t (*fromstring)(struct adb*, apk_blob_t);
-	int (*compare)(adb_val_t, adb_val_t);
+	int (*compare)(struct adb*, adb_val_t, struct adb*, adb_val_t);
 };
 
 struct adb_adb_schema {
 	uint8_t kind;
 	uint32_t schema_id;
-	struct adb_object_schema *obj;
+	const struct adb_object_schema *schema;
 };
 
 /* Database read interface */
@@ -153,6 +153,7 @@ struct adb_obj {
 int adb_free(struct adb *);
 void adb_reset(struct adb *);
 
+int adb_m_blob(struct adb *, apk_blob_t, struct adb_trust *);
 int adb_m_map(struct adb *, int fd, uint32_t expected_schema, struct adb_trust *);
 #define adb_w_init_alloca(db, schema, num_buckets) adb_w_init_dynamic(db, schema, alloca(sizeof(struct list_head[num_buckets])), num_buckets)
 #define adb_w_init_tmp(db, size) adb_w_init_static(db, alloca(size), size)
@@ -174,6 +175,7 @@ adb_val_t adb_ro_val(const struct adb_obj *o, unsigned i);
 uint32_t adb_ro_int(const struct adb_obj *o, unsigned i);
 apk_blob_t adb_ro_blob(const struct adb_obj *o, unsigned i);
 struct adb_obj *adb_ro_obj(const struct adb_obj *o, unsigned i, struct adb_obj *);
+int adb_ro_cmp(const struct adb_obj *o1, const struct adb_obj *o2, unsigned i);
 int adb_ra_find(struct adb_obj *arr, int cur, struct adb *db, adb_val_t val);
 
 /* Primitive write */
diff --git a/src/apk_adb.c b/src/apk_adb.c
index 4abc0f3..3bd5827 100644
--- a/src/apk_adb.c
+++ b/src/apk_adb.c
@@ -90,10 +90,16 @@ static adb_val_t string_fromstring(struct adb *db, apk_blob_t val)
 	return adb_w_blob(db, val);
 }
 
+static int string_compare(struct adb *db1, adb_val_t v1, struct adb *db2, adb_val_t v2)
+{
+	return apk_blob_sort(adb_r_blob(db1, v1), adb_r_blob(db2, v2));
+}
+
 static struct adb_scalar_schema scalar_string = {
 	.kind = ADB_KIND_BLOB,
 	.tostring = string_tostring,
 	.fromstring = string_fromstring,
+	.compare = string_compare,
 };
 
 const struct adb_object_schema schema_string_array = {
@@ -102,6 +108,23 @@ const struct adb_object_schema schema_string_array = {
 	.fields = ADB_ARRAY_ITEM(scalar_string),
 };
 
+static int version_compare(struct adb *db1, adb_val_t v1, struct adb *db2, adb_val_t v2)
+{
+	switch (apk_version_compare_blob(adb_r_blob(db1, v1), adb_r_blob(db2, v2))) {
+	case APK_VERSION_LESS: return -1;
+	case APK_VERSION_GREATER: return 1;
+	default: return 0;
+	}
+}
+
+static struct adb_scalar_schema scalar_version = {
+	.kind = ADB_KIND_BLOB,
+	.tostring = string_tostring,
+	.fromstring = string_fromstring,
+	.compare = version_compare,
+};
+
+
 static apk_blob_t hexblob_tostring(struct adb *db, adb_val_t val, char *buf, size_t bufsz)
 {
 	apk_blob_t b = adb_r_blob(db, val), to = APK_BLOB_PTR_LEN(buf, bufsz);
@@ -132,10 +155,20 @@ static adb_val_t int_fromstring(struct adb *db, apk_blob_t val)
 	return adb_w_int(db, n);
 }
 
+static int int_compare(struct adb *db1, adb_val_t v1, struct adb *db2, adb_val_t v2)
+{
+	uint32_t r1 = adb_r_int(db1, v1);
+	uint32_t r2 = adb_r_int(db1, v2);
+	if (r1 < r2) return -1;
+	if (r1 > r2) return 1;
+	return 0;
+}
+
 static struct adb_scalar_schema scalar_int = {
 	.kind = ADB_KIND_INT,
 	.tostring = int_tostring,
 	.fromstring = int_fromstring,
+	.compare = int_compare,
 };
 
 static apk_blob_t oct_tostring(struct adb *db, adb_val_t val, char *buf, size_t bufsz)
@@ -160,6 +193,7 @@ static struct adb_scalar_schema scalar_hsize = {
 	.kind = ADB_KIND_INT,
 	.tostring = hsize_tostring,
 	.fromstring = int_fromstring,
+	.compare = int_compare,
 };
 
 static apk_blob_t dependency_tostring(struct adb_obj *obj, char *buf, size_t bufsz)
@@ -247,11 +281,9 @@ fail:
 	return -EAPKDEPFORMAT;
 }
 
-static int dependency_cmp(struct adb_obj *o1, struct adb_obj *o2)
+static int dependency_cmp(const struct adb_obj *o1, const struct adb_obj *o2)
 {
-	return apk_blob_sort(
-		adb_ro_blob(o1, ADBI_DEP_NAME),
-		adb_ro_blob(o2, ADBI_DEP_NAME));
+	return adb_ro_cmp(o1, o2, ADBI_DEP_NAME);
 }
 
 const struct adb_object_schema schema_dependency = {
@@ -262,7 +294,7 @@ const struct adb_object_schema schema_dependency = {
 	.compare = dependency_cmp,
 	.fields = {
 		ADB_FIELD(ADBI_DEP_NAME,	"name",		scalar_string),
-		ADB_FIELD(ADBI_DEP_VERSION,	"version",	scalar_string),
+		ADB_FIELD(ADBI_DEP_VERSION,	"version",	scalar_version),
 		ADB_FIELD(ADBI_DEP_MATCH,	"match",	scalar_int),
 	},
 };
@@ -290,22 +322,14 @@ const struct adb_object_schema schema_dependency_array = {
 	.fields = ADB_ARRAY_ITEM(schema_dependency),
 };
 
-static int pkginfo_cmp(struct adb_obj *o1, struct adb_obj *o2)
+static int pkginfo_cmp(const struct adb_obj *o1, const struct adb_obj *o2)
 {
 	int r;
-	r = apk_blob_sort(
-		adb_ro_blob(o1, ADBI_PI_NAME),
-		adb_ro_blob(o2, ADBI_PI_NAME));
+	r = adb_ro_cmp(o1, o2, ADBI_PI_NAME);
 	if (r) return r;
-
-	r = apk_version_compare_blob(
-		adb_ro_blob(o1, ADBI_PI_VERSION),
-		adb_ro_blob(o2, ADBI_PI_VERSION));
-	switch (r) {
-	case APK_VERSION_LESS: return -1;
-	case APK_VERSION_GREATER: return 1;
-	}
-	return 0;
+	r = adb_ro_cmp(o1, o2, ADBI_PI_VERSION);
+	if (r) return r;
+	return adb_ro_cmp(o1, o2, ADBI_PI_UNIQUE_ID);
 }
 
 const struct adb_object_schema schema_pkginfo = {
@@ -314,7 +338,7 @@ const struct adb_object_schema schema_pkginfo = {
 	.compare = pkginfo_cmp,
 	.fields = {
 		ADB_FIELD(ADBI_PI_NAME,		"name",		scalar_string),
-		ADB_FIELD(ADBI_PI_VERSION,	"version",	scalar_string),
+		ADB_FIELD(ADBI_PI_VERSION,	"version",	scalar_version),
 		ADB_FIELD(ADBI_PI_UNIQUE_ID,	"unique-id",	scalar_int),
 		ADB_FIELD(ADBI_PI_DESCRIPTION,	"description",	scalar_string),
 		ADB_FIELD(ADBI_PI_ARCH,		"arch",		scalar_string),
@@ -363,11 +387,9 @@ static uint32_t file_get_default_int(unsigned i)
 	return -1;
 }
 
-static int file_cmp(struct adb_obj *o1, struct adb_obj *o2)
+static int file_cmp(const struct adb_obj *o1, const struct adb_obj *o2)
 {
-	return apk_blob_sort(
-		adb_ro_blob(o1, ADBI_FI_NAME),
-		adb_ro_blob(o2, ADBI_FI_NAME));
+	return adb_ro_cmp(o1, o2, ADBI_FI_NAME);
 }
 
 const struct adb_object_schema schema_file = {
@@ -440,9 +462,15 @@ const struct adb_object_schema schema_scripts = {
 	},
 };
 
+static int package_cmp(const struct adb_obj *o1, const struct adb_obj *o2)
+{
+	return adb_ro_cmp(o1, o2, ADBI_PKG_PKGINFO);
+}
+
 const struct adb_object_schema schema_package = {
 	.kind = ADB_KIND_OBJECT,
 	.num_fields = ADBI_PKG_MAX,
+	.compare = package_cmp,
 	.fields = {
 		ADB_FIELD(ADBI_PKG_PKGINFO,	"info",		schema_pkginfo),
 		ADB_FIELD(ADBI_PKG_PATHS,	"paths",	schema_path_array),
@@ -455,10 +483,12 @@ const struct adb_object_schema schema_package = {
 const struct adb_adb_schema schema_package_adb = {
 	.kind = ADB_KIND_ADB,
 	.schema_id = ADB_SCHEMA_PACKAGE,
+	.schema = &schema_package,
 };
 
 const struct adb_object_schema schema_package_adb_array = {
 	.kind = ADB_KIND_ARRAY,
+	.pre_commit = adb_wa_sort,
 	.num_fields = APK_MAX_INDEX_PACKAGES,
 	.fields = ADB_ARRAY_ITEM(schema_package_adb),
 };