PostgreSQL Source Code  git master
bipartite_match.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  BipartiteMatchState
 

Typedefs

typedef struct BipartiteMatchState BipartiteMatchState
 

Functions

BipartiteMatchStateBipartiteMatch (int u_size, int v_size, short **adjacency)
 
void BipartiteMatchFree (BipartiteMatchState *state)
 

Typedef Documentation

◆ BipartiteMatchState

Function Documentation

◆ BipartiteMatch()

BipartiteMatchState* BipartiteMatch ( int  u_size,
int  v_size,
short **  adjacency 
)

Definition at line 39 of file bipartite_match.c.

40 {
42 
43  if (u_size < 0 || u_size >= SHRT_MAX ||
44  v_size < 0 || v_size >= SHRT_MAX)
45  elog(ERROR, "invalid set size for BipartiteMatch");
46 
47  state->u_size = u_size;
48  state->v_size = v_size;
49  state->adjacency = adjacency;
50  state->matching = 0;
51  state->pair_uv = (short *) palloc0((u_size + 1) * sizeof(short));
52  state->pair_vu = (short *) palloc0((v_size + 1) * sizeof(short));
53  state->distance = (short *) palloc((u_size + 1) * sizeof(short));
54  state->queue = (short *) palloc((u_size + 2) * sizeof(short));
55 
56  while (hk_breadth_search(state))
57  {
58  int u;
59 
60  for (u = 1; u <= u_size; u++)
61  {
62  if (state->pair_uv[u] == 0)
63  if (hk_depth_search(state, u))
64  state->matching++;
65  }
66 
67  CHECK_FOR_INTERRUPTS(); /* just in case */
68  }
69 
70  return state;
71 }
static bool hk_depth_search(BipartiteMatchState *state, int u)
static bool hk_breadth_search(BipartiteMatchState *state)
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
void * palloc0(Size size)
Definition: mcxt.c:1347
void * palloc(Size size)
Definition: mcxt.c:1317
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:122
Definition: regguts.h:323

References CHECK_FOR_INTERRUPTS, elog, ERROR, hk_breadth_search(), hk_depth_search(), palloc(), and palloc0().

Referenced by extract_rollup_sets().

◆ BipartiteMatchFree()

void BipartiteMatchFree ( BipartiteMatchState state)

Definition at line 78 of file bipartite_match.c.

79 {
80  /* adjacency matrix is treated as owned by the caller */
81  pfree(state->pair_uv);
82  pfree(state->pair_vu);
83  pfree(state->distance);
84  pfree(state->queue);
85  pfree(state);
86 }
void pfree(void *pointer)
Definition: mcxt.c:1521

References pfree().

Referenced by extract_rollup_sets().