I have written a generic code for implementing a Tournament with c language. i have written all the documentation with Doxygen standard and kept it in header file, also I have written a unit test with CUnit framework. I am attaching all the files below.
tournament.h
/**
* @file tournament.h
* @author praveen kumar
* @date 26 sept 2017
* @brief Tournament Data Structure.
*
* The data structure Tournament, as the name signifies, is a knock out tournament
* of objects/elements of same data type where it is characterized by rounds. every
* round, except the last one where we are left with the winner only, consist of set of
* objects. only the winners from the previous round proceed in the next round.<br>
* <br>
* The library is flexible to be used for any data type and have several of functions for
* manipulating the tournament.for the matter of usecase, the first call to a
* function (during using this structure) must be a #newTournament and must end
* with a call to #finishTournament, failing to do so may result in inconsistency or
* memory leak.
*/
#ifndef _tournament_h
#define _tournament_h
/**
* @brief Abstract data type for a Tournament data structure.
*
* typedef-ed for a pointer to a internally maintained structure for the tournament.
*/
typedef struct tournament *Tournament;
struct tournament {
struct tournam *tourn;
void *temp;
};
/**
* @brief Constructor for dynamically allocating a space for the Tournament.
*
* @param sizeofPlayer Size of the player(in bytes) or the object taking part in a
* tournament. @c sizeof operator can be useful here for determining
* the size of the object in bytes.
* @param noOfPlayers Total no of players or objects taking part in the Tournament in the
initial phase.
* @return Tournament Immutable Pointer to a allocated space for the tournament to take place
* or @c NULL if the request for allocation fails.
*
* @note Its an error (Dereferencing the incomplete type) if the pointer
* returned by this function is dereferenced, there are getters provided by this library
* in order to fetch any attribute if needed.
*/
extern Tournament newTournament(size_t sizeofPlayer, uint32_t noOfPlayers);
/**
* @brief Starts the Tournament.
*
* The tournament starts with the players or objects residing in the memory pointed by @p base
* where a policy for win or loose between players is decided by the @p comp. Call to this function
* guarantee the completion of all the rounds to be held(depending on the no of players participating).
* @param tour Pointer to a space allocated for tournament to be held, this pointer must be the one
* returned by #newTournament.
* @param base Pointer to a memory holding the players/elements taking part in the tournament.
* @param comp pointer to a comparator function for evaluating a loss or win among players.
* @return Tournament a pointer to a memory holding the tournament structure after completion of rounds
* or @c NULL if either of the parameter passed is @c NULL.
*/
extern Tournament setupTour(Tournament tour, void *base,
int (*comp)(const void *, const void *));
/**
* @brief Useful for viewing the winner of the Tournament @p tour.
*
* The function returns a flexible pointer, so its the responsibility of the user of this library to
* correctly cast the result. For the consistent result the type of the cast must be the type of the
* players pointed by @p base, which is passed as a parameter in #setupTour.
* @param tour Tournament for which the winner is to be evaluated.
* @return void* pointer to a winner and @c NULL if @p tour is @c NULL.
* @note Their is not any effect of changing the value(through dereferencing) in the memory pointed by
* the pointer returned here on the actual data structure, however changing the value is not
* accompanied.
*/
extern void *getWinner(Tournament tour);
/**
* @brief Useful for viewing the Next winner of the Tournament @p tour.
*
* Please note the next winner can be different from a runner up. next winner means that this
* element will loose to the winner only and win against all the other tournament players. since this
* element might have loose to the winner in the initial rounds their is a good possibility for be it
* the runner up.<br>
* The function returns a flexible pointer, so its the responsibility of the user of this library to
* correctly cast the result. For the consistent result the type of the cast must be the type of the
* players pointed by @p base, which is passed as a parameter in #setupTour.
* @param tour Tournament for which the winner is to be evaluated.
* @return void* pointer to a next winner and @c NULL if @p tour is @c NULL.
* @note Their is not any effect of changing the value(through dereferencing) in the memory pointed by
* the pointer returned here on the actual data structure, however changing the value is not
* accompanied.
*/
extern void *getNextWinner(Tournament tour);
/**
* @brief Useful for viewing the element at arbitrary position in a Tournament.
* The function returns a flexible pointer, so its the responsibility of the user of this library to
* correctly cast the result. For the consistent result the type of the cast must be the type of the
* players pointed by @p base, which is passed as a parameter in #setupTour.
* @param tour Tournament for which the element is to be evaluated.
* @param i index of the element in the tournament, which conventionally starts from @c 0 and must end
* at a value <tt>2 * getNoOfPlayers(tour) - 2</tt>.
* @return void* pointer to a element at index @c i or @c NULL if @p tour is @c NULL
* @note Their is not any effect of changing the value(through dereferencing) in the memory pointed by
* the pointer returned here on the actual data structure, however changing the value is not
* accompanied.
*/
extern void *getElemAt(Tournament tour, uint16_t i);
/**
* Useful for evaluating total no of objects or players who had participated in the initial phase of
* tournament(i.e.. round one).
* @param tour where the players or objects have participated.
* @return int the total no of players participating in the tournament @c tour or @c -1 if the @c tour
* is @c NULL.
*/
extern int getNoOfPlayers(Tournament tour);
/**
* @brief Prints the complete tournament in the sequence from winner to the initial phase i.e.. round one.
*
* The total no of elements printed are one less than the twice of the initial no of players or elements in
* the tournament in the initial phase. if we see the view of this printing round wise then it depends upon
* either the initial no of players are either odd or even. we will start from end. lets see the example:
* @verbatim CASE: Even
* Lets suppose we have an array of integers as {8, 7, 15, 1, 6, 9, 4, 3} then the play
* begins from end i.e.. 3 and 4 will be paired to play, 9 and 6 will be paired to play
* and so on, our comparator is the max of 2 values. the winners will proceed in round
* two according to the comparator and are put in front of the round 1 elements,
* as shown below:
* {8, 15, 9, 4, 8, 7, 15, 1, 6, 9, 4, 3}, here {8, 15, 9, 4} are round 2 elements
* the same process will continue among round two elements to get to round Three and so on.
* finally we will be left with the single element which is the winner and the complete
* structure looks as:
* {15, 15, 9, 8, 15, 9, 4, 8, 7, 15, 1, 6, 9, 4, 3} 15 is the winner.
CASE: odd
* This time take the example: {8, 7, 15, 1, 6, 9, 4}
* we will proceed in the same way as we do earlier, only the difference is we are left
* with 1 element in round 1 having not any pair, so this element will be moved to round
* two without any comparison and the view looks as:
* {15, 6, 9, 8, 7, 15, 1, 6, 9, 4}
* please note 8 is not put twice and is shared among round one and two for the view purpose
* and so we will move further as we did. finally complete structure looks as:
* {15, 15, 9, 15, 6, 9, 8, 7, 15, 1, 6, 9, 4} 15 is the winner.@endverbatim
* @param tour tournament to be printed.
* @param toString pointer to a function providing the string(of characters) view of the player.
* @param buffer pointer to a memory that will hold the string representation of player returned by @p toString
* @return void
*
*/
extern void printTour(Tournament tour, char *(*toString)(const void *elem,
char *buffer), char *buffer);
/**
* @brief Clears all the memory owned by this library.
*
* This must be a last function called during utilising this library.
* @param tour tournament to be freed. their is no effect if @c NULL is passed as parameters.
* @return void
* @note @p tour must be a pointer returned by the call to #newTournament.
* if this function is called twice on the same Tournament then their is a chance of
* inconsistency for the underlying program and it may crash.
*/
extern void finishTournament(Tournament tour);
#endif
tournament.c
#include <stdio.h>
#include <stdlib.h>
#include "headers/tournament.h"
struct tournam {
uint32_t size;
size_t sizeofPlayer;
void *tourTree;
};
static int (*compa)(const void *, const void *);
static Tournament play(Tournament tour,
int (*comp)(const void *, const void *));
static void setElemAt(Tournament tour, uint16_t i);
Tournament newTournament(size_t sizeofPlayer, uint32_t noOfPlayers) {
if (sizeofPlayer == 0 || noOfPlayers == 0) {
return NULL;
}
Tournament tour = (struct tournament *) malloc(sizeof(struct tournament));
tour->temp = malloc(sizeofPlayer);
tour->tourn = (struct tournam *) malloc(sizeof(struct tournam));
tour->tourn->tourTree = malloc((2 * noOfPlayers - 1) * sizeofPlayer);
if (tour == NULL || tour->tourn == NULL || tour->temp == NULL
|| tour->tourn->tourTree == NULL) {
return NULL;
}
tour->tourn->size = noOfPlayers;
tour->tourn->sizeofPlayer = sizeofPlayer;
return tour;
}
Tournament setupTour(Tournament tour, void *base,
int (*comp)(const void *, const void *)) {
if (tour == NULL || base == NULL
|| comp == NULL) return NULL;
compa = comp;
uint32_t i;
char *_base = (char *) base;
char * _tourTree = (char *) (tour->tourn->tourTree);
_tourTree = _tourTree + ((tour->tourn->size - 1) * tour->tourn->sizeofPlayer);
for (i = 0; i < tour->tourn->size * tour->tourn->sizeofPlayer; i++) {
*_tourTree++ = *_base++;
}
tour = play(tour, comp);
return tour;
}
static Tournament play(Tournament tour,
int (*comp)(const void *, const void *)) {
for (uint32_t i = 2 * tour->tourn->size - 2; i > 0; i = i - 2) {
char *j, *k;
char *p;
j = ((char *)(tour->tourn->tourTree) + (i * tour->tourn->sizeofPlayer));
k = ((char *)(tour->tourn->tourTree) + ((i - 1) * tour->tourn->sizeofPlayer));
p = ((char *)(tour->tourn->tourTree) + (((i * tour->tourn->sizeofPlayer) / 2) -
tour->tourn->sizeofPlayer));
if ((*comp)(j, k) > 0) {
for (uint32_t h = 0; h < tour->tourn->sizeofPlayer; h++) {
*(p + h) = *(j + h);
}
} else {
for (uint32_t h = 0; h < tour->tourn->sizeofPlayer; h++) {
*(p + h) = *(k + h);
}
}
}
return tour;
}
static void setElemAt(Tournament tour, uint16_t i) {
char *p = ((char *) tour->tourn->tourTree) + i * tour->tourn->sizeofPlayer;
for (uint16_t j = 0; j < tour->tourn->sizeofPlayer; j++) {
*(((char *) tour->temp) + j) = *(p + j);
}
return;
}
static void setNextWinner(Tournament tour) {
char *next, *i, *j;
i = ((char *) tour->tourn->tourTree) + tour->tourn->sizeofPlayer;
j = i + tour->tourn->sizeofPlayer;
if ((*compa)((void *)i, (void *)j) > 0) {
next = j;
} else {
next = i;
i = j;
}
char *k = ((char *)tour->tourn->tourTree) + ((2 * tour->tourn->size - 2) *
tour->tourn->sizeofPlayer);
while (1) {
if ((i = i + 2 * tour->tourn->sizeofPlayer) > k) break;
if ((*compa)(tour->tourn->tourTree, (void *)i) > 0) {
if ((*compa)((void *)i, (void *)next) > 0) {
next = (void *) i;
}
} else {
i = i + tour->tourn->sizeofPlayer;
if (i > k) break;
if ((*compa)((void *)i, next) > 0) {
next = (void *) i;
}
}
}
for (uint16_t m = 0; m < tour->tourn->sizeofPlayer; m++) {
*(((char *) tour->temp) + m) = *(next + m);
}
return;
}
int getNoOfPlayers(Tournament tour) {
if (tour == NULL) return -1;
else
return tour->tourn->size;
}
void *getWinner(Tournament tour) {
if (tour == NULL) {
return NULL;
}
setElemAt(tour, 0);
return tour->temp;
}
void *getNextWinner(Tournament tour) {
if (tour == NULL || tour->tourn->size <= 1 || compa == NULL) {
return NULL;
}
setNextWinner(tour);
return tour->temp;
}
void *getElemAt(Tournament tour, uint16_t i) {
if (tour == NULL || i >= 2 * tour->tourn->size - 1) {
return NULL;
}
setElemAt(tour, i);
return tour->temp;
}
void printTour(Tournament tour, char *(*toString)(const void *elem,
char *buffer), char *buffer) {
if (tour == NULL || toString == NULL || buffer == NULL) {
printf("EMPTY TOURNAMENT\n");
return;
}
uint32_t i;
for (i = 0; i < 2 * tour->tourn->size - 1; i++) {
printf("%s ", (*toString)((char *)(tour->tourn->tourTree) +
(i * tour->tourn->sizeofPlayer),
buffer));
}
printf("\n");
return;
}
void finishTournament(Tournament tour) {
if (tour == NULL) return;
free(tour->tourn->tourTree);
free(tour->tourn);
free(tour->temp);
free(tour);
return;
}
Unit test with CUnit
#include <stdio.h>
#include "headers/tournament.h"
#include <CUnit/Basic.h>
#include <string.h>
#define SIZE1 sizeof(int)
#define NPLAYERS1 0
#define WINNER1 NULL
#define NEXT_WINNER_NULL NULL
#define NPLAYERS2 2
#define WINNER2 8
#define NEXTWINNER2 7
#define NPLAYERS3 1
#define WINNER3 8
#define NPLAYERS4 8
#define WINNER4 15
#define NEXTWINNER4 9
#define NPLAYERS5 9
#define WINNER5 -4
#define NEXTWINNER5 -10
#define NPLAYERS6 9
#define WINNER6 -4
#define NEXTWINNER6 5
#define SIZE2 sizeof(char *)
#define NPLAYERS7 6
#define WINNER7 "WORLD"
#define NEXTWINNER7 "UNITTESTING"
#define SIZE3 sizeof(struct userType)
#define NPLAYERS8 6
static Tournament tour1 = NULL;
static void *base1 = NULL ;
static Tournament tour2 = NULL;
static int base2[] = {8, 7} ;
static int tournament2[] = {8, 8, 7};
static Tournament tour3 = NULL;
static int base3[] = {8};
static int tournament3[] = {8};
static Tournament tour4 = NULL;
static int base4[] = {8, 7, 15, 1, 6, 9, 4, 3} ;
static int tournament4[] = {15, 15, 9, 8, 15, 9, 4, 8, 7, 15, 1, 6, 9, 4, 3};
static Tournament tour5 = NULL;
static int base5[] = {-4, -12, -11, -16, -17, -10, -20, -108, -201};
static int tournament5[] = {-4, -4, -10, -4, -11, -16, -10, -108, -4, -12, -11, -16, -17, -10, -20, -108, -201};
static Tournament tour6 = NULL;
static int base6[] = {-4, 5, 7, 8, 9, 10, 18, 101, 786};
static int tournament6[] = {-4, -4, 8, -4, 5, 8, 10, 101, -4, 5, 7, 8, 9, 10, 18, 101, 786};
static Tournament tour7 = NULL;
static char *base7[] = {"HELLO", "WORLD", "ONE", "TWO", "TOURNAMENT", "UNITTESTING"};
static char *tournament7[] = {"WORLD", "UNITTESTING", "WORLD", "TWO", "UNITTESTING", "HELLO", "WORLD", "ONE", "TWO", "TOURNAMENT", "UNITTESTING"};
typedef struct userType {
char name[10];
int id;
} UserType;
const struct userType WINNER8 = {.name = "C#", .id = 1244};
const struct userType NEXTWINNER8 = {.name = "java", .id = 1239};
static Tournament tour8 = NULL;
static UserType base8[] = {
{.name = "C language", .id = 1234},
{.name = "C++", .id = 1235},
{.name = "java", .id = 1239},
{.name = "python", .id = 1237},
{.name = "Lua", .id = 1236},
{.name = "C#", .id = 1244}
};
static UserType tournament8[] = {
{.name = "C#", .id = 1244},
{.name = "C#", .id = 1244},
{.name = "C++", .id = 1235},
{.name = "java", .id = 1239},
{.name = "C#", .id = 1244},
{.name = "C language", .id = 1234},
{.name = "C++", .id = 1235},
{.name = "java", .id = 1239},
{.name = "python", .id = 1237},
{.name = "Lua", .id = 1236},
{.name = "C#", .id = 1244}
};
int init_suite1(void) {
if ((tour1 = newTournament(SIZE1, NPLAYERS1)) != NULL
|| (tour2 = newTournament(SIZE1, NPLAYERS2)) == NULL
|| (tour3 = newTournament(SIZE1, NPLAYERS3)) == NULL
|| (tour4 = newTournament(SIZE1, NPLAYERS4)) == NULL
|| (tour5 = newTournament(SIZE1, NPLAYERS5)) == NULL) {
return -1;
} else {
return 0;
}
}
int init_suite2(void) {
if ((tour6 = newTournament(SIZE1, NPLAYERS6)) == NULL) {
return -1;
} else {
return 0;
}
}
int init_suite3(void) {
if ((tour7 = newTournament(SIZE2, NPLAYERS7))) {
return -1;
} else {
return 0;
}
}
int init_suite4(void) {
if ((tour8 = newTournament(SIZE3, NPLAYERS8)) == NULL) {
return -1;
} else {
return 0;
}
}
int clean_suite1(void) {
finishTournament(tour1);
finishTournament(tour2);
finishTournament(tour3);
finishTournament(tour4);
finishTournament(tour5);
return 0;
}
int clean_suite2(void) {
finishTournament(tour6);
return 0;
}
int clean_suite3(void) {
finishTournament(tour7);
return 0;
}
int clean_suite4(void) {
finishTournament(tour8);
return 0;
}
int comp_max(const void *a, const void *b) {
return *((int *)a) > *((int *)b) ? 1 : 0;
}
int comp_min(const void *a, const void *b) {
return *((int *)a) < *((int *)b) ? 1 : 0;
}
int comp_str(const void *a, const void *b) {
return strcmp(*((char **)a), *((char **)b));
}
int comp_usert(const void *a, const void *b) {
return ((struct userType *)a)->id > ((struct userType *)b)->id;
}
static int usert_equals(const struct userType a, const struct userType b) {
return (strcmp(a.name, b.name) == 0 && a.id == b.id);
}
void testSetupTour(void) {
tour1 = setupTour(tour1, base1, comp_max);
CU_ASSERT_PTR_EQUAL(NULL, tour1);
tour1 = setupTour(tour1, base1, NULL);
CU_ASSERT_PTR_EQUAL(NULL, tour1);
tour2 = setupTour(tour2, base2, comp_max);
if (tour2 != NULL) {
for (uint16_t i = 0; i < 2 * NPLAYERS2 - 1; i++) {
CU_ASSERT(tournament2[i] == *((int *) getElemAt(tour2, i)));
}
}
tour3 = setupTour(tour3, base3, comp_max);
if (tour3 != NULL) {
for (uint16_t i = 0; i < 2 * NPLAYERS3 - 1; i++) {
CU_ASSERT(tournament3[i] == *((int *) getElemAt(tour3, i)));
}
}
tour4 = setupTour(tour4, base4, comp_max);
if (tour4 != NULL) {
for (uint16_t i = 0; i < 2 * NPLAYERS4 - 1; i++) {
CU_ASSERT(tournament4[i] == *((int *) getElemAt(tour4, i)));
}
}
tour5 = setupTour(tour5, base5, comp_max);
if (tour5 != NULL) {
for (uint16_t i = 0; i < 2 * NPLAYERS5 - 1; i++) {
CU_ASSERT(tournament5[i] == *((int *) getElemAt(tour5, i)));
}
}
}
void testSetupTour2(void) {
tour6 = setupTour(tour6, base6, comp_min);
if (tour6 != NULL) {
for (uint16_t i = 0; i < 2 * NPLAYERS6 - 1; i++) {
CU_ASSERT(tournament6[i] == *((int *) getElemAt(tour6, i)));
}
}
}
void testSetupTour3(void) {
tour7 = setupTour(tour7, base7, comp_str);
if (tour7 != NULL) {
for (uint16_t i = 0; i < 2 * NPLAYERS7 - 1; i++) {
CU_ASSERT_STRING_EQUAL(tournament7[i], *((char **) getElemAt(tour7, i)));
}
}
}
void testSetupTour4(void) {
tour8 = setupTour(tour8, base8, comp_usert);
if (tour8 != NULL) {
for (uint16_t i = 0; i < 2 * NPLAYERS8 - 1; i++) {
CU_ASSERT(usert_equals(tournament8[i], *((struct userType *) getElemAt(tour8,
i))));
}
}
}
void testgetWinner(void) {
CU_ASSERT_PTR_EQUAL(WINNER1, (int *) getWinner(tour1));
CU_ASSERT(WINNER2 == *((int *)getWinner(tour2)));
CU_ASSERT(WINNER3 == *((int *)getWinner(tour3)));
CU_ASSERT(WINNER4 == *((int *)getWinner(tour4)));
CU_ASSERT(WINNER5 == *((int *)getWinner(tour5)));
}
void testgetWinner2(void) {
CU_ASSERT(WINNER6 == *((int *)getWinner(tour6)));
}
void testgetWinner3(void) {
CU_ASSERT_STRING_EQUAL(WINNER7, *((char **)getWinner(tour7)));
}
void testgetWinner4(void) {
CU_ASSERT(usert_equals(WINNER8, *((struct userType *)getWinner(tour8))));
}
void testgetNextWinner(void) {
CU_ASSERT_PTR_EQUAL(NEXT_WINNER_NULL, ((int *) getNextWinner(tour1)));
CU_ASSERT(NEXTWINNER2 == *((int *)getNextWinner(tour2)));
CU_ASSERT_PTR_EQUAL(NEXT_WINNER_NULL, ((int *) getNextWinner(tour3)));
CU_ASSERT(NEXTWINNER4 == *((int *)getNextWinner(tour4)));
CU_ASSERT(NEXTWINNER5 == *((int *)getNextWinner(tour5)));
}
void testgetNextWinner2(void) {
CU_ASSERT(NEXTWINNER6 == *((int *)getNextWinner(tour6)));
}
void testgetNextWinner3(void) {
CU_ASSERT_STRING_EQUAL(NEXTWINNER7, *((char **)getNextWinner(tour7)));
}
void testgetNextWinner4(void) {
CU_ASSERT(usert_equals(NEXTWINNER8, *((struct userType*)getNextWinner(tour8))));
}
int main() {
CU_pSuite pSuite1 = NULL;
CU_pSuite pSuite2 = NULL;
CU_pSuite pSuite3 = NULL;
CU_pSuite pSuite4 = NULL;
if (CUE_SUCCESS != CU_initialize_registry()) {
return CU_get_error();
}
pSuite1 = CU_add_suite("Suite1", init_suite1, clean_suite1);
pSuite2 = CU_add_suite("Suite2", init_suite2, clean_suite2);
pSuite3 = CU_add_suite("Suite3", init_suite3, clean_suite3);
pSuite4 = CU_add_suite("Suite4", init_suite4, clean_suite4);
if (pSuite1 == NULL || pSuite2 == NULL || pSuite3 == NULL || pSuite4 == NULL ) {
CU_cleanup_registry();
return CU_get_error();
}
if (NULL == CU_add_test(pSuite1, "test of setupTour()", testSetupTour)
|| NULL == CU_add_test(pSuite1, "test of getWinner()", testgetWinner)
|| NULL == CU_add_test(pSuite1, "test of getNextWinner()", testgetNextWinner)
|| NULL == CU_add_test(pSuite2, "test of setupTour()", testSetupTour2)
|| NULL == CU_add_test(pSuite2, "test of getWinner()", testgetWinner2)
|| NULL == CU_add_test(pSuite2, "test of getNextWinner()", testgetNextWinner2)
|| NULL == CU_add_test(pSuite3, "test of setupTour()", testSetupTour3)
|| NULL == CU_add_test(pSuite3, "test of getWinner()", testgetWinner3)
|| NULL == CU_add_test(pSuite3, "test of getNextWinner()", testgetNextWinner3)
|| NULL == CU_add_test(pSuite4, "test of setupTour()", testSetupTour4)
|| NULL == CU_add_test(pSuite4, "test of getWinner()", testgetWinner4)
|| NULL == CU_add_test(pSuite4, "test of getNextWinner()",
testgetNextWinner4)) {
CU_cleanup_registry();
return CU_get_error();
}
CU_basic_set_mode(CU_BRM_VERBOSE);
CU_basic_run_tests();
CU_cleanup_registry();
return CU_get_error();
}
Please share the improvements/optimizations related with design, algorithm, testing etc that to my code.
struct tournament { struct tournam *tourn; void *temp; };not needed intournament.h, justtournament.c\$\endgroup\$