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