From 44ed65a545970829322098e22d10947e6d545d9a Mon Sep 17 00:00:00 2001
From: Tom Lane
Date: Sun, 23 Aug 2015 13:02:13 -0400
Subject: Avoid use of float arithmetic in bipartite_match.c.

Since the distances used in this algorithm are small integers (not more
than the size of the U set, in fact), there is no good reason to use float
arithmetic for them.  Use short ints instead: they're smaller, faster, and
require no special portability assumptions.

Per testing by Greg Stark, which disclosed that the code got into an
infinite loop on VAX for lack of IEEE-style float infinities.  We don't
really care all that much whether Postgres can run on a VAX anymore,
but there seems sufficient reason to change this code anyway.

In passing, make a few other small adjustments to make the code match
usual Postgres coding style a bit better.
---
 src/include/lib/bipartite_match.h | 16 +++++++++-------
 1 file changed, 9 insertions(+), 7 deletions(-)

(limited to 'src/include/lib')

diff --git a/src/include/lib/bipartite_match.h b/src/include/lib/bipartite_match.h
index 373bbede1e1..c106a7e41d1 100644
--- a/src/include/lib/bipartite_match.h
+++ b/src/include/lib/bipartite_match.h
@@ -11,7 +11,7 @@
 /*
  * Given a bipartite graph consisting of nodes U numbered 1..nU, nodes V
  * numbered 1..nV, and an adjacency map of undirected edges in the form
- * adjacency[u] = [n, v1, v2, v3, ... vn], we wish to find a "maximum
+ * adjacency[u] = [k, v1, v2, v3, ... vk], we wish to find a "maximum
  * cardinality matching", which is defined as follows: a matching is a subset
  * of the original edges such that no node has more than one edge, and a
  * matching has maximum cardinality if there exists no other matching with a
@@ -24,21 +24,23 @@
  * the problem of planning a collection of grouping sets with the provably
  * minimal number of sort operations.
  */
-typedef struct bipartite_match_state
+typedef struct BipartiteMatchState
 {
+	/* inputs: */
 	int			u_size;			/* size of U */
 	int			v_size;			/* size of V */
+	short	  **adjacency;		/* adjacency[u] = [k, v1,v2,v3,...,vk] */
+	/* outputs: */
 	int			matching;		/* number of edges in matching */
-	short	  **adjacency;		/* adjacency[u] = [n, v1,v2,v3,...,vn] */
 	short	   *pair_uv;		/* pair_uv[u] -> v */
 	short	   *pair_vu;		/* pair_vu[v] -> u */
-
-	float	   *distance;		/* distance[u], float so we can have +inf */
+	/* private state for matching algorithm: */
+	short	   *distance;		/* distance[u] */
 	short	   *queue;			/* queue storage for breadth search */
 } BipartiteMatchState;
 
-BipartiteMatchState *BipartiteMatch(int u_size, int v_size, short **adjacency);
+extern BipartiteMatchState *BipartiteMatch(int u_size, int v_size, short **adjacency);
 
-void		BipartiteMatchFree(BipartiteMatchState *state);
+extern void BipartiteMatchFree(BipartiteMatchState *state);
 
 #endif   /* BIPARTITE_MATCH_H */
-- 
cgit v1.2.3