PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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

Function Documentation

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

Definition at line 39 of file bipartite_match.c.

References BipartiteMatchState::adjacency, CHECK_FOR_INTERRUPTS, BipartiteMatchState::distance, elog, ERROR, hk_breadth_search(), hk_depth_search(), BipartiteMatchState::matching, BipartiteMatchState::pair_uv, BipartiteMatchState::pair_vu, palloc(), palloc0(), BipartiteMatchState::queue, BipartiteMatchState::u_size, and BipartiteMatchState::v_size.

Referenced by extract_rollup_sets().

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)
#define ERROR
Definition: elog.h:43
static bool hk_breadth_search(BipartiteMatchState *state)
void * palloc0(Size size)
Definition: mcxt.c:878
Definition: regguts.h:298
void * palloc(Size size)
Definition: mcxt.c:849
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:100
#define elog
Definition: elog.h:219
void BipartiteMatchFree ( BipartiteMatchState state)

Definition at line 78 of file bipartite_match.c.

References BipartiteMatchState::distance, BipartiteMatchState::pair_uv, BipartiteMatchState::pair_vu, pfree(), and BipartiteMatchState::queue.

Referenced by extract_rollup_sets().

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:950