[pacman-dev] [PATCH 1/5] graph.h: replace hardcoded values with an enum
Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> --- This series is an attempt to clean up sortbydeps primarily by giving variables better names and factoring out the dependency cycle warning. There shouldn't be any change in behavior. lib/libalpm/delta.c | 4 ++-- lib/libalpm/deps.c | 10 +++++----- lib/libalpm/graph.h | 8 +++++++- 3 files changed, 14 insertions(+), 8 deletions(-) diff --git a/lib/libalpm/delta.c b/lib/libalpm/delta.c index c5571b29..58b1b41e 100644 --- a/lib/libalpm/delta.c +++ b/lib/libalpm/delta.c @@ -130,7 +130,7 @@ static void dijkstra(alpm_list_t *vertices) for(i = vertices; i; i = i->next) { alpm_graph_t *v_i = i->data; - if(v_i->state == -1) { + if(v_i->state == ALPM_GRAPH_STATE_PROCESSING) { continue; } @@ -142,7 +142,7 @@ static void dijkstra(alpm_list_t *vertices) break; } - v->state = -1; + v->state = ALPM_GRAPH_STATE_PROCESSING; v->childptr = v->children; while(v->childptr) { diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index 40b2be6d..e5527d6c 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -194,16 +194,16 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, vertex = vertices->data; while(vptr) { /* mark that we touched the vertex */ - vertex->state = -1; + vertex->state = ALPM_GRAPH_STATE_PROCESSING; int found = 0; while(vertex->childptr && !found) { alpm_graph_t *nextchild = vertex->childptr->data; vertex->childptr = vertex->childptr->next; - if(nextchild->state == 0) { + if(nextchild->state == ALPM_GRAPH_STATE_UNPROCESSED) { found = 1; nextchild->parent = vertex; vertex = nextchild; - } else if(nextchild->state == -1) { + } else if(nextchild->state == ALPM_GRAPH_STATE_PROCESSING) { /* child is an ancestor of vertex */ alpm_graph_t *transvertex = vertex; @@ -244,13 +244,13 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, newtargs = alpm_list_add(newtargs, vertex->data); } /* mark that we've left this vertex */ - vertex->state = 1; + vertex->state = ALPM_GRAPH_STATE_PROCESSED; vertex = vertex->parent; if(!vertex) { /* top level vertex reached, move to the next unprocessed vertex */ for( vptr = vptr->next; vptr; vptr = vptr->next) { vertex = vptr->data; - if(vertex->state == 0) { + if(vertex->state == ALPM_GRAPH_STATE_UNPROCESSED) { break; } } diff --git a/lib/libalpm/graph.h b/lib/libalpm/graph.h index 2e9eac10..f1da837c 100644 --- a/lib/libalpm/graph.h +++ b/lib/libalpm/graph.h @@ -23,13 +23,19 @@ #include "alpm_list.h" +enum __alpm_graph_vertex_state { + ALPM_GRAPH_STATE_UNPROCESSED = 0, + ALPM_GRAPH_STATE_PROCESSING = -1, + ALPM_GRAPH_STATE_PROCESSED = 1 +}; + typedef struct __alpm_graph_t { void *data; struct __alpm_graph_t *parent; /* where did we come from? */ alpm_list_t *children; alpm_list_t *childptr; /* points to a child in children list */ off_t weight; /* weight of the node */ - signed char state; /* 0: untouched, -1: entered, other: leaving time */ + signed char state; } alpm_graph_t; alpm_graph_t *_alpm_graph_new(void); -- 2.12.2
Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> --- lib/libalpm/delta.c | 10 +++++----- lib/libalpm/deps.c | 8 ++++---- lib/libalpm/graph.h | 2 +- 3 files changed, 10 insertions(+), 10 deletions(-) diff --git a/lib/libalpm/delta.c b/lib/libalpm/delta.c index 58b1b41e..89bc32ff 100644 --- a/lib/libalpm/delta.c +++ b/lib/libalpm/delta.c @@ -71,7 +71,7 @@ static alpm_list_t *graph_init(alpm_list_t *deltas, int reverse) v_i->children = alpm_list_add(v_i->children, v_j); } } - v_i->childptr = v_i->children; + v_i->iterator = v_i->children; } return vertices; } @@ -144,16 +144,16 @@ static void dijkstra(alpm_list_t *vertices) v->state = ALPM_GRAPH_STATE_PROCESSING; - v->childptr = v->children; - while(v->childptr) { - alpm_graph_t *v_c = v->childptr->data; + v->iterator = v->children; + while(v->iterator) { + alpm_graph_t *v_c = v->iterator->data; alpm_delta_t *d_c = v_c->data; if(v_c->weight > v->weight + d_c->download_size) { v_c->weight = v->weight + d_c->download_size; v_c->parent = v; } - v->childptr = (v->childptr)->next; + v->iterator = (v->iterator)->next; } } diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index e5527d6c..6f05f0d0 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -152,7 +152,7 @@ static alpm_list_t *dep_graph_init(alpm_handle_t *handle, j = next; } - vertex_i->childptr = vertex_i->children; + vertex_i->iterator = vertex_i->children; } alpm_list_free(localpkgs); return vertices; @@ -196,9 +196,9 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, /* mark that we touched the vertex */ vertex->state = ALPM_GRAPH_STATE_PROCESSING; int found = 0; - while(vertex->childptr && !found) { - alpm_graph_t *nextchild = vertex->childptr->data; - vertex->childptr = vertex->childptr->next; + while(vertex->iterator && !found) { + alpm_graph_t *nextchild = vertex->iterator->data; + vertex->iterator = vertex->iterator->next; if(nextchild->state == ALPM_GRAPH_STATE_UNPROCESSED) { found = 1; nextchild->parent = vertex; diff --git a/lib/libalpm/graph.h b/lib/libalpm/graph.h index f1da837c..76e97525 100644 --- a/lib/libalpm/graph.h +++ b/lib/libalpm/graph.h @@ -33,7 +33,7 @@ typedef struct __alpm_graph_t { void *data; struct __alpm_graph_t *parent; /* where did we come from? */ alpm_list_t *children; - alpm_list_t *childptr; /* points to a child in children list */ + alpm_list_t *iterator; /* used for DFS without recursion */ off_t weight; /* weight of the node */ signed char state; } alpm_graph_t; -- 2.12.2
Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> --- lib/libalpm/deps.c | 70 +++++++++++++++++++++++++++++------------------------- 1 file changed, 37 insertions(+), 33 deletions(-) diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index 6f05f0d0..01e550a4 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -158,6 +158,42 @@ static alpm_list_t *dep_graph_init(alpm_handle_t *handle, return vertices; } +static void _alpm_warn_dep_cycle(alpm_handle_t *handle, alpm_list_t *targets, + alpm_graph_t *ancestor, alpm_graph_t *vertex, int reverse) +{ + /* vertex depends on and is required by ancestor */ + if(!alpm_list_find_ptr(targets, vertex->data)) { + /* child is not part of the transaction, not a problem */ + return; + } + + /* find the nearest ancestor that's part of the transaction */ + while(ancestor) { + if(alpm_list_find_ptr(targets, ancestor->data)) { + break; + } + ancestor = ancestor->parent; + } + + if(!ancestor || ancestor == vertex) { + /* no transaction package in our ancestry or the package has + * a circular dependency with itself, not a problem */ + } else { + alpm_pkg_t *ancestorpkg = ancestor->data; + alpm_pkg_t *childpkg = vertex->data; + _alpm_log(handle, ALPM_LOG_WARNING, _("dependency cycle detected:\n")); + if(reverse) { + _alpm_log(handle, ALPM_LOG_WARNING, + _("%s will be removed after its %s dependency\n"), + ancestorpkg->name, childpkg->name); + } else { + _alpm_log(handle, ALPM_LOG_WARNING, + _("%s will be installed before its %s dependency\n"), + ancestorpkg->name, childpkg->name); + } + } +} + /* Re-order a list of target packages with respect to their dependencies. * * Example (reverse == 0): @@ -204,39 +240,7 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, nextchild->parent = vertex; vertex = nextchild; } else if(nextchild->state == ALPM_GRAPH_STATE_PROCESSING) { - /* child is an ancestor of vertex */ - alpm_graph_t *transvertex = vertex; - - if(!alpm_list_find_ptr(targets, nextchild->data)) { - /* child is not part of the transaction, not a problem */ - continue; - } - - /* find the nearest parent that's part of the transaction */ - while(transvertex) { - if(alpm_list_find_ptr(targets, transvertex->data)) { - break; - } - transvertex = transvertex->parent; - } - - if(!transvertex || transvertex == nextchild) { - /* no transaction package in our ancestry or the package has - * a circular dependency with itself, not a problem */ - } else { - alpm_pkg_t *transpkg = transvertex->data; - alpm_pkg_t *childpkg = nextchild->data; - _alpm_log(handle, ALPM_LOG_WARNING, _("dependency cycle detected:\n")); - if(reverse) { - _alpm_log(handle, ALPM_LOG_WARNING, - _("%s will be removed after its %s dependency\n"), - transpkg->name, childpkg->name); - } else { - _alpm_log(handle, ALPM_LOG_WARNING, - _("%s will be installed before its %s dependency\n"), - transpkg->name, childpkg->name); - } - } + _alpm_warn_dep_cycle(handle, targets, vertex, nextchild, reverse); } } if(!found) { -- 2.12.2
On 16/04/17 07:57, Andrew Gregory wrote:
Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> --- lib/libalpm/deps.c | 70 +++++++++++++++++++++++++++++------------------------- 1 file changed, 37 insertions(+), 33 deletions(-)
diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index 6f05f0d0..01e550a4 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -158,6 +158,42 @@ static alpm_list_t *dep_graph_init(alpm_handle_t *handle, return vertices; }
+static void _alpm_warn_dep_cycle(alpm_handle_t *handle, alpm_list_t *targets, + alpm_graph_t *ancestor, alpm_graph_t *vertex, int reverse) +{ + /* vertex depends on and is required by ancestor */ + if(!alpm_list_find_ptr(targets, vertex->data)) { + /* child is not part of the transaction, not a problem */ + return; + } + + /* find the nearest ancestor that's part of the transaction */ + while(ancestor) { + if(alpm_list_find_ptr(targets, ancestor->data)) { + break; + } + ancestor = ancestor->parent; + } + + if(!ancestor || ancestor == vertex) { + /* no transaction package in our ancestry or the package has + * a circular dependency with itself, not a problem */ + } else { + alpm_pkg_t *ancestorpkg = ancestor->data; + alpm_pkg_t *childpkg = vertex->data; + _alpm_log(handle, ALPM_LOG_WARNING, _("dependency cycle detected:\n")); + if(reverse) { + _alpm_log(handle, ALPM_LOG_WARNING, + _("%s will be removed after its %s dependency\n"), + ancestorpkg->name, childpkg->name); + } else { + _alpm_log(handle, ALPM_LOG_WARNING, + _("%s will be installed before its %s dependency\n"), + ancestorpkg->name, childpkg->name); + } + } +} +
Patch is OK. I'd love it if these messages migrated to the front end too... A
/* Re-order a list of target packages with respect to their dependencies. * * Example (reverse == 0): @@ -204,39 +240,7 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, nextchild->parent = vertex; vertex = nextchild; } else if(nextchild->state == ALPM_GRAPH_STATE_PROCESSING) { - /* child is an ancestor of vertex */ - alpm_graph_t *transvertex = vertex; - - if(!alpm_list_find_ptr(targets, nextchild->data)) { - /* child is not part of the transaction, not a problem */ - continue; - } - - /* find the nearest parent that's part of the transaction */ - while(transvertex) { - if(alpm_list_find_ptr(targets, transvertex->data)) { - break; - } - transvertex = transvertex->parent; - } - - if(!transvertex || transvertex == nextchild) { - /* no transaction package in our ancestry or the package has - * a circular dependency with itself, not a problem */ - } else { - alpm_pkg_t *transpkg = transvertex->data; - alpm_pkg_t *childpkg = nextchild->data; - _alpm_log(handle, ALPM_LOG_WARNING, _("dependency cycle detected:\n")); - if(reverse) { - _alpm_log(handle, ALPM_LOG_WARNING, - _("%s will be removed after its %s dependency\n"), - transpkg->name, childpkg->name); - } else { - _alpm_log(handle, ALPM_LOG_WARNING, - _("%s will be installed before its %s dependency\n"), - transpkg->name, childpkg->name); - } - } + _alpm_warn_dep_cycle(handle, targets, vertex, nextchild, reverse); } } if(!found) {
Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> --- lib/libalpm/deps.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index 01e550a4..f55d6074 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -231,19 +231,19 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, while(vptr) { /* mark that we touched the vertex */ vertex->state = ALPM_GRAPH_STATE_PROCESSING; - int found = 0; - while(vertex->iterator && !found) { + int switched_to_child = 0; + while(vertex->iterator && !switched_to_child) { alpm_graph_t *nextchild = vertex->iterator->data; vertex->iterator = vertex->iterator->next; if(nextchild->state == ALPM_GRAPH_STATE_UNPROCESSED) { - found = 1; + switched_to_child = 1; nextchild->parent = vertex; vertex = nextchild; } else if(nextchild->state == ALPM_GRAPH_STATE_PROCESSING) { _alpm_warn_dep_cycle(handle, targets, vertex, nextchild, reverse); } } - if(!found) { + if(!switched_to_child) { if(alpm_list_find_ptr(targets, vertex->data)) { newtargs = alpm_list_add(newtargs, vertex->data); } -- 2.12.2
vptr is a simple list iterator, which are typically named i. Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> --- lib/libalpm/deps.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index f55d6074..96f91739 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -215,7 +215,7 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, { alpm_list_t *newtargs = NULL; alpm_list_t *vertices = NULL; - alpm_list_t *vptr; + alpm_list_t *i; alpm_graph_t *vertex; if(targets == NULL) { @@ -226,9 +226,9 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, vertices = dep_graph_init(handle, targets, ignore); - vptr = vertices; + i = vertices; vertex = vertices->data; - while(vptr) { + while(i) { /* mark that we touched the vertex */ vertex->state = ALPM_GRAPH_STATE_PROCESSING; int switched_to_child = 0; @@ -252,8 +252,8 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, vertex = vertex->parent; if(!vertex) { /* top level vertex reached, move to the next unprocessed vertex */ - for( vptr = vptr->next; vptr; vptr = vptr->next) { - vertex = vptr->data; + for(i = i->next; i; i = i->next) { + vertex = i->data; if(vertex->state == ALPM_GRAPH_STATE_UNPROCESSED) { break; } -- 2.12.2
On 16/04/17 07:57, Andrew Gregory wrote:
Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> ---
<snip>
+enum __alpm_graph_vertex_state { + ALPM_GRAPH_STATE_UNPROCESSED = 0, + ALPM_GRAPH_STATE_PROCESSING = -1, + ALPM_GRAPH_STATE_PROCESSED = 1 +}; +
Why keep the -1, 0, 1 state when switching to an enum? I can't see a point when it matters?
typedef struct __alpm_graph_t { void *data; struct __alpm_graph_t *parent; /* where did we come from? */ alpm_list_t *children; alpm_list_t *childptr; /* points to a child in children list */ off_t weight; /* weight of the node */ - signed char state; /* 0: untouched, -1: entered, other: leaving time */ + signed char state;
struct __alpm_graph_vertex_state state ?
} alpm_graph_t;
alpm_graph_t *_alpm_graph_new(void);
Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> --- Removed explicit enum values since they don't matter and converted the state field type to enum. lib/libalpm/delta.c | 4 ++-- lib/libalpm/deps.c | 10 +++++----- lib/libalpm/graph.h | 8 +++++++- 3 files changed, 14 insertions(+), 8 deletions(-) diff --git a/lib/libalpm/delta.c b/lib/libalpm/delta.c index c5571b29..58b1b41e 100644 --- a/lib/libalpm/delta.c +++ b/lib/libalpm/delta.c @@ -130,7 +130,7 @@ static void dijkstra(alpm_list_t *vertices) for(i = vertices; i; i = i->next) { alpm_graph_t *v_i = i->data; - if(v_i->state == -1) { + if(v_i->state == ALPM_GRAPH_STATE_PROCESSING) { continue; } @@ -142,7 +142,7 @@ static void dijkstra(alpm_list_t *vertices) break; } - v->state = -1; + v->state = ALPM_GRAPH_STATE_PROCESSING; v->childptr = v->children; while(v->childptr) { diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index 40b2be6d..e5527d6c 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -194,16 +194,16 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, vertex = vertices->data; while(vptr) { /* mark that we touched the vertex */ - vertex->state = -1; + vertex->state = ALPM_GRAPH_STATE_PROCESSING; int found = 0; while(vertex->childptr && !found) { alpm_graph_t *nextchild = vertex->childptr->data; vertex->childptr = vertex->childptr->next; - if(nextchild->state == 0) { + if(nextchild->state == ALPM_GRAPH_STATE_UNPROCESSED) { found = 1; nextchild->parent = vertex; vertex = nextchild; - } else if(nextchild->state == -1) { + } else if(nextchild->state == ALPM_GRAPH_STATE_PROCESSING) { /* child is an ancestor of vertex */ alpm_graph_t *transvertex = vertex; @@ -244,13 +244,13 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, newtargs = alpm_list_add(newtargs, vertex->data); } /* mark that we've left this vertex */ - vertex->state = 1; + vertex->state = ALPM_GRAPH_STATE_PROCESSED; vertex = vertex->parent; if(!vertex) { /* top level vertex reached, move to the next unprocessed vertex */ for( vptr = vptr->next; vptr; vptr = vptr->next) { vertex = vptr->data; - if(vertex->state == 0) { + if(vertex->state == ALPM_GRAPH_STATE_UNPROCESSED) { break; } } diff --git a/lib/libalpm/graph.h b/lib/libalpm/graph.h index 2e9eac10..233862b9 100644 --- a/lib/libalpm/graph.h +++ b/lib/libalpm/graph.h @@ -23,13 +23,19 @@ #include "alpm_list.h" +enum __alpm_graph_vertex_state { + ALPM_GRAPH_STATE_UNPROCESSED, + ALPM_GRAPH_STATE_PROCESSING, + ALPM_GRAPH_STATE_PROCESSED +}; + typedef struct __alpm_graph_t { void *data; struct __alpm_graph_t *parent; /* where did we come from? */ alpm_list_t *children; alpm_list_t *childptr; /* points to a child in children list */ off_t weight; /* weight of the node */ - signed char state; /* 0: untouched, -1: entered, other: leaving time */ + enum __alpm_graph_vertex_state state; } alpm_graph_t; alpm_graph_t *_alpm_graph_new(void); -- 2.12.2
participants (2)
-
Allan McRae
-
Andrew Gregory