/* AUTOMATICALLY GENERATED SOURCE FILE. DO NOT MODIFY. */ #include "test_auto.h" #include #define AUTOC_MIN(a,b) ((a) > (b) ? (b) : (a)) #define AUTOC_MAX(a,b) ((a) > (b) ? (a) : (b)) #define AUTOC_RCYCLE(x) (((x) << 1) | ((x) >> (sizeof(x)*CHAR_BIT - 1))) /* NOTE : valid for unsigned types only */ #include struct { int total, processed, failed; } tests; int failure; typedef void (*test_func)(void); void run_test(const char* name, test_func func) { fprintf(stdout, "| %s\n", name); fflush(stdout); failure = 0; func(); if(failure) tests.failed++; tests.processed++; } void print_condition_failure(const char* message, const char* condition, const char* file, int line) { fprintf(stderr, "*** %s : %s (%s:%d)\n", condition, message, file, line); fflush(stderr); failure = 1; } void print_equality_failure(const char* message, const char* x, const char* y, const char* file, int line) { fprintf(stderr, "*** %s == %s : %s (%s:%d)\n", x, y, message, file, line); fflush(stderr); failure = 1; } void print_summary(void) { if(tests.failed) fprintf(stdout, "*** Failed %d of %d tests\n", tests.failed, tests.processed); else fprintf(stdout, "+++ All %d tests passed successfully\n", tests.processed); fflush(stdout); } #define TEST_MESSAGE(s) fprintf(stderr, "*** %s\n", s); fflush(stderr); #define TEST_ASSERT(x) if(x) {} else print_condition_failure("evaluated to FALSE", #x, __FILE__, __LINE__) #define TEST_TRUE(x) if(x) {} else print_condition_failure("expected TRUE but got FALSE", #x, __FILE__, __LINE__) #define TEST_FALSE(x) if(x) print_condition_failure("expected FALSE but got TRUE", #x, __FILE__, __LINE__) #define TEST_NULL(x) if((x) == NULL) {} else print_condition_failure("expected NULL", #x, __FILE__, __LINE__) #define TEST_NOT_NULL(x) if((x) == NULL) print_condition_failure("expected not NULL", #x, __FILE__, __LINE__) #define TEST_EQUAL(x, y) if((x) == (y)) {} else print_equality_failure("expected equality", #x, #y, __FILE__, __LINE__) #define TEST_NOT_EQUAL(x, y) if((x) == (y)) print_equality_failure("expected non-equality", #x, #y, __FILE__, __LINE__) #define TEST_EQUAL_CHARS(x, y) if(strcmp(x, y) == 0) {} else print_equality_failure("expected strings equality", #x, #y, __FILE__, __LINE__) #define TEST_NOT_EQUAL_CHARS(x, y) if(strcmp(x, y) == 0) print_equality_failure("expected strings non-equality", #x, #y, __FILE__, __LINE__) #define _CharStringListCtor(self) CharStringListCtor(&self) #define _CharStringListDtor(self) CharStringListDtor(&self) #define _CharStringListIdentify(self) CharStringListIdentify(&self) #define _CharStringListCopy(dst,src) CharStringListCopy(&dst,&src) #define _CharStringListEqual(lt,rt) CharStringListEqual(<,&rt) #define _CharStringListLess(lt,rt) CharStringListLess(<,&rt) AUTOC_STATIC void CharStringListItCtor(CharStringListIt*, CharStringList*); AUTOC_STATIC int CharStringListItMove(CharStringListIt*); AUTOC_STATIC char* CharStringListItGet(CharStringListIt*); AUTOC_STATIC void CharStringListCtor(CharStringList*); AUTOC_STATIC void CharStringListDtor(CharStringList*); AUTOC_STATIC void CharStringListCopy(CharStringList*,CharStringList*); AUTOC_STATIC int CharStringListEqual(CharStringList*,CharStringList*); AUTOC_STATIC size_t CharStringListIdentify(CharStringList*); AUTOC_STATIC void CharStringListPurge(CharStringList*); AUTOC_STATIC char* CharStringListPeek(CharStringList*); AUTOC_STATIC char* CharStringListPop(CharStringList*); AUTOC_STATIC void CharStringListPush(CharStringList*, char*); AUTOC_STATIC int CharStringListContains(CharStringList*, char*); AUTOC_STATIC char* CharStringListFind(CharStringList*, char*); #define CharStringListReplace(self, with) CharStringListReplaceEx(self, with, 1) #define CharStringListReplaceAll(self, with) CharStringListReplaceEx(self, with, -1) AUTOC_STATIC int CharStringListReplaceEx(CharStringList*, char*, int); #define CharStringListRemove(self, what) CharStringListRemoveEx(self, what, 1) #define CharStringListRemoveAll(self, what) CharStringListRemoveEx(self, what, -1) AUTOC_STATIC int CharStringListRemoveEx(CharStringList*, char*, int); AUTOC_STATIC size_t CharStringListSize(CharStringList*); #define CharStringListEmpty(self) (CharStringListSize(self) == 0) static char** CharStringListItGetRef(CharStringListIt*); AUTOC_STATIC void CharStringListCtor(CharStringList* self) { assert(self); self->head_node = NULL; self->node_count = 0; } AUTOC_STATIC void CharStringListDtor(CharStringList* self) { CharStringListNode* node; assert(self); node = self->head_node; while(node) { CharStringListNode* this_node = node; node = node->next_node; free(this_node->element); free(this_node); } } AUTOC_STATIC void CharStringListCopy(CharStringList* dst,CharStringList* src) { CharStringListIt it; size_t index, size; char*** elements; assert(src); assert(dst); CharStringListCtor(dst); if(!CharStringListEmpty(src)) { /* List is a LIFO type container therefore the insertion order into the destination container should be reversed */ elements = (char***)malloc((size = CharStringListSize(src))*sizeof(char**)); assert(elements); index = 0; CharStringListItCtor(&it, src); while(CharStringListItMove(&it)) { assert(index < size); elements[index++] = CharStringListItGetRef(&it); } for(index = size; index > 0; --index) CharStringListPush(dst, *elements[index-1]); /* Be careful not to run into the underflow of the unsigned integer type */ free(elements); } } AUTOC_STATIC int CharStringListEqual(CharStringList* lt,CharStringList* rt) { if(CharStringListSize(lt) == CharStringListSize(rt)) { CharStringListIt lit, rit; CharStringListItCtor(&lit, lt); CharStringListItCtor(&rit, rt); while(CharStringListItMove(&lit) && CharStringListItMove(&rit)) { int equal; char** le; char** re; le = CharStringListItGetRef(&lit); re = CharStringListItGetRef(&rit); equal = ((*le) == (*re)); if(!equal) return 0; } return 1; } else return 0; } AUTOC_STATIC size_t CharStringListIdentify(CharStringList* self) { CharStringListNode* node; size_t result = 0; assert(self); for(node = self->head_node; node != NULL; node = node->next_node) { result ^= ((size_t)(node->element)); result = AUTOC_RCYCLE(result); } return result; } AUTOC_STATIC void CharStringListPurge(CharStringList* self) { CharStringListDtor(self); CharStringListCtor(self); } AUTOC_STATIC char* CharStringListPeek(CharStringList* self) { char* result; assert(self); assert(!CharStringListEmpty(self)); ((result) = (self->head_node->element)); return result; } AUTOC_STATIC char* CharStringListPop(CharStringList* self) { CharStringListNode* node; char* result; assert(self); assert(!CharStringListEmpty(self)); node = self->head_node; result = node->element; self->head_node = self->head_node->next_node; --self->node_count; free(node); return result; } AUTOC_STATIC void CharStringListPush(CharStringList* self, char* element) { CharStringListNode* node; assert(self); node = (CharStringListNode*)malloc(sizeof(CharStringListNode)); assert(node); ((node->element) = (element)); node->next_node = self->head_node; self->head_node = node; ++self->node_count; } AUTOC_STATIC int CharStringListContains(CharStringList* self, char* what) { CharStringListNode* node; int found = 0; assert(self); node = self->head_node; while(node) { if(((node->element) == (what))) { found = 1; break; } node = node->next_node; } return found; } AUTOC_STATIC char* CharStringListFind(CharStringList* self, char* what) { CharStringListNode* node; assert(self); assert(CharStringListContains(self, what)); node = self->head_node; while(node) { if(((node->element) == (what))) { char* result; ((result) = (node->element)); return result; } node = node->next_node; } abort(); } /* FIXME: for the generality's sake there should be both `what` and `with` values This is not achievable without breaking the interface, however, therefore defer this change to the major version bump */ AUTOC_STATIC int CharStringListReplaceEx(CharStringList* self, char* with, int count) { CharStringListNode* node; int replaced = 0; assert(self); if(count == 0) return 0; node = self->head_node; while(node) { if(((node->element) == (with))) { free(node->element); ((node->element) = (with)); ++replaced; if(count > 0 && replaced >= count) break; } node = node->next_node; } return replaced; } AUTOC_STATIC int CharStringListRemoveEx(CharStringList* self, char* what, int count) { CharStringListNode *node, *prev_node; int removed = 0; assert(self); if(count == 0) return 0; node = self->head_node; prev_node = NULL; while(node) { if(((node->element) == (what))) { CharStringListNode* this_node; if(prev_node) { this_node = prev_node->next_node = node->next_node; } else { this_node = self->head_node = node->next_node; } ++removed; --self->node_count; free(node->element); free(node); node = this_node; if(count > 0 && removed >= count) break; } else { prev_node = node; node = node->next_node; } } return removed; } AUTOC_STATIC size_t CharStringListSize(CharStringList* self) { assert(self); return self->node_count; } AUTOC_STATIC void CharStringListItCtor(CharStringListIt* self, CharStringList* list) { assert(self); assert(list); self->start = 1; self->list = list; } AUTOC_STATIC int CharStringListItMove(CharStringListIt* self) { assert(self); if(self->start) { self->this_node = self->list->head_node; self->start = 0; } else { self->this_node = self->this_node ? self->this_node->next_node : NULL; } return self->this_node != NULL; } AUTOC_STATIC char* CharStringListItGet(CharStringListIt* self) { char* result; assert(self); assert(self->this_node); ((result) = (self->this_node->element)); return result; } static char** CharStringListItGetRef(CharStringListIt* self) { assert(self); assert(self->this_node); return &self->this_node->element; } #include #include #undef AUTOC_VSNPRINTF #if defined(_MSC_VER) #define AUTOC_VSNPRINTF _vsnprintf #elif defined(__DMC__) || defined (__LCC__) #define AUTOC_VSNPRINTF vsnprintf #elif defined(HAVE_VSNPRINTF) || __STDC_VERSION__ >= 199901L /* Be Autotools-friendly, C99 must have snprintf() */ #define AUTOC_VSNPRINTF vsnprintf #endif #ifndef AUTOC_VSNPRINTF /* #warning Using unsafe vsprintf() function */ #endif void _CharStringJoin(CharString* self) { CharStringListIt it; char* string; size_t* size; /* size sizes cache to avoid excessive calls to strlen() */ size_t i, start = 0, total = 0; assert(self); assert(self->is_list); if(!CharStringListEmpty(&self->data.list)) { size = (size_t*)malloc(CharStringListSize(&self->data.list)*sizeof(size_t)); assert(size); CharStringListItCtor(&it, &self->data.list); for(i = 0; CharStringListItMove(&it); ++i) { total += (size[i] = strlen(CharStringListItGet(&it))); } string = (char*)malloc((total + 1)*sizeof(char)); assert(string); CharStringListItCtor(&it, &self->data.list); /* List is a LIFO structure therefore merging should be performed from right to left */ i = 0; start = total; while(CharStringListItMove(&it)) { start -= size[i]; memcpy(&string[start], CharStringListItGet(&it), size[i]*sizeof(char)); ++i; } string[total] = '\0'; free(size); } else { string = (char*)calloc(1, sizeof(char)); assert(string); } CharStringListDtor(&self->data.list); self->size = total; self->data.string = string; self->is_list = 0; } void _CharStringSplit(CharString* self) { CharStringList list; assert(self); assert(!self->is_list); CharStringListCtor(&list); CharStringListPush(&list, self->data.string); /* self->size = strlen(self->data.string); not needed since the size shouldn't have changed */ assert(self->size == strlen(self->data.string)); self->data.list = list; self->is_list = 1; } void CharStringCtor(CharString* self,const char* chars) { assert(self); if(chars) { size_t nbytes; self->size = strlen(chars); nbytes = (self->size + 1)*sizeof(char); self->data.string = (char*)malloc(nbytes); assert(self->data.string); memcpy(self->data.string, chars, nbytes); self->is_list = 0; } else { /* NULL argument is permitted and corresponds to empty string */ self->size = 0; CharStringListCtor(&self->data.list); self->is_list = 1; } } void CharStringDtor(CharString* self) { assert(self); if(self->is_list) CharStringListDtor(&self->data.list); else free(self->data.string); } void CharStringCopy(CharString* dst,CharString* src) { assert(src); assert(dst); assert(src != dst); CharStringCtor(dst, CharStringChars(src)); } void CharStringCopyRange(CharString* dst, CharString* src, size_t first, size_t last) { size_t size; char* string; assert(src); assert(src != dst); assert(first <= last); assert(CharStringWithin(src, first)); assert(CharStringWithin(src, last)); size = last - first + 1; string = (char*)malloc((size + 1)*sizeof(char)); assert(string); memcpy(string, &CharStringChars(src)[first], size*sizeof(char)); string[size] = '\0'; CharStringCtor(dst, string); free(string); } int CharStringEqual(CharString* lt,CharString* rt) { assert(lt); assert(rt); return strcmp(CharStringChars(lt), CharStringChars(rt)) == 0; } size_t CharStringIdentify(CharString* self) { size_t index, result = 0; assert(self); CharStringJoin(self); for(index = 0; index < CharStringSize(self); ++index) { result ^= self->data.string[index]; result = AUTOC_RCYCLE(result); } return result; } int CharStringPushFormat(CharString* self, const char* format, ...) { va_list args; char* buffer; int i, c, buffer_size = _CharStringBufferSize; assert(self); assert(format); do { buffer = (char*)malloc(buffer_size*sizeof(char)); assert(buffer); va_start(args, format); #ifdef AUTOC_VSNPRINTF i = AUTOC_VSNPRINTF(buffer, buffer_size, format, args); #else i = vsprintf(buffer, format, args); if(i >= buffer_size) abort(); /* Since vsprintf() can not truncate its output this means the buffer overflow and there is no guarantee that some useful data is not corrupted so its better to crash right here than to let the corruption slip away uncaught */ #endif c = (i > 0 && !(i < buffer_size)); if(i > 0 && !c) CharStringPushChars(self, buffer); va_end(args); free(buffer); buffer_size *= 2; } while(c); return i >= 0; } void CharStringPushChars(CharString* self, const char* chars) { char* string; size_t size, nbytes; assert(self); assert(chars); CharStringSplit(self); size = strlen(chars); nbytes = (size + 1)*sizeof(char); string = (char*)malloc(nbytes); assert(string); memcpy(string, chars, nbytes); CharStringListPush(&self->data.list, string); self->size += size; } void CharStringPushString(CharString* self, CharString* from) { assert(self); assert(from); CharStringPushChars(self, CharStringChars(from)); } #undef AUTOC_SNPRINTF void CharStringTestCreate(void) { CharString t; CharStringCtor(&t, "XYZ"); CharStringDtor(&t); } void CharStringTestCreateWithNULL(void) { CharString t; CharStringCtor(&t, NULL); TEST_TRUE( CharStringEmpty(&t) ); CharStringDtor(&t); } void CharStringTestCreateWithEmptyChars(void) { CharString t; CharStringCtor(&t, ""); TEST_TRUE( CharStringEmpty(&t) ); CharStringDtor(&t); } void CharStringTestHash(void) { CharString t; CharStringCtor(&t, "XYZ"); CharStringIdentify(&t); CharStringDtor(&t); } void CharStringTestWithin(void) { CharString t; CharStringCtor(&t, "XYZ"); TEST_FALSE( CharStringEmpty(&t) ); TEST_TRUE( CharStringWithin(&t, 0) ); TEST_TRUE( CharStringWithin(&t, 2) ); TEST_FALSE( CharStringWithin(&t, 3) ); CharStringDtor(&t); } void CharStringTestWithinNULLString(void) { CharString t; CharStringCtor(&t, NULL); TEST_TRUE( CharStringEmpty(&t) ); TEST_FALSE( CharStringWithin(&t, 0) ); TEST_FALSE( CharStringWithin(&t, 1) ); CharStringDtor(&t); } void CharStringTestWithinEmptyString(void) { CharString t; CharStringCtor(&t, ""); TEST_TRUE( CharStringEmpty(&t) ); TEST_FALSE( CharStringWithin(&t, 0) ); TEST_FALSE( CharStringWithin(&t, 1) ); CharStringDtor(&t); } void CharStringTestStringSize(void) { CharString t; CharStringCtor(&t, "XYZ"); TEST_EQUAL( CharStringSize(&t), 3 ); CharStringDtor(&t); } void CharStringTestEmptyStringSize(void) { CharString t; CharStringCtor(&t, ""); TEST_TRUE( CharStringEmpty(&t) ); TEST_EQUAL( CharStringSize(&t), 0 ); CharStringDtor(&t); } void CharStringTestNULLStringSize(void) { CharString t; CharStringCtor(&t, NULL); TEST_TRUE( CharStringEmpty(&t) ); TEST_EQUAL( CharStringSize(&t), 0 ); CharStringDtor(&t); } void CharStringTestChars(void) { CharString t; CharStringCtor(&t, "XYZ"); TEST_EQUAL_CHARS( CharStringChars(&t), "XYZ" ); TEST_NOT_EQUAL_CHARS( CharStringChars(&t), "xyz" ); CharStringDtor(&t); } void CharStringTestGetChar(void) { CharString t; CharStringCtor(&t, "XYZ"); TEST_EQUAL( CharStringGet(&t, 2), 'Z' ); CharStringDtor(&t); } void CharStringTestSetChar(void) { CharString t; CharStringCtor(&t, "XYZ"); TEST_NOT_EQUAL( CharStringGet(&t, 0), 'x' ); CharStringSet(&t, 0, 'x'); TEST_EQUAL( CharStringGet(&t, 0), 'x' ); CharStringDtor(&t); } void CharStringTestPushChars(void) { CharString t; CharStringCtor(&t, "X"); CharStringPushChars(&t, "Y"); CharStringPushChars(&t, "Z"); TEST_EQUAL_CHARS( CharStringChars(&t), "XYZ" ); CharStringDtor(&t); } void CharStringTestPushEmptyChars(void) { CharString t; CharStringCtor(&t, "XYZ"); CharStringPushChars(&t, ""); TEST_EQUAL_CHARS( CharStringChars(&t), "XYZ" ); CharStringDtor(&t); } void CharStringTestPushCharsToNULL(void) { CharString t; CharStringCtor(&t, NULL); CharStringPushChars(&t, "XY"); CharStringPushChars(&t, "Z"); TEST_EQUAL_CHARS( CharStringChars(&t), "XYZ" ); CharStringDtor(&t); } void CharStringTestPushCharsToEmpty(void) { CharString t; CharStringCtor(&t, ""); CharStringPushChars(&t, "X"); CharStringPushChars(&t, "YZ"); TEST_EQUAL_CHARS( CharStringChars(&t), "XYZ" ); CharStringDtor(&t); } void CharStringTestPushString(void) { CharString t; CharString s; CharStringCtor(&s, "YZ"); CharStringCtor(&t, "X"); CharStringPushString(&t, &s); TEST_EQUAL_CHARS( CharStringChars(&t), "XYZ" ); CharStringDtor(&s); CharStringDtor(&t); } void CharStringTestPushChar(void) { CharString t; CharStringCtor(&t, "XY"); CharStringPushChar(&t, 'Z'); TEST_EQUAL_CHARS( CharStringChars(&t), "XYZ" ); CharStringDtor(&t); } void CharStringTestPushInt(void) { CharString t; CharStringCtor(&t, "XYZ"); CharStringPushInt(&t, -123); TEST_EQUAL_CHARS( CharStringChars(&t), "XYZ-123" ); CharStringDtor(&t); } void CharStringTestPushFloat(void) { CharString t; CharStringCtor(&t, "XYZ"); CharStringPushFloat(&t, -1.23); CharStringDtor(&t); } void CharStringTestPushPtr(void) { CharString t; CharStringCtor(&t, "XYZ"); CharStringPushPtr(&t, &t); CharStringDtor(&t); } void CharStringTestPushNULLPtr(void) { CharString t; CharStringCtor(&t, "XYZ"); CharStringPushPtr(&t, NULL); CharStringDtor(&t); } void CharStringTestPushFormat(void) { CharString t; CharStringCtor(&t, NULL); CharStringPushFormat(&t, "%s%c%d", "XY", 'Z', -123); TEST_EQUAL_CHARS( CharStringChars(&t), "XYZ-123" ); CharStringDtor(&t); } void CharStringTestPushFormatExactBuffer(void) { CharString t; char* b = malloc(_CharStringBufferSize*sizeof(char)); assert(b); memset(b, '*', _CharStringBufferSize); b[_CharStringBufferSize-1] = '\0'; CharStringCtor(&t, NULL); CharStringPushFormat(&t, "%s", b); TEST_EQUAL_CHARS( CharStringChars(&t), b ); free(b); CharStringDtor(&t); } void CharStringTestPushFormatOverBuffer(void) { CharString t; char* b = malloc(_CharStringBufferSize*sizeof(char)); assert(b); memset(b, '*', _CharStringBufferSize); b[_CharStringBufferSize-1] = '\0'; CharStringCtor(&t, "-"); #ifdef AUTOC_VSNPRINTF CharStringPushFormat(&t, "%s-", b); TEST_EQUAL(CharStringSize(&t), _CharStringBufferSize+1); #else TEST_MESSAGE("vsnprintf() is not used, skipping") #endif free(b); CharStringDtor(&t); } void CharStringTestIterateOverNULL(void) { CharString t; CharStringIt it; CharStringCtor(&t, NULL); CharStringItCtor(&it, &t); TEST_FALSE( CharStringItMove(&it) ); CharStringDtor(&t); } void CharStringTestIterateOverEmpty(void) { CharString t; CharStringIt it; CharStringCtor(&t, ""); CharStringItCtor(&it, &t); TEST_FALSE( CharStringItMove(&it) ); CharStringDtor(&t); } void CharStringTestIterateForward(void) { CharString t; CharStringIt it; CharStringCtor(&t, "XYZ"); CharStringItCtor(&it, &t); TEST_TRUE( CharStringItMove(&it) ); TEST_EQUAL( CharStringItGet(&it), 'X' ); TEST_TRUE( CharStringItMove(&it) ); TEST_EQUAL( CharStringItGet(&it), 'Y' ); TEST_TRUE( CharStringItMove(&it) ); TEST_EQUAL( CharStringItGet(&it), 'Z' ); TEST_FALSE( CharStringItMove(&it) ); CharStringDtor(&t); } void CharStringTestIterateBackward(void) { CharString t; CharStringIt it; CharStringCtor(&t, "ZYX"); CharStringItCtorEx(&it, &t, 0); TEST_TRUE( CharStringItMove(&it) ); TEST_EQUAL( CharStringItGet(&it), 'X' ); TEST_TRUE( CharStringItMove(&it) ); TEST_EQUAL( CharStringItGet(&it), 'Y' ); TEST_TRUE( CharStringItMove(&it) ); TEST_EQUAL( CharStringItGet(&it), 'Z' ); TEST_FALSE( CharStringItMove(&it) ); CharStringDtor(&t); } void CharStringTestCopy(void) { CharString t1, t2; CharStringCtor(&t1, "XYZ"); CharStringCopy(&t2, &t1); TEST_TRUE( CharStringEqual(&t1, &t2) ); CharStringDtor(&t1); CharStringDtor(&t2); } void CharStringTestCopyNULL(void) { CharString t1, t2; CharStringCtor(&t1, NULL); CharStringCopy(&t2, &t1); TEST_TRUE( CharStringEqual(&t1, &t2) ); CharStringDtor(&t1); CharStringDtor(&t2); } void CharStringTestCopyEmpty(void) { CharString t1, t2; CharStringCtor(&t1, ""); CharStringCopy(&t2, &t1); TEST_TRUE( CharStringEqual(&t1, &t2) ); CharStringDtor(&t1); CharStringDtor(&t2); } void CharStringTestCopyFullRange(void) { CharString t1, t2; CharStringCtor(&t1, "XYZ"); CharStringCopyRange(&t2, &t1, 0, 2); TEST_TRUE( CharStringEqual(&t1, &t2) ); CharStringDtor(&t1); CharStringDtor(&t2); } void CharStringTestCopyPartialRange(void) { CharString t1, t2; CharStringCtor(&t1, "_XYZ_"); CharStringCopyRange(&t2, &t1, 1, 3); TEST_EQUAL_CHARS( CharStringChars(&t2), "XYZ" ); CharStringDtor(&t1); CharStringDtor(&t2); } void CharStringTestCopySingleCharRange(void) { CharString t1, t2; CharStringCtor(&t1, "XYZ"); CharStringCopyRange(&t2, &t1, 1, 1); TEST_EQUAL_CHARS( CharStringChars(&t2), "Y" ); CharStringDtor(&t1); CharStringDtor(&t2); } void CharStringTestEqual(void) { CharString t1, t2; CharStringCtor(&t1, "XYZ"); CharStringCtor(&t2, "XYZ"); TEST_TRUE( CharStringEqual(&t1, &t2) ); CharStringDtor(&t1); CharStringDtor(&t2); } void CharStringTestNotEqual(void) { CharString t1, t2; CharStringCtor(&t1, "-XYZ"); CharStringCtor(&t2, "XYZ-"); TEST_FALSE( CharStringEqual(&t1, &t2) ); CharStringDtor(&t1); CharStringDtor(&t2); } void CharStringRunTests(void) { fprintf(stdout, "* %s\n", "CharString"); fflush(stdout); run_test("create", CharStringTestCreate); run_test("createWithNULL", CharStringTestCreateWithNULL); run_test("createWithEmptyChars", CharStringTestCreateWithEmptyChars); run_test("hash", CharStringTestHash); run_test("within", CharStringTestWithin); run_test("withinNULLString", CharStringTestWithinNULLString); run_test("withinEmptyString", CharStringTestWithinEmptyString); run_test("stringSize", CharStringTestStringSize); run_test("emptyStringSize", CharStringTestEmptyStringSize); run_test("NULLStringSize", CharStringTestNULLStringSize); run_test("chars", CharStringTestChars); run_test("getChar", CharStringTestGetChar); run_test("setChar", CharStringTestSetChar); run_test("pushChars", CharStringTestPushChars); run_test("pushEmptyChars", CharStringTestPushEmptyChars); run_test("pushCharsToNULL", CharStringTestPushCharsToNULL); run_test("pushCharsToEmpty", CharStringTestPushCharsToEmpty); run_test("pushString", CharStringTestPushString); run_test("pushChar", CharStringTestPushChar); run_test("pushInt", CharStringTestPushInt); run_test("pushFloat", CharStringTestPushFloat); run_test("pushPtr", CharStringTestPushPtr); run_test("pushNULLPtr", CharStringTestPushNULLPtr); run_test("pushFormat", CharStringTestPushFormat); run_test("pushFormatExactBuffer", CharStringTestPushFormatExactBuffer); run_test("pushFormatOverBuffer", CharStringTestPushFormatOverBuffer); run_test("iterateOverNULL", CharStringTestIterateOverNULL); run_test("iterateOverEmpty", CharStringTestIterateOverEmpty); run_test("iterateForward", CharStringTestIterateForward); run_test("iterateBackward", CharStringTestIterateBackward); run_test("copy", CharStringTestCopy); run_test("copyNULL", CharStringTestCopyNULL); run_test("copyEmpty", CharStringTestCopyEmpty); run_test("copyFullRange", CharStringTestCopyFullRange); run_test("copyPartialRange", CharStringTestCopyPartialRange); run_test("copySingleCharRange", CharStringTestCopySingleCharRange); run_test("equal", CharStringTestEqual); run_test("notEqual", CharStringTestNotEqual); fputs("\n", stdout); fflush(stdout); } void _ValueCtor(Value* self) { assert(self); self->value = calloc(1, sizeof(int)); assert(self->value); } void _ValueCtorEx(Value* self, int value) { assert(self); ValueCtor(*self); *self->value = value; } void _ValueDtor(Value* self) { assert(self); free(self->value); } void _ValueCopy(Value* dst, Value* src) { assert(src); assert(dst); assert(src->value); ValueCtorEx(*dst, *src->value); } int _ValueEqual(Value* lt, Value* rt) { assert(lt); assert(rt); assert(lt->value); assert(rt->value); return *lt->value == *rt->value; } int _ValueLess(Value* lt, Value* rt) { assert(lt); assert(rt); assert(lt->value); assert(rt->value); return *lt->value < *rt->value; } size_t _ValueIdentify(Value* self) { assert(self); assert(self->value); return *self->value ^ 0xAAAA; } static int* IntListItGetRef(IntListIt*); void IntListCtor(IntList* self) { assert(self); self->head_node = NULL; self->node_count = 0; } void IntListDtor(IntList* self) { IntListNode* node; assert(self); node = self->head_node; while(node) { IntListNode* this_node = node; node = node->next_node; ; free(this_node); } } void IntListCopy(IntList* dst,IntList* src) { IntListIt it; size_t index, size; int** elements; assert(src); assert(dst); IntListCtor(dst); if(!IntListEmpty(src)) { /* List is a LIFO type container therefore the insertion order into the destination container should be reversed */ elements = (int**)malloc((size = IntListSize(src))*sizeof(int*)); assert(elements); index = 0; IntListItCtor(&it, src); while(IntListItMove(&it)) { assert(index < size); elements[index++] = IntListItGetRef(&it); } for(index = size; index > 0; --index) IntListPush(dst, *elements[index-1]); /* Be careful not to run into the underflow of the unsigned integer type */ free(elements); } } int IntListEqual(IntList* lt,IntList* rt) { if(IntListSize(lt) == IntListSize(rt)) { IntListIt lit, rit; IntListItCtor(&lit, lt); IntListItCtor(&rit, rt); while(IntListItMove(&lit) && IntListItMove(&rit)) { int equal; int* le; int* re; le = IntListItGetRef(&lit); re = IntListItGetRef(&rit); equal = ((*le) == (*re)); if(!equal) return 0; } return 1; } else return 0; } size_t IntListIdentify(IntList* self) { IntListNode* node; size_t result = 0; assert(self); for(node = self->head_node; node != NULL; node = node->next_node) { result ^= ((size_t)(node->element)); result = AUTOC_RCYCLE(result); } return result; } void IntListPurge(IntList* self) { IntListDtor(self); IntListCtor(self); } int IntListPeek(IntList* self) { int result; assert(self); assert(!IntListEmpty(self)); ((result) = (self->head_node->element)); return result; } int IntListPop(IntList* self) { IntListNode* node; int result; assert(self); assert(!IntListEmpty(self)); node = self->head_node; result = node->element; self->head_node = self->head_node->next_node; --self->node_count; free(node); return result; } void IntListPush(IntList* self, int element) { IntListNode* node; assert(self); node = (IntListNode*)malloc(sizeof(IntListNode)); assert(node); ((node->element) = (element)); node->next_node = self->head_node; self->head_node = node; ++self->node_count; } int IntListContains(IntList* self, int what) { IntListNode* node; int found = 0; assert(self); node = self->head_node; while(node) { if(((node->element) == (what))) { found = 1; break; } node = node->next_node; } return found; } int IntListFind(IntList* self, int what) { IntListNode* node; assert(self); assert(IntListContains(self, what)); node = self->head_node; while(node) { if(((node->element) == (what))) { int result; ((result) = (node->element)); return result; } node = node->next_node; } abort(); } /* FIXME: for the generality's sake there should be both `what` and `with` values This is not achievable without breaking the interface, however, therefore defer this change to the major version bump */ int IntListReplaceEx(IntList* self, int with, int count) { IntListNode* node; int replaced = 0; assert(self); if(count == 0) return 0; node = self->head_node; while(node) { if(((node->element) == (with))) { ; ((node->element) = (with)); ++replaced; if(count > 0 && replaced >= count) break; } node = node->next_node; } return replaced; } int IntListRemoveEx(IntList* self, int what, int count) { IntListNode *node, *prev_node; int removed = 0; assert(self); if(count == 0) return 0; node = self->head_node; prev_node = NULL; while(node) { if(((node->element) == (what))) { IntListNode* this_node; if(prev_node) { this_node = prev_node->next_node = node->next_node; } else { this_node = self->head_node = node->next_node; } ++removed; --self->node_count; ; free(node); node = this_node; if(count > 0 && removed >= count) break; } else { prev_node = node; node = node->next_node; } } return removed; } size_t IntListSize(IntList* self) { assert(self); return self->node_count; } void IntListItCtor(IntListIt* self, IntList* list) { assert(self); assert(list); self->start = 1; self->list = list; } int IntListItMove(IntListIt* self) { assert(self); if(self->start) { self->this_node = self->list->head_node; self->start = 0; } else { self->this_node = self->this_node ? self->this_node->next_node : NULL; } return self->this_node != NULL; } int IntListItGet(IntListIt* self) { int result; assert(self); assert(self->this_node); ((result) = (self->this_node->element)); return result; } static int* IntListItGetRef(IntListIt* self) { assert(self); assert(self->this_node); return &self->this_node->element; } void IntListTestCreate(void) { IntList t; IntListCtor(&t); TEST_TRUE( IntListEmpty(&t) ); TEST_EQUAL( IntListSize(&t), 0 ); IntListDtor(&t); } void IntListTestEqual(void) { int i, c = 3; IntList t1, t2; IntListCtor(&t1); IntListCtor(&t2); for(i = 0; i < c; ++i) { IntListPush(&t1, i); IntListPush(&t2, i); } TEST_EQUAL( IntListSize(&t1), IntListSize(&t2) ); TEST_TRUE( IntListEqual(&t1, &t2) ); IntListPush(&t2, -1); TEST_NOT_EQUAL( IntListSize(&t1), IntListSize(&t2) ); TEST_FALSE( IntListEqual(&t1, &t2) ); IntListDtor(&t1); IntListDtor(&t2); } void IntListRunTests(void) { fprintf(stdout, "* %s\n", "IntList"); fflush(stdout); run_test("create", IntListTestCreate); run_test("equal", IntListTestEqual); fputs("\n", stdout); fflush(stdout); } static int* IntTreeSetItGetRef(IntTreeSetIt*); static int IntTreeSetContainsAllOf(IntTreeSet* self, IntTreeSet* other) { IntTreeSetIt it; IntTreeSetItCtor(&it, self); while(IntTreeSetItMove(&it)) { if(!IntTreeSetContains(other, *IntTreeSetItGetRef(&it))) return 0; } return 1; } void IntTreeSetCopy(IntTreeSet* dst,IntTreeSet* src) { IntTreeSetIt it; assert(src); assert(dst); IntTreeSetCtor(dst); IntTreeSetItCtor(&it, src); while(IntTreeSetItMove(&it)) IntTreeSetPut(dst, *IntTreeSetItGetRef(&it)); } int IntTreeSetEqual(IntTreeSet* lt,IntTreeSet* rt) { assert(lt); assert(rt); return IntTreeSetSize(lt) == IntTreeSetSize(rt) && IntTreeSetContainsAllOf(lt, rt) && IntTreeSetContainsAllOf(rt, lt); } size_t IntTreeSetIdentify(IntTreeSet* self) { IntTreeSetIt it; size_t result = 0; assert(self); IntTreeSetItCtor(&it, self); while(IntTreeSetItMove(&it)) { int* e = IntTreeSetItGetRef(&it); result ^= ((size_t)(*e)); result = AUTOC_RCYCLE(result); } return result; } size_t IntTreeSetSize(IntTreeSet* self) { assert(self); return self->size; } void IntTreeSetInclude(IntTreeSet* self, IntTreeSet* other) { IntTreeSetIt it; assert(self); assert(other); IntTreeSetItCtor(&it, other); while(IntTreeSetItMove(&it)) IntTreeSetPut(self, *IntTreeSetItGetRef(&it)); } void IntTreeSetRetain(IntTreeSet* self, IntTreeSet* other) { IntTreeSetIt it; IntTreeSet set; assert(self); assert(other); IntTreeSetCtor(&set); IntTreeSetItCtor(&it, self); while(IntTreeSetItMove(&it)) { int* e = IntTreeSetItGetRef(&it); assert(e); if(IntTreeSetContains(other, *e)) IntTreeSetPut(&set, *e); } IntTreeSetDtor(self); *self = set; } void IntTreeSetInvert(IntTreeSet* self, IntTreeSet* other) { IntTreeSetIt it; IntTreeSet set; assert(self); assert(other); IntTreeSetCtor(&set); IntTreeSetItCtor(&it, self); while(IntTreeSetItMove(&it)) { int* e = IntTreeSetItGetRef(&it); if(!IntTreeSetContains(other, *e)) IntTreeSetPut(&set, *e); } IntTreeSetItCtor(&it, other); while(IntTreeSetItMove(&it)) { int* e = IntTreeSetItGetRef(&it); if(!IntTreeSetContains(self, *e)) IntTreeSetPut(&set, *e); } IntTreeSetDtor(self); *self = set; } void IntTreeSetExclude(IntTreeSet* self, IntTreeSet* other) { IntTreeSetIt it; assert(self); assert(other); IntTreeSetItCtor(&it, other); while(IntTreeSetItMove(&it)) IntTreeSetRemove(self, *IntTreeSetItGetRef(&it)); } #define IntTreeSetIsRed(x) (x->color) #define IntTreeSetIsBlack(x) !IntTreeSetIsRed(x) #define IntTreeSetSetRed(x) (x->color = 1) #define IntTreeSetSetBlack(x) (x->color = 0) #define IntTreeSetCompare(lt, rt) (((lt) == (rt)) ? 0 : (((lt) < (rt)) ? -1 : +1)) static IntTreeSetNode IntTreeSetNullNode = {0, NULL, NULL, NULL}; static IntTreeSetNode* IntTreeSetNull = &IntTreeSetNullNode; static void IntTreeSetDestroyNode(IntTreeSetNode* node) { assert(node); assert(node != IntTreeSetNull); ; free(node); } void IntTreeSetCtor(IntTreeSet* self) { assert(self); self->size = 0; self->root = IntTreeSetNull; } static void IntTreeSetDestroy(IntTreeSetNode* node) { if(node != IntTreeSetNull) { IntTreeSetDestroy(node->left); IntTreeSetDestroy(node->right); IntTreeSetDestroyNode(node); } } void IntTreeSetDtor(IntTreeSet* self) { assert(self); IntTreeSetDestroy(self->root); /* FIXME recursive algorithm might be inefficient */ } void IntTreeSetPurge(IntTreeSet* self) { assert(self); IntTreeSetDtor(self); IntTreeSetCtor(self); } static void IntTreeSetRotateLeft(IntTreeSet* self, IntTreeSetNode* node) { IntTreeSetNode* right = node->right; node->right = right->left; if(right->left != IntTreeSetNull) right->left->parent = node; right->parent = node->parent; if(node->parent != IntTreeSetNull) { if(node == node->parent->left) { node->parent->left = right; } else { node->parent->right = right; } } else { self->root = right; } right->left = node; node->parent = right; } static void IntTreeSetRotateRight(IntTreeSet* self, IntTreeSetNode* node) { IntTreeSetNode* left = node->left; node->left = left->right; if(left->right != IntTreeSetNull) left->right->parent = node; left->parent = node->parent; if(node->parent != IntTreeSetNull) { if(node == node->parent->right) { node->parent->right = left; } else { node->parent->left = left; } } else { self->root = left; } left->right = node; node->parent = left; } static void IntTreeSetInsertFixup(IntTreeSet* self, IntTreeSetNode* node) { IntTreeSetNode* uncle; while(node != self->root && IntTreeSetIsRed(node->parent)) { if(node->parent == node->parent->parent->left) { uncle = node->parent->parent->right; if(IntTreeSetIsRed(uncle)) { IntTreeSetSetBlack(node->parent); IntTreeSetSetBlack(uncle); IntTreeSetSetRed(node->parent->parent); node = node->parent->parent; } else { if(node == node->parent->right) { node = node->parent; IntTreeSetRotateLeft(self, node); } IntTreeSetSetBlack(node->parent); IntTreeSetSetRed(node->parent->parent); IntTreeSetRotateRight(self, node->parent->parent); } } else { uncle = node->parent->parent->left; if(IntTreeSetIsRed(uncle)) { IntTreeSetSetBlack(node->parent); IntTreeSetSetBlack(uncle); IntTreeSetSetRed(node->parent->parent); node = node->parent->parent; } else { if(node == node->parent->left) { node = node->parent; IntTreeSetRotateRight(self, node); } IntTreeSetSetBlack(node->parent); IntTreeSetSetRed(node->parent->parent); IntTreeSetRotateLeft(self, node->parent->parent); } } } IntTreeSetSetBlack(self->root); } static void IntTreeSetDeleteFixup(IntTreeSet* self, IntTreeSetNode* child, IntTreeSetNode* child_parent) { IntTreeSetNode* sibling; int go_up = 1; if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; while(go_up) { if(child_parent == IntTreeSetNull) return; if(IntTreeSetIsRed(sibling)) { IntTreeSetSetRed(child_parent); IntTreeSetSetBlack(sibling); if(child_parent->right == child) IntTreeSetRotateRight(self, child_parent); else IntTreeSetRotateLeft(self, child_parent); if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; } if(IntTreeSetIsBlack(child_parent) && IntTreeSetIsBlack(sibling) && IntTreeSetIsBlack(sibling->left) && IntTreeSetIsBlack(sibling->right)) { if(sibling != IntTreeSetNull) IntTreeSetSetRed(sibling); child = child_parent; child_parent = child_parent->parent; if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; } else go_up = 0; } if(IntTreeSetIsRed(child_parent) && IntTreeSetIsBlack(sibling) && IntTreeSetIsBlack(sibling->left) && IntTreeSetIsBlack(sibling->right)) { if(sibling != IntTreeSetNull) IntTreeSetSetRed(sibling); IntTreeSetSetBlack(child_parent); return; } if(child_parent->right == child && IntTreeSetIsBlack(sibling) && IntTreeSetIsRed(sibling->right) && IntTreeSetIsBlack(sibling->left)) { IntTreeSetSetRed(sibling); IntTreeSetSetBlack(sibling->right); IntTreeSetRotateLeft(self, sibling); if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; } else if(child_parent->left == child && IntTreeSetIsBlack(sibling) && IntTreeSetIsRed(sibling->left) && IntTreeSetIsBlack(sibling->right)) { IntTreeSetSetRed(sibling); IntTreeSetSetBlack(sibling->left); IntTreeSetRotateRight(self, sibling); if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; } sibling->color = child_parent->color; IntTreeSetSetBlack(child_parent); if(child_parent->right == child) { IntTreeSetSetBlack(sibling->left); IntTreeSetRotateRight(self, child_parent); } else { IntTreeSetSetBlack(sibling->right); IntTreeSetRotateLeft(self, child_parent); } } static IntTreeSetNode* IntTreeSetFindNode(IntTreeSet* self, int element) { int r; IntTreeSetNode* node; assert(self); node = self->root; while(node != IntTreeSetNull) { if((r = IntTreeSetCompare(element, node->element)) == 0) { return node; } if(r < 0) { node = node->left; } else { node = node->right; } } return NULL; } int IntTreeSetContains(IntTreeSet* self, int element) { assert(self); return IntTreeSetFindNode(self, element) != NULL; } int IntTreeSetGet(IntTreeSet* self, int element) { IntTreeSetNode *node; int result; assert(self); assert(IntTreeSetContains(self, element)); node = IntTreeSetFindNode(self, element); ((result) = (node->element)); /* Here we rely on NULL pointer dereference to manifest the failure! */ return result; } int IntTreeSetPut(IntTreeSet* self, int element) { int r; IntTreeSetNode* data; IntTreeSetNode* node; IntTreeSetNode* parent; assert(self); node = self->root; parent = IntTreeSetNull; while(node != IntTreeSetNull) { if((r = IntTreeSetCompare(element, node->element)) == 0) { return 0; } parent = node; if (r < 0) { node = node->left; } else { node = node->right; } } data = malloc(sizeof(IntTreeSetNode)); assert(data); ((data->element) = (element)); data->parent = parent; data->left = data->right = IntTreeSetNull; IntTreeSetSetRed(data); ++self->size; if(parent != IntTreeSetNull) { if(r < 0) { parent->left = data; } else { parent->right = data; } } else { self->root = data; } IntTreeSetInsertFixup(self, data); return 1; } int IntTreeSetReplace(IntTreeSet* self, int element) { int removed; assert(self); /* FIXME removing followed by putting might be inefficient */ if((removed = IntTreeSetRemove(self, element))) IntTreeSetPut(self, element); return removed; } static void IntTreeSetSwapColors(IntTreeSetNode* x, IntTreeSetNode* y) { int t = x->color; assert(x); assert(y); x->color = y->color; y->color = t; } static void IntTreeSetSwapNodes(IntTreeSetNode** x, IntTreeSetNode** y) { IntTreeSetNode* t = *x; *x = *y; *y = t; } static void IntTreeSetChangeParent(IntTreeSet* self, IntTreeSetNode* parent, IntTreeSetNode* old_node, IntTreeSetNode* new_node) { if(parent == IntTreeSetNull) { if(self->root == old_node) self->root = new_node; return; } if(parent->left == old_node) parent->left = new_node; if(parent->right == old_node) parent->right = new_node; } static void IntTreeSetChangeChild(IntTreeSetNode* child, IntTreeSetNode* old_node, IntTreeSetNode* new_node) { if(child == IntTreeSetNull) return; if(child->parent == old_node) child->parent = new_node; } int IntTreeSetRemove(IntTreeSet* self, int element) { IntTreeSetNode* to_delete; IntTreeSetNode* child; assert(self); if((to_delete = IntTreeSetFindNode(self, element)) == NULL) return 0; if(to_delete->left != IntTreeSetNull && to_delete->right != IntTreeSetNull) { IntTreeSetNode *smright = to_delete->right; while(smright->left != IntTreeSetNull) smright = smright->left; IntTreeSetSwapColors(to_delete, smright); IntTreeSetChangeParent(self, to_delete->parent, to_delete, smright); if(to_delete->right != smright) IntTreeSetChangeParent(self, smright->parent, smright, to_delete); IntTreeSetChangeChild(smright->left, smright, to_delete); IntTreeSetChangeChild(smright->left, smright, to_delete); IntTreeSetChangeChild(smright->right, smright, to_delete); IntTreeSetChangeChild(smright->right, smright, to_delete); IntTreeSetChangeChild(to_delete->left, to_delete, smright); if(to_delete->right != smright) IntTreeSetChangeChild(to_delete->right, to_delete, smright); if(to_delete->right == smright) { to_delete->right = to_delete; smright->parent = smright; } IntTreeSetSwapNodes(&to_delete->parent, &smright->parent); IntTreeSetSwapNodes(&to_delete->left, &smright->left); IntTreeSetSwapNodes(&to_delete->right, &smright->right); } if(to_delete->left != IntTreeSetNull) child = to_delete->left; else child = to_delete->right; IntTreeSetChangeParent(self, to_delete->parent, to_delete, child); IntTreeSetChangeChild(child, to_delete, to_delete->parent); if(IntTreeSetIsRed(to_delete)) {} else if(IntTreeSetIsRed(child)) { if(child != IntTreeSetNull) IntTreeSetSetBlack(child); } else IntTreeSetDeleteFixup(self, child, to_delete->parent); IntTreeSetDestroyNode(to_delete); --self->size; return 1; } static IntTreeSetNode* IntTreeSetLowestNode(IntTreeSet* self) { IntTreeSetNode* node; assert(self); node = self->root; if(self->root != IntTreeSetNull) { for(node = self->root; node->left != IntTreeSetNull; node = node->left); } return node; } static IntTreeSetNode* IntTreeSetHighestNode(IntTreeSet* self) { IntTreeSetNode* node; assert(self); node = self->root; if(self->root != IntTreeSetNull) { for(node = self->root; node->right != IntTreeSetNull; node = node->right); } return node; } static IntTreeSetNode* IntTreeSetNextNode(IntTreeSetNode* node) { IntTreeSetNode* parent; assert(node); if(node->right != IntTreeSetNull) { for(node = node->right; node->left != IntTreeSetNull; node = node->left); } else { parent = node->parent; while(parent != IntTreeSetNull && node == parent->right) { node = parent; parent = parent->parent; } node = parent; } return node; } static IntTreeSetNode* IntTreeSetPrevNode(IntTreeSetNode* node) { IntTreeSetNode* parent; assert(node); if(node->left != IntTreeSetNull) { for(node = node->left; node->right != IntTreeSetNull; node = node->right); } else { parent = node->parent; while(parent != IntTreeSetNull && node == parent->left) { node = parent; parent = parent->parent; } node = parent; } return node; } int IntTreeSetPeekLowest(IntTreeSet* self) { IntTreeSetNode* node; int result; assert(self); assert(!IntTreeSetEmpty(self)); node = IntTreeSetLowestNode(self); assert(node); assert(node != IntTreeSetNull); ((result) = (node->element)); return result; } int IntTreeSetPeekHighest(IntTreeSet* self) { IntTreeSetNode* node; int result; assert(self); assert(!IntTreeSetEmpty(self)); node = IntTreeSetHighestNode(self); assert(node); assert(node != IntTreeSetNull); ((result) = (node->element)); return result; } void IntTreeSetItCtorEx(IntTreeSetIt* self, IntTreeSet* tree, int ascending) { assert(self); assert(tree); self->node = (self->ascending = ascending) ? IntTreeSetLowestNode(tree) : IntTreeSetHighestNode(tree); self->start = 1; } int IntTreeSetItMove(IntTreeSetIt* self) { assert(self); if(self->start) { self->start = 0; } else { self->node = self->ascending ? IntTreeSetNextNode(self->node) : IntTreeSetPrevNode(self->node); } return self->node != IntTreeSetNull; } static int* IntTreeSetItGetRef(IntTreeSetIt* self) { assert(self); assert(self->node); assert(self->node != IntTreeSetNull); return &self->node->element; } int IntTreeSetItGet(IntTreeSetIt* self) { int result; assert(self); ((result) = (*IntTreeSetItGetRef(self))); return result; } void IntTreeSetTestCreate(void) { IntTreeSet t; IntTreeSetCtor(&t); TEST_TRUE( IntTreeSetEmpty(&t) ); TEST_EQUAL( IntTreeSetSize(&t), 0 ); IntTreeSetDtor(&t); } void IntTreeSetTestPut(void) { IntTreeSet t; IntTreeSetCtor(&t); TEST_EQUAL( IntTreeSetSize(&t), 0 ); TEST_FALSE( IntTreeSetContains(&t, 1) ); TEST_TRUE( IntTreeSetPut(&t, 1) ); TEST_TRUE( IntTreeSetContains(&t, 1) ); TEST_FALSE( IntTreeSetPut(&t, 1) ); TEST_EQUAL( IntTreeSetSize(&t), 1 ); TEST_TRUE( IntTreeSetPut(&t, -1) ); TEST_TRUE( IntTreeSetPut(&t, 2) ); TEST_EQUAL( IntTreeSetSize(&t), 3 ); TEST_FALSE( IntTreeSetContains(&t, 0) ); IntTreeSetDtor(&t); } void IntTreeSetTestEqual(void) { int i, c = 3; IntTreeSet t1, t2; IntTreeSetCtor(&t1); IntTreeSetCtor(&t2); for(i = 0; i < c; ++i) { IntTreeSetPut(&t1, i); IntTreeSetPut(&t2, i); } TEST_EQUAL( IntTreeSetSize(&t1), IntTreeSetSize(&t2) ); TEST_TRUE( IntTreeSetEqual(&t1, &t2) ); IntTreeSetPut(&t2, -1); TEST_NOT_EQUAL( IntTreeSetSize(&t1), IntTreeSetSize(&t2) ); TEST_FALSE( IntTreeSetEqual(&t1, &t2) ); IntTreeSetDtor(&t1); IntTreeSetDtor(&t2); } void IntTreeSetTestSize(void) { int values[] = {2,-6,7,-6,1,2,5,7,4,3,1,-6,0}; int* p = values; IntTreeSet t; IntTreeSetCtor(&t); while(*p != 0) { IntTreeSetPut(&t, *p); TEST_TRUE( IntTreeSetContains(&t, *p) ); ++p; } TEST_EQUAL( IntTreeSetSize(&t), 7 ); IntTreeSetDtor(&t); } void IntTreeSetTestContains(void) { int values[] = {2,-6,7,-6,1,2,5,7,4,3,1,-6,0}; int* p = values; IntTreeSet t; IntTreeSetCtor(&t); while(*p != 0) { IntTreeSetPut(&t, *p); TEST_TRUE( IntTreeSetContains(&t, *p) ); ++p; } TEST_TRUE( IntTreeSetContains(&t, 1) ); TEST_FALSE( IntTreeSetContains(&t, -1) ); IntTreeSetDtor(&t); } void IntTreeSetTestIterateAscending(void) { int values[] = {2,-6,7,-6,1,2,5,7,4,3,1,-6,0}; int* p = values; IntTreeSet t; IntTreeSetCtor(&t); while(*p != 0) { IntTreeSetPut(&t, *p); TEST_TRUE( IntTreeSetContains(&t, *p) ); ++p; } int cur, pre, start = 1; IntTreeSetIt it; IntTreeSetItCtorEx(&it, &t, 1); cur = pre = IntTreeSetPeekLowest(&t); while(IntTreeSetItMove(&it)) { cur = IntTreeSetItGet(&it); if(start) { start = 0; } else { TEST_TRUE( pre < cur ); pre = cur; } } IntTreeSetDtor(&t); } void IntTreeSetTestIterateDescending(void) { int values[] = {2,-6,7,-6,1,2,5,7,4,3,1,-6,0}; int* p = values; IntTreeSet t; IntTreeSetCtor(&t); while(*p != 0) { IntTreeSetPut(&t, *p); TEST_TRUE( IntTreeSetContains(&t, *p) ); ++p; } int cur, pre, start = 1; IntTreeSetIt it; IntTreeSetItCtorEx(&it, &t, 0); cur = pre = IntTreeSetPeekHighest(&t); while(IntTreeSetItMove(&it)) { cur = IntTreeSetItGet(&it); if(start) { start = 0; } else { TEST_TRUE( pre > cur ); pre = cur; } } IntTreeSetDtor(&t); } void IntTreeSetTestPeekHighest(void) { int values[] = {2,-6,7,-6,1,2,5,7,4,3,1,-6,0}; int* p = values; IntTreeSet t; IntTreeSetCtor(&t); while(*p != 0) { IntTreeSetPut(&t, *p); TEST_TRUE( IntTreeSetContains(&t, *p) ); ++p; } TEST_EQUAL( IntTreeSetPeekHighest(&t), 7 ); IntTreeSetDtor(&t); } void IntTreeSetTestPeekLowest(void) { int values[] = {2,-6,7,-6,1,2,5,7,4,3,1,-6,0}; int* p = values; IntTreeSet t; IntTreeSetCtor(&t); while(*p != 0) { IntTreeSetPut(&t, *p); TEST_TRUE( IntTreeSetContains(&t, *p) ); ++p; } TEST_EQUAL( IntTreeSetPeekLowest(&t), -6 ); IntTreeSetDtor(&t); } void IntTreeSetRunTests(void) { fprintf(stdout, "* %s\n", "IntTreeSet"); fflush(stdout); run_test("create", IntTreeSetTestCreate); run_test("put", IntTreeSetTestPut); run_test("equal", IntTreeSetTestEqual); run_test("size", IntTreeSetTestSize); run_test("contains", IntTreeSetTestContains); run_test("iterateAscending", IntTreeSetTestIterateAscending); run_test("iterateDescending", IntTreeSetTestIterateDescending); run_test("peekHighest", IntTreeSetTestPeekHighest); run_test("peekLowest", IntTreeSetTestPeekLowest); fputs("\n", stdout); fflush(stdout); } #undef PUT #define PUT(t, v) {Value e; ValueCtorEx(e, v); ValueHashSetPut(t, e); ValueDtor(e);} #define _ValueHashSetListCtor(self) ValueHashSetListCtor(&self) #define _ValueHashSetListDtor(self) ValueHashSetListDtor(&self) #define _ValueHashSetListIdentify(self) ValueHashSetListIdentify(&self) #define _ValueHashSetListCopy(dst,src) ValueHashSetListCopy(&dst,&src) #define _ValueHashSetListEqual(lt,rt) ValueHashSetListEqual(<,&rt) #define _ValueHashSetListLess(lt,rt) ValueHashSetListLess(<,&rt) AUTOC_STATIC void ValueHashSetListItCtor(ValueHashSetListIt*, ValueHashSetList*); AUTOC_STATIC int ValueHashSetListItMove(ValueHashSetListIt*); AUTOC_STATIC Value ValueHashSetListItGet(ValueHashSetListIt*); AUTOC_STATIC void ValueHashSetListCtor(ValueHashSetList*); AUTOC_STATIC void ValueHashSetListDtor(ValueHashSetList*); AUTOC_STATIC void ValueHashSetListCopy(ValueHashSetList*,ValueHashSetList*); AUTOC_STATIC int ValueHashSetListEqual(ValueHashSetList*,ValueHashSetList*); AUTOC_STATIC size_t ValueHashSetListIdentify(ValueHashSetList*); AUTOC_STATIC void ValueHashSetListPurge(ValueHashSetList*); AUTOC_STATIC Value ValueHashSetListPeek(ValueHashSetList*); AUTOC_STATIC Value ValueHashSetListPop(ValueHashSetList*); AUTOC_STATIC void ValueHashSetListPush(ValueHashSetList*, Value); AUTOC_STATIC int ValueHashSetListContains(ValueHashSetList*, Value); AUTOC_STATIC Value ValueHashSetListFind(ValueHashSetList*, Value); #define ValueHashSetListReplace(self, with) ValueHashSetListReplaceEx(self, with, 1) #define ValueHashSetListReplaceAll(self, with) ValueHashSetListReplaceEx(self, with, -1) AUTOC_STATIC int ValueHashSetListReplaceEx(ValueHashSetList*, Value, int); #define ValueHashSetListRemove(self, what) ValueHashSetListRemoveEx(self, what, 1) #define ValueHashSetListRemoveAll(self, what) ValueHashSetListRemoveEx(self, what, -1) AUTOC_STATIC int ValueHashSetListRemoveEx(ValueHashSetList*, Value, int); AUTOC_STATIC size_t ValueHashSetListSize(ValueHashSetList*); #define ValueHashSetListEmpty(self) (ValueHashSetListSize(self) == 0) static Value* ValueHashSetListItGetRef(ValueHashSetListIt*); AUTOC_STATIC void ValueHashSetListCtor(ValueHashSetList* self) { assert(self); self->head_node = NULL; self->node_count = 0; } AUTOC_STATIC void ValueHashSetListDtor(ValueHashSetList* self) { ValueHashSetListNode* node; assert(self); node = self->head_node; while(node) { ValueHashSetListNode* this_node = node; node = node->next_node; ValueDtor(this_node->element); free(this_node); } } AUTOC_STATIC void ValueHashSetListCopy(ValueHashSetList* dst,ValueHashSetList* src) { ValueHashSetListIt it; size_t index, size; Value** elements; assert(src); assert(dst); ValueHashSetListCtor(dst); if(!ValueHashSetListEmpty(src)) { /* List is a LIFO type container therefore the insertion order into the destination container should be reversed */ elements = (Value**)malloc((size = ValueHashSetListSize(src))*sizeof(Value*)); assert(elements); index = 0; ValueHashSetListItCtor(&it, src); while(ValueHashSetListItMove(&it)) { assert(index < size); elements[index++] = ValueHashSetListItGetRef(&it); } for(index = size; index > 0; --index) ValueHashSetListPush(dst, *elements[index-1]); /* Be careful not to run into the underflow of the unsigned integer type */ free(elements); } } AUTOC_STATIC int ValueHashSetListEqual(ValueHashSetList* lt,ValueHashSetList* rt) { if(ValueHashSetListSize(lt) == ValueHashSetListSize(rt)) { ValueHashSetListIt lit, rit; ValueHashSetListItCtor(&lit, lt); ValueHashSetListItCtor(&rit, rt); while(ValueHashSetListItMove(&lit) && ValueHashSetListItMove(&rit)) { int equal; Value* le; Value* re; le = ValueHashSetListItGetRef(&lit); re = ValueHashSetListItGetRef(&rit); equal = ValueEqual(*le,*re); if(!equal) return 0; } return 1; } else return 0; } AUTOC_STATIC size_t ValueHashSetListIdentify(ValueHashSetList* self) { ValueHashSetListNode* node; size_t result = 0; assert(self); for(node = self->head_node; node != NULL; node = node->next_node) { result ^= ValueIdentify(node->element); result = AUTOC_RCYCLE(result); } return result; } AUTOC_STATIC void ValueHashSetListPurge(ValueHashSetList* self) { ValueHashSetListDtor(self); ValueHashSetListCtor(self); } AUTOC_STATIC Value ValueHashSetListPeek(ValueHashSetList* self) { Value result; assert(self); assert(!ValueHashSetListEmpty(self)); ValueCopy(result,self->head_node->element); return result; } AUTOC_STATIC Value ValueHashSetListPop(ValueHashSetList* self) { ValueHashSetListNode* node; Value result; assert(self); assert(!ValueHashSetListEmpty(self)); node = self->head_node; result = node->element; self->head_node = self->head_node->next_node; --self->node_count; free(node); return result; } AUTOC_STATIC void ValueHashSetListPush(ValueHashSetList* self, Value element) { ValueHashSetListNode* node; assert(self); node = (ValueHashSetListNode*)malloc(sizeof(ValueHashSetListNode)); assert(node); ValueCopy(node->element,element); node->next_node = self->head_node; self->head_node = node; ++self->node_count; } AUTOC_STATIC int ValueHashSetListContains(ValueHashSetList* self, Value what) { ValueHashSetListNode* node; int found = 0; assert(self); node = self->head_node; while(node) { if(ValueEqual(node->element,what)) { found = 1; break; } node = node->next_node; } return found; } AUTOC_STATIC Value ValueHashSetListFind(ValueHashSetList* self, Value what) { ValueHashSetListNode* node; assert(self); assert(ValueHashSetListContains(self, what)); node = self->head_node; while(node) { if(ValueEqual(node->element,what)) { Value result; ValueCopy(result,node->element); return result; } node = node->next_node; } abort(); } /* FIXME: for the generality's sake there should be both `what` and `with` values This is not achievable without breaking the interface, however, therefore defer this change to the major version bump */ AUTOC_STATIC int ValueHashSetListReplaceEx(ValueHashSetList* self, Value with, int count) { ValueHashSetListNode* node; int replaced = 0; assert(self); if(count == 0) return 0; node = self->head_node; while(node) { if(ValueEqual(node->element,with)) { ValueDtor(node->element); ValueCopy(node->element,with); ++replaced; if(count > 0 && replaced >= count) break; } node = node->next_node; } return replaced; } AUTOC_STATIC int ValueHashSetListRemoveEx(ValueHashSetList* self, Value what, int count) { ValueHashSetListNode *node, *prev_node; int removed = 0; assert(self); if(count == 0) return 0; node = self->head_node; prev_node = NULL; while(node) { if(ValueEqual(node->element,what)) { ValueHashSetListNode* this_node; if(prev_node) { this_node = prev_node->next_node = node->next_node; } else { this_node = self->head_node = node->next_node; } ++removed; --self->node_count; ValueDtor(node->element); free(node); node = this_node; if(count > 0 && removed >= count) break; } else { prev_node = node; node = node->next_node; } } return removed; } AUTOC_STATIC size_t ValueHashSetListSize(ValueHashSetList* self) { assert(self); return self->node_count; } AUTOC_STATIC void ValueHashSetListItCtor(ValueHashSetListIt* self, ValueHashSetList* list) { assert(self); assert(list); self->start = 1; self->list = list; } AUTOC_STATIC int ValueHashSetListItMove(ValueHashSetListIt* self) { assert(self); if(self->start) { self->this_node = self->list->head_node; self->start = 0; } else { self->this_node = self->this_node ? self->this_node->next_node : NULL; } return self->this_node != NULL; } AUTOC_STATIC Value ValueHashSetListItGet(ValueHashSetListIt* self) { Value result; assert(self); assert(self->this_node); ValueCopy(result,self->this_node->element); return result; } static Value* ValueHashSetListItGetRef(ValueHashSetListIt* self) { assert(self); assert(self->this_node); return &self->this_node->element; } static Value* ValueHashSetItGetRef(ValueHashSetIt*); static int ValueHashSetContainsAllOf(ValueHashSet* self, ValueHashSet* other) { ValueHashSetIt it; ValueHashSetItCtor(&it, self); while(ValueHashSetItMove(&it)) { if(!ValueHashSetContains(other, *ValueHashSetItGetRef(&it))) return 0; } return 1; } void ValueHashSetCopy(ValueHashSet* dst,ValueHashSet* src) { ValueHashSetIt it; assert(src); assert(dst); ValueHashSetCtor(dst); ValueHashSetItCtor(&it, src); while(ValueHashSetItMove(&it)) ValueHashSetPut(dst, *ValueHashSetItGetRef(&it)); } int ValueHashSetEqual(ValueHashSet* lt,ValueHashSet* rt) { assert(lt); assert(rt); return ValueHashSetSize(lt) == ValueHashSetSize(rt) && ValueHashSetContainsAllOf(lt, rt) && ValueHashSetContainsAllOf(rt, lt); } size_t ValueHashSetIdentify(ValueHashSet* self) { ValueHashSetIt it; size_t result = 0; assert(self); ValueHashSetItCtor(&it, self); while(ValueHashSetItMove(&it)) { Value* e = ValueHashSetItGetRef(&it); result ^= ValueIdentify(*e); result = AUTOC_RCYCLE(result); } return result; } size_t ValueHashSetSize(ValueHashSet* self) { assert(self); return self->size; } void ValueHashSetInclude(ValueHashSet* self, ValueHashSet* other) { ValueHashSetIt it; assert(self); assert(other); ValueHashSetItCtor(&it, other); while(ValueHashSetItMove(&it)) ValueHashSetPut(self, *ValueHashSetItGetRef(&it)); } void ValueHashSetRetain(ValueHashSet* self, ValueHashSet* other) { ValueHashSetIt it; ValueHashSet set; assert(self); assert(other); ValueHashSetCtor(&set); ValueHashSetItCtor(&it, self); while(ValueHashSetItMove(&it)) { Value* e = ValueHashSetItGetRef(&it); assert(e); if(ValueHashSetContains(other, *e)) ValueHashSetPut(&set, *e); } ValueHashSetDtor(self); *self = set; } void ValueHashSetInvert(ValueHashSet* self, ValueHashSet* other) { ValueHashSetIt it; ValueHashSet set; assert(self); assert(other); ValueHashSetCtor(&set); ValueHashSetItCtor(&it, self); while(ValueHashSetItMove(&it)) { Value* e = ValueHashSetItGetRef(&it); if(!ValueHashSetContains(other, *e)) ValueHashSetPut(&set, *e); } ValueHashSetItCtor(&it, other); while(ValueHashSetItMove(&it)) { Value* e = ValueHashSetItGetRef(&it); if(!ValueHashSetContains(self, *e)) ValueHashSetPut(&set, *e); } ValueHashSetDtor(self); *self = set; } void ValueHashSetExclude(ValueHashSet* self, ValueHashSet* other) { ValueHashSetIt it; assert(self); assert(other); ValueHashSetItCtor(&it, other); while(ValueHashSetItMove(&it)) ValueHashSetRemove(self, *ValueHashSetItGetRef(&it)); } static void ValueHashSetRehash(ValueHashSet* self) { ValueHashSetList* buckets; size_t index, bucket_count, size, fill; assert(self); assert(self->min_fill > 0); assert(self->max_fill > 0); assert(self->min_fill < self->max_fill); assert(self->min_bucket_count > 0); if(self->buckets) { if(self->min_size < self->size && self->size < self->max_size) return; fill = (size_t)((float)self->size/self->bucket_count*100); if(fill > self->max_fill) { bucket_count = (size_t)((float)self->bucket_count/100*self->capacity_multiplier); } else if(fill < self->min_fill && self->bucket_count > self->min_bucket_count) { bucket_count = (size_t)((float)self->bucket_count/self->capacity_multiplier*100); if(bucket_count < self->min_bucket_count) bucket_count = self->min_bucket_count; } else return; size = self->size; self->min_size = (size_t)((float)self->min_fill/100*size); self->max_size = (size_t)((float)self->max_fill/100*size); } else { bucket_count = self->min_bucket_count; size = 0; } buckets = (ValueHashSetList*)malloc(bucket_count*sizeof(ValueHashSetList)); assert(buckets); for(index = 0; index < bucket_count; ++index) { ValueHashSetListCtor(&buckets[index]); } if(self->buckets) { ValueHashSetIt it; ValueHashSetItCtor(&it, self); while(ValueHashSetItMove(&it)) { ValueHashSetList* bucket; Value element = ValueHashSetItGet(&it); bucket = &buckets[ValueIdentify(element) % bucket_count]; ValueHashSetListPush(bucket, element); ValueDtor(element); } ValueHashSetDtor(self); } self->buckets = buckets; self->bucket_count = bucket_count; self->size = size; } void ValueHashSetCtor(ValueHashSet* self) { assert(self); self->min_bucket_count = 16; self->min_fill = 20; self->max_fill = 80; self->min_size = (size_t)((float)self->min_fill/100*self->min_bucket_count); self->max_size = (size_t)((float)self->max_fill/100*self->min_bucket_count); self->capacity_multiplier = 200; self->buckets = NULL; ValueHashSetRehash(self); } void ValueHashSetDtor(ValueHashSet* self) { size_t i; assert(self); for(i = 0; i < self->bucket_count; ++i) { ValueHashSetListDtor(&self->buckets[i]); } free(self->buckets); } void ValueHashSetPurge(ValueHashSet* self) { assert(self); ValueHashSetDtor(self); self->buckets = NULL; ValueHashSetRehash(self); } int ValueHashSetContains(ValueHashSet* self, Value element) { assert(self); return ValueHashSetListContains(&self->buckets[ValueIdentify(element) % self->bucket_count], element); } Value ValueHashSetGet(ValueHashSet* self, Value element) { Value result; assert(self); assert(ValueHashSetContains(self, element)); result = ValueHashSetListFind(&self->buckets[ValueIdentify(element) % self->bucket_count], element); return result; } int ValueHashSetPut(ValueHashSet* self, Value element) { ValueHashSetList* bucket; assert(self); bucket = &self->buckets[ValueIdentify(element) % self->bucket_count]; if(!ValueHashSetListContains(bucket, element)) { ValueHashSetListPush(bucket, element); ++self->size; ValueHashSetRehash(self); return 1; } return 0; } int ValueHashSetReplace(ValueHashSet* self, Value element) { ValueHashSetList* bucket; assert(self); bucket = &self->buckets[ValueIdentify(element) % self->bucket_count]; return ValueHashSetListReplace(bucket, element); } int ValueHashSetRemove(ValueHashSet* self, Value element) { ValueHashSetList* bucket; assert(self); bucket = &self->buckets[ValueIdentify(element) % self->bucket_count]; if(ValueHashSetListRemove(bucket, element)) { --self->size; ValueHashSetRehash(self); return 1; } return 0; } void ValueHashSetItCtor(ValueHashSetIt* self, ValueHashSet* set) { assert(self); self->set = set; self->bucket_index = self->set->bucket_count; } int ValueHashSetItMove(ValueHashSetIt* self) { assert(self); if(self->bucket_index >= self->set->bucket_count) ValueHashSetListItCtor(&self->it, &self->set->buckets[self->bucket_index = 0]); if(ValueHashSetListItMove(&self->it)) return 1; while(++self->bucket_index < self->set->bucket_count) { ValueHashSetListItCtor(&self->it, &self->set->buckets[self->bucket_index]); if(ValueHashSetListItMove(&self->it)) return 1; } return 0; } Value ValueHashSetItGet(ValueHashSetIt* self) { assert(self); return ValueHashSetListItGet(&self->it); } static Value* ValueHashSetItGetRef(ValueHashSetIt* self) { assert(self); return ValueHashSetListItGetRef(&self->it); } void ValueHashSetTestCreate(void) { ValueHashSet t; ValueHashSetCtor(&t); TEST_EQUAL( ValueHashSetSize(&t), 0 ); TEST_TRUE( ValueHashSetEmpty(&t) ); ValueHashSetDtor(&t); } void ValueHashSetTestPurge(void) { ValueHashSet t; ValueHashSetCtor(&t); PUT(&t, 0); TEST_FALSE( ValueHashSetEmpty(&t) ); ValueHashSetPurge(&t); TEST_TRUE( ValueHashSetEmpty(&t) ); ValueHashSetDtor(&t); } void ValueHashSetTestContains(void) { /* a: [1,2,3], e: 0 */ ValueHashSet a; Value e; ValueCtor(e); ValueHashSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); TEST_FALSE( ValueHashSetContains(&a, e) ); ValueSet(e, 1); TEST_TRUE( ValueHashSetContains(&a, e) ); ValueHashSetDtor(&a); ValueDtor(e); } void ValueHashSetTestGet(void) { /* a: [1,2,3], e: 0 */ ValueHashSet a; Value e; ValueCtor(e); ValueHashSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); Value e2; ValueSet(e, -1); ValueHashSetPut(&a, e); e2 = ValueHashSetGet(&a, e); TEST_TRUE( ValueEqual(e, e2) ); ValueDtor(e2); ValueHashSetDtor(&a); ValueDtor(e); } void ValueHashSetTestPutNew(void) { /* a: [1,2,3], e: 0 */ ValueHashSet a; Value e; ValueCtor(e); ValueHashSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueSet(e, -1); TEST_FALSE( ValueHashSetContains(&a, e) ); TEST_TRUE( ValueHashSetPut(&a, e) ); TEST_TRUE( ValueHashSetContains(&a, e) ); ValueHashSetDtor(&a); ValueDtor(e); } void ValueHashSetTestPutExisting(void) { /* a: [1,2,3], e: 0 */ ValueHashSet a; Value e; ValueCtor(e); ValueHashSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueSet(e, -1); TEST_FALSE( ValueHashSetContains(&a, e) ); TEST_TRUE( ValueHashSetPut(&a, e) ); TEST_TRUE( ValueHashSetContains(&a, e) ); TEST_FALSE( ValueHashSetPut(&a, e) ); ValueHashSetDtor(&a); ValueDtor(e); } void ValueHashSetTestReplace(void) { /* a: [1,2,3], e: 0 */ ValueHashSet a; Value e; ValueCtor(e); ValueHashSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueSet(e, 1); TEST_TRUE( ValueHashSetContains(&a, e) ); TEST_TRUE( ValueHashSetReplace(&a, e) ); TEST_TRUE( ValueHashSetContains(&a, e) ); ValueHashSetDtor(&a); ValueDtor(e); } void ValueHashSetTestReplaceNone(void) { /* a: [1,2,3], e: 0 */ ValueHashSet a; Value e; ValueCtor(e); ValueHashSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueSet(e, -1); TEST_FALSE( ValueHashSetContains(&a, e) ); TEST_FALSE( ValueHashSetReplace(&a, e) ); TEST_FALSE( ValueHashSetContains(&a, e) ); ValueHashSetDtor(&a); ValueDtor(e); } void ValueHashSetTestRemove(void) { /* a: [1,2,3], e: 0 */ ValueHashSet a; Value e; ValueCtor(e); ValueHashSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueSet(e, 1); TEST_TRUE( ValueHashSetContains(&a, e) ); TEST_TRUE( ValueHashSetRemove(&a, e) ); TEST_FALSE( ValueHashSetContains(&a, e) ); ValueHashSetDtor(&a); ValueDtor(e); } void ValueHashSetTestRemoveNone(void) { /* a: [1,2,3], e: 0 */ ValueHashSet a; Value e; ValueCtor(e); ValueHashSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueSet(e, -1); TEST_FALSE( ValueHashSetContains(&a, e) ); TEST_FALSE( ValueHashSetRemove(&a, e) ); ValueHashSetDtor(&a); ValueDtor(e); } void ValueHashSetTestIterate(void) { /* a: [1,2,3], e: 0 */ ValueHashSet a; Value e; ValueCtor(e); ValueHashSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueHashSetIt it; size_t i = 0; ValueHashSetItCtor(&it, &a); while(ValueHashSetItMove(&it)) { Value e2 = ValueHashSetItGet(&it); ValueDtor(e2); i++; } TEST_EQUAL( ValueHashSetSize(&a), i ); ValueHashSetDtor(&a); ValueDtor(e); } void ValueHashSetTestCopy(void) { /* a: [1,2,3] */ ValueHashSet a, b; ValueHashSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueHashSetCopy(&b, &a); TEST_TRUE( ValueHashSetEqual(&a, &b) ); ValueHashSetDtor(&a); ValueHashSetDtor(&b); } void ValueHashSetTestEmpty(void) { /* a: [1,2,3] */ ValueHashSet a, b; ValueHashSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueHashSetCtor(&b); TEST_FALSE( ValueHashSetEmpty(&a) ); TEST_TRUE( ValueHashSetEmpty(&b) ); ValueHashSetDtor(&a); ValueHashSetDtor(&b); } void ValueHashSetTestExclude(void) { /* a: [1,2,3], b: [2,3,4] */ ValueHashSet a, b, c; ValueHashSetCtor(&a); ValueHashSetCtor(&b); ValueHashSetCtor(&c); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); PUT(&b, 4); PUT(&b, 2); PUT(&b, 3); PUT(&c, 1); ValueHashSetExclude(&a, &b); TEST_TRUE( ValueHashSetEqual(&a, &c) ); ValueHashSetDtor(&a); ValueHashSetDtor(&b); ValueHashSetDtor(&c); } void ValueHashSetTestInclude(void) { /* a: [1,2,3], b: [2,3,4] */ ValueHashSet a, b, c; ValueHashSetCtor(&a); ValueHashSetCtor(&b); ValueHashSetCtor(&c); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); PUT(&b, 4); PUT(&b, 2); PUT(&b, 3); PUT(&c, 1); PUT(&c, 2); PUT(&c, 3); PUT(&c, 4); ValueHashSetInclude(&a, &b); TEST_TRUE( ValueHashSetEqual(&a, &c) ); ValueHashSetDtor(&a); ValueHashSetDtor(&b); ValueHashSetDtor(&c); } void ValueHashSetTestInvert(void) { /* a: [1,2,3], b: [2,3,4] */ ValueHashSet a, b, c; ValueHashSetCtor(&a); ValueHashSetCtor(&b); ValueHashSetCtor(&c); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); PUT(&b, 4); PUT(&b, 2); PUT(&b, 3); PUT(&c, 1); PUT(&c, 4); ValueHashSetInvert(&a, &b); TEST_TRUE( ValueHashSetEqual(&a, &c) ); ValueHashSetDtor(&a); ValueHashSetDtor(&b); ValueHashSetDtor(&c); } void ValueHashSetTestRetain(void) { /* a: [1,2,3], b: [2,3,4] */ ValueHashSet a, b, c; ValueHashSetCtor(&a); ValueHashSetCtor(&b); ValueHashSetCtor(&c); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); PUT(&b, 4); PUT(&b, 2); PUT(&b, 3); PUT(&c, 2); PUT(&c, 3); ValueHashSetRetain(&a, &b); TEST_TRUE( ValueHashSetEqual(&a, &c) ); ValueHashSetDtor(&a); ValueHashSetDtor(&b); ValueHashSetDtor(&c); } void ValueHashSetRunTests(void) { fprintf(stdout, "* %s\n", "ValueHashSet"); fflush(stdout); run_test("create", ValueHashSetTestCreate); run_test("purge", ValueHashSetTestPurge); run_test("contains", ValueHashSetTestContains); run_test("get", ValueHashSetTestGet); run_test("putNew", ValueHashSetTestPutNew); run_test("putExisting", ValueHashSetTestPutExisting); run_test("replace", ValueHashSetTestReplace); run_test("replaceNone", ValueHashSetTestReplaceNone); run_test("remove", ValueHashSetTestRemove); run_test("removeNone", ValueHashSetTestRemoveNone); run_test("iterate", ValueHashSetTestIterate); run_test("copy", ValueHashSetTestCopy); run_test("empty", ValueHashSetTestEmpty); run_test("exclude", ValueHashSetTestExclude); run_test("include", ValueHashSetTestInclude); run_test("invert", ValueHashSetTestInvert); run_test("retain", ValueHashSetTestRetain); fputs("\n", stdout); fflush(stdout); } static void ValueVectorAllocate(ValueVector* self, size_t element_count) { assert(self); assert(element_count > 0); self->element_count = element_count; self->values = (Value*)malloc(element_count*sizeof(Value)); assert(self->values); } void ValueVectorCtor(ValueVector* self,size_t element_count) { size_t index; assert(self); ValueVectorAllocate(self, element_count); for(index = 0; index < ValueVectorSize(self); ++index) { ValueCtor(self->values[index]); } } void ValueVectorDtor(ValueVector* self) { size_t index; assert(self); for(index = 0; index < ValueVectorSize(self); ++index) { ValueDtor(self->values[index]); } free(self->values); } void ValueVectorCopy(ValueVector* dst,ValueVector* src) { size_t index, size; assert(src); assert(dst); ValueVectorAllocate(dst, size = ValueVectorSize(src)); for(index = 0; index < size; ++index) { ValueCopy(dst->values[index],src->values[index]); } } int ValueVectorEqual(ValueVector* lt,ValueVector* rt) { size_t index, size; assert(lt); assert(rt); if(ValueVectorSize(lt) == (size = ValueVectorSize(rt))) { for(index = 0; index < size; ++index) { if(!ValueEqual(lt->values[index],rt->values[index])) return 0; } return 1; } else return 0; } size_t ValueVectorIdentify(ValueVector* self) { size_t index, result = 0; assert(self); for(index = 0; index < self->element_count; ++index) { result ^= ValueIdentify(self->values[index]); result = AUTOC_RCYCLE(result); } return result; } void ValueVectorResize(ValueVector* self, size_t new_element_count) { size_t index, element_count, from, to; assert(self); if((element_count = ValueVectorSize(self)) != new_element_count) { Value* values = (Value*)malloc(new_element_count*sizeof(Value)); assert(values); from = AUTOC_MIN(element_count, new_element_count); to = AUTOC_MAX(element_count, new_element_count); for(index = 0; index < from; ++index) { values[index] = self->values[index]; } if(element_count > new_element_count) { for(index = from; index < to; ++index) { ValueDtor(self->values[index]); } } else { for(index = from; index < to; ++index) { ValueCtor(values[index]); } } free(self->values); self->values = values; self->element_count = new_element_count; } } static int ValueVectorAscend(void* lp_, void* rp_) { Value* lp = (Value*)lp_; Value* rp = (Value*)rp_; if(ValueEqual(*lp,*rp)) { return 0; } else if(ValueLess(*lp,*rp)) { return -1; } else { return +1; } } static int ValueVectorDescend(void* lp_, void* rp_) { return -ValueVectorAscend(lp_, rp_); } void ValueVectorSortEx(ValueVector* self, int ascending) { typedef int (*F)(const void*, const void*); assert(self); qsort(self->values, ValueVectorSize(self), sizeof(Value), ascending ? (F)ValueVectorAscend : (F)ValueVectorDescend); } void ValueVectorTestCreateSmallest(void) { ValueVector t; ValueVectorCtor(&t, 1); TEST_EQUAL( ValueVectorSize(&t), 1 ); ValueVectorDtor(&t); } void ValueVectorTestCreateLarge(void) { ValueVector t; ValueVectorCtor(&t, 1024); TEST_EQUAL( ValueVectorSize(&t), 1024 ); ValueVectorDtor(&t); } void ValueVectorTestGet(void) { ValueVector t; Value e; int i, c = 3; ValueVectorCtor(&t, c); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueVectorSet(&t, i, e); ValueDtor(e); } Value e2; ValueCtorEx(e, 2); e2 = ValueVectorGet(&t, 2); TEST_TRUE( ValueEqual(e, e2) ); ValueDtor(e); ValueDtor(e2); ValueVectorDtor(&t); } void ValueVectorTestSet(void) { ValueVector t; Value e; int i, c = 3; ValueVectorCtor(&t, c); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueVectorSet(&t, i, e); ValueDtor(e); } Value e2; ValueCtorEx(e, -1); ValueVectorSet(&t, 2, e); e2 = ValueVectorGet(&t, 2); TEST_TRUE( ValueEqual(e, e2) ); ValueDtor(e); ValueDtor(e2); ValueVectorDtor(&t); } void ValueVectorTestWithin(void) { ValueVector t; Value e; int i, c = 3; ValueVectorCtor(&t, c); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueVectorSet(&t, i, e); ValueDtor(e); } TEST_TRUE( ValueVectorWithin(&t, 0) ); TEST_TRUE( ValueVectorWithin(&t, 2) ); TEST_FALSE( ValueVectorWithin(&t, 3) ); ValueVectorDtor(&t); } void ValueVectorTestIterateForward(void) { ValueVector t; Value e; int i, c = 3; ValueVectorCtor(&t, c); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueVectorSet(&t, i, e); ValueDtor(e); } ValueVectorIt it; ValueVectorItCtor(&it, &t); i = 0; while(ValueVectorItMove(&it)) { e = ValueVectorItGet(&it); TEST_EQUAL( ValueGet(e), i++ ); ValueDtor(e); } ValueVectorDtor(&t); } void ValueVectorTestIterateExactForward(void) { ValueVector t; Value e; int i, c = 3; ValueVectorCtor(&t, c); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueVectorSet(&t, i, e); ValueDtor(e); } ValueVectorIt it; ValueVectorItCtorEx(&it, &t, 1); i = 0; while(ValueVectorItMove(&it)) { e = ValueVectorItGet(&it); TEST_EQUAL( ValueGet(e), i++ ); ValueDtor(e); } ValueVectorDtor(&t); } void ValueVectorTestIterateBackward(void) { ValueVector t; Value e; int i, c = 3; ValueVectorCtor(&t, c); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueVectorSet(&t, i, e); ValueDtor(e); } ValueVectorIt it; ValueVectorItCtorEx(&it, &t, 0); i = c-1; while(ValueVectorItMove(&it)) { e = ValueVectorItGet(&it); TEST_EQUAL( ValueGet(e), i-- ); ValueDtor(e); } ValueVectorDtor(&t); } void ValueVectorTestSize(void) { ValueVector t1, t2; Value e; int i, c = 3; ValueVectorCtor(&t1, c); ValueVectorCtor(&t2, c); TEST_TRUE( ValueVectorEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueVectorSet(&t1, i, e); ValueVectorSet(&t2, i, e); ValueDtor(e); } TEST_TRUE( ValueVectorEqual(&t1, &t2) ); TEST_EQUAL( ValueVectorSize(&t1), 3 ); TEST_EQUAL( ValueVectorSize(&t1), ValueVectorSize(&t2) ); ValueVectorResize(&t2, 1); TEST_EQUAL( ValueVectorSize(&t2), 1 ); TEST_NOT_EQUAL( ValueVectorSize(&t1), ValueVectorSize(&t2) ); ValueVectorDtor(&t1); ValueVectorDtor(&t2); } void ValueVectorTestEqual(void) { ValueVector t1, t2; Value e; int i, c = 3; ValueVectorCtor(&t1, c); ValueVectorCtor(&t2, c); TEST_TRUE( ValueVectorEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueVectorSet(&t1, i, e); ValueVectorSet(&t2, i, e); ValueDtor(e); } TEST_TRUE( ValueVectorEqual(&t1, &t2) ); ValueCtorEx(e, -1); ValueVectorSet(&t1, 0, e); ValueDtor(e); TEST_FALSE( ValueVectorEqual(&t1, &t2) ); ValueVectorDtor(&t1); ValueVectorDtor(&t2); } void ValueVectorTestResizeShrink(void) { ValueVector t1, t2; Value e; int i, c = 3; ValueVectorCtor(&t1, c); ValueVectorCtor(&t2, c); TEST_TRUE( ValueVectorEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueVectorSet(&t1, i, e); ValueVectorSet(&t2, i, e); ValueDtor(e); } TEST_TRUE( ValueVectorEqual(&t1, &t2) ); ValueVectorResize(&t2, 2); TEST_EQUAL( ValueVectorSize(&t2), 2 ); TEST_FALSE( ValueVectorEqual(&t1, &t2) ); ValueVectorDtor(&t1); ValueVectorDtor(&t2); } void ValueVectorTestResizeExpand(void) { ValueVector t1, t2; Value e; int i, c = 3; ValueVectorCtor(&t1, c); ValueVectorCtor(&t2, c); TEST_TRUE( ValueVectorEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueVectorSet(&t1, i, e); ValueVectorSet(&t2, i, e); ValueDtor(e); } TEST_TRUE( ValueVectorEqual(&t1, &t2) ); ValueVectorResize(&t2, 4); TEST_EQUAL( ValueVectorSize(&t2), 4 ); TEST_FALSE( ValueVectorEqual(&t1, &t2) ); e = ValueVectorGet(&t2, 3); TEST_EQUAL( ValueGet(e), 0 ); TEST_NOT_EQUAL( ValueGet(e), 1 ); ValueDtor(e); ValueVectorDtor(&t1); ValueVectorDtor(&t2); } void ValueVectorTestSort(void) { ValueVector t1, t2; Value e; int i, c = 3; ValueVectorCtor(&t1, c); ValueVectorCtor(&t2, c); TEST_TRUE( ValueVectorEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueVectorSet(&t1, i, e); ValueVectorSet(&t2, i, e); ValueDtor(e); } TEST_TRUE( ValueVectorEqual(&t1, &t2) ); ValueVectorSort(&t2); TEST_TRUE( ValueVectorEqual(&t1, &t2) ); e = ValueVectorGet(&t2, 0); TEST_EQUAL( ValueGet(e), 0 ); ValueDtor(e); ValueVectorSortEx(&t2, 0); TEST_FALSE( ValueVectorEqual(&t1, &t2) ); e = ValueVectorGet(&t2, 0); TEST_EQUAL( ValueGet(e), 2 ); ValueDtor(e); ValueVectorDtor(&t1); ValueVectorDtor(&t2); } void ValueVectorRunTests(void) { fprintf(stdout, "* %s\n", "ValueVector"); fflush(stdout); run_test("createSmallest", ValueVectorTestCreateSmallest); run_test("createLarge", ValueVectorTestCreateLarge); run_test("get", ValueVectorTestGet); run_test("set", ValueVectorTestSet); run_test("within", ValueVectorTestWithin); run_test("iterateForward", ValueVectorTestIterateForward); run_test("iterateExactForward", ValueVectorTestIterateExactForward); run_test("iterateBackward", ValueVectorTestIterateBackward); run_test("size", ValueVectorTestSize); run_test("equal", ValueVectorTestEqual); run_test("resizeShrink", ValueVectorTestResizeShrink); run_test("resizeExpand", ValueVectorTestResizeExpand); run_test("sort", ValueVectorTestSort); fputs("\n", stdout); fflush(stdout); } static Value* ValueListItGetRef(ValueListIt*); void ValueListCtor(ValueList* self) { assert(self); self->head_node = NULL; self->node_count = 0; } void ValueListDtor(ValueList* self) { ValueListNode* node; assert(self); node = self->head_node; while(node) { ValueListNode* this_node = node; node = node->next_node; ValueDtor(this_node->element); free(this_node); } } void ValueListCopy(ValueList* dst,ValueList* src) { ValueListIt it; size_t index, size; Value** elements; assert(src); assert(dst); ValueListCtor(dst); if(!ValueListEmpty(src)) { /* List is a LIFO type container therefore the insertion order into the destination container should be reversed */ elements = (Value**)malloc((size = ValueListSize(src))*sizeof(Value*)); assert(elements); index = 0; ValueListItCtor(&it, src); while(ValueListItMove(&it)) { assert(index < size); elements[index++] = ValueListItGetRef(&it); } for(index = size; index > 0; --index) ValueListPush(dst, *elements[index-1]); /* Be careful not to run into the underflow of the unsigned integer type */ free(elements); } } int ValueListEqual(ValueList* lt,ValueList* rt) { if(ValueListSize(lt) == ValueListSize(rt)) { ValueListIt lit, rit; ValueListItCtor(&lit, lt); ValueListItCtor(&rit, rt); while(ValueListItMove(&lit) && ValueListItMove(&rit)) { int equal; Value* le; Value* re; le = ValueListItGetRef(&lit); re = ValueListItGetRef(&rit); equal = ValueEqual(*le,*re); if(!equal) return 0; } return 1; } else return 0; } size_t ValueListIdentify(ValueList* self) { ValueListNode* node; size_t result = 0; assert(self); for(node = self->head_node; node != NULL; node = node->next_node) { result ^= ValueIdentify(node->element); result = AUTOC_RCYCLE(result); } return result; } void ValueListPurge(ValueList* self) { ValueListDtor(self); ValueListCtor(self); } Value ValueListPeek(ValueList* self) { Value result; assert(self); assert(!ValueListEmpty(self)); ValueCopy(result,self->head_node->element); return result; } Value ValueListPop(ValueList* self) { ValueListNode* node; Value result; assert(self); assert(!ValueListEmpty(self)); node = self->head_node; result = node->element; self->head_node = self->head_node->next_node; --self->node_count; free(node); return result; } void ValueListPush(ValueList* self, Value element) { ValueListNode* node; assert(self); node = (ValueListNode*)malloc(sizeof(ValueListNode)); assert(node); ValueCopy(node->element,element); node->next_node = self->head_node; self->head_node = node; ++self->node_count; } int ValueListContains(ValueList* self, Value what) { ValueListNode* node; int found = 0; assert(self); node = self->head_node; while(node) { if(ValueEqual(node->element,what)) { found = 1; break; } node = node->next_node; } return found; } Value ValueListFind(ValueList* self, Value what) { ValueListNode* node; assert(self); assert(ValueListContains(self, what)); node = self->head_node; while(node) { if(ValueEqual(node->element,what)) { Value result; ValueCopy(result,node->element); return result; } node = node->next_node; } abort(); } /* FIXME: for the generality's sake there should be both `what` and `with` values This is not achievable without breaking the interface, however, therefore defer this change to the major version bump */ int ValueListReplaceEx(ValueList* self, Value with, int count) { ValueListNode* node; int replaced = 0; assert(self); if(count == 0) return 0; node = self->head_node; while(node) { if(ValueEqual(node->element,with)) { ValueDtor(node->element); ValueCopy(node->element,with); ++replaced; if(count > 0 && replaced >= count) break; } node = node->next_node; } return replaced; } int ValueListRemoveEx(ValueList* self, Value what, int count) { ValueListNode *node, *prev_node; int removed = 0; assert(self); if(count == 0) return 0; node = self->head_node; prev_node = NULL; while(node) { if(ValueEqual(node->element,what)) { ValueListNode* this_node; if(prev_node) { this_node = prev_node->next_node = node->next_node; } else { this_node = self->head_node = node->next_node; } ++removed; --self->node_count; ValueDtor(node->element); free(node); node = this_node; if(count > 0 && removed >= count) break; } else { prev_node = node; node = node->next_node; } } return removed; } size_t ValueListSize(ValueList* self) { assert(self); return self->node_count; } void ValueListItCtor(ValueListIt* self, ValueList* list) { assert(self); assert(list); self->start = 1; self->list = list; } int ValueListItMove(ValueListIt* self) { assert(self); if(self->start) { self->this_node = self->list->head_node; self->start = 0; } else { self->this_node = self->this_node ? self->this_node->next_node : NULL; } return self->this_node != NULL; } Value ValueListItGet(ValueListIt* self) { Value result; assert(self); assert(self->this_node); ValueCopy(result,self->this_node->element); return result; } static Value* ValueListItGetRef(ValueListIt* self) { assert(self); assert(self->this_node); return &self->this_node->element; } void ValueListTestCreate(void) { ValueList t; ValueListCtor(&t); TEST_EQUAL( ValueListSize(&t), 0 ); TEST_TRUE( ValueListEmpty(&t) ); ValueListDtor(&t); } void ValueListTestCopy(void) { /* [0,1,2] */ ValueList t; Value e; int i, c = 3; ValueListCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t, e); ValueDtor(e); } ValueList t2; ValueListCopy(&t2, &t); TEST_TRUE( ValueListEqual(&t2, &t) ); { ValueListIt it; ValueListItCtor(&it, &t); while(ValueListItMove(&it)) { ValueGet(e = ValueListItGet(&it)); ValueDtor(e); } } ValueListDtor(&t2); ValueListDtor(&t); } void ValueListTestIterate(void) { /* [0,1,2] */ ValueList t; Value e; int i, c = 3; ValueListCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t, e); ValueDtor(e); } ValueListIt it; ValueListItCtor(&it, &t); i = ValueListSize(&t)-1; while(ValueListItMove(&it)) { e = ValueListItGet(&it); TEST_EQUAL( ValueGet(e), i-- ); ValueDtor(e); } ValueListDtor(&t); } void ValueListTestPurge(void) { /* [0,1,2] */ ValueList t; Value e; int i, c = 3; ValueListCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t, e); ValueDtor(e); } TEST_FALSE( ValueListEmpty(&t) ); ValueListPurge(&t); TEST_TRUE( ValueListEmpty(&t) ); ValueListDtor(&t); } void ValueListTestPeek(void) { /* [0,1,2] */ ValueList t; Value e; int i, c = 3; ValueListCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t, e); ValueDtor(e); } size_t s1 = ValueListSize(&t); e = ValueListPeek(&t); TEST_EQUAL( ValueGet(e), 2 ); ValueDtor(e); size_t s2 = ValueListSize(&t); TEST_EQUAL( s1, s2 ); ValueListDtor(&t); } void ValueListTestPop(void) { /* [0,1,2] */ ValueList t; Value e; int i, c = 3; ValueListCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t, e); ValueDtor(e); } size_t s1 = ValueListSize(&t); e = ValueListPop(&t); TEST_EQUAL( ValueGet(e), 2 ); ValueDtor(e); size_t s2 = ValueListSize(&t); TEST_EQUAL( s1-1, s2 ); ValueListDtor(&t); } void ValueListTestPush(void) { /* [0,1,2] */ ValueList t; Value e; int i, c = 3; ValueListCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t, e); ValueDtor(e); } size_t s1 = ValueListSize(&t); ValueCtorEx(e, -1); ValueListPush(&t, e); ValueDtor(e); size_t s2 = ValueListSize(&t); TEST_EQUAL( s1+1, s2 ); e = ValueListPeek(&t); TEST_EQUAL( ValueGet(e), -1 ); ValueDtor(e); ValueListDtor(&t); } void ValueListTestContains(void) { /* [0,1,2] */ ValueList t; Value e; int i, c = 3; ValueListCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t, e); ValueDtor(e); } ValueCtorEx(e, -1); TEST_FALSE( ValueListContains(&t, e) ); ValueSet(e, 1); TEST_TRUE( ValueListContains(&t, e) ); ValueDtor(e); ValueListDtor(&t); } void ValueListTestFind(void) { /* [0,1,2] */ ValueList t; Value e; int i, c = 3; ValueListCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t, e); ValueDtor(e); } Value e2; ValueCtorEx(e, 1); e2 = ValueListFind(&t, e); TEST_TRUE( ValueEqual(e, e2) ); ValueDtor(e); ValueDtor(e2); ValueListDtor(&t); } void ValueListTestEqual(void) { /* [0,1,2,0] */ ValueList t1, t2; Value e; int i, c = 3; ValueListCtor(&t1); ValueListCtor(&t2); TEST_TRUE( ValueListEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); TEST_TRUE( ValueListEqual(&t1, &t2) ); TEST_TRUE( ValueListEqual(&t1, &t2) ); ValueCtorEx(e, -1); ValueListPush(&t2, e); ValueDtor(e); TEST_FALSE( ValueListEqual(&t1, &t2) ); ValueListDtor(&t1); ValueListDtor(&t2); } void ValueListTestReplaceNone(void) { /* [0,1,2,0] */ ValueList t1, t2; Value e; int i, c = 3; ValueListCtor(&t1); ValueListCtor(&t2); TEST_TRUE( ValueListEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); TEST_TRUE( ValueListEqual(&t1, &t2) ); ValueCtorEx(e, -1); TEST_FALSE( ValueListReplace(&t2, e) ); TEST_TRUE( ValueListEqual(&t1, &t2) ); ValueDtor(e); ValueListDtor(&t1); ValueListDtor(&t2); } void ValueListTestReplaceOne(void) { /* [0,1,2,0] */ ValueList t1, t2; Value e; int i, c = 3; ValueListCtor(&t1); ValueListCtor(&t2); TEST_TRUE( ValueListEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); TEST_TRUE( ValueListEqual(&t1, &t2) ); ValueCtorEx(e, 0); TEST_EQUAL( ValueListReplace(&t2, e), 1 ); ValueDtor(e); ValueListDtor(&t1); ValueListDtor(&t2); } void ValueListTestReplaceExactOne(void) { /* [0,1,2,0] */ ValueList t1, t2; Value e; int i, c = 3; ValueListCtor(&t1); ValueListCtor(&t2); TEST_TRUE( ValueListEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); TEST_TRUE( ValueListEqual(&t1, &t2) ); ValueCtorEx(e, 0); TEST_EQUAL( ValueListReplaceEx(&t2, e, 1), 1 ); ValueDtor(e); ValueListDtor(&t1); ValueListDtor(&t2); } void ValueListTestReplaceAll(void) { /* [0,1,2,0] */ ValueList t1, t2; Value e; int i, c = 3; ValueListCtor(&t1); ValueListCtor(&t2); TEST_TRUE( ValueListEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); TEST_TRUE( ValueListEqual(&t1, &t2) ); ValueCtorEx(e, 0); TEST_EQUAL( ValueListReplaceAll(&t2, e), 2 ); ValueDtor(e); ValueListDtor(&t1); ValueListDtor(&t2); } void ValueListTestRemoveNone(void) { /* [0,1,2,0] */ ValueList t1, t2; Value e; int i, c = 3; ValueListCtor(&t1); ValueListCtor(&t2); TEST_TRUE( ValueListEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); TEST_TRUE( ValueListEqual(&t1, &t2) ); ValueCtorEx(e, -1); TEST_FALSE( ValueListRemove(&t2, e) ); TEST_TRUE( ValueListEqual(&t1, &t2) ); ValueDtor(e); ValueListDtor(&t1); ValueListDtor(&t2); } void ValueListTestRemoveOne(void) { /* [0,1,2,0] */ ValueList t1, t2; Value e; int i, c = 3; ValueListCtor(&t1); ValueListCtor(&t2); TEST_TRUE( ValueListEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); TEST_TRUE( ValueListEqual(&t1, &t2) ); ValueCtorEx(e, 0); TEST_EQUAL( ValueListRemove(&t2, e), 1 ); TEST_EQUAL( ValueListSize(&t1)-1, ValueListSize(&t2) ); ValueDtor(e); ValueListDtor(&t1); ValueListDtor(&t2); } void ValueListTestRemoveExactOne(void) { /* [0,1,2,0] */ ValueList t1, t2; Value e; int i, c = 3; ValueListCtor(&t1); ValueListCtor(&t2); TEST_TRUE( ValueListEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); TEST_TRUE( ValueListEqual(&t1, &t2) ); ValueCtorEx(e, 0); TEST_EQUAL( ValueListRemoveEx(&t2, e, 1), 1 ); TEST_EQUAL( ValueListSize(&t1)-1, ValueListSize(&t2) ); ValueDtor(e); ValueListDtor(&t1); ValueListDtor(&t2); } void ValueListTestRemoveAll(void) { /* [0,1,2,0] */ ValueList t1, t2; Value e; int i, c = 3; ValueListCtor(&t1); ValueListCtor(&t2); TEST_TRUE( ValueListEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueListPush(&t1, e); ValueListPush(&t2, e); ValueDtor(e); TEST_TRUE( ValueListEqual(&t1, &t2) ); ValueCtorEx(e, 0); TEST_EQUAL( ValueListRemoveAll(&t2, e), 2 ); TEST_EQUAL( ValueListSize(&t1)-2, ValueListSize(&t2) ); ValueDtor(e); ValueListDtor(&t1); ValueListDtor(&t2); } void ValueListRunTests(void) { fprintf(stdout, "* %s\n", "ValueList"); fflush(stdout); run_test("create", ValueListTestCreate); run_test("copy", ValueListTestCopy); run_test("iterate", ValueListTestIterate); run_test("purge", ValueListTestPurge); run_test("peek", ValueListTestPeek); run_test("pop", ValueListTestPop); run_test("push", ValueListTestPush); run_test("contains", ValueListTestContains); run_test("find", ValueListTestFind); run_test("equal", ValueListTestEqual); run_test("replaceNone", ValueListTestReplaceNone); run_test("replaceOne", ValueListTestReplaceOne); run_test("replaceExactOne", ValueListTestReplaceExactOne); run_test("replaceAll", ValueListTestReplaceAll); run_test("removeNone", ValueListTestRemoveNone); run_test("removeOne", ValueListTestRemoveOne); run_test("removeExactOne", ValueListTestRemoveExactOne); run_test("removeAll", ValueListTestRemoveAll); fputs("\n", stdout); fflush(stdout); } static void IntVectorAllocate(IntVector* self, size_t element_count) { assert(self); assert(element_count > 0); self->element_count = element_count; self->values = (int*)malloc(element_count*sizeof(int)); assert(self->values); } void IntVectorCtor(IntVector* self,size_t element_count) { size_t index; assert(self); IntVectorAllocate(self, element_count); for(index = 0; index < IntVectorSize(self); ++index) { ((self->values[index]) = 0); } } void IntVectorDtor(IntVector* self) { size_t index; assert(self); for(index = 0; index < IntVectorSize(self); ++index) { ; } free(self->values); } void IntVectorCopy(IntVector* dst,IntVector* src) { size_t index, size; assert(src); assert(dst); IntVectorAllocate(dst, size = IntVectorSize(src)); for(index = 0; index < size; ++index) { ((dst->values[index]) = (src->values[index])); } } int IntVectorEqual(IntVector* lt,IntVector* rt) { size_t index, size; assert(lt); assert(rt); if(IntVectorSize(lt) == (size = IntVectorSize(rt))) { for(index = 0; index < size; ++index) { if(!((lt->values[index]) == (rt->values[index]))) return 0; } return 1; } else return 0; } size_t IntVectorIdentify(IntVector* self) { size_t index, result = 0; assert(self); for(index = 0; index < self->element_count; ++index) { result ^= ((size_t)(self->values[index])); result = AUTOC_RCYCLE(result); } return result; } void IntVectorResize(IntVector* self, size_t new_element_count) { size_t index, element_count, from, to; assert(self); if((element_count = IntVectorSize(self)) != new_element_count) { int* values = (int*)malloc(new_element_count*sizeof(int)); assert(values); from = AUTOC_MIN(element_count, new_element_count); to = AUTOC_MAX(element_count, new_element_count); for(index = 0; index < from; ++index) { values[index] = self->values[index]; } if(element_count > new_element_count) { for(index = from; index < to; ++index) { ; } } else { for(index = from; index < to; ++index) { ((values[index]) = 0); } } free(self->values); self->values = values; self->element_count = new_element_count; } } static int IntVectorAscend(void* lp_, void* rp_) { int* lp = (int*)lp_; int* rp = (int*)rp_; if(((*lp) == (*rp))) { return 0; } else if(((*lp) < (*rp))) { return -1; } else { return +1; } } static int IntVectorDescend(void* lp_, void* rp_) { return -IntVectorAscend(lp_, rp_); } void IntVectorSortEx(IntVector* self, int ascending) { typedef int (*F)(const void*, const void*); assert(self); qsort(self->values, IntVectorSize(self), sizeof(int), ascending ? (F)IntVectorAscend : (F)IntVectorDescend); } void IntVectorTestSort(void) { IntVector t1, t2; int e; int i, c = 3; IntVectorCtor(&t1, c); IntVectorCtor(&t2, c); TEST_TRUE( IntVectorEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { IntVectorSet(&t1, i, i); IntVectorSet(&t2, i, i); } TEST_TRUE( IntVectorEqual(&t1, &t2) ); IntVectorSortEx(&t2, 0); /* 2,1,0 */ TEST_FALSE( IntVectorEqual(&t1, &t2) ); TEST_EQUAL( IntVectorGet(&t2, 0), 2 ); TEST_EQUAL( IntVectorGet(&t2, 1), 1 ); IntVectorSortEx(&t2, 1); /* 0,1,2 */ TEST_TRUE( IntVectorEqual(&t1, &t2) ); TEST_EQUAL( IntVectorGet(&t2, 0), 0 ); TEST_EQUAL( IntVectorGet(&t2, 1), 1 ); IntVectorDtor(&t1); IntVectorDtor(&t2); } void IntVectorRunTests(void) { fprintf(stdout, "* %s\n", "IntVector"); fflush(stdout); run_test("sort", IntVectorTestSort); fputs("\n", stdout); fflush(stdout); } static Value* ValueQueueItGetRef(ValueQueueIt*); void ValueQueueCtor(ValueQueue* self) { assert(self); self->head_node = self->tail_node = NULL; self->node_count = 0; } void ValueQueueDtor(ValueQueue* self) { ValueQueueNode* node; assert(self); node = self->head_node; while(node) { ValueQueueNode* this_node = node; node = node->next_node; ValueDtor(this_node->element); free(this_node); } } void ValueQueueCopy(ValueQueue* dst,ValueQueue* src) { ValueQueueIt it; assert(src); assert(dst); ValueQueueCtor(dst); ValueQueueItCtor(&it, src); while(ValueQueueItMove(&it)) { Value element; ValueQueuePushTail(dst, element = ValueQueueItGet(&it)); ValueDtor(element); } } int ValueQueueEqual(ValueQueue* lt,ValueQueue* rt) { if(ValueQueueSize(lt) == ValueQueueSize(rt)) { ValueQueueIt lit, rit; ValueQueueItCtor(&lit, lt); ValueQueueItCtor(&rit, rt); while(ValueQueueItMove(&lit) && ValueQueueItMove(&rit)) { int equal; Value *le, *re; le = ValueQueueItGetRef(&lit); re = ValueQueueItGetRef(&rit); equal = ValueEqual(*le,*re); if(!equal) return 0; } return 1; } else return 0; } size_t ValueQueueIdentify(ValueQueue* self) { ValueQueueNode* node; size_t result = 0; assert(self); for(node = self->head_node; node != NULL; node = node->next_node) { result ^= ValueIdentify(node->element); result = AUTOC_RCYCLE(result); } return result; } void ValueQueuePurge(ValueQueue* self) { ValueQueueDtor(self); ValueQueueCtor(self); } Value ValueQueuePeekHead(ValueQueue* self) { Value result; assert(self); assert(!ValueQueueEmpty(self)); ValueCopy(result,self->head_node->element); return result; } Value ValueQueuePeekTail(ValueQueue* self) { Value result; assert(self); assert(!ValueQueueEmpty(self)); ValueCopy(result,self->tail_node->element); return result; } Value ValueQueuePopHead(ValueQueue* self) { ValueQueueNode* node; Value result; assert(self); assert(!ValueQueueEmpty(self)); node = self->head_node; result = node->element; self->head_node = self->head_node->next_node; self->head_node->prev_node = NULL; --self->node_count; free(node); return result; } Value ValueQueuePopTail(ValueQueue* self) { ValueQueueNode* node; Value result; assert(self); assert(!ValueQueueEmpty(self)); node = self->tail_node; result = node->element; self->tail_node = self->tail_node->prev_node; self->tail_node->next_node = NULL; --self->node_count; free(node); return result; } void ValueQueuePushTail(ValueQueue* self, Value element) { ValueQueueNode* node; assert(self); node = (ValueQueueNode*)malloc(sizeof(ValueQueueNode)); assert(node); ValueCopy(node->element,element); if(ValueQueueEmpty(self)) { node->prev_node = node->next_node = NULL; self->tail_node = self->head_node = node; } else { node->next_node = NULL; node->prev_node = self->tail_node; self->tail_node->next_node = node; self->tail_node = node; } ++self->node_count; } void ValueQueuePushHead(ValueQueue* self, Value element) { ValueQueueNode* node; assert(self); node = (ValueQueueNode*)malloc(sizeof(ValueQueueNode)); assert(node); ValueCopy(node->element,element); if(ValueQueueEmpty(self)) { node->prev_node = node->next_node = NULL; self->tail_node = self->head_node = node; } else { node->prev_node = NULL; node->next_node = self->head_node; self->head_node->prev_node = node; self->head_node = node; } ++self->node_count; } int ValueQueueContains(ValueQueue* self, Value what) { ValueQueueNode* node; int found = 0; assert(self); node = self->head_node; while(node) { if(ValueEqual(node->element,what)) { found = 1; break; } node = node->next_node; } return found; } Value ValueQueueFind(ValueQueue* self, Value what) { ValueQueueNode* node; assert(self); assert(ValueQueueContains(self, what)); node = self->head_node; while(node) { if(ValueEqual(node->element,what)) { Value result; ValueCopy(result,node->element); return result; } node = node->next_node; } abort(); } int ValueQueueReplaceEx(ValueQueue* self, Value with, int count) { ValueQueueNode* node; int replaced = 0; assert(self); if(count == 0) return 0; node = self->head_node; while(node) { if(ValueEqual(node->element,with)) { ValueDtor(node->element); ValueCopy(node->element,with); ++replaced; if(count > 0 && replaced >= count) break; } node = node->next_node; } return replaced; } int ValueQueueRemoveEx(ValueQueue* self, Value what, int count) { ValueQueueNode* node; int removed = 0; assert(self); if(count == 0) return 0; node = self->head_node; while(node) { if(ValueEqual(node->element,what)) { ValueQueueNode* this_node; if(node == self->head_node) { assert(!node->prev_node); this_node = self->head_node = node->next_node; if(self->head_node) self->head_node->prev_node = NULL; } else if(node == self->tail_node) { assert(!node->next_node); self->tail_node = node->prev_node; this_node = self->tail_node->next_node = NULL; } else { assert(node->prev_node); assert(node->next_node); this_node = node->next_node; node->next_node->prev_node = node->prev_node; node->prev_node->next_node = node->next_node; } ++removed; --self->node_count; ValueDtor(node->element); free(node); node = this_node; if(count > 0 && removed >= count) break; } else { node = node->next_node; } } return removed; } size_t ValueQueueSize(ValueQueue* self) { assert(self); return self->node_count; } void ValueQueueItCtorEx(ValueQueueIt* self, ValueQueue* queue, int forward) { assert(self); assert(queue); self->start = 1; self->queue = queue; self->forward = forward; } int ValueQueueItMove(ValueQueueIt* self) { assert(self); if(self->start) { self->this_node = self->forward ? self->queue->head_node : self->queue->tail_node; self->start = 0; } else { self->this_node = self->forward ? self->this_node->next_node : self->this_node->prev_node; } return self->this_node != NULL; } Value ValueQueueItGet(ValueQueueIt* self) { Value result; assert(self); assert(self->this_node); ValueCopy(result,self->this_node->element); return result; } static Value* ValueQueueItGetRef(ValueQueueIt* self) { assert(self); assert(self->this_node); return &self->this_node->element; } void ValueQueueTestCreate(void) { ValueQueue t; ValueQueueCtor(&t); TEST_EQUAL( ValueQueueSize(&t), 0 ); TEST_TRUE( ValueQueueEmpty(&t) ); ValueQueueDtor(&t); } void ValueQueueTestCopy(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } ValueQueue t2; ValueQueueCopy(&t2, &t); TEST_TRUE( ValueQueueEqual(&t2, &t) ); { ValueQueueIt it; ValueQueueItCtor(&it, &t); while(ValueQueueItMove(&it)) { ValueGet(e = ValueQueueItGet(&it)); ValueDtor(e); } } ValueQueueDtor(&t2); ValueQueueDtor(&t); } void ValueQueueTestIterateForward(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } ValueQueueIt it; ValueQueueItCtor(&it, &t); i = 0; while(ValueQueueItMove(&it)) { e = ValueQueueItGet(&it); TEST_EQUAL( ValueGet(e), i++ ); ValueDtor(e); } ValueQueueDtor(&t); } void ValueQueueTestIterateExactForward(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } ValueQueueIt it; ValueQueueItCtorEx(&it, &t, 1); i = 0; while(ValueQueueItMove(&it)) { e = ValueQueueItGet(&it); TEST_EQUAL( ValueGet(e), i++ ); ValueDtor(e); } ValueQueueDtor(&t); } void ValueQueueTestIterateBackward(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } ValueQueueIt it; ValueQueueItCtorEx(&it, &t, 0); i = ValueQueueSize(&t)-1; while(ValueQueueItMove(&it)) { e = ValueQueueItGet(&it); TEST_EQUAL( ValueGet(e), i-- ); ValueDtor(e); } ValueQueueDtor(&t); } void ValueQueueTestPurge(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } TEST_FALSE( ValueQueueEmpty(&t) ); ValueQueuePurge(&t); TEST_TRUE( ValueQueueEmpty(&t) ); ValueQueueDtor(&t); } void ValueQueueTestPeek(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } size_t s1 = ValueQueueSize(&t); e = ValueQueuePeek(&t); TEST_EQUAL( ValueGet(e), 0 ); ValueDtor(e); size_t s2 = ValueQueueSize(&t); TEST_EQUAL( s1, s2 ); ValueQueueDtor(&t); } void ValueQueueTestPeekHead(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } size_t s1 = ValueQueueSize(&t); e = ValueQueuePeekHead(&t); TEST_EQUAL( ValueGet(e), 0 ); ValueDtor(e); size_t s2 = ValueQueueSize(&t); TEST_EQUAL( s1, s2 ); ValueQueueDtor(&t); } void ValueQueueTestPeekTail(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } size_t s1 = ValueQueueSize(&t); e = ValueQueuePeekTail(&t); TEST_EQUAL( ValueGet(e), 2 ); ValueDtor(e); size_t s2 = ValueQueueSize(&t); TEST_EQUAL( s1, s2 ); ValueQueueDtor(&t); } void ValueQueueTestPop(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } size_t s1 = ValueQueueSize(&t); e = ValueQueuePop(&t); TEST_EQUAL( ValueGet(e), 0 ); ValueDtor(e); size_t s2 = ValueQueueSize(&t); TEST_EQUAL( s1-1, s2 ); ValueQueueDtor(&t); } void ValueQueueTestPopHead(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } size_t s1 = ValueQueueSize(&t); e = ValueQueuePopHead(&t); TEST_EQUAL( ValueGet(e), 0 ); ValueDtor(e); size_t s2 = ValueQueueSize(&t); TEST_EQUAL( s1-1, s2 ); ValueQueueDtor(&t); } void ValueQueueTestPopTail(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } size_t s1 = ValueQueueSize(&t); e = ValueQueuePopTail(&t); TEST_EQUAL( ValueGet(e), 2 ); ValueDtor(e); size_t s2 = ValueQueueSize(&t); TEST_EQUAL( s1-1, s2 ); ValueQueueDtor(&t); } void ValueQueueTestPush(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } size_t s1 = ValueQueueSize(&t); ValueCtorEx(e, -1); ValueQueuePush(&t, e); ValueDtor(e); size_t s2 = ValueQueueSize(&t); TEST_EQUAL( s1+1, s2 ); e = ValueQueuePeekTail(&t); TEST_EQUAL( ValueGet(e), -1 ); ValueDtor(e); ValueQueueDtor(&t); } void ValueQueueTestPushTail(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } size_t s1 = ValueQueueSize(&t); ValueCtorEx(e, -1); ValueQueuePushTail(&t, e); ValueDtor(e); size_t s2 = ValueQueueSize(&t); TEST_EQUAL( s1+1, s2 ); e = ValueQueuePeekTail(&t); TEST_EQUAL( ValueGet(e), -1 ); ValueDtor(e); ValueQueueDtor(&t); } void ValueQueueTestPushHead(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } size_t s1 = ValueQueueSize(&t); ValueCtorEx(e, -1); ValueQueuePushHead(&t, e); ValueDtor(e); size_t s2 = ValueQueueSize(&t); TEST_EQUAL( s1+1, s2 ); e = ValueQueuePeekHead(&t); TEST_EQUAL( ValueGet(e), -1 ); ValueDtor(e); ValueQueueDtor(&t); } void ValueQueueTestContains(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } ValueCtorEx(e, -1); TEST_FALSE( ValueQueueContains(&t, e) ); ValueSet(e, 1); TEST_TRUE( ValueQueueContains(&t, e) ); ValueDtor(e); ValueQueueDtor(&t); } void ValueQueueTestFind(void) { /* [0,1,2] */ ValueQueue t; Value e; int i, c = 3; ValueQueueCtor(&t); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t, e); ValueDtor(e); } Value e2; ValueCtorEx(e, 1); e2 = ValueQueueFind(&t, e); TEST_TRUE( ValueEqual(e, e2) ); ValueDtor(e); ValueDtor(e2); ValueQueueDtor(&t); } void ValueQueueTestEqual(void) { /* [0,1,2,0] */ ValueQueue t1, t2; Value e; int i, c = 3; ValueQueueCtor(&t1); ValueQueueCtor(&t2); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); ValueCtorEx(e, -1); ValueQueuePush(&t2, e); ValueDtor(e); TEST_FALSE( ValueQueueEqual(&t1, &t2) ); ValueQueueDtor(&t1); ValueQueueDtor(&t2); } void ValueQueueTestReplaceNone(void) { /* [0,1,2,0] */ ValueQueue t1, t2; Value e; int i, c = 3; ValueQueueCtor(&t1); ValueQueueCtor(&t2); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); ValueCtorEx(e, -1); TEST_FALSE( ValueQueueReplace(&t2, e) ); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); ValueDtor(e); ValueQueueDtor(&t1); ValueQueueDtor(&t2); } void ValueQueueTestReplaceOne(void) { /* [0,1,2,0] */ ValueQueue t1, t2; Value e; int i, c = 3; ValueQueueCtor(&t1); ValueQueueCtor(&t2); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); ValueCtorEx(e, 0); TEST_EQUAL( ValueQueueReplace(&t2, e), 1 ); ValueDtor(e); ValueQueueDtor(&t1); ValueQueueDtor(&t2); } void ValueQueueTestReplaceExactOne(void) { /* [0,1,2,0] */ ValueQueue t1, t2; Value e; int i, c = 3; ValueQueueCtor(&t1); ValueQueueCtor(&t2); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); ValueCtorEx(e, 0); TEST_EQUAL( ValueQueueReplaceEx(&t2, e, 1), 1 ); ValueDtor(e); ValueQueueDtor(&t1); ValueQueueDtor(&t2); } void ValueQueueTestReplaceAll(void) { /* [0,1,2,0] */ ValueQueue t1, t2; Value e; int i, c = 3; ValueQueueCtor(&t1); ValueQueueCtor(&t2); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); ValueCtorEx(e, 0); TEST_EQUAL( ValueQueueReplaceAll(&t2, e), 2 ); ValueDtor(e); ValueQueueDtor(&t1); ValueQueueDtor(&t2); } void ValueQueueTestRemoveNone(void) { /* [0,1,2,0] */ ValueQueue t1, t2; Value e; int i, c = 3; ValueQueueCtor(&t1); ValueQueueCtor(&t2); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); ValueCtorEx(e, -1); TEST_FALSE( ValueQueueRemove(&t2, e) ); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); ValueDtor(e); ValueQueueDtor(&t1); ValueQueueDtor(&t2); } void ValueQueueTestRemoveOne(void) { /* [0,1,2,0] */ ValueQueue t1, t2; Value e; int i, c = 3; ValueQueueCtor(&t1); ValueQueueCtor(&t2); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); ValueCtorEx(e, 0); TEST_EQUAL( ValueQueueRemove(&t2, e), 1 ); TEST_EQUAL( ValueQueueSize(&t1)-1, ValueQueueSize(&t2) ); ValueDtor(e); ValueQueueDtor(&t1); ValueQueueDtor(&t2); } void ValueQueueTestRemoveExactOne(void) { /* [0,1,2,0] */ ValueQueue t1, t2; Value e; int i, c = 3; ValueQueueCtor(&t1); ValueQueueCtor(&t2); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); ValueCtorEx(e, 0); TEST_EQUAL( ValueQueueRemoveEx(&t2, e, 1), 1 ); TEST_EQUAL( ValueQueueSize(&t1)-1, ValueQueueSize(&t2) ); ValueDtor(e); ValueQueueDtor(&t1); ValueQueueDtor(&t2); } void ValueQueueTestRemoveAll(void) { /* [0,1,2,0] */ ValueQueue t1, t2; Value e; int i, c = 3; ValueQueueCtor(&t1); ValueQueueCtor(&t2); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); for(i = 0; i < c; ++i) { ValueCtorEx(e, i); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); } ValueCtorEx(e, 0); ValueQueuePush(&t1, e); ValueQueuePush(&t2, e); ValueDtor(e); TEST_TRUE( ValueQueueEqual(&t1, &t2) ); ValueCtorEx(e, 0); TEST_EQUAL( ValueQueueRemoveAll(&t2, e), 2 ); TEST_EQUAL( ValueQueueSize(&t1)-2, ValueQueueSize(&t2) ); ValueDtor(e); ValueQueueDtor(&t1); ValueQueueDtor(&t2); } void ValueQueueRunTests(void) { fprintf(stdout, "* %s\n", "ValueQueue"); fflush(stdout); run_test("create", ValueQueueTestCreate); run_test("copy", ValueQueueTestCopy); run_test("iterateForward", ValueQueueTestIterateForward); run_test("iterateExactForward", ValueQueueTestIterateExactForward); run_test("iterateBackward", ValueQueueTestIterateBackward); run_test("purge", ValueQueueTestPurge); run_test("peek", ValueQueueTestPeek); run_test("peekHead", ValueQueueTestPeekHead); run_test("peekTail", ValueQueueTestPeekTail); run_test("pop", ValueQueueTestPop); run_test("popHead", ValueQueueTestPopHead); run_test("popTail", ValueQueueTestPopTail); run_test("push", ValueQueueTestPush); run_test("pushTail", ValueQueueTestPushTail); run_test("pushHead", ValueQueueTestPushHead); run_test("contains", ValueQueueTestContains); run_test("find", ValueQueueTestFind); run_test("equal", ValueQueueTestEqual); run_test("replaceNone", ValueQueueTestReplaceNone); run_test("replaceOne", ValueQueueTestReplaceOne); run_test("replaceExactOne", ValueQueueTestReplaceExactOne); run_test("replaceAll", ValueQueueTestReplaceAll); run_test("removeNone", ValueQueueTestRemoveNone); run_test("removeOne", ValueQueueTestRemoveOne); run_test("removeExactOne", ValueQueueTestRemoveExactOne); run_test("removeAll", ValueQueueTestRemoveAll); fputs("\n", stdout); fflush(stdout); } #undef PUT #define PUT(t, k, v) {Value ek; Value ev; ValueCtorEx(ek, k); ValueCtorEx(ev, v); ValueTreeMapPut(t, ek, ev); ValueDtor(ek); ValueDtor(ev);} #define ValueTreeMapValidValue 1 #define ValueTreeMapValidKey 2 #define ValueTreeMapOwnedValue 4 #define ValueTreeMapOwnedKey 8 static ValueTreeMapEntry ValueTreeMapEntryKeyOnlyRef(Value* key) { ValueTreeMapEntry entry; entry.key = *key; entry.flags = ValueTreeMapValidKey; return entry; } static ValueTreeMapEntry ValueTreeMapEntryKeyValueRef(Value* key, Value* value) { ValueTreeMapEntry entry; entry.key = *key; entry.value = *value; entry.flags = (ValueTreeMapValidKey | ValueTreeMapValidValue); return entry; } #define ValueTreeMapEntryEqual(lt, rt) ValueTreeMapEntryEqualRef(<, &rt) static int ValueTreeMapEntryEqualRef(ValueTreeMapEntry* lt, ValueTreeMapEntry* rt) { return ValueEqual(lt->key,rt->key); } #define ValueTreeMapEntryLess(lt, rt) ValueTreeMapEntryLessRef(<, &rt) static int ValueTreeMapEntryLessRef(ValueTreeMapEntry* lt, ValueTreeMapEntry* rt) { return ValueLess(lt->key,rt->key); } #define ValueTreeMapEntryIdentify(obj) ValueTreeMapEntryIdentifyRef(&obj) static size_t ValueTreeMapEntryIdentifyRef(ValueTreeMapEntry* entry) { return ValueIdentify(entry->key); } #define ValueTreeMapEntryCopy(dst, src) ValueTreeMapEntryCopyRef(&dst, &src) static void ValueTreeMapEntryCopyRef(ValueTreeMapEntry* dst, ValueTreeMapEntry* src) { assert(src->flags & ValueTreeMapValidKey); dst->flags = (ValueTreeMapValidKey | ValueTreeMapOwnedKey); ValueCopy(dst->key,src->key); if(src->flags & ValueTreeMapValidValue) { dst->flags |= (ValueTreeMapValidValue | ValueTreeMapOwnedValue); ValueCopy(dst->value,src->value); } } #define ValueTreeMapEntryDtor(obj) ValueTreeMapEntryDtorRef(&obj) static void ValueTreeMapEntryDtorRef(ValueTreeMapEntry* entry) { assert(entry->flags & ValueTreeMapValidKey); if(entry->flags & ValueTreeMapOwnedKey) ValueDtor(entry->key); if(entry->flags & ValueTreeMapValidValue && entry->flags & ValueTreeMapOwnedValue) ValueDtor(entry->value); } static ValueTreeMapEntry* ValueTreeMapItGetEntryRef(ValueTreeMapIt*); static int ValueTreeMapContainsAllOf(ValueTreeMap* self, ValueTreeMap* other) { ValueTreeMapIt it; ValueTreeMapItCtor(&it, self); while(ValueTreeMapItMove(&it)) { int found = 0; ValueTreeMapEntry* e = ValueTreeMapItGetEntryRef(&it); if(ValueTreeMapContainsKey(other, e->key)) { Value other_value = ValueTreeMapGet(other, e->key); found = ValueEqual(e->value,other_value); ValueDtor(other_value); } if(!found) return 0; } return 1; } #define _ValueTreeMapSetCtor(self) ValueTreeMapSetCtor(&self) #define _ValueTreeMapSetDtor(self) ValueTreeMapSetDtor(&self) #define _ValueTreeMapSetIdentify(self) ValueTreeMapSetIdentify(&self) #define _ValueTreeMapSetCopy(dst,src) ValueTreeMapSetCopy(&dst,&src) #define _ValueTreeMapSetEqual(lt,rt) ValueTreeMapSetEqual(<,&rt) #define _ValueTreeMapSetLess(lt,rt) ValueTreeMapSetLess(<,&rt) AUTOC_STATIC void ValueTreeMapSetCtor(ValueTreeMapSet*); AUTOC_STATIC void ValueTreeMapSetDtor(ValueTreeMapSet*); AUTOC_STATIC void ValueTreeMapSetCopy(ValueTreeMapSet*,ValueTreeMapSet*); AUTOC_STATIC int ValueTreeMapSetEqual(ValueTreeMapSet*,ValueTreeMapSet*); AUTOC_STATIC size_t ValueTreeMapSetIdentify(ValueTreeMapSet*); AUTOC_STATIC void ValueTreeMapSetPurge(ValueTreeMapSet*); AUTOC_STATIC int ValueTreeMapSetContains(ValueTreeMapSet*, ValueTreeMapEntry); AUTOC_STATIC ValueTreeMapEntry ValueTreeMapSetGet(ValueTreeMapSet*, ValueTreeMapEntry); AUTOC_STATIC size_t ValueTreeMapSetSize(ValueTreeMapSet*); #define ValueTreeMapSetEmpty(self) (ValueTreeMapSetSize(self) == 0) AUTOC_STATIC int ValueTreeMapSetPut(ValueTreeMapSet*, ValueTreeMapEntry); AUTOC_STATIC int ValueTreeMapSetReplace(ValueTreeMapSet*, ValueTreeMapEntry); AUTOC_STATIC int ValueTreeMapSetRemove(ValueTreeMapSet*, ValueTreeMapEntry); AUTOC_STATIC void ValueTreeMapSetExclude(ValueTreeMapSet*, ValueTreeMapSet*); AUTOC_STATIC void ValueTreeMapSetRetain(ValueTreeMapSet*, ValueTreeMapSet*); AUTOC_STATIC void ValueTreeMapSetInclude(ValueTreeMapSet*, ValueTreeMapSet*); AUTOC_STATIC void ValueTreeMapSetInvert(ValueTreeMapSet*, ValueTreeMapSet*); AUTOC_STATIC void ValueTreeMapSetItCtor(ValueTreeMapSetIt*, ValueTreeMapSet*); #define ValueTreeMapSetItCtor(self, type) ValueTreeMapSetItCtorEx(self, type, 1) AUTOC_STATIC void ValueTreeMapSetItCtorEx(ValueTreeMapSetIt*, ValueTreeMapSet*, int); AUTOC_STATIC int ValueTreeMapSetItMove(ValueTreeMapSetIt*); AUTOC_STATIC ValueTreeMapEntry ValueTreeMapSetItGet(ValueTreeMapSetIt*); AUTOC_STATIC ValueTreeMapEntry ValueTreeMapSetPeekLowest(ValueTreeMapSet*); AUTOC_STATIC ValueTreeMapEntry ValueTreeMapSetPeekHighest(ValueTreeMapSet*); static ValueTreeMapEntry* ValueTreeMapSetItGetRef(ValueTreeMapSetIt*); static int ValueTreeMapSetContainsAllOf(ValueTreeMapSet* self, ValueTreeMapSet* other) { ValueTreeMapSetIt it; ValueTreeMapSetItCtor(&it, self); while(ValueTreeMapSetItMove(&it)) { if(!ValueTreeMapSetContains(other, *ValueTreeMapSetItGetRef(&it))) return 0; } return 1; } AUTOC_STATIC void ValueTreeMapSetCopy(ValueTreeMapSet* dst,ValueTreeMapSet* src) { ValueTreeMapSetIt it; assert(src); assert(dst); ValueTreeMapSetCtor(dst); ValueTreeMapSetItCtor(&it, src); while(ValueTreeMapSetItMove(&it)) ValueTreeMapSetPut(dst, *ValueTreeMapSetItGetRef(&it)); } AUTOC_STATIC int ValueTreeMapSetEqual(ValueTreeMapSet* lt,ValueTreeMapSet* rt) { assert(lt); assert(rt); return ValueTreeMapSetSize(lt) == ValueTreeMapSetSize(rt) && ValueTreeMapSetContainsAllOf(lt, rt) && ValueTreeMapSetContainsAllOf(rt, lt); } AUTOC_STATIC size_t ValueTreeMapSetIdentify(ValueTreeMapSet* self) { ValueTreeMapSetIt it; size_t result = 0; assert(self); ValueTreeMapSetItCtor(&it, self); while(ValueTreeMapSetItMove(&it)) { ValueTreeMapEntry* e = ValueTreeMapSetItGetRef(&it); result ^= ValueTreeMapEntryIdentify(*e); result = AUTOC_RCYCLE(result); } return result; } AUTOC_STATIC size_t ValueTreeMapSetSize(ValueTreeMapSet* self) { assert(self); return self->size; } AUTOC_STATIC void ValueTreeMapSetInclude(ValueTreeMapSet* self, ValueTreeMapSet* other) { ValueTreeMapSetIt it; assert(self); assert(other); ValueTreeMapSetItCtor(&it, other); while(ValueTreeMapSetItMove(&it)) ValueTreeMapSetPut(self, *ValueTreeMapSetItGetRef(&it)); } AUTOC_STATIC void ValueTreeMapSetRetain(ValueTreeMapSet* self, ValueTreeMapSet* other) { ValueTreeMapSetIt it; ValueTreeMapSet set; assert(self); assert(other); ValueTreeMapSetCtor(&set); ValueTreeMapSetItCtor(&it, self); while(ValueTreeMapSetItMove(&it)) { ValueTreeMapEntry* e = ValueTreeMapSetItGetRef(&it); assert(e); if(ValueTreeMapSetContains(other, *e)) ValueTreeMapSetPut(&set, *e); } ValueTreeMapSetDtor(self); *self = set; } AUTOC_STATIC void ValueTreeMapSetInvert(ValueTreeMapSet* self, ValueTreeMapSet* other) { ValueTreeMapSetIt it; ValueTreeMapSet set; assert(self); assert(other); ValueTreeMapSetCtor(&set); ValueTreeMapSetItCtor(&it, self); while(ValueTreeMapSetItMove(&it)) { ValueTreeMapEntry* e = ValueTreeMapSetItGetRef(&it); if(!ValueTreeMapSetContains(other, *e)) ValueTreeMapSetPut(&set, *e); } ValueTreeMapSetItCtor(&it, other); while(ValueTreeMapSetItMove(&it)) { ValueTreeMapEntry* e = ValueTreeMapSetItGetRef(&it); if(!ValueTreeMapSetContains(self, *e)) ValueTreeMapSetPut(&set, *e); } ValueTreeMapSetDtor(self); *self = set; } AUTOC_STATIC void ValueTreeMapSetExclude(ValueTreeMapSet* self, ValueTreeMapSet* other) { ValueTreeMapSetIt it; assert(self); assert(other); ValueTreeMapSetItCtor(&it, other); while(ValueTreeMapSetItMove(&it)) ValueTreeMapSetRemove(self, *ValueTreeMapSetItGetRef(&it)); } #define ValueTreeMapSetIsRed(x) (x->color) #define ValueTreeMapSetIsBlack(x) !ValueTreeMapSetIsRed(x) #define ValueTreeMapSetSetRed(x) (x->color = 1) #define ValueTreeMapSetSetBlack(x) (x->color = 0) #define ValueTreeMapSetCompare(lt, rt) (ValueTreeMapEntryEqual(lt,rt) ? 0 : (ValueTreeMapEntryLess(lt,rt) ? -1 : +1)) static ValueTreeMapSetNode ValueTreeMapSetNullNode = {0, NULL, NULL, NULL}; static ValueTreeMapSetNode* ValueTreeMapSetNull = &ValueTreeMapSetNullNode; static void ValueTreeMapSetDestroyNode(ValueTreeMapSetNode* node) { assert(node); assert(node != ValueTreeMapSetNull); ValueTreeMapEntryDtor(node->element); free(node); } AUTOC_STATIC void ValueTreeMapSetCtor(ValueTreeMapSet* self) { assert(self); self->size = 0; self->root = ValueTreeMapSetNull; } static void ValueTreeMapSetDestroy(ValueTreeMapSetNode* node) { if(node != ValueTreeMapSetNull) { ValueTreeMapSetDestroy(node->left); ValueTreeMapSetDestroy(node->right); ValueTreeMapSetDestroyNode(node); } } AUTOC_STATIC void ValueTreeMapSetDtor(ValueTreeMapSet* self) { assert(self); ValueTreeMapSetDestroy(self->root); /* FIXME recursive algorithm might be inefficient */ } AUTOC_STATIC void ValueTreeMapSetPurge(ValueTreeMapSet* self) { assert(self); ValueTreeMapSetDtor(self); ValueTreeMapSetCtor(self); } static void ValueTreeMapSetRotateLeft(ValueTreeMapSet* self, ValueTreeMapSetNode* node) { ValueTreeMapSetNode* right = node->right; node->right = right->left; if(right->left != ValueTreeMapSetNull) right->left->parent = node; right->parent = node->parent; if(node->parent != ValueTreeMapSetNull) { if(node == node->parent->left) { node->parent->left = right; } else { node->parent->right = right; } } else { self->root = right; } right->left = node; node->parent = right; } static void ValueTreeMapSetRotateRight(ValueTreeMapSet* self, ValueTreeMapSetNode* node) { ValueTreeMapSetNode* left = node->left; node->left = left->right; if(left->right != ValueTreeMapSetNull) left->right->parent = node; left->parent = node->parent; if(node->parent != ValueTreeMapSetNull) { if(node == node->parent->right) { node->parent->right = left; } else { node->parent->left = left; } } else { self->root = left; } left->right = node; node->parent = left; } static void ValueTreeMapSetInsertFixup(ValueTreeMapSet* self, ValueTreeMapSetNode* node) { ValueTreeMapSetNode* uncle; while(node != self->root && ValueTreeMapSetIsRed(node->parent)) { if(node->parent == node->parent->parent->left) { uncle = node->parent->parent->right; if(ValueTreeMapSetIsRed(uncle)) { ValueTreeMapSetSetBlack(node->parent); ValueTreeMapSetSetBlack(uncle); ValueTreeMapSetSetRed(node->parent->parent); node = node->parent->parent; } else { if(node == node->parent->right) { node = node->parent; ValueTreeMapSetRotateLeft(self, node); } ValueTreeMapSetSetBlack(node->parent); ValueTreeMapSetSetRed(node->parent->parent); ValueTreeMapSetRotateRight(self, node->parent->parent); } } else { uncle = node->parent->parent->left; if(ValueTreeMapSetIsRed(uncle)) { ValueTreeMapSetSetBlack(node->parent); ValueTreeMapSetSetBlack(uncle); ValueTreeMapSetSetRed(node->parent->parent); node = node->parent->parent; } else { if(node == node->parent->left) { node = node->parent; ValueTreeMapSetRotateRight(self, node); } ValueTreeMapSetSetBlack(node->parent); ValueTreeMapSetSetRed(node->parent->parent); ValueTreeMapSetRotateLeft(self, node->parent->parent); } } } ValueTreeMapSetSetBlack(self->root); } static void ValueTreeMapSetDeleteFixup(ValueTreeMapSet* self, ValueTreeMapSetNode* child, ValueTreeMapSetNode* child_parent) { ValueTreeMapSetNode* sibling; int go_up = 1; if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; while(go_up) { if(child_parent == ValueTreeMapSetNull) return; if(ValueTreeMapSetIsRed(sibling)) { ValueTreeMapSetSetRed(child_parent); ValueTreeMapSetSetBlack(sibling); if(child_parent->right == child) ValueTreeMapSetRotateRight(self, child_parent); else ValueTreeMapSetRotateLeft(self, child_parent); if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; } if(ValueTreeMapSetIsBlack(child_parent) && ValueTreeMapSetIsBlack(sibling) && ValueTreeMapSetIsBlack(sibling->left) && ValueTreeMapSetIsBlack(sibling->right)) { if(sibling != ValueTreeMapSetNull) ValueTreeMapSetSetRed(sibling); child = child_parent; child_parent = child_parent->parent; if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; } else go_up = 0; } if(ValueTreeMapSetIsRed(child_parent) && ValueTreeMapSetIsBlack(sibling) && ValueTreeMapSetIsBlack(sibling->left) && ValueTreeMapSetIsBlack(sibling->right)) { if(sibling != ValueTreeMapSetNull) ValueTreeMapSetSetRed(sibling); ValueTreeMapSetSetBlack(child_parent); return; } if(child_parent->right == child && ValueTreeMapSetIsBlack(sibling) && ValueTreeMapSetIsRed(sibling->right) && ValueTreeMapSetIsBlack(sibling->left)) { ValueTreeMapSetSetRed(sibling); ValueTreeMapSetSetBlack(sibling->right); ValueTreeMapSetRotateLeft(self, sibling); if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; } else if(child_parent->left == child && ValueTreeMapSetIsBlack(sibling) && ValueTreeMapSetIsRed(sibling->left) && ValueTreeMapSetIsBlack(sibling->right)) { ValueTreeMapSetSetRed(sibling); ValueTreeMapSetSetBlack(sibling->left); ValueTreeMapSetRotateRight(self, sibling); if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; } sibling->color = child_parent->color; ValueTreeMapSetSetBlack(child_parent); if(child_parent->right == child) { ValueTreeMapSetSetBlack(sibling->left); ValueTreeMapSetRotateRight(self, child_parent); } else { ValueTreeMapSetSetBlack(sibling->right); ValueTreeMapSetRotateLeft(self, child_parent); } } static ValueTreeMapSetNode* ValueTreeMapSetFindNode(ValueTreeMapSet* self, ValueTreeMapEntry element) { int r; ValueTreeMapSetNode* node; assert(self); node = self->root; while(node != ValueTreeMapSetNull) { if((r = ValueTreeMapSetCompare(element, node->element)) == 0) { return node; } if(r < 0) { node = node->left; } else { node = node->right; } } return NULL; } AUTOC_STATIC int ValueTreeMapSetContains(ValueTreeMapSet* self, ValueTreeMapEntry element) { assert(self); return ValueTreeMapSetFindNode(self, element) != NULL; } AUTOC_STATIC ValueTreeMapEntry ValueTreeMapSetGet(ValueTreeMapSet* self, ValueTreeMapEntry element) { ValueTreeMapSetNode *node; ValueTreeMapEntry result; assert(self); assert(ValueTreeMapSetContains(self, element)); node = ValueTreeMapSetFindNode(self, element); ValueTreeMapEntryCopy(result,node->element); /* Here we rely on NULL pointer dereference to manifest the failure! */ return result; } AUTOC_STATIC int ValueTreeMapSetPut(ValueTreeMapSet* self, ValueTreeMapEntry element) { int r; ValueTreeMapSetNode* data; ValueTreeMapSetNode* node; ValueTreeMapSetNode* parent; assert(self); node = self->root; parent = ValueTreeMapSetNull; while(node != ValueTreeMapSetNull) { if((r = ValueTreeMapSetCompare(element, node->element)) == 0) { return 0; } parent = node; if (r < 0) { node = node->left; } else { node = node->right; } } data = malloc(sizeof(ValueTreeMapSetNode)); assert(data); ValueTreeMapEntryCopy(data->element,element); data->parent = parent; data->left = data->right = ValueTreeMapSetNull; ValueTreeMapSetSetRed(data); ++self->size; if(parent != ValueTreeMapSetNull) { if(r < 0) { parent->left = data; } else { parent->right = data; } } else { self->root = data; } ValueTreeMapSetInsertFixup(self, data); return 1; } AUTOC_STATIC int ValueTreeMapSetReplace(ValueTreeMapSet* self, ValueTreeMapEntry element) { int removed; assert(self); /* FIXME removing followed by putting might be inefficient */ if((removed = ValueTreeMapSetRemove(self, element))) ValueTreeMapSetPut(self, element); return removed; } static void ValueTreeMapSetSwapColors(ValueTreeMapSetNode* x, ValueTreeMapSetNode* y) { int t = x->color; assert(x); assert(y); x->color = y->color; y->color = t; } static void ValueTreeMapSetSwapNodes(ValueTreeMapSetNode** x, ValueTreeMapSetNode** y) { ValueTreeMapSetNode* t = *x; *x = *y; *y = t; } static void ValueTreeMapSetChangeParent(ValueTreeMapSet* self, ValueTreeMapSetNode* parent, ValueTreeMapSetNode* old_node, ValueTreeMapSetNode* new_node) { if(parent == ValueTreeMapSetNull) { if(self->root == old_node) self->root = new_node; return; } if(parent->left == old_node) parent->left = new_node; if(parent->right == old_node) parent->right = new_node; } static void ValueTreeMapSetChangeChild(ValueTreeMapSetNode* child, ValueTreeMapSetNode* old_node, ValueTreeMapSetNode* new_node) { if(child == ValueTreeMapSetNull) return; if(child->parent == old_node) child->parent = new_node; } int ValueTreeMapSetRemove(ValueTreeMapSet* self, ValueTreeMapEntry element) { ValueTreeMapSetNode* to_delete; ValueTreeMapSetNode* child; assert(self); if((to_delete = ValueTreeMapSetFindNode(self, element)) == NULL) return 0; if(to_delete->left != ValueTreeMapSetNull && to_delete->right != ValueTreeMapSetNull) { ValueTreeMapSetNode *smright = to_delete->right; while(smright->left != ValueTreeMapSetNull) smright = smright->left; ValueTreeMapSetSwapColors(to_delete, smright); ValueTreeMapSetChangeParent(self, to_delete->parent, to_delete, smright); if(to_delete->right != smright) ValueTreeMapSetChangeParent(self, smright->parent, smright, to_delete); ValueTreeMapSetChangeChild(smright->left, smright, to_delete); ValueTreeMapSetChangeChild(smright->left, smright, to_delete); ValueTreeMapSetChangeChild(smright->right, smright, to_delete); ValueTreeMapSetChangeChild(smright->right, smright, to_delete); ValueTreeMapSetChangeChild(to_delete->left, to_delete, smright); if(to_delete->right != smright) ValueTreeMapSetChangeChild(to_delete->right, to_delete, smright); if(to_delete->right == smright) { to_delete->right = to_delete; smright->parent = smright; } ValueTreeMapSetSwapNodes(&to_delete->parent, &smright->parent); ValueTreeMapSetSwapNodes(&to_delete->left, &smright->left); ValueTreeMapSetSwapNodes(&to_delete->right, &smright->right); } if(to_delete->left != ValueTreeMapSetNull) child = to_delete->left; else child = to_delete->right; ValueTreeMapSetChangeParent(self, to_delete->parent, to_delete, child); ValueTreeMapSetChangeChild(child, to_delete, to_delete->parent); if(ValueTreeMapSetIsRed(to_delete)) {} else if(ValueTreeMapSetIsRed(child)) { if(child != ValueTreeMapSetNull) ValueTreeMapSetSetBlack(child); } else ValueTreeMapSetDeleteFixup(self, child, to_delete->parent); ValueTreeMapSetDestroyNode(to_delete); --self->size; return 1; } static ValueTreeMapSetNode* ValueTreeMapSetLowestNode(ValueTreeMapSet* self) { ValueTreeMapSetNode* node; assert(self); node = self->root; if(self->root != ValueTreeMapSetNull) { for(node = self->root; node->left != ValueTreeMapSetNull; node = node->left); } return node; } static ValueTreeMapSetNode* ValueTreeMapSetHighestNode(ValueTreeMapSet* self) { ValueTreeMapSetNode* node; assert(self); node = self->root; if(self->root != ValueTreeMapSetNull) { for(node = self->root; node->right != ValueTreeMapSetNull; node = node->right); } return node; } static ValueTreeMapSetNode* ValueTreeMapSetNextNode(ValueTreeMapSetNode* node) { ValueTreeMapSetNode* parent; assert(node); if(node->right != ValueTreeMapSetNull) { for(node = node->right; node->left != ValueTreeMapSetNull; node = node->left); } else { parent = node->parent; while(parent != ValueTreeMapSetNull && node == parent->right) { node = parent; parent = parent->parent; } node = parent; } return node; } static ValueTreeMapSetNode* ValueTreeMapSetPrevNode(ValueTreeMapSetNode* node) { ValueTreeMapSetNode* parent; assert(node); if(node->left != ValueTreeMapSetNull) { for(node = node->left; node->right != ValueTreeMapSetNull; node = node->right); } else { parent = node->parent; while(parent != ValueTreeMapSetNull && node == parent->left) { node = parent; parent = parent->parent; } node = parent; } return node; } AUTOC_STATIC ValueTreeMapEntry ValueTreeMapSetPeekLowest(ValueTreeMapSet* self) { ValueTreeMapSetNode* node; ValueTreeMapEntry result; assert(self); assert(!ValueTreeMapSetEmpty(self)); node = ValueTreeMapSetLowestNode(self); assert(node); assert(node != ValueTreeMapSetNull); ValueTreeMapEntryCopy(result,node->element); return result; } AUTOC_STATIC ValueTreeMapEntry ValueTreeMapSetPeekHighest(ValueTreeMapSet* self) { ValueTreeMapSetNode* node; ValueTreeMapEntry result; assert(self); assert(!ValueTreeMapSetEmpty(self)); node = ValueTreeMapSetHighestNode(self); assert(node); assert(node != ValueTreeMapSetNull); ValueTreeMapEntryCopy(result,node->element); return result; } AUTOC_STATIC void ValueTreeMapSetItCtorEx(ValueTreeMapSetIt* self, ValueTreeMapSet* tree, int ascending) { assert(self); assert(tree); self->node = (self->ascending = ascending) ? ValueTreeMapSetLowestNode(tree) : ValueTreeMapSetHighestNode(tree); self->start = 1; } AUTOC_STATIC int ValueTreeMapSetItMove(ValueTreeMapSetIt* self) { assert(self); if(self->start) { self->start = 0; } else { self->node = self->ascending ? ValueTreeMapSetNextNode(self->node) : ValueTreeMapSetPrevNode(self->node); } return self->node != ValueTreeMapSetNull; } static ValueTreeMapEntry* ValueTreeMapSetItGetRef(ValueTreeMapSetIt* self) { assert(self); assert(self->node); assert(self->node != ValueTreeMapSetNull); return &self->node->element; } AUTOC_STATIC ValueTreeMapEntry ValueTreeMapSetItGet(ValueTreeMapSetIt* self) { ValueTreeMapEntry result; assert(self); ValueTreeMapEntryCopy(result,*ValueTreeMapSetItGetRef(self)); return result; } void ValueTreeMapCtor(ValueTreeMap* self) { assert(self); ValueTreeMapSetCtor(&self->entries); } void ValueTreeMapDtor(ValueTreeMap* self) { assert(self); ValueTreeMapSetDtor(&self->entries); } static int ValueTreeMapPutEntryRef(ValueTreeMap* self, ValueTreeMapEntry* entry) { int absent; assert(self); assert(entry); absent = !ValueTreeMapContainsKey(self, entry->key); if(absent) ValueTreeMapSetPut(&self->entries, *entry); return absent; } void ValueTreeMapCopy(ValueTreeMap* dst,ValueTreeMap* src) { ValueTreeMapIt it; assert(src); assert(dst); ValueTreeMapCtor(dst); ValueTreeMapItCtor(&it, src); while(ValueTreeMapItMove(&it)) { ValueTreeMapEntry* e = ValueTreeMapItGetEntryRef(&it); ValueTreeMapPutEntryRef(dst, e); } } int ValueTreeMapEqual(ValueTreeMap* lt,ValueTreeMap* rt) { assert(lt); assert(rt); return ValueTreeMapSize(lt) == ValueTreeMapSize(rt) && ValueTreeMapContainsAllOf(lt, rt) && ValueTreeMapContainsAllOf(rt, lt); } size_t ValueTreeMapIdentify(ValueTreeMap* self) { assert(self); return ValueTreeMapSetIdentify(&self->entries); /* TODO : make use of the values' hashes */ } void ValueTreeMapPurge(ValueTreeMap* self) { assert(self); ValueTreeMapSetPurge(&self->entries); } size_t ValueTreeMapSize(ValueTreeMap* self) { assert(self); return ValueTreeMapSetSize(&self->entries); } int ValueTreeMapContainsKey(ValueTreeMap* self, Value key) { int result; ValueTreeMapEntry entry; assert(self); result = ValueTreeMapSetContains(&self->entries, entry = ValueTreeMapEntryKeyOnlyRef(&key)); ValueTreeMapEntryDtor(entry); return result; } Value ValueTreeMapGet(ValueTreeMap* self, Value key) { Value result; ValueTreeMapEntry entry, existing_entry; assert(self); assert(ValueTreeMapContainsKey(self, key)); existing_entry = ValueTreeMapSetGet(&self->entries, entry = ValueTreeMapEntryKeyOnlyRef(&key)); ValueCopy(result,existing_entry.value); ValueTreeMapEntryDtor(existing_entry); ValueTreeMapEntryDtor(entry); return result; } Value ValueTreeMapPeekLowestKey(ValueTreeMap* self) { Value result; ValueTreeMapSetNode* node; assert(self); assert(!ValueTreeMapEmpty(self)); node = ValueTreeMapSetLowestNode(&self->entries); assert(node); ValueCopy(result,node->element.key); return result; } Value ValueTreeMapPeekLowestElement(ValueTreeMap* self) { Value result; ValueTreeMapSetNode* node; assert(self); assert(!ValueTreeMapEmpty(self)); node = ValueTreeMapSetLowestNode(&self->entries); assert(node); ValueCopy(result,node->element.value); return result; } Value ValueTreeMapPeekHighestKey(ValueTreeMap* self) { Value result; ValueTreeMapSetNode* node; assert(self); assert(!ValueTreeMapEmpty(self)); node = ValueTreeMapSetHighestNode(&self->entries); assert(node); ValueCopy(result,node->element.key); return result; } Value ValueTreeMapPeekHighestElement(ValueTreeMap* self) { Value result; ValueTreeMapSetNode* node; assert(self); assert(!ValueTreeMapEmpty(self)); node = ValueTreeMapSetHighestNode(&self->entries); assert(node); ValueCopy(result,node->element.value); return result; } int ValueTreeMapPut(ValueTreeMap* self, Value key, Value value) { int result; ValueTreeMapEntry entry; assert(self); entry = ValueTreeMapEntryKeyValueRef(&key, &value); result = ValueTreeMapPutEntryRef(self, &entry); ValueTreeMapEntryDtor(entry); return result; } int ValueTreeMapReplace(ValueTreeMap* self, Value key, Value value) { int result; ValueTreeMapEntry entry; assert(self); entry = ValueTreeMapEntryKeyValueRef(&key, &value); result = ValueTreeMapSetReplace(&self->entries, entry); ValueTreeMapEntryDtor(entry); return result; } int ValueTreeMapRemove(ValueTreeMap* self, Value key) { int result; ValueTreeMapEntry entry; assert(self); result = ValueTreeMapSetRemove(&self->entries, entry = ValueTreeMapEntryKeyOnlyRef(&key)); ValueTreeMapEntryDtor(entry); return result; } void ValueTreeMapItCtorEx(ValueTreeMapIt* self, ValueTreeMap* map, int ascending) { assert(self); assert(map); ValueTreeMapSetItCtorEx(&self->it, &map->entries, ascending); } int ValueTreeMapItMove(ValueTreeMapIt* self) { assert(self); return ValueTreeMapSetItMove(&self->it); } Value ValueTreeMapItGetKey(ValueTreeMapIt* self) { ValueTreeMapEntry* e; Value key; assert(self); e = ValueTreeMapItGetEntryRef(self); ValueCopy(key,e->key); return key; } Value ValueTreeMapItGetElement(ValueTreeMapIt* self) { ValueTreeMapEntry* e; Value value; assert(self); e = ValueTreeMapItGetEntryRef(self); assert(e->flags & ValueTreeMapValidValue); ValueCopy(value,e->value); return value; } static ValueTreeMapEntry* ValueTreeMapItGetEntryRef(ValueTreeMapIt* self) { assert(self); return ValueTreeMapSetItGetRef(&self->it); } void ValueTreeMapTestCreate(void) { ValueTreeMap t; ValueTreeMapCtor(&t); TEST_EQUAL( ValueTreeMapSize(&t), 0 ); TEST_TRUE( ValueTreeMapEmpty(&t) ); ValueTreeMapDtor(&t); } void ValueTreeMapTestPurge(void) { ValueTreeMap t; ValueTreeMapCtor(&t); PUT(&t, 0, 0); TEST_FALSE( ValueTreeMapEmpty(&t) ); ValueTreeMapPurge(&t); TEST_TRUE( ValueTreeMapEmpty(&t) ); ValueTreeMapDtor(&t); } void ValueTreeMapTestEmpty(void) { ValueTreeMap t; ValueTreeMapCtor(&t); TEST_TRUE( ValueTreeMapEmpty(&t) ); PUT(&t, 1, -1); TEST_FALSE( ValueTreeMapEmpty(&t) ); ValueTreeMapDtor(&t); } void ValueTreeMapTestSize(void) { ValueTreeMap t; ValueTreeMapCtor(&t); TEST_TRUE( ValueTreeMapEmpty(&t) ); TEST_EQUAL( ValueTreeMapSize(&t), 0 ); PUT(&t, 1, -1); TEST_FALSE( ValueTreeMapEmpty(&t) ); TEST_EQUAL( ValueTreeMapSize(&t), 1 ); ValueTreeMapDtor(&t); } void ValueTreeMapTestCopy(void) { /* {i => -i} */ int i, c = 3; ValueTreeMap t; Value k; Value v; ValueTreeMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueTreeMap t2; ValueTreeMapCopy(&t2, &t); TEST_TRUE( ValueTreeMapEqual(&t2, &t) ); ValueTreeMapDtor(&t2); ValueTreeMapDtor(&t); } void ValueTreeMapTestEqual(void) { /* {i => -i} */ int i, c = 3; ValueTreeMap t; Value k; Value v; ValueTreeMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueTreeMap t2; ValueTreeMapCopy(&t2, &t); TEST_TRUE( ValueTreeMapEqual(&t2, &t) ); PUT(&t2, -1, 1); TEST_FALSE( ValueTreeMapEqual(&t2, &t) ); ValueTreeMapDtor(&t2); ValueTreeMapDtor(&t); } void ValueTreeMapTestContainsKey(void) { /* {i => -i} */ int i, c = 3; ValueTreeMap t; Value k; Value v; ValueTreeMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 0); TEST_FALSE( ValueTreeMapContainsKey(&t, k) ); ValueSet(k, 1); TEST_TRUE( ValueTreeMapContainsKey(&t, k) ); ValueDtor(k); ValueTreeMapDtor(&t); } void ValueTreeMapTestGet(void) { /* {i => -i} */ int i, c = 3; ValueTreeMap t; Value k; Value v; ValueTreeMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 3); TEST_TRUE( ValueTreeMapContainsKey(&t, k) ); v = ValueTreeMapGet(&t, k); TEST_EQUAL( ValueGet(v), -3 ); ValueDtor(v); ValueDtor(k); ValueTreeMapDtor(&t); } void ValueTreeMapTestPutNew(void) { /* {i => -i} */ int i, c = 3; ValueTreeMap t; Value k; Value v; ValueTreeMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 0); TEST_FALSE( ValueTreeMapContainsKey(&t, k) ); TEST_TRUE( ValueTreeMapPut(&t, k, k) ) ; ValueDtor(k); ValueTreeMapDtor(&t); } void ValueTreeMapTestPutExisting(void) { /* {i => -i} */ int i, c = 3; ValueTreeMap t; Value k; Value v; ValueTreeMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 1); TEST_TRUE( ValueTreeMapContainsKey(&t, k) ); TEST_FALSE( ValueTreeMapPut(&t, k, k) ) ; ValueDtor(k); ValueTreeMapDtor(&t); } void ValueTreeMapTestRemove(void) { /* {i => -i} */ int i, c = 3; ValueTreeMap t; Value k; Value v; ValueTreeMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 1); TEST_TRUE( ValueTreeMapContainsKey(&t, k) ); TEST_TRUE( ValueTreeMapRemove(&t, k) ) ; TEST_FALSE( ValueTreeMapContainsKey(&t, k) ); ValueDtor(k); ValueTreeMapDtor(&t); } void ValueTreeMapTestRemoveNone(void) { /* {i => -i} */ int i, c = 3; ValueTreeMap t; Value k; Value v; ValueTreeMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 0); TEST_FALSE( ValueTreeMapContainsKey(&t, k) ); TEST_FALSE( ValueTreeMapRemove(&t, k) ) ; TEST_FALSE( ValueTreeMapContainsKey(&t, k) ); ValueDtor(k); ValueTreeMapDtor(&t); } void ValueTreeMapTestReplace(void) { /* {i => -i} */ int i, c = 3; ValueTreeMap t; Value k; Value v; ValueTreeMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 1); TEST_TRUE( ValueTreeMapContainsKey(&t, k) ); TEST_TRUE( ValueTreeMapReplace(&t, k, k) ) ; TEST_TRUE( ValueTreeMapContainsKey(&t, k) ); ValueDtor(k); ValueTreeMapDtor(&t); } void ValueTreeMapTestReplaceNone(void) { /* {i => -i} */ int i, c = 3; ValueTreeMap t; Value k; Value v; ValueTreeMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 0); TEST_FALSE( ValueTreeMapContainsKey(&t, k) ); TEST_FALSE( ValueTreeMapReplace(&t, k, k) ) ; TEST_FALSE( ValueTreeMapContainsKey(&t, k) ); ValueDtor(k); ValueTreeMapDtor(&t); } void ValueTreeMapTestIterateAscending(void) { /* {i => -i} */ int i, c = 3; ValueTreeMap t; Value k; Value v; ValueTreeMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueTreeMapIt it; ValueTreeMapItCtor(&it, &t); while(ValueTreeMapItMove(&it)) { Value k; Value v; k = ValueTreeMapItGetKey(&it); v = ValueTreeMapItGetElement(&it); TEST_EQUAL( ValueGet(k), -ValueGet(v) ); ValueDtor(k); ValueDtor(v); } ValueTreeMapDtor(&t); } void ValueTreeMapTestIterateDescending(void) { /* {i => -i} */ int i, c = 3; ValueTreeMap t; Value k; Value v; ValueTreeMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueTreeMapIt it; ValueTreeMapItCtorEx(&it, &t, 0); while(ValueTreeMapItMove(&it)) { Value k; Value v; k = ValueTreeMapItGetKey(&it); v = ValueTreeMapItGetElement(&it); TEST_EQUAL( ValueGet(k), -ValueGet(v) ); ValueDtor(k); ValueDtor(v); } ValueTreeMapDtor(&t); } void ValueTreeMapRunTests(void) { fprintf(stdout, "* %s\n", "ValueTreeMap"); fflush(stdout); run_test("create", ValueTreeMapTestCreate); run_test("purge", ValueTreeMapTestPurge); run_test("empty", ValueTreeMapTestEmpty); run_test("size", ValueTreeMapTestSize); run_test("copy", ValueTreeMapTestCopy); run_test("equal", ValueTreeMapTestEqual); run_test("containsKey", ValueTreeMapTestContainsKey); run_test("get", ValueTreeMapTestGet); run_test("putNew", ValueTreeMapTestPutNew); run_test("putExisting", ValueTreeMapTestPutExisting); run_test("remove", ValueTreeMapTestRemove); run_test("removeNone", ValueTreeMapTestRemoveNone); run_test("replace", ValueTreeMapTestReplace); run_test("replaceNone", ValueTreeMapTestReplaceNone); run_test("iterateAscending", ValueTreeMapTestIterateAscending); run_test("iterateDescending", ValueTreeMapTestIterateDescending); fputs("\n", stdout); fflush(stdout); } #undef PUT #define PUT(t, k, v) {Value ek; Value ev; ValueCtorEx(ek, k); ValueCtorEx(ev, v); ValueHashMapPut(t, ek, ev); ValueDtor(ek); ValueDtor(ev);} #define ValueHashMapValidValue 1 #define ValueHashMapValidKey 2 #define ValueHashMapOwnedValue 4 #define ValueHashMapOwnedKey 8 static ValueHashMapEntry ValueHashMapEntryKeyOnlyRef(Value* key) { ValueHashMapEntry entry; entry.key = *key; entry.flags = ValueHashMapValidKey; return entry; } static ValueHashMapEntry ValueHashMapEntryKeyValueRef(Value* key, Value* value) { ValueHashMapEntry entry; entry.key = *key; entry.value = *value; entry.flags = (ValueHashMapValidKey | ValueHashMapValidValue); return entry; } #define ValueHashMapEntryIdentify(obj) ValueHashMapEntryIdentifyRef(&obj) static size_t ValueHashMapEntryIdentifyRef(ValueHashMapEntry* entry) { return ValueIdentify(entry->key); } #define ValueHashMapEntryEqual(lt, rt) ValueHashMapEntryEqualRef(<, &rt) static int ValueHashMapEntryEqualRef(ValueHashMapEntry* lt, ValueHashMapEntry* rt) { return ValueEqual(lt->key,rt->key); } #define ValueHashMapEntryCopy(dst, src) ValueHashMapEntryCopyRef(&dst, &src) static void ValueHashMapEntryCopyRef(ValueHashMapEntry* dst, ValueHashMapEntry* src) { assert(src->flags & ValueHashMapValidKey); dst->flags = (ValueHashMapValidKey | ValueHashMapOwnedKey); ValueCopy(dst->key,src->key); if(src->flags & ValueHashMapValidValue) { dst->flags |= (ValueHashMapValidValue | ValueHashMapOwnedValue); ValueCopy(dst->value,src->value); } } #define ValueHashMapEntryDtor(obj) ValueHashMapEntryDtorRef(&obj) static void ValueHashMapEntryDtorRef(ValueHashMapEntry* entry) { assert(entry->flags & ValueHashMapValidKey); if(entry->flags & ValueHashMapOwnedKey) ValueDtor(entry->key); if(entry->flags & ValueHashMapValidValue && entry->flags & ValueHashMapOwnedValue) ValueDtor(entry->value); } static ValueHashMapEntry* ValueHashMapItGetEntryRef(ValueHashMapIt*); static int ValueHashMapContainsAllOf(ValueHashMap* self, ValueHashMap* other) { ValueHashMapIt it; ValueHashMapItCtor(&it, self); while(ValueHashMapItMove(&it)) { int found = 0; ValueHashMapEntry* e = ValueHashMapItGetEntryRef(&it); if(ValueHashMapContainsKey(other, e->key)) { Value other_value = ValueHashMapGet(other, e->key); found = ValueEqual(e->value,other_value); ValueDtor(other_value); } if(!found) return 0; } return 1; } #define _ValueHashMapSetCtor(self) ValueHashMapSetCtor(&self) #define _ValueHashMapSetDtor(self) ValueHashMapSetDtor(&self) #define _ValueHashMapSetIdentify(self) ValueHashMapSetIdentify(&self) #define _ValueHashMapSetCopy(dst,src) ValueHashMapSetCopy(&dst,&src) #define _ValueHashMapSetEqual(lt,rt) ValueHashMapSetEqual(<,&rt) #define _ValueHashMapSetLess(lt,rt) ValueHashMapSetLess(<,&rt) AUTOC_STATIC void ValueHashMapSetCtor(ValueHashMapSet*); AUTOC_STATIC void ValueHashMapSetDtor(ValueHashMapSet*); AUTOC_STATIC void ValueHashMapSetCopy(ValueHashMapSet*,ValueHashMapSet*); AUTOC_STATIC int ValueHashMapSetEqual(ValueHashMapSet*,ValueHashMapSet*); AUTOC_STATIC size_t ValueHashMapSetIdentify(ValueHashMapSet*); AUTOC_STATIC void ValueHashMapSetPurge(ValueHashMapSet*); AUTOC_STATIC int ValueHashMapSetContains(ValueHashMapSet*, ValueHashMapEntry); AUTOC_STATIC ValueHashMapEntry ValueHashMapSetGet(ValueHashMapSet*, ValueHashMapEntry); AUTOC_STATIC size_t ValueHashMapSetSize(ValueHashMapSet*); #define ValueHashMapSetEmpty(self) (ValueHashMapSetSize(self) == 0) AUTOC_STATIC int ValueHashMapSetPut(ValueHashMapSet*, ValueHashMapEntry); AUTOC_STATIC int ValueHashMapSetReplace(ValueHashMapSet*, ValueHashMapEntry); AUTOC_STATIC int ValueHashMapSetRemove(ValueHashMapSet*, ValueHashMapEntry); AUTOC_STATIC void ValueHashMapSetExclude(ValueHashMapSet*, ValueHashMapSet*); AUTOC_STATIC void ValueHashMapSetRetain(ValueHashMapSet*, ValueHashMapSet*); AUTOC_STATIC void ValueHashMapSetInclude(ValueHashMapSet*, ValueHashMapSet*); AUTOC_STATIC void ValueHashMapSetInvert(ValueHashMapSet*, ValueHashMapSet*); AUTOC_STATIC void ValueHashMapSetItCtor(ValueHashMapSetIt*, ValueHashMapSet*); AUTOC_STATIC int ValueHashMapSetItMove(ValueHashMapSetIt*); AUTOC_STATIC ValueHashMapEntry ValueHashMapSetItGet(ValueHashMapSetIt*); #define _ValueHashMapSetListCtor(self) ValueHashMapSetListCtor(&self) #define _ValueHashMapSetListDtor(self) ValueHashMapSetListDtor(&self) #define _ValueHashMapSetListIdentify(self) ValueHashMapSetListIdentify(&self) #define _ValueHashMapSetListCopy(dst,src) ValueHashMapSetListCopy(&dst,&src) #define _ValueHashMapSetListEqual(lt,rt) ValueHashMapSetListEqual(<,&rt) #define _ValueHashMapSetListLess(lt,rt) ValueHashMapSetListLess(<,&rt) AUTOC_STATIC void ValueHashMapSetListItCtor(ValueHashMapSetListIt*, ValueHashMapSetList*); AUTOC_STATIC int ValueHashMapSetListItMove(ValueHashMapSetListIt*); AUTOC_STATIC ValueHashMapEntry ValueHashMapSetListItGet(ValueHashMapSetListIt*); AUTOC_STATIC void ValueHashMapSetListCtor(ValueHashMapSetList*); AUTOC_STATIC void ValueHashMapSetListDtor(ValueHashMapSetList*); AUTOC_STATIC void ValueHashMapSetListCopy(ValueHashMapSetList*,ValueHashMapSetList*); AUTOC_STATIC int ValueHashMapSetListEqual(ValueHashMapSetList*,ValueHashMapSetList*); AUTOC_STATIC size_t ValueHashMapSetListIdentify(ValueHashMapSetList*); AUTOC_STATIC void ValueHashMapSetListPurge(ValueHashMapSetList*); AUTOC_STATIC ValueHashMapEntry ValueHashMapSetListPeek(ValueHashMapSetList*); AUTOC_STATIC ValueHashMapEntry ValueHashMapSetListPop(ValueHashMapSetList*); AUTOC_STATIC void ValueHashMapSetListPush(ValueHashMapSetList*, ValueHashMapEntry); AUTOC_STATIC int ValueHashMapSetListContains(ValueHashMapSetList*, ValueHashMapEntry); AUTOC_STATIC ValueHashMapEntry ValueHashMapSetListFind(ValueHashMapSetList*, ValueHashMapEntry); #define ValueHashMapSetListReplace(self, with) ValueHashMapSetListReplaceEx(self, with, 1) #define ValueHashMapSetListReplaceAll(self, with) ValueHashMapSetListReplaceEx(self, with, -1) AUTOC_STATIC int ValueHashMapSetListReplaceEx(ValueHashMapSetList*, ValueHashMapEntry, int); #define ValueHashMapSetListRemove(self, what) ValueHashMapSetListRemoveEx(self, what, 1) #define ValueHashMapSetListRemoveAll(self, what) ValueHashMapSetListRemoveEx(self, what, -1) AUTOC_STATIC int ValueHashMapSetListRemoveEx(ValueHashMapSetList*, ValueHashMapEntry, int); AUTOC_STATIC size_t ValueHashMapSetListSize(ValueHashMapSetList*); #define ValueHashMapSetListEmpty(self) (ValueHashMapSetListSize(self) == 0) static ValueHashMapEntry* ValueHashMapSetListItGetRef(ValueHashMapSetListIt*); AUTOC_STATIC void ValueHashMapSetListCtor(ValueHashMapSetList* self) { assert(self); self->head_node = NULL; self->node_count = 0; } AUTOC_STATIC void ValueHashMapSetListDtor(ValueHashMapSetList* self) { ValueHashMapSetListNode* node; assert(self); node = self->head_node; while(node) { ValueHashMapSetListNode* this_node = node; node = node->next_node; ValueHashMapEntryDtor(this_node->element); free(this_node); } } AUTOC_STATIC void ValueHashMapSetListCopy(ValueHashMapSetList* dst,ValueHashMapSetList* src) { ValueHashMapSetListIt it; size_t index, size; ValueHashMapEntry** elements; assert(src); assert(dst); ValueHashMapSetListCtor(dst); if(!ValueHashMapSetListEmpty(src)) { /* List is a LIFO type container therefore the insertion order into the destination container should be reversed */ elements = (ValueHashMapEntry**)malloc((size = ValueHashMapSetListSize(src))*sizeof(ValueHashMapEntry*)); assert(elements); index = 0; ValueHashMapSetListItCtor(&it, src); while(ValueHashMapSetListItMove(&it)) { assert(index < size); elements[index++] = ValueHashMapSetListItGetRef(&it); } for(index = size; index > 0; --index) ValueHashMapSetListPush(dst, *elements[index-1]); /* Be careful not to run into the underflow of the unsigned integer type */ free(elements); } } AUTOC_STATIC int ValueHashMapSetListEqual(ValueHashMapSetList* lt,ValueHashMapSetList* rt) { if(ValueHashMapSetListSize(lt) == ValueHashMapSetListSize(rt)) { ValueHashMapSetListIt lit, rit; ValueHashMapSetListItCtor(&lit, lt); ValueHashMapSetListItCtor(&rit, rt); while(ValueHashMapSetListItMove(&lit) && ValueHashMapSetListItMove(&rit)) { int equal; ValueHashMapEntry* le; ValueHashMapEntry* re; le = ValueHashMapSetListItGetRef(&lit); re = ValueHashMapSetListItGetRef(&rit); equal = ValueHashMapEntryEqual(*le,*re); if(!equal) return 0; } return 1; } else return 0; } AUTOC_STATIC size_t ValueHashMapSetListIdentify(ValueHashMapSetList* self) { ValueHashMapSetListNode* node; size_t result = 0; assert(self); for(node = self->head_node; node != NULL; node = node->next_node) { result ^= ValueHashMapEntryIdentify(node->element); result = AUTOC_RCYCLE(result); } return result; } AUTOC_STATIC void ValueHashMapSetListPurge(ValueHashMapSetList* self) { ValueHashMapSetListDtor(self); ValueHashMapSetListCtor(self); } AUTOC_STATIC ValueHashMapEntry ValueHashMapSetListPeek(ValueHashMapSetList* self) { ValueHashMapEntry result; assert(self); assert(!ValueHashMapSetListEmpty(self)); ValueHashMapEntryCopy(result,self->head_node->element); return result; } AUTOC_STATIC ValueHashMapEntry ValueHashMapSetListPop(ValueHashMapSetList* self) { ValueHashMapSetListNode* node; ValueHashMapEntry result; assert(self); assert(!ValueHashMapSetListEmpty(self)); node = self->head_node; result = node->element; self->head_node = self->head_node->next_node; --self->node_count; free(node); return result; } AUTOC_STATIC void ValueHashMapSetListPush(ValueHashMapSetList* self, ValueHashMapEntry element) { ValueHashMapSetListNode* node; assert(self); node = (ValueHashMapSetListNode*)malloc(sizeof(ValueHashMapSetListNode)); assert(node); ValueHashMapEntryCopy(node->element,element); node->next_node = self->head_node; self->head_node = node; ++self->node_count; } AUTOC_STATIC int ValueHashMapSetListContains(ValueHashMapSetList* self, ValueHashMapEntry what) { ValueHashMapSetListNode* node; int found = 0; assert(self); node = self->head_node; while(node) { if(ValueHashMapEntryEqual(node->element,what)) { found = 1; break; } node = node->next_node; } return found; } AUTOC_STATIC ValueHashMapEntry ValueHashMapSetListFind(ValueHashMapSetList* self, ValueHashMapEntry what) { ValueHashMapSetListNode* node; assert(self); assert(ValueHashMapSetListContains(self, what)); node = self->head_node; while(node) { if(ValueHashMapEntryEqual(node->element,what)) { ValueHashMapEntry result; ValueHashMapEntryCopy(result,node->element); return result; } node = node->next_node; } abort(); } /* FIXME: for the generality's sake there should be both `what` and `with` values This is not achievable without breaking the interface, however, therefore defer this change to the major version bump */ AUTOC_STATIC int ValueHashMapSetListReplaceEx(ValueHashMapSetList* self, ValueHashMapEntry with, int count) { ValueHashMapSetListNode* node; int replaced = 0; assert(self); if(count == 0) return 0; node = self->head_node; while(node) { if(ValueHashMapEntryEqual(node->element,with)) { ValueHashMapEntryDtor(node->element); ValueHashMapEntryCopy(node->element,with); ++replaced; if(count > 0 && replaced >= count) break; } node = node->next_node; } return replaced; } AUTOC_STATIC int ValueHashMapSetListRemoveEx(ValueHashMapSetList* self, ValueHashMapEntry what, int count) { ValueHashMapSetListNode *node, *prev_node; int removed = 0; assert(self); if(count == 0) return 0; node = self->head_node; prev_node = NULL; while(node) { if(ValueHashMapEntryEqual(node->element,what)) { ValueHashMapSetListNode* this_node; if(prev_node) { this_node = prev_node->next_node = node->next_node; } else { this_node = self->head_node = node->next_node; } ++removed; --self->node_count; ValueHashMapEntryDtor(node->element); free(node); node = this_node; if(count > 0 && removed >= count) break; } else { prev_node = node; node = node->next_node; } } return removed; } AUTOC_STATIC size_t ValueHashMapSetListSize(ValueHashMapSetList* self) { assert(self); return self->node_count; } AUTOC_STATIC void ValueHashMapSetListItCtor(ValueHashMapSetListIt* self, ValueHashMapSetList* list) { assert(self); assert(list); self->start = 1; self->list = list; } AUTOC_STATIC int ValueHashMapSetListItMove(ValueHashMapSetListIt* self) { assert(self); if(self->start) { self->this_node = self->list->head_node; self->start = 0; } else { self->this_node = self->this_node ? self->this_node->next_node : NULL; } return self->this_node != NULL; } AUTOC_STATIC ValueHashMapEntry ValueHashMapSetListItGet(ValueHashMapSetListIt* self) { ValueHashMapEntry result; assert(self); assert(self->this_node); ValueHashMapEntryCopy(result,self->this_node->element); return result; } static ValueHashMapEntry* ValueHashMapSetListItGetRef(ValueHashMapSetListIt* self) { assert(self); assert(self->this_node); return &self->this_node->element; } static ValueHashMapEntry* ValueHashMapSetItGetRef(ValueHashMapSetIt*); static int ValueHashMapSetContainsAllOf(ValueHashMapSet* self, ValueHashMapSet* other) { ValueHashMapSetIt it; ValueHashMapSetItCtor(&it, self); while(ValueHashMapSetItMove(&it)) { if(!ValueHashMapSetContains(other, *ValueHashMapSetItGetRef(&it))) return 0; } return 1; } AUTOC_STATIC void ValueHashMapSetCopy(ValueHashMapSet* dst,ValueHashMapSet* src) { ValueHashMapSetIt it; assert(src); assert(dst); ValueHashMapSetCtor(dst); ValueHashMapSetItCtor(&it, src); while(ValueHashMapSetItMove(&it)) ValueHashMapSetPut(dst, *ValueHashMapSetItGetRef(&it)); } AUTOC_STATIC int ValueHashMapSetEqual(ValueHashMapSet* lt,ValueHashMapSet* rt) { assert(lt); assert(rt); return ValueHashMapSetSize(lt) == ValueHashMapSetSize(rt) && ValueHashMapSetContainsAllOf(lt, rt) && ValueHashMapSetContainsAllOf(rt, lt); } AUTOC_STATIC size_t ValueHashMapSetIdentify(ValueHashMapSet* self) { ValueHashMapSetIt it; size_t result = 0; assert(self); ValueHashMapSetItCtor(&it, self); while(ValueHashMapSetItMove(&it)) { ValueHashMapEntry* e = ValueHashMapSetItGetRef(&it); result ^= ValueHashMapEntryIdentify(*e); result = AUTOC_RCYCLE(result); } return result; } AUTOC_STATIC size_t ValueHashMapSetSize(ValueHashMapSet* self) { assert(self); return self->size; } AUTOC_STATIC void ValueHashMapSetInclude(ValueHashMapSet* self, ValueHashMapSet* other) { ValueHashMapSetIt it; assert(self); assert(other); ValueHashMapSetItCtor(&it, other); while(ValueHashMapSetItMove(&it)) ValueHashMapSetPut(self, *ValueHashMapSetItGetRef(&it)); } AUTOC_STATIC void ValueHashMapSetRetain(ValueHashMapSet* self, ValueHashMapSet* other) { ValueHashMapSetIt it; ValueHashMapSet set; assert(self); assert(other); ValueHashMapSetCtor(&set); ValueHashMapSetItCtor(&it, self); while(ValueHashMapSetItMove(&it)) { ValueHashMapEntry* e = ValueHashMapSetItGetRef(&it); assert(e); if(ValueHashMapSetContains(other, *e)) ValueHashMapSetPut(&set, *e); } ValueHashMapSetDtor(self); *self = set; } AUTOC_STATIC void ValueHashMapSetInvert(ValueHashMapSet* self, ValueHashMapSet* other) { ValueHashMapSetIt it; ValueHashMapSet set; assert(self); assert(other); ValueHashMapSetCtor(&set); ValueHashMapSetItCtor(&it, self); while(ValueHashMapSetItMove(&it)) { ValueHashMapEntry* e = ValueHashMapSetItGetRef(&it); if(!ValueHashMapSetContains(other, *e)) ValueHashMapSetPut(&set, *e); } ValueHashMapSetItCtor(&it, other); while(ValueHashMapSetItMove(&it)) { ValueHashMapEntry* e = ValueHashMapSetItGetRef(&it); if(!ValueHashMapSetContains(self, *e)) ValueHashMapSetPut(&set, *e); } ValueHashMapSetDtor(self); *self = set; } AUTOC_STATIC void ValueHashMapSetExclude(ValueHashMapSet* self, ValueHashMapSet* other) { ValueHashMapSetIt it; assert(self); assert(other); ValueHashMapSetItCtor(&it, other); while(ValueHashMapSetItMove(&it)) ValueHashMapSetRemove(self, *ValueHashMapSetItGetRef(&it)); } static void ValueHashMapSetRehash(ValueHashMapSet* self) { ValueHashMapSetList* buckets; size_t index, bucket_count, size, fill; assert(self); assert(self->min_fill > 0); assert(self->max_fill > 0); assert(self->min_fill < self->max_fill); assert(self->min_bucket_count > 0); if(self->buckets) { if(self->min_size < self->size && self->size < self->max_size) return; fill = (size_t)((float)self->size/self->bucket_count*100); if(fill > self->max_fill) { bucket_count = (size_t)((float)self->bucket_count/100*self->capacity_multiplier); } else if(fill < self->min_fill && self->bucket_count > self->min_bucket_count) { bucket_count = (size_t)((float)self->bucket_count/self->capacity_multiplier*100); if(bucket_count < self->min_bucket_count) bucket_count = self->min_bucket_count; } else return; size = self->size; self->min_size = (size_t)((float)self->min_fill/100*size); self->max_size = (size_t)((float)self->max_fill/100*size); } else { bucket_count = self->min_bucket_count; size = 0; } buckets = (ValueHashMapSetList*)malloc(bucket_count*sizeof(ValueHashMapSetList)); assert(buckets); for(index = 0; index < bucket_count; ++index) { ValueHashMapSetListCtor(&buckets[index]); } if(self->buckets) { ValueHashMapSetIt it; ValueHashMapSetItCtor(&it, self); while(ValueHashMapSetItMove(&it)) { ValueHashMapSetList* bucket; ValueHashMapEntry element = ValueHashMapSetItGet(&it); bucket = &buckets[ValueHashMapEntryIdentify(element) % bucket_count]; ValueHashMapSetListPush(bucket, element); ValueHashMapEntryDtor(element); } ValueHashMapSetDtor(self); } self->buckets = buckets; self->bucket_count = bucket_count; self->size = size; } AUTOC_STATIC void ValueHashMapSetCtor(ValueHashMapSet* self) { assert(self); self->min_bucket_count = 16; self->min_fill = 20; self->max_fill = 80; self->min_size = (size_t)((float)self->min_fill/100*self->min_bucket_count); self->max_size = (size_t)((float)self->max_fill/100*self->min_bucket_count); self->capacity_multiplier = 200; self->buckets = NULL; ValueHashMapSetRehash(self); } AUTOC_STATIC void ValueHashMapSetDtor(ValueHashMapSet* self) { size_t i; assert(self); for(i = 0; i < self->bucket_count; ++i) { ValueHashMapSetListDtor(&self->buckets[i]); } free(self->buckets); } AUTOC_STATIC void ValueHashMapSetPurge(ValueHashMapSet* self) { assert(self); ValueHashMapSetDtor(self); self->buckets = NULL; ValueHashMapSetRehash(self); } AUTOC_STATIC int ValueHashMapSetContains(ValueHashMapSet* self, ValueHashMapEntry element) { assert(self); return ValueHashMapSetListContains(&self->buckets[ValueHashMapEntryIdentify(element) % self->bucket_count], element); } AUTOC_STATIC ValueHashMapEntry ValueHashMapSetGet(ValueHashMapSet* self, ValueHashMapEntry element) { ValueHashMapEntry result; assert(self); assert(ValueHashMapSetContains(self, element)); result = ValueHashMapSetListFind(&self->buckets[ValueHashMapEntryIdentify(element) % self->bucket_count], element); return result; } AUTOC_STATIC int ValueHashMapSetPut(ValueHashMapSet* self, ValueHashMapEntry element) { ValueHashMapSetList* bucket; assert(self); bucket = &self->buckets[ValueHashMapEntryIdentify(element) % self->bucket_count]; if(!ValueHashMapSetListContains(bucket, element)) { ValueHashMapSetListPush(bucket, element); ++self->size; ValueHashMapSetRehash(self); return 1; } return 0; } AUTOC_STATIC int ValueHashMapSetReplace(ValueHashMapSet* self, ValueHashMapEntry element) { ValueHashMapSetList* bucket; assert(self); bucket = &self->buckets[ValueHashMapEntryIdentify(element) % self->bucket_count]; return ValueHashMapSetListReplace(bucket, element); } AUTOC_STATIC int ValueHashMapSetRemove(ValueHashMapSet* self, ValueHashMapEntry element) { ValueHashMapSetList* bucket; assert(self); bucket = &self->buckets[ValueHashMapEntryIdentify(element) % self->bucket_count]; if(ValueHashMapSetListRemove(bucket, element)) { --self->size; ValueHashMapSetRehash(self); return 1; } return 0; } AUTOC_STATIC void ValueHashMapSetItCtor(ValueHashMapSetIt* self, ValueHashMapSet* set) { assert(self); self->set = set; self->bucket_index = self->set->bucket_count; } AUTOC_STATIC int ValueHashMapSetItMove(ValueHashMapSetIt* self) { assert(self); if(self->bucket_index >= self->set->bucket_count) ValueHashMapSetListItCtor(&self->it, &self->set->buckets[self->bucket_index = 0]); if(ValueHashMapSetListItMove(&self->it)) return 1; while(++self->bucket_index < self->set->bucket_count) { ValueHashMapSetListItCtor(&self->it, &self->set->buckets[self->bucket_index]); if(ValueHashMapSetListItMove(&self->it)) return 1; } return 0; } AUTOC_STATIC ValueHashMapEntry ValueHashMapSetItGet(ValueHashMapSetIt* self) { assert(self); return ValueHashMapSetListItGet(&self->it); } static ValueHashMapEntry* ValueHashMapSetItGetRef(ValueHashMapSetIt* self) { assert(self); return ValueHashMapSetListItGetRef(&self->it); } void ValueHashMapCtor(ValueHashMap* self) { assert(self); ValueHashMapSetCtor(&self->entries); } void ValueHashMapDtor(ValueHashMap* self) { assert(self); ValueHashMapSetDtor(&self->entries); } static int ValueHashMapPutEntryRef(ValueHashMap* self, ValueHashMapEntry* entry) { int absent; assert(self); assert(entry); absent = !ValueHashMapContainsKey(self, entry->key); if(absent) ValueHashMapSetPut(&self->entries, *entry); return absent; } void ValueHashMapCopy(ValueHashMap* dst,ValueHashMap* src) { ValueHashMapIt it; assert(src); assert(dst); ValueHashMapCtor(dst); ValueHashMapItCtor(&it, src); while(ValueHashMapItMove(&it)) { ValueHashMapEntry* e = ValueHashMapItGetEntryRef(&it); ValueHashMapPutEntryRef(dst, e); } } int ValueHashMapEqual(ValueHashMap* lt,ValueHashMap* rt) { assert(lt); assert(rt); return ValueHashMapSize(lt) == ValueHashMapSize(rt) && ValueHashMapContainsAllOf(lt, rt) && ValueHashMapContainsAllOf(rt, lt); } size_t ValueHashMapIdentify(ValueHashMap* self) { assert(self); return ValueHashMapSetIdentify(&self->entries); /* TODO : make use of the values' hashes */ } void ValueHashMapPurge(ValueHashMap* self) { assert(self); ValueHashMapSetPurge(&self->entries); } size_t ValueHashMapSize(ValueHashMap* self) { assert(self); return ValueHashMapSetSize(&self->entries); } int ValueHashMapContainsKey(ValueHashMap* self, Value key) { int result; ValueHashMapEntry entry; assert(self); result = ValueHashMapSetContains(&self->entries, entry = ValueHashMapEntryKeyOnlyRef(&key)); ValueHashMapEntryDtor(entry); return result; } Value ValueHashMapGet(ValueHashMap* self, Value key) { Value result; ValueHashMapEntry entry, existing_entry; assert(self); assert(ValueHashMapContainsKey(self, key)); existing_entry = ValueHashMapSetGet(&self->entries, entry = ValueHashMapEntryKeyOnlyRef(&key)); ValueCopy(result,existing_entry.value); ValueHashMapEntryDtor(existing_entry); ValueHashMapEntryDtor(entry); return result; } int ValueHashMapPut(ValueHashMap* self, Value key, Value value) { int result; ValueHashMapEntry entry; assert(self); entry = ValueHashMapEntryKeyValueRef(&key, &value); result = ValueHashMapPutEntryRef(self, &entry); ValueHashMapEntryDtor(entry); return result; } int ValueHashMapReplace(ValueHashMap* self, Value key, Value value) { int result; ValueHashMapEntry entry; assert(self); entry = ValueHashMapEntryKeyValueRef(&key, &value); result = ValueHashMapSetReplace(&self->entries, entry); ValueHashMapEntryDtor(entry); return result; } int ValueHashMapRemove(ValueHashMap* self, Value key) { int result; ValueHashMapEntry entry; assert(self); result = ValueHashMapSetRemove(&self->entries, entry = ValueHashMapEntryKeyOnlyRef(&key)); ValueHashMapEntryDtor(entry); return result; } void ValueHashMapItCtor(ValueHashMapIt* self, ValueHashMap* map) { assert(self); assert(map); ValueHashMapSetItCtor(&self->it, &map->entries); } int ValueHashMapItMove(ValueHashMapIt* self) { assert(self); return ValueHashMapSetItMove(&self->it); } Value ValueHashMapItGetKey(ValueHashMapIt* self) { ValueHashMapEntry* e; Value key; assert(self); e = ValueHashMapItGetEntryRef(self); ValueCopy(key,e->key); return key; } Value ValueHashMapItGetElement(ValueHashMapIt* self) { ValueHashMapEntry* e; Value value; assert(self); e = ValueHashMapItGetEntryRef(self); assert(e->flags & ValueHashMapValidValue); ValueCopy(value,e->value); return value; } static ValueHashMapEntry* ValueHashMapItGetEntryRef(ValueHashMapIt* self) { assert(self); return ValueHashMapSetItGetRef(&self->it); } void ValueHashMapTestCreate(void) { ValueHashMap t; ValueHashMapCtor(&t); TEST_EQUAL( ValueHashMapSize(&t), 0 ); TEST_TRUE( ValueHashMapEmpty(&t) ); ValueHashMapDtor(&t); } void ValueHashMapTestPurge(void) { ValueHashMap t; ValueHashMapCtor(&t); PUT(&t, 0, 0); TEST_FALSE( ValueHashMapEmpty(&t) ); ValueHashMapPurge(&t); TEST_TRUE( ValueHashMapEmpty(&t) ); ValueHashMapDtor(&t); } void ValueHashMapTestEmpty(void) { ValueHashMap t; ValueHashMapCtor(&t); TEST_TRUE( ValueHashMapEmpty(&t) ); PUT(&t, 1, -1); TEST_FALSE( ValueHashMapEmpty(&t) ); ValueHashMapDtor(&t); } void ValueHashMapTestSize(void) { ValueHashMap t; ValueHashMapCtor(&t); TEST_TRUE( ValueHashMapEmpty(&t) ); TEST_EQUAL( ValueHashMapSize(&t), 0 ); PUT(&t, 1, -1); TEST_FALSE( ValueHashMapEmpty(&t) ); TEST_EQUAL( ValueHashMapSize(&t), 1 ); ValueHashMapDtor(&t); } void ValueHashMapTestCopy(void) { /* {i => -i} */ int i, c = 3; ValueHashMap t; Value k; Value v; ValueHashMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueHashMap t2; ValueHashMapCopy(&t2, &t); TEST_TRUE( ValueHashMapEqual(&t2, &t) ); ValueHashMapDtor(&t2); ValueHashMapDtor(&t); } void ValueHashMapTestEqual(void) { /* {i => -i} */ int i, c = 3; ValueHashMap t; Value k; Value v; ValueHashMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueHashMap t2; ValueHashMapCopy(&t2, &t); TEST_TRUE( ValueHashMapEqual(&t2, &t) ); PUT(&t2, -1, 1); TEST_FALSE( ValueHashMapEqual(&t2, &t) ); ValueHashMapDtor(&t2); ValueHashMapDtor(&t); } void ValueHashMapTestContainsKey(void) { /* {i => -i} */ int i, c = 3; ValueHashMap t; Value k; Value v; ValueHashMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 0); TEST_FALSE( ValueHashMapContainsKey(&t, k) ); ValueSet(k, 1); TEST_TRUE( ValueHashMapContainsKey(&t, k) ); ValueDtor(k); ValueHashMapDtor(&t); } void ValueHashMapTestGet(void) { /* {i => -i} */ int i, c = 3; ValueHashMap t; Value k; Value v; ValueHashMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 3); TEST_TRUE( ValueHashMapContainsKey(&t, k) ); v = ValueHashMapGet(&t, k); TEST_EQUAL( ValueGet(v), -3 ); ValueDtor(v); ValueDtor(k); ValueHashMapDtor(&t); } void ValueHashMapTestPutNew(void) { /* {i => -i} */ int i, c = 3; ValueHashMap t; Value k; Value v; ValueHashMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 0); TEST_FALSE( ValueHashMapContainsKey(&t, k) ); TEST_TRUE( ValueHashMapPut(&t, k, k) ) ; ValueDtor(k); ValueHashMapDtor(&t); } void ValueHashMapTestPutExisting(void) { /* {i => -i} */ int i, c = 3; ValueHashMap t; Value k; Value v; ValueHashMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 1); TEST_TRUE( ValueHashMapContainsKey(&t, k) ); TEST_FALSE( ValueHashMapPut(&t, k, k) ) ; ValueDtor(k); ValueHashMapDtor(&t); } void ValueHashMapTestRemove(void) { /* {i => -i} */ int i, c = 3; ValueHashMap t; Value k; Value v; ValueHashMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 1); TEST_TRUE( ValueHashMapContainsKey(&t, k) ); TEST_TRUE( ValueHashMapRemove(&t, k) ) ; TEST_FALSE( ValueHashMapContainsKey(&t, k) ); ValueDtor(k); ValueHashMapDtor(&t); } void ValueHashMapTestRemoveNone(void) { /* {i => -i} */ int i, c = 3; ValueHashMap t; Value k; Value v; ValueHashMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 0); TEST_FALSE( ValueHashMapContainsKey(&t, k) ); TEST_FALSE( ValueHashMapRemove(&t, k) ) ; TEST_FALSE( ValueHashMapContainsKey(&t, k) ); ValueDtor(k); ValueHashMapDtor(&t); } void ValueHashMapTestReplace(void) { /* {i => -i} */ int i, c = 3; ValueHashMap t; Value k; Value v; ValueHashMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 1); TEST_TRUE( ValueHashMapContainsKey(&t, k) ); TEST_TRUE( ValueHashMapReplace(&t, k, k) ) ; TEST_TRUE( ValueHashMapContainsKey(&t, k) ); ValueDtor(k); ValueHashMapDtor(&t); } void ValueHashMapTestReplaceNone(void) { /* {i => -i} */ int i, c = 3; ValueHashMap t; Value k; Value v; ValueHashMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueCtor(k); ValueSet(k, 0); TEST_FALSE( ValueHashMapContainsKey(&t, k) ); TEST_FALSE( ValueHashMapReplace(&t, k, k) ) ; TEST_FALSE( ValueHashMapContainsKey(&t, k) ); ValueDtor(k); ValueHashMapDtor(&t); } void ValueHashMapTestIterate(void) { /* {i => -i} */ int i, c = 3; ValueHashMap t; Value k; Value v; ValueHashMapCtor(&t); for(i = 1; i <= c; i++) { PUT(&t, i, -i); } ValueHashMapIt it; ValueHashMapItCtor(&it, &t); while(ValueHashMapItMove(&it)) { Value k; Value v; k = ValueHashMapItGetKey(&it); v = ValueHashMapItGetElement(&it); TEST_EQUAL( ValueGet(k), -ValueGet(v) ); ValueDtor(k); ValueDtor(v); } ValueHashMapDtor(&t); } void ValueHashMapRunTests(void) { fprintf(stdout, "* %s\n", "ValueHashMap"); fflush(stdout); run_test("create", ValueHashMapTestCreate); run_test("purge", ValueHashMapTestPurge); run_test("empty", ValueHashMapTestEmpty); run_test("size", ValueHashMapTestSize); run_test("copy", ValueHashMapTestCopy); run_test("equal", ValueHashMapTestEqual); run_test("containsKey", ValueHashMapTestContainsKey); run_test("get", ValueHashMapTestGet); run_test("putNew", ValueHashMapTestPutNew); run_test("putExisting", ValueHashMapTestPutExisting); run_test("remove", ValueHashMapTestRemove); run_test("removeNone", ValueHashMapTestRemoveNone); run_test("replace", ValueHashMapTestReplace); run_test("replaceNone", ValueHashMapTestReplaceNone); run_test("iterate", ValueHashMapTestIterate); fputs("\n", stdout); fflush(stdout); } #undef PUT #define PUT(t, v) {Value e; ValueCtorEx(e, v); ValueTreeSetPut(t, e); ValueDtor(e);} static Value* ValueTreeSetItGetRef(ValueTreeSetIt*); static int ValueTreeSetContainsAllOf(ValueTreeSet* self, ValueTreeSet* other) { ValueTreeSetIt it; ValueTreeSetItCtor(&it, self); while(ValueTreeSetItMove(&it)) { if(!ValueTreeSetContains(other, *ValueTreeSetItGetRef(&it))) return 0; } return 1; } void ValueTreeSetCopy(ValueTreeSet* dst,ValueTreeSet* src) { ValueTreeSetIt it; assert(src); assert(dst); ValueTreeSetCtor(dst); ValueTreeSetItCtor(&it, src); while(ValueTreeSetItMove(&it)) ValueTreeSetPut(dst, *ValueTreeSetItGetRef(&it)); } int ValueTreeSetEqual(ValueTreeSet* lt,ValueTreeSet* rt) { assert(lt); assert(rt); return ValueTreeSetSize(lt) == ValueTreeSetSize(rt) && ValueTreeSetContainsAllOf(lt, rt) && ValueTreeSetContainsAllOf(rt, lt); } size_t ValueTreeSetIdentify(ValueTreeSet* self) { ValueTreeSetIt it; size_t result = 0; assert(self); ValueTreeSetItCtor(&it, self); while(ValueTreeSetItMove(&it)) { Value* e = ValueTreeSetItGetRef(&it); result ^= ValueIdentify(*e); result = AUTOC_RCYCLE(result); } return result; } size_t ValueTreeSetSize(ValueTreeSet* self) { assert(self); return self->size; } void ValueTreeSetInclude(ValueTreeSet* self, ValueTreeSet* other) { ValueTreeSetIt it; assert(self); assert(other); ValueTreeSetItCtor(&it, other); while(ValueTreeSetItMove(&it)) ValueTreeSetPut(self, *ValueTreeSetItGetRef(&it)); } void ValueTreeSetRetain(ValueTreeSet* self, ValueTreeSet* other) { ValueTreeSetIt it; ValueTreeSet set; assert(self); assert(other); ValueTreeSetCtor(&set); ValueTreeSetItCtor(&it, self); while(ValueTreeSetItMove(&it)) { Value* e = ValueTreeSetItGetRef(&it); assert(e); if(ValueTreeSetContains(other, *e)) ValueTreeSetPut(&set, *e); } ValueTreeSetDtor(self); *self = set; } void ValueTreeSetInvert(ValueTreeSet* self, ValueTreeSet* other) { ValueTreeSetIt it; ValueTreeSet set; assert(self); assert(other); ValueTreeSetCtor(&set); ValueTreeSetItCtor(&it, self); while(ValueTreeSetItMove(&it)) { Value* e = ValueTreeSetItGetRef(&it); if(!ValueTreeSetContains(other, *e)) ValueTreeSetPut(&set, *e); } ValueTreeSetItCtor(&it, other); while(ValueTreeSetItMove(&it)) { Value* e = ValueTreeSetItGetRef(&it); if(!ValueTreeSetContains(self, *e)) ValueTreeSetPut(&set, *e); } ValueTreeSetDtor(self); *self = set; } void ValueTreeSetExclude(ValueTreeSet* self, ValueTreeSet* other) { ValueTreeSetIt it; assert(self); assert(other); ValueTreeSetItCtor(&it, other); while(ValueTreeSetItMove(&it)) ValueTreeSetRemove(self, *ValueTreeSetItGetRef(&it)); } #define ValueTreeSetIsRed(x) (x->color) #define ValueTreeSetIsBlack(x) !ValueTreeSetIsRed(x) #define ValueTreeSetSetRed(x) (x->color = 1) #define ValueTreeSetSetBlack(x) (x->color = 0) #define ValueTreeSetCompare(lt, rt) (ValueEqual(lt,rt) ? 0 : (ValueLess(lt,rt) ? -1 : +1)) static ValueTreeSetNode ValueTreeSetNullNode = {0, NULL, NULL, NULL}; static ValueTreeSetNode* ValueTreeSetNull = &ValueTreeSetNullNode; static void ValueTreeSetDestroyNode(ValueTreeSetNode* node) { assert(node); assert(node != ValueTreeSetNull); ValueDtor(node->element); free(node); } void ValueTreeSetCtor(ValueTreeSet* self) { assert(self); self->size = 0; self->root = ValueTreeSetNull; } static void ValueTreeSetDestroy(ValueTreeSetNode* node) { if(node != ValueTreeSetNull) { ValueTreeSetDestroy(node->left); ValueTreeSetDestroy(node->right); ValueTreeSetDestroyNode(node); } } void ValueTreeSetDtor(ValueTreeSet* self) { assert(self); ValueTreeSetDestroy(self->root); /* FIXME recursive algorithm might be inefficient */ } void ValueTreeSetPurge(ValueTreeSet* self) { assert(self); ValueTreeSetDtor(self); ValueTreeSetCtor(self); } static void ValueTreeSetRotateLeft(ValueTreeSet* self, ValueTreeSetNode* node) { ValueTreeSetNode* right = node->right; node->right = right->left; if(right->left != ValueTreeSetNull) right->left->parent = node; right->parent = node->parent; if(node->parent != ValueTreeSetNull) { if(node == node->parent->left) { node->parent->left = right; } else { node->parent->right = right; } } else { self->root = right; } right->left = node; node->parent = right; } static void ValueTreeSetRotateRight(ValueTreeSet* self, ValueTreeSetNode* node) { ValueTreeSetNode* left = node->left; node->left = left->right; if(left->right != ValueTreeSetNull) left->right->parent = node; left->parent = node->parent; if(node->parent != ValueTreeSetNull) { if(node == node->parent->right) { node->parent->right = left; } else { node->parent->left = left; } } else { self->root = left; } left->right = node; node->parent = left; } static void ValueTreeSetInsertFixup(ValueTreeSet* self, ValueTreeSetNode* node) { ValueTreeSetNode* uncle; while(node != self->root && ValueTreeSetIsRed(node->parent)) { if(node->parent == node->parent->parent->left) { uncle = node->parent->parent->right; if(ValueTreeSetIsRed(uncle)) { ValueTreeSetSetBlack(node->parent); ValueTreeSetSetBlack(uncle); ValueTreeSetSetRed(node->parent->parent); node = node->parent->parent; } else { if(node == node->parent->right) { node = node->parent; ValueTreeSetRotateLeft(self, node); } ValueTreeSetSetBlack(node->parent); ValueTreeSetSetRed(node->parent->parent); ValueTreeSetRotateRight(self, node->parent->parent); } } else { uncle = node->parent->parent->left; if(ValueTreeSetIsRed(uncle)) { ValueTreeSetSetBlack(node->parent); ValueTreeSetSetBlack(uncle); ValueTreeSetSetRed(node->parent->parent); node = node->parent->parent; } else { if(node == node->parent->left) { node = node->parent; ValueTreeSetRotateRight(self, node); } ValueTreeSetSetBlack(node->parent); ValueTreeSetSetRed(node->parent->parent); ValueTreeSetRotateLeft(self, node->parent->parent); } } } ValueTreeSetSetBlack(self->root); } static void ValueTreeSetDeleteFixup(ValueTreeSet* self, ValueTreeSetNode* child, ValueTreeSetNode* child_parent) { ValueTreeSetNode* sibling; int go_up = 1; if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; while(go_up) { if(child_parent == ValueTreeSetNull) return; if(ValueTreeSetIsRed(sibling)) { ValueTreeSetSetRed(child_parent); ValueTreeSetSetBlack(sibling); if(child_parent->right == child) ValueTreeSetRotateRight(self, child_parent); else ValueTreeSetRotateLeft(self, child_parent); if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; } if(ValueTreeSetIsBlack(child_parent) && ValueTreeSetIsBlack(sibling) && ValueTreeSetIsBlack(sibling->left) && ValueTreeSetIsBlack(sibling->right)) { if(sibling != ValueTreeSetNull) ValueTreeSetSetRed(sibling); child = child_parent; child_parent = child_parent->parent; if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; } else go_up = 0; } if(ValueTreeSetIsRed(child_parent) && ValueTreeSetIsBlack(sibling) && ValueTreeSetIsBlack(sibling->left) && ValueTreeSetIsBlack(sibling->right)) { if(sibling != ValueTreeSetNull) ValueTreeSetSetRed(sibling); ValueTreeSetSetBlack(child_parent); return; } if(child_parent->right == child && ValueTreeSetIsBlack(sibling) && ValueTreeSetIsRed(sibling->right) && ValueTreeSetIsBlack(sibling->left)) { ValueTreeSetSetRed(sibling); ValueTreeSetSetBlack(sibling->right); ValueTreeSetRotateLeft(self, sibling); if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; } else if(child_parent->left == child && ValueTreeSetIsBlack(sibling) && ValueTreeSetIsRed(sibling->left) && ValueTreeSetIsBlack(sibling->right)) { ValueTreeSetSetRed(sibling); ValueTreeSetSetBlack(sibling->left); ValueTreeSetRotateRight(self, sibling); if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right; } sibling->color = child_parent->color; ValueTreeSetSetBlack(child_parent); if(child_parent->right == child) { ValueTreeSetSetBlack(sibling->left); ValueTreeSetRotateRight(self, child_parent); } else { ValueTreeSetSetBlack(sibling->right); ValueTreeSetRotateLeft(self, child_parent); } } static ValueTreeSetNode* ValueTreeSetFindNode(ValueTreeSet* self, Value element) { int r; ValueTreeSetNode* node; assert(self); node = self->root; while(node != ValueTreeSetNull) { if((r = ValueTreeSetCompare(element, node->element)) == 0) { return node; } if(r < 0) { node = node->left; } else { node = node->right; } } return NULL; } int ValueTreeSetContains(ValueTreeSet* self, Value element) { assert(self); return ValueTreeSetFindNode(self, element) != NULL; } Value ValueTreeSetGet(ValueTreeSet* self, Value element) { ValueTreeSetNode *node; Value result; assert(self); assert(ValueTreeSetContains(self, element)); node = ValueTreeSetFindNode(self, element); ValueCopy(result,node->element); /* Here we rely on NULL pointer dereference to manifest the failure! */ return result; } int ValueTreeSetPut(ValueTreeSet* self, Value element) { int r; ValueTreeSetNode* data; ValueTreeSetNode* node; ValueTreeSetNode* parent; assert(self); node = self->root; parent = ValueTreeSetNull; while(node != ValueTreeSetNull) { if((r = ValueTreeSetCompare(element, node->element)) == 0) { return 0; } parent = node; if (r < 0) { node = node->left; } else { node = node->right; } } data = malloc(sizeof(ValueTreeSetNode)); assert(data); ValueCopy(data->element,element); data->parent = parent; data->left = data->right = ValueTreeSetNull; ValueTreeSetSetRed(data); ++self->size; if(parent != ValueTreeSetNull) { if(r < 0) { parent->left = data; } else { parent->right = data; } } else { self->root = data; } ValueTreeSetInsertFixup(self, data); return 1; } int ValueTreeSetReplace(ValueTreeSet* self, Value element) { int removed; assert(self); /* FIXME removing followed by putting might be inefficient */ if((removed = ValueTreeSetRemove(self, element))) ValueTreeSetPut(self, element); return removed; } static void ValueTreeSetSwapColors(ValueTreeSetNode* x, ValueTreeSetNode* y) { int t = x->color; assert(x); assert(y); x->color = y->color; y->color = t; } static void ValueTreeSetSwapNodes(ValueTreeSetNode** x, ValueTreeSetNode** y) { ValueTreeSetNode* t = *x; *x = *y; *y = t; } static void ValueTreeSetChangeParent(ValueTreeSet* self, ValueTreeSetNode* parent, ValueTreeSetNode* old_node, ValueTreeSetNode* new_node) { if(parent == ValueTreeSetNull) { if(self->root == old_node) self->root = new_node; return; } if(parent->left == old_node) parent->left = new_node; if(parent->right == old_node) parent->right = new_node; } static void ValueTreeSetChangeChild(ValueTreeSetNode* child, ValueTreeSetNode* old_node, ValueTreeSetNode* new_node) { if(child == ValueTreeSetNull) return; if(child->parent == old_node) child->parent = new_node; } int ValueTreeSetRemove(ValueTreeSet* self, Value element) { ValueTreeSetNode* to_delete; ValueTreeSetNode* child; assert(self); if((to_delete = ValueTreeSetFindNode(self, element)) == NULL) return 0; if(to_delete->left != ValueTreeSetNull && to_delete->right != ValueTreeSetNull) { ValueTreeSetNode *smright = to_delete->right; while(smright->left != ValueTreeSetNull) smright = smright->left; ValueTreeSetSwapColors(to_delete, smright); ValueTreeSetChangeParent(self, to_delete->parent, to_delete, smright); if(to_delete->right != smright) ValueTreeSetChangeParent(self, smright->parent, smright, to_delete); ValueTreeSetChangeChild(smright->left, smright, to_delete); ValueTreeSetChangeChild(smright->left, smright, to_delete); ValueTreeSetChangeChild(smright->right, smright, to_delete); ValueTreeSetChangeChild(smright->right, smright, to_delete); ValueTreeSetChangeChild(to_delete->left, to_delete, smright); if(to_delete->right != smright) ValueTreeSetChangeChild(to_delete->right, to_delete, smright); if(to_delete->right == smright) { to_delete->right = to_delete; smright->parent = smright; } ValueTreeSetSwapNodes(&to_delete->parent, &smright->parent); ValueTreeSetSwapNodes(&to_delete->left, &smright->left); ValueTreeSetSwapNodes(&to_delete->right, &smright->right); } if(to_delete->left != ValueTreeSetNull) child = to_delete->left; else child = to_delete->right; ValueTreeSetChangeParent(self, to_delete->parent, to_delete, child); ValueTreeSetChangeChild(child, to_delete, to_delete->parent); if(ValueTreeSetIsRed(to_delete)) {} else if(ValueTreeSetIsRed(child)) { if(child != ValueTreeSetNull) ValueTreeSetSetBlack(child); } else ValueTreeSetDeleteFixup(self, child, to_delete->parent); ValueTreeSetDestroyNode(to_delete); --self->size; return 1; } static ValueTreeSetNode* ValueTreeSetLowestNode(ValueTreeSet* self) { ValueTreeSetNode* node; assert(self); node = self->root; if(self->root != ValueTreeSetNull) { for(node = self->root; node->left != ValueTreeSetNull; node = node->left); } return node; } static ValueTreeSetNode* ValueTreeSetHighestNode(ValueTreeSet* self) { ValueTreeSetNode* node; assert(self); node = self->root; if(self->root != ValueTreeSetNull) { for(node = self->root; node->right != ValueTreeSetNull; node = node->right); } return node; } static ValueTreeSetNode* ValueTreeSetNextNode(ValueTreeSetNode* node) { ValueTreeSetNode* parent; assert(node); if(node->right != ValueTreeSetNull) { for(node = node->right; node->left != ValueTreeSetNull; node = node->left); } else { parent = node->parent; while(parent != ValueTreeSetNull && node == parent->right) { node = parent; parent = parent->parent; } node = parent; } return node; } static ValueTreeSetNode* ValueTreeSetPrevNode(ValueTreeSetNode* node) { ValueTreeSetNode* parent; assert(node); if(node->left != ValueTreeSetNull) { for(node = node->left; node->right != ValueTreeSetNull; node = node->right); } else { parent = node->parent; while(parent != ValueTreeSetNull && node == parent->left) { node = parent; parent = parent->parent; } node = parent; } return node; } Value ValueTreeSetPeekLowest(ValueTreeSet* self) { ValueTreeSetNode* node; Value result; assert(self); assert(!ValueTreeSetEmpty(self)); node = ValueTreeSetLowestNode(self); assert(node); assert(node != ValueTreeSetNull); ValueCopy(result,node->element); return result; } Value ValueTreeSetPeekHighest(ValueTreeSet* self) { ValueTreeSetNode* node; Value result; assert(self); assert(!ValueTreeSetEmpty(self)); node = ValueTreeSetHighestNode(self); assert(node); assert(node != ValueTreeSetNull); ValueCopy(result,node->element); return result; } void ValueTreeSetItCtorEx(ValueTreeSetIt* self, ValueTreeSet* tree, int ascending) { assert(self); assert(tree); self->node = (self->ascending = ascending) ? ValueTreeSetLowestNode(tree) : ValueTreeSetHighestNode(tree); self->start = 1; } int ValueTreeSetItMove(ValueTreeSetIt* self) { assert(self); if(self->start) { self->start = 0; } else { self->node = self->ascending ? ValueTreeSetNextNode(self->node) : ValueTreeSetPrevNode(self->node); } return self->node != ValueTreeSetNull; } static Value* ValueTreeSetItGetRef(ValueTreeSetIt* self) { assert(self); assert(self->node); assert(self->node != ValueTreeSetNull); return &self->node->element; } Value ValueTreeSetItGet(ValueTreeSetIt* self) { Value result; assert(self); ValueCopy(result,*ValueTreeSetItGetRef(self)); return result; } void ValueTreeSetTestCreate(void) { ValueTreeSet t; ValueTreeSetCtor(&t); TEST_EQUAL( ValueTreeSetSize(&t), 0 ); TEST_TRUE( ValueTreeSetEmpty(&t) ); ValueTreeSetDtor(&t); } void ValueTreeSetTestPurge(void) { ValueTreeSet t; ValueTreeSetCtor(&t); PUT(&t, 0); TEST_FALSE( ValueTreeSetEmpty(&t) ); ValueTreeSetPurge(&t); TEST_TRUE( ValueTreeSetEmpty(&t) ); ValueTreeSetDtor(&t); } void ValueTreeSetTestContains(void) { /* a: [1,2,3], e: 0 */ ValueTreeSet a; Value e; ValueCtor(e); ValueTreeSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); TEST_FALSE( ValueTreeSetContains(&a, e) ); ValueSet(e, 1); TEST_TRUE( ValueTreeSetContains(&a, e) ); ValueTreeSetDtor(&a); ValueDtor(e); } void ValueTreeSetTestGet(void) { /* a: [1,2,3], e: 0 */ ValueTreeSet a; Value e; ValueCtor(e); ValueTreeSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); Value e2; ValueSet(e, -1); ValueTreeSetPut(&a, e); e2 = ValueTreeSetGet(&a, e); TEST_TRUE( ValueEqual(e, e2) ); ValueDtor(e2); ValueTreeSetDtor(&a); ValueDtor(e); } void ValueTreeSetTestPutNew(void) { /* a: [1,2,3], e: 0 */ ValueTreeSet a; Value e; ValueCtor(e); ValueTreeSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueSet(e, -1); TEST_FALSE( ValueTreeSetContains(&a, e) ); TEST_TRUE( ValueTreeSetPut(&a, e) ); TEST_TRUE( ValueTreeSetContains(&a, e) ); ValueTreeSetDtor(&a); ValueDtor(e); } void ValueTreeSetTestPutExisting(void) { /* a: [1,2,3], e: 0 */ ValueTreeSet a; Value e; ValueCtor(e); ValueTreeSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueSet(e, -1); TEST_FALSE( ValueTreeSetContains(&a, e) ); TEST_TRUE( ValueTreeSetPut(&a, e) ); TEST_TRUE( ValueTreeSetContains(&a, e) ); TEST_FALSE( ValueTreeSetPut(&a, e) ); ValueTreeSetDtor(&a); ValueDtor(e); } void ValueTreeSetTestReplace(void) { /* a: [1,2,3], e: 0 */ ValueTreeSet a; Value e; ValueCtor(e); ValueTreeSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueSet(e, 1); TEST_TRUE( ValueTreeSetContains(&a, e) ); TEST_TRUE( ValueTreeSetReplace(&a, e) ); TEST_TRUE( ValueTreeSetContains(&a, e) ); ValueTreeSetDtor(&a); ValueDtor(e); } void ValueTreeSetTestReplaceNone(void) { /* a: [1,2,3], e: 0 */ ValueTreeSet a; Value e; ValueCtor(e); ValueTreeSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueSet(e, -1); TEST_FALSE( ValueTreeSetContains(&a, e) ); TEST_FALSE( ValueTreeSetReplace(&a, e) ); TEST_FALSE( ValueTreeSetContains(&a, e) ); ValueTreeSetDtor(&a); ValueDtor(e); } void ValueTreeSetTestRemove(void) { /* a: [1,2,3], e: 0 */ ValueTreeSet a; Value e; ValueCtor(e); ValueTreeSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueSet(e, 1); TEST_TRUE( ValueTreeSetContains(&a, e) ); TEST_TRUE( ValueTreeSetRemove(&a, e) ); TEST_FALSE( ValueTreeSetContains(&a, e) ); ValueTreeSetDtor(&a); ValueDtor(e); } void ValueTreeSetTestRemoveNone(void) { /* a: [1,2,3], e: 0 */ ValueTreeSet a; Value e; ValueCtor(e); ValueTreeSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueSet(e, -1); TEST_FALSE( ValueTreeSetContains(&a, e) ); TEST_FALSE( ValueTreeSetRemove(&a, e) ); ValueTreeSetDtor(&a); ValueDtor(e); } void ValueTreeSetTestIterate(void) { /* a: [1,2,3], e: 0 */ ValueTreeSet a; Value e; ValueCtor(e); ValueTreeSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueTreeSetIt it; size_t i = 0; ValueTreeSetItCtor(&it, &a); while(ValueTreeSetItMove(&it)) { Value e2 = ValueTreeSetItGet(&it); ValueDtor(e2); i++; } TEST_EQUAL( ValueTreeSetSize(&a), i ); ValueTreeSetDtor(&a); ValueDtor(e); } void ValueTreeSetTestCopy(void) { /* a: [1,2,3] */ ValueTreeSet a, b; ValueTreeSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueTreeSetCopy(&b, &a); TEST_TRUE( ValueTreeSetEqual(&a, &b) ); ValueTreeSetDtor(&a); ValueTreeSetDtor(&b); } void ValueTreeSetTestEmpty(void) { /* a: [1,2,3] */ ValueTreeSet a, b; ValueTreeSetCtor(&a); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); ValueTreeSetCtor(&b); TEST_FALSE( ValueTreeSetEmpty(&a) ); TEST_TRUE( ValueTreeSetEmpty(&b) ); ValueTreeSetDtor(&a); ValueTreeSetDtor(&b); } void ValueTreeSetTestExclude(void) { /* a: [1,2,3], b: [2,3,4] */ ValueTreeSet a, b, c; ValueTreeSetCtor(&a); ValueTreeSetCtor(&b); ValueTreeSetCtor(&c); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); PUT(&b, 4); PUT(&b, 2); PUT(&b, 3); PUT(&c, 1); ValueTreeSetExclude(&a, &b); TEST_TRUE( ValueTreeSetEqual(&a, &c) ); ValueTreeSetDtor(&a); ValueTreeSetDtor(&b); ValueTreeSetDtor(&c); } void ValueTreeSetTestInclude(void) { /* a: [1,2,3], b: [2,3,4] */ ValueTreeSet a, b, c; ValueTreeSetCtor(&a); ValueTreeSetCtor(&b); ValueTreeSetCtor(&c); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); PUT(&b, 4); PUT(&b, 2); PUT(&b, 3); PUT(&c, 1); PUT(&c, 2); PUT(&c, 3); PUT(&c, 4); ValueTreeSetInclude(&a, &b); TEST_TRUE( ValueTreeSetEqual(&a, &c) ); ValueTreeSetDtor(&a); ValueTreeSetDtor(&b); ValueTreeSetDtor(&c); } void ValueTreeSetTestInvert(void) { /* a: [1,2,3], b: [2,3,4] */ ValueTreeSet a, b, c; ValueTreeSetCtor(&a); ValueTreeSetCtor(&b); ValueTreeSetCtor(&c); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); PUT(&b, 4); PUT(&b, 2); PUT(&b, 3); PUT(&c, 1); PUT(&c, 4); ValueTreeSetInvert(&a, &b); TEST_TRUE( ValueTreeSetEqual(&a, &c) ); ValueTreeSetDtor(&a); ValueTreeSetDtor(&b); ValueTreeSetDtor(&c); } void ValueTreeSetTestRetain(void) { /* a: [1,2,3], b: [2,3,4] */ ValueTreeSet a, b, c; ValueTreeSetCtor(&a); ValueTreeSetCtor(&b); ValueTreeSetCtor(&c); PUT(&a, 1); PUT(&a, 2); PUT(&a, 3); PUT(&b, 4); PUT(&b, 2); PUT(&b, 3); PUT(&c, 2); PUT(&c, 3); ValueTreeSetRetain(&a, &b); TEST_TRUE( ValueTreeSetEqual(&a, &c) ); ValueTreeSetDtor(&a); ValueTreeSetDtor(&b); ValueTreeSetDtor(&c); } void ValueTreeSetRunTests(void) { fprintf(stdout, "* %s\n", "ValueTreeSet"); fflush(stdout); run_test("create", ValueTreeSetTestCreate); run_test("purge", ValueTreeSetTestPurge); run_test("contains", ValueTreeSetTestContains); run_test("get", ValueTreeSetTestGet); run_test("putNew", ValueTreeSetTestPutNew); run_test("putExisting", ValueTreeSetTestPutExisting); run_test("replace", ValueTreeSetTestReplace); run_test("replaceNone", ValueTreeSetTestReplaceNone); run_test("remove", ValueTreeSetTestRemove); run_test("removeNone", ValueTreeSetTestRemoveNone); run_test("iterate", ValueTreeSetTestIterate); run_test("copy", ValueTreeSetTestCopy); run_test("empty", ValueTreeSetTestEmpty); run_test("exclude", ValueTreeSetTestExclude); run_test("include", ValueTreeSetTestInclude); run_test("invert", ValueTreeSetTestInvert); run_test("retain", ValueTreeSetTestRetain); fputs("\n", stdout); fflush(stdout); } int main(int argc, char** argv) { tests.total = 172; tests.processed = tests.failed = 0; ValueTreeSetRunTests(); CharStringRunTests(); ValueHashMapRunTests(); ValueTreeMapRunTests(); ValueQueueRunTests(); IntVectorRunTests(); ValueListRunTests(); ValueVectorRunTests(); ValueHashSetRunTests(); IntTreeSetRunTests(); IntListRunTests(); print_summary(); return tests.failed > 0; }