From 4beec8f055fd3b0cc4ef618cce8b52c58dd0ee08 Mon Sep 17 00:00:00 2001 From: Karen Arutyunov Date: Wed, 6 Sep 2017 17:40:06 +0300 Subject: Add implementation --- libpkgconf/queue.c | 194 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 194 insertions(+) create mode 100644 libpkgconf/queue.c (limited to 'libpkgconf/queue.c') diff --git a/libpkgconf/queue.c b/libpkgconf/queue.c new file mode 100644 index 0000000..227b160 --- /dev/null +++ b/libpkgconf/queue.c @@ -0,0 +1,194 @@ +/* + * queue.c + * compilation of a list of packages into a world dependency set + * + * Copyright (c) 2012 pkgconf authors (see AUTHORS). + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * This software is provided 'as is' and without any warranty, express or + * implied. In no event shall the authors be liable for any damages arising + * from the use of this software. + */ + +#include + +/* + * !doc + * + * libpkgconf `queue` module + * ========================= + * + * The `queue` module provides an interface that allows easily building a dependency graph from an + * arbitrary set of dependencies. It also provides support for doing "preflight" checks on the entire + * dependency graph prior to working with it. + * + * Using the `queue` module functions is the recommended way of working with dependency graphs. + */ + +typedef struct { + pkgconf_node_t iter; + char *package; +} pkgconf_queue_t; + +/* + * !doc + * + * .. c:function:: void pkgconf_queue_push(pkgconf_list_t *list, const char *package) + * + * Pushes a requested dependency onto the dependency resolver's queue. + * + * :param pkgconf_list_t* list: the dependency resolution queue to add the package request to. + * :param char* package: the dependency atom requested + * :return: nothing + */ +void +pkgconf_queue_push(pkgconf_list_t *list, const char *package) +{ + pkgconf_queue_t *pkgq = calloc(sizeof(pkgconf_queue_t), 1); + + pkgq->package = strdup(package); + pkgconf_node_insert_tail(&pkgq->iter, pkgq, list); +} + +/* + * !doc + * + * .. c:function:: bool pkgconf_queue_compile(pkgconf_client_t *client, pkgconf_pkg_t *world, pkgconf_list_t *list) + * + * Compile a dependency resolution queue into a dependency resolution problem if possible, otherwise report an error. + * + * :param pkgconf_client_t* client: The pkgconf client object to use for dependency resolution. + * :param pkgconf_pkg_t* world: The designated root of the dependency graph. + * :param pkgconf_list_t* list: The list of dependency requests to consider. + * :return: true if the built dependency resolution problem is consistent, else false + * :rtype: bool + */ +bool +pkgconf_queue_compile(pkgconf_client_t *client, pkgconf_pkg_t *world, pkgconf_list_t *list) +{ + pkgconf_node_t *iter; + + PKGCONF_FOREACH_LIST_ENTRY(list->head, iter) + { + pkgconf_queue_t *pkgq; + + pkgq = iter->data; + pkgconf_dependency_parse(client, world, &world->requires, pkgq->package); + } + + return (world->requires.head != NULL); +} + +/* + * !doc + * + * .. c:function:: void pkgconf_queue_free(pkgconf_list_t *list) + * + * Release any memory related to a dependency resolution queue. + * + * :param pkgconf_list_t* list: The dependency resolution queue to release. + * :return: nothing + */ +void +pkgconf_queue_free(pkgconf_list_t *list) +{ + pkgconf_node_t *node, *tnode; + + PKGCONF_FOREACH_LIST_ENTRY_SAFE(list->head, tnode, node) + { + pkgconf_queue_t *pkgq = node->data; + + free(pkgq->package); + free(pkgq); + } +} + +static inline unsigned int +pkgconf_queue_verify(pkgconf_client_t *client, pkgconf_pkg_t *world, pkgconf_list_t *list, int maxdepth) +{ + if (!pkgconf_queue_compile(client, world, list)) + return PKGCONF_PKG_ERRF_DEPGRAPH_BREAK; + + return pkgconf_pkg_verify_graph(client, world, maxdepth); +} + +/* + * !doc + * + * .. c:function:: void pkgconf_queue_apply(pkgconf_client_t *client, pkgconf_list_t *list, pkgconf_queue_apply_func_t func, int maxdepth, void *data) + * + * Attempt to compile a dependency resolution queue into a dependency resolution problem, then attempt to solve the problem and + * feed the solution to a callback function if a complete dependency graph is found. + * + * :param pkgconf_client_t* client: The pkgconf client object to use for dependency resolution. + * :param pkgconf_list_t* list: The list of dependency requests to consider. + * :param pkgconf_queue_apply_func_t func: The callback function to call if a solution is found by the dependency resolver. + * :param int maxdepth: The maximum allowed depth for the dependency resolver. A depth of -1 means unlimited. + * :param void* data: An opaque pointer which is passed to the callback function. + * :returns: true if the dependency resolver found a solution, otherwise false. + * :rtype: bool + */ +bool +pkgconf_queue_apply(pkgconf_client_t *client, pkgconf_list_t *list, pkgconf_queue_apply_func_t func, int maxdepth, void *data) +{ + pkgconf_pkg_t world = { + .id = "virtual:world", + .realname = "virtual world package", + .flags = PKGCONF_PKG_PROPF_STATIC | PKGCONF_PKG_PROPF_VIRTUAL, + }; + + /* if maxdepth is one, then we will not traverse deeper than our virtual package. */ + if (!maxdepth) + maxdepth = -1; + + if (pkgconf_queue_verify(client, &world, list, maxdepth) != PKGCONF_PKG_ERRF_OK) + return false; + + if (!func(client, &world, data, maxdepth)) + { + pkgconf_pkg_free(client, &world); + return false; + } + + pkgconf_pkg_free(client, &world); + + return true; +} + +/* + * !doc + * + * .. c:function:: void pkgconf_queue_validate(pkgconf_client_t *client, pkgconf_list_t *list, pkgconf_queue_apply_func_t func, int maxdepth, void *data) + * + * Attempt to compile a dependency resolution queue into a dependency resolution problem, then attempt to solve the problem. + * + * :param pkgconf_client_t* client: The pkgconf client object to use for dependency resolution. + * :param pkgconf_list_t* list: The list of dependency requests to consider. + * :param int maxdepth: The maximum allowed depth for the dependency resolver. A depth of -1 means unlimited. + * :returns: true if the dependency resolver found a solution, otherwise false. + * :rtype: bool + */ +bool +pkgconf_queue_validate(pkgconf_client_t *client, pkgconf_list_t *list, int maxdepth) +{ + bool retval = true; + pkgconf_pkg_t world = { + .id = "virtual:world", + .realname = "virtual world package", + .flags = PKGCONF_PKG_PROPF_STATIC | PKGCONF_PKG_PROPF_VIRTUAL, + }; + + /* if maxdepth is one, then we will not traverse deeper than our virtual package. */ + if (!maxdepth) + maxdepth = -1; + + if (pkgconf_queue_verify(client, &world, list, maxdepth) != PKGCONF_PKG_ERRF_OK) + retval = false; + + pkgconf_pkg_free(client, &world); + + return retval; +} -- cgit v1.1