[PATCH 1/5] graph.h: replace hardcoded values with an enum

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

[PATCH 1/5] graph.h: replace hardcoded values with an enum

Andrew Gregory
Signed-off-by: Andrew Gregory <[hidden email]>
---

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
Reply | Threaded
Open this post in threaded view
|

[PATCH 2/5] graph.h: rename childptr -> iterator

Andrew Gregory
Signed-off-by: Andrew Gregory <[hidden email]>
---
 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
Reply | Threaded
Open this post in threaded view
|

[PATCH 4/5] sortbydeps: rename found -> switched_to_child

Andrew Gregory
In reply to this post by Andrew Gregory
Signed-off-by: Andrew Gregory <[hidden email]>
---
 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
Reply | Threaded
Open this post in threaded view
|

[PATCH 3/5] sortbydeps: factor out dep cycle warning

Andrew Gregory
In reply to this post by Andrew Gregory
Signed-off-by: Andrew Gregory <[hidden email]>
---
 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
Reply | Threaded
Open this post in threaded view
|

[PATCH 5/5] sortbydeps: rename vptr -> i

Andrew Gregory
In reply to this post by Andrew Gregory
vptr is a simple list iterator, which are typically named i.

Signed-off-by: Andrew Gregory <[hidden email]>
---
 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
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH 1/5] graph.h: replace hardcoded values with an enum

Allan McRae
In reply to this post by Andrew Gregory
On 16/04/17 07:57, Andrew Gregory wrote:
> Signed-off-by: Andrew Gregory <[hidden email]>
> ---

<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);
>
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH 3/5] sortbydeps: factor out dep cycle warning

Allan McRae
In reply to this post by Andrew Gregory
On 16/04/17 07:57, Andrew Gregory wrote:

> Signed-off-by: Andrew Gregory <[hidden email]>
> ---
>  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) {
>
Reply | Threaded
Open this post in threaded view
|

[PATCH v2] graph.h: replace hardcoded values with an enum

Andrew Gregory
In reply to this post by Allan McRae
Signed-off-by: Andrew Gregory <[hidden email]>
---

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