aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--hungarian.c131
1 files changed, 49 insertions, 82 deletions
diff --git a/hungarian.c b/hungarian.c
index 4c0ea17..e981066 100644
--- a/hungarian.c
+++ b/hungarian.c
@@ -35,35 +35,6 @@
-//new cell[X]
-#define new_cells(X) new_longs(X)
-
-//new boolean[X]
-#define new_booleans(X) new_longs(X)
-
-//new byte[X]
-#define new_bytes(X) malloc((size_t)(X))
-
-//new llong[X]
-#define new_llongs(X) malloc((size_t)(X) << 3)
-
-//new long[X]
-#if !(defined __LP64__ || defined __LLP64__)
-# define new_longs(X) malloc((size_t)(X) << 2) /*32-bit*/
-#else
-# define new_longs(X) malloc((size_t)(X) << 3) /*64-bit*/
-#endif
-
-//new float[X]
-#define new_floats(X) malloc((size_t)(X) << 2)
-
-//new double[X]
-#define new_doubles(X) malloc((size_t)(X) << 3)
-
-//new ?[][X]
-#define new_arrays(X) new_longs(X)
-
-
#ifdef DEBUG
# define debug(X) fprintf(stderr, "\033[31m%s\033[m\n", X)
#else
@@ -103,17 +74,17 @@ typedef struct
/**
* Singleton array with the index of the first non-zero limb
*/
- ssize_t* first;
+ size_t* first;
/**
* Array the the index of the previous non-zero limb for each limb
*/
- ssize_t* prev;
+ size_t* prev;
/**
* Array the the index of the next non-zero limb for each limb
*/
- ssize_t* next;
+ size_t* next;
} BitSet;
@@ -123,8 +94,8 @@ ssize_t** kuhn_match(cell** table, size_t n, size_t m);
void kuhn_reduceRows(cell** t, size_t n, size_t m);
byte** kuhn_mark(cell** t, size_t n, size_t m);
boolean kuhn_isDone(byte** marks, boolean* colCovered, size_t n, size_t m);
-long* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCovered, size_t n, size_t m);
-void kuhn_altMarks(byte** marks, ssize_t* altRow, ssize_t* altCol, ssize_t* colMarks, ssize_t* rowPrimes, ssize_t* prime, size_t n, size_t m);
+size_t* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCovered, size_t n, size_t m);
+void kuhn_altMarks(byte** marks, size_t* altRow, size_t* altCol, ssize_t* colMarks, ssize_t* rowPrimes, size_t* prime, size_t n, size_t m);
void kuhn_addAndSubtract(cell** t, boolean* rowCovered, boolean* colCovered, size_t n, size_t m);
ssize_t** kuhn_assign(byte** marks, size_t n, size_t m);
@@ -133,13 +104,13 @@ void BitSet_set(BitSet this, size_t i);
void BitSet_unset(BitSet this, size_t i);
ssize_t BitSet_any(BitSet this) __attribute__((pure));
-ssize_t lb(llong x) __attribute__((const));
+size_t lb(llong x) __attribute__((const));
void print(cell** t, size_t n, size_t m, long** assignment);
-int main(int argc, char** argv __attribute__((unused)))
+int main(int argc, char** argv)
{
FILE* urandom = fopen(RANDOM_DEVICE, "r");
unsigned int seed;
@@ -148,30 +119,26 @@ int main(int argc, char** argv __attribute__((unused)))
fclose(urandom);
- size_t n = 10, m = 15;
-
size_t i, j;
- cell** t = new_arrays(n);
- cell** table = new_arrays(n);
- if (argc < 2)
+ size_t n = argc < 3 ? 10 : (size_t)atol(*(argv + 1));
+ size_t m = argc < 3 ? 15 : (size_t)atol(*(argv + 2));
+ cell** t = malloc(n * sizeof(cell*));
+ cell** table = malloc(n * sizeof(cell*));
+ if (argc < 3)
for (i = 0; i < n; i++)
{
- *(t + i) = new_llongs(m);
- *(table + i) = new_llongs(m);
+ *(t + i) = malloc(m * sizeof(cell));
+ *(table + i) = malloc(m * sizeof(cell));
for (j = 0; j < m; j++)
*(*(table + i) + j) = *(*(t + i) + j) = (cell)(random() & 63);
}
else
{
cell x;
- scanf("%lu", &n);
- scanf("%lu", &m);
- t = new_arrays(n);
- table = new_arrays(n);
for (i = 0; i < n; i++)
{
- *(t + i) = new_llongs(m);
- *(table + i) = new_llongs(m);
+ *(t + i) = malloc(m * sizeof(cell));
+ *(table + i) = malloc(m * sizeof(cell));
for (j = 0; j < m; j++)
{
scanf(CELL_STR, &x);
@@ -207,10 +174,10 @@ void print(cell** t, size_t n, size_t m, ssize_t** assignment)
{
size_t i, j;
- ssize_t** assigned = new_arrays(n);
+ ssize_t** assigned = malloc(n * sizeof(ssize_t*));
for (i = 0; i < n; i++)
{
- *(assigned + i) = new_longs(m);
+ *(assigned + i) = malloc(m * sizeof(ssize_t));
for (j = 0; j < m; j++)
*(*(assigned + i) + j) = 0;
}
@@ -256,8 +223,8 @@ ssize_t** kuhn_match(cell** table, size_t n, size_t m)
kuhn_reduceRows(table, n, m);
byte** marks = kuhn_mark(table, n, m);
- boolean* rowCovered = new_booleans(n);
- boolean* colCovered = new_booleans(m);
+ boolean* rowCovered = malloc(n * sizeof(boolean));
+ boolean* colCovered = malloc(m * sizeof(boolean));
for (i = 0; i < n; i++)
{
*(rowCovered + i) = false;
@@ -266,13 +233,13 @@ ssize_t** kuhn_match(cell** table, size_t n, size_t m)
for (i = n; i < m; i++)
*(colCovered + i) = false;
- long* altRow = new_longs(n * m);
- long* altCol = new_longs(n * m);
+ size_t* altRow = malloc(n * m * sizeof(ssize_t));
+ size_t* altCol = malloc(n * m * sizeof(ssize_t));
- long* rowPrimes = new_longs(n);
- long* colMarks = new_longs(m);
+ ssize_t* rowPrimes = malloc(n * sizeof(ssize_t));
+ ssize_t* colMarks = malloc(m * sizeof(ssize_t));
- long* prime;
+ size_t* prime;
for (;;)
{
@@ -357,17 +324,17 @@ void kuhn_reduceRows(cell** t, size_t n, size_t m)
byte** kuhn_mark(cell** t, size_t n, size_t m)
{
size_t i, j;
- byte** marks = new_arrays(n);
+ byte** marks = malloc(n * sizeof(byte*));
byte* marksi;
for (i = 0; i < n; i++)
{
- marksi = *(marks + i) = new_bytes(m);
+ marksi = *(marks + i) = malloc(m * sizeof(byte));
for (j = 0; j < m; j++)
*(marksi + j) = UNMARKED;
}
- boolean* rowCovered = new_booleans(n);
- boolean* colCovered = new_booleans(m);
+ boolean* rowCovered = malloc(n * sizeof(boolean));
+ boolean* colCovered = malloc(m * sizeof(boolean));
for (i = 0; i < n; i++)
{
*(rowCovered + i) = false;
@@ -432,7 +399,7 @@ boolean kuhn_isDone(byte** marks, boolean* colCovered, size_t n, size_t m)
* @param m The table's width
* @return The row and column of the found print, <code>null</code> will be returned if none can be found
*/
-ssize_t* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCovered, size_t n, size_t m)
+size_t* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCovered, size_t n, size_t m)
{
size_t i, j;
BitSet zeroes = new_BitSet(n * m);
@@ -502,7 +469,7 @@ ssize_t* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* co
}
else
{
- long* rc = new_longs(2);
+ size_t* rc = malloc(2 * sizeof(size_t));
*rc = row;
*(rc + 1) = col;
free(zeroes.limbs);
@@ -527,7 +494,7 @@ ssize_t* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* co
* @param n The table's height
* @param m The table's width
*/
-void kuhn_altMarks(byte** marks, ssize_t* altRow, ssize_t* altCol, ssize_t* colMarks, ssize_t* rowPrimes, ssize_t* prime, size_t n, size_t m)
+void kuhn_altMarks(byte** marks, size_t* altRow, size_t* altCol, ssize_t* colMarks, ssize_t* rowPrimes, size_t* prime, size_t n, size_t m)
{
size_t index = 0, i, j;
*altRow = *prime;
@@ -556,14 +523,14 @@ void kuhn_altMarks(byte** marks, ssize_t* altRow, ssize_t* altCol, ssize_t* colM
break;
index++;
- *(altRow + index) = row;
+ *(altRow + index) = (size_t)row;
*(altCol + index) = *(altCol + index - 1);
col = *(rowPrimes + *(altRow + index));
index++;
*(altRow + index) = *(altRow + index - 1);
- *(altCol + index) = col;
+ *(altCol + index) = (size_t)col;
}
byte* markx;
@@ -629,12 +596,12 @@ void kuhn_addAndSubtract(cell** t, boolean* rowCovered, boolean* colCovered, siz
*/
ssize_t** kuhn_assign(byte** marks, size_t n, size_t m)
{
- ssize_t** assignment = new_arrays(n);
+ ssize_t** assignment = malloc(n * sizeof(ssize_t*));
size_t i, j;
for (i = 0; i < n; i++)
{
- *(assignment + i) = new_longs(2);
+ *(assignment + i) = malloc(2 * sizeof(ssize_t));
for (j = 0; j < m; j++)
if (*(*(marks + i) + j) == MARKED)
{
@@ -661,10 +628,10 @@ BitSet new_BitSet(size_t size)
if (size & 63L)
c++;
- this.limbs = new_llongs(c);
- this.prev = new_longs(c + 1L);
- this.next = new_longs(c + 1L);
- *(this.first = new_longs(1)) = 0;
+ this.limbs = malloc(c * sizeof(llong));
+ this.prev = malloc((c + 1) * sizeof(long));
+ this.next = malloc((c + 1) * sizeof(long));
+ *(this.first = malloc(sizeof(long))) = 0;
size_t i;
for (i = 0; i < c; i++)
@@ -693,10 +660,10 @@ void BitSet_set(BitSet this, size_t i)
if ((!*(this.limbs + j)) ^ (!old))
{
j++;
- *(this.prev + *(this.first)) = (ssize_t)j;
+ *(this.prev + *(this.first)) = j;
*(this.prev + j) = 0;
*(this.next + j) = *(this.first);
- *(this.first) = (ssize_t)j;
+ *(this.first) = j;
}
}
@@ -716,11 +683,11 @@ void BitSet_unset(BitSet this, size_t i)
if ((!*(this.limbs + j)) ^ (!old))
{
j++;
- ssize_t p = *(this.prev + j);
- ssize_t n = *(this.next + j);
+ size_t p = *(this.prev + j);
+ size_t n = *(this.next + j);
*(this.prev + n) = p;
*(this.next + p) = n;
- if (*(this.first) == (ssize_t)j)
+ if (*(this.first) == j)
*(this.first) = n;
}
}
@@ -736,8 +703,8 @@ ssize_t BitSet_any(BitSet this)
if (*(this.first) == 0L)
return -1;
- ssize_t i = *(this.first) - 1;
- return lb(*(this.limbs + i) & -*(this.limbs + i)) + (i << 6L);
+ size_t i = *(this.first) - 1;
+ return (ssize_t)(lb(*(this.limbs + i) & -*(this.limbs + i)) + (i << 6L));
}
@@ -747,9 +714,9 @@ ssize_t BitSet_any(BitSet this)
* @param value The integer whose logarithm to calculate
* @return The floored binary logarithm of the integer
*/
-ssize_t lb(llong value)
+size_t lb(llong value)
{
- ssize_t rc = 0;
+ size_t rc = 0;
llong v = value;
if (v & (int_fast64_t)0xFFFFFFFF00000000LL) { rc |= 32L; v >>= 32LL; }