From d974a48b3dbf9f3bda27b73990087f88eca08dbe Mon Sep 17 00:00:00 2001 From: Wilfried Goesgens Date: Mon, 25 Oct 2010 16:10:25 +0200 Subject: [PATCH] * add a permutation to the hashlist one can store msets in -> parse once, poll often quick. --- libcitadel/lib/hash.c | 133 ++++++++++++++++++++++++++++++- libcitadel/lib/libcitadel.h | 11 ++- libcitadel/tests/hashlist_test.c | 119 ++++++++++++++++++++++++++- 3 files changed, 256 insertions(+), 7 deletions(-) diff --git a/libcitadel/lib/hash.c b/libcitadel/lib/hash.c index bd22f10a8..f6adc2a9b 100644 --- a/libcitadel/lib/hash.c +++ b/libcitadel/lib/hash.c @@ -1,6 +1,7 @@ #include #include #include +#include //dbg #include #include "libcitadel.h" @@ -426,18 +427,31 @@ static long FindInHash(HashList *Hash, long HashBinKey) /** - * @brief another hashing algorithm; treat it as just a pointer to long. - * @param str Our pointer to the long value + * @brief another hashing algorithm; treat it as just a pointer to int. + * @param str Our pointer to the int value * @param len the length of the data pointed to; needs to be sizeof int, else we won't use it! * \returns the calculated hash value */ -int Flathash(const char *str, long len) +long Flathash(const char *str, long len) { if (len != sizeof (int)) return 0; else return *(int*)str; } +/** + * @brief another hashing algorithm; treat it as just a pointer to long. + * @param str Our pointer to the long value + * @param len the length of the data pointed to; needs to be sizeof long, else we won't use it! + * \returns the calculated hash value + */ +long lFlathash(const char *str, long len) +{ + if (len != sizeof (long)) + return 0; + else return *(long*)str; +} + /** * @brief private abstract wrapper around the hashing algorithm * @param HKey the hash string @@ -972,3 +986,116 @@ int HashLittle(const void *key, size_t length) { return (int)hashlittle(key, length, 1); } + +/** + * \brief parses an MSet string into a list for later use + * \param MSetList List to be read from MSetStr + * \param MSetStr String containing the list + */ +int ParseMSet(MSet **MSetList, StrBuf *MSetStr) +{ + const char *POS = NULL, *SetPOS = NULL; + StrBuf *OneSet; + HashList *ThisMSet; + long StartSet, EndSet; + long *pEndSet; + + *MSetList = NULL; + if ((MSetStr == NULL) || (StrLength(MSetStr) == 0)) + return 0; + + OneSet = NewStrBufPlain(NULL, StrLength(MSetStr)); + + ThisMSet = NewHash(0, lFlathash); + + *MSetList = (MSet*) ThisMSet; + + /* an MSet is a coma separated value list. */ + StrBufExtract_NextToken(OneSet, MSetStr, &POS, ','); + do { + SetPOS = NULL; + + /* One set may consist of two Numbers: Start + optional End */ + StartSet = StrBufExtractNext_long(OneSet, &SetPOS, ':'); + EndSet = 0; /* no range is our default. */ + /* do we have an end (aka range?) */ + if ((SetPOS != NULL) && (SetPOS != StrBufNOTNULL)) + { + if (*(SetPOS) == '*') + EndSet = LONG_MAX; /* ranges with '*' go until infinity */ + else + /* in other cases, get the EndPoint */ + EndSet = StrBufExtractNext_long(OneSet, &SetPOS, ':'); + } + + pEndSet = (long*) malloc (sizeof(long)); + *pEndSet = EndSet; + + Put(ThisMSet, LKEY(StartSet), pEndSet, NULL); + /* if we don't have another, we're done. */ + if (POS == StrBufNOTNULL) + break; + StrBufExtract_NextToken(OneSet, MSetStr, &POS, ','); + } while (1); + FreeStrBuf(&OneSet); + + return 1; +} + +/** + * \brief checks whether a message is inside a mset + * \param MSetList List to search for MsgNo + * \param MsgNo number to search in mset + */ +int IsInMSetList(MSet *MSetList, long MsgNo) +{ + /* basicaly we are a ... */ + long MemberPosition; + HashList *Hash = (HashList*) MSetList; + long HashAt; + long EndAt; + + if (Hash == NULL) + return 0; + if (Hash->MemberSize == 0) + return 0; + /** first, find out were we could fit in... */ + HashAt = FindInHash(Hash, MsgNo); + + /* we're below the first entry, so not found. */ + if (HashAt < 0) + return 0; + /* upper edge? move to last item */ + if (HashAt >= Hash->nMembersUsed) + HashAt = Hash->nMembersUsed - 1; + /* Match? then we got it. */ + else if (Hash->LookupTable[HashAt]->Key == MsgNo) + return 1; + /* One above possible range start? we need to move to the lower one. */ + else if ((HashAt > 0) && + (Hash->LookupTable[HashAt]->Key > MsgNo)) + HashAt -=1; + + /* Fetch the actual data */ + MemberPosition = Hash->LookupTable[HashAt]->Position; + EndAt = *(long*) Hash->Members[MemberPosition]->Data; + if (EndAt == LONG_MAX) + return 1; + /* no range? */ + if (EndAt == 0) + return 0; + /* inside of range? */ + if (EndAt >= MsgNo) + return 1; + return 0; +} + + +/** + * \brief frees a mset [redirects to @ref DeleteHash + * \param FreeMe to be free'd + */ +void DeleteMSet(MSet **FreeMe) +{ + DeleteHash((HashList**) FreeMe); +} diff --git a/libcitadel/lib/libcitadel.h b/libcitadel/lib/libcitadel.h index 10fb22f79..188a13a5b 100644 --- a/libcitadel/lib/libcitadel.h +++ b/libcitadel/lib/libcitadel.h @@ -107,6 +107,7 @@ typedef enum _room_views { VIEW_MAX } ROOM_VIEWS; + #ifndef IsEmptyStr #define IsEmptyStr(a) ((a)[0] == '\0') #endif @@ -405,12 +406,14 @@ typedef struct HashPos HashPos; typedef void (*DeleteHashDataFunc)(void * Data); typedef const char *(*PrintHashContent)(void * Data); typedef int (*CompareFunc)(const void* Item1, const void*Item2); -typedef int (*HashFunc)(const char *Str, long Len); +typedef long (*HashFunc)(const char *Str, long Len); typedef void (*TransitionFunc) (void *Item1, void *Item2, int Odd); typedef void (*PrintHashDataFunc) (const char *Key, void *Item, int Odd); -int Flathash(const char *str, long len); +long Flathash(const char *str, long len); +long lFlathash(const char *str, long len); #define IKEY(a) (const char*) &a, sizeof(a) +#define LKEY(a) (const char*) &a, sizeof(a) HashList *NewHash(int Uniq, HashFunc F); void DeleteHash(HashList **Hash); @@ -438,6 +441,10 @@ void SortByPayload(HashList *Hash, CompareFunc SortBy); void reference_free_handler(void *ptr); int HashLittle(const void *key, size_t length); +typedef struct MSet MSet; +int ParseMSet(MSet **MsetList, StrBuf *MSetStr); +int IsInMSetList(MSet *MSetList, long MsgNo); +void DeleteMSet(MSet **FreeMe); void convert_spaces_to_underscores(char *str); int CheckEncode(const char *pch, long len, const char *pche); diff --git a/libcitadel/tests/hashlist_test.c b/libcitadel/tests/hashlist_test.c index fc638ccbc..e7b929b6b 100644 --- a/libcitadel/tests/hashlist_test.c +++ b/libcitadel/tests/hashlist_test.c @@ -175,6 +175,122 @@ Some samples from the original... +const char *MSetStrings[] = { + "65", + "1,65,77", + "1:65,77,80:*", + NULL +}; + +#define InMSet 0 +#define NotInMSet 1 +const long MessageNumbers[4][2][10] = { +/* First MSet */ + { + {65, 0, 0, 0, 0, 0, 0, 0, 0, 0}, /* In */ + {1, 64, 66, 0, 0, 0, 0, 0, 0, 0} /* NotIn */ + }, + + { + {1, 65, 77, 0, 0, 0, 0, 0, 0, 0}, /* In */ + {2, 64, 66, 76, 78, 0, 0, 0, 0, 0} /* NotIn */ + }, + { + {1, 2, 30, 64, 65, 77, 80, 81, 222222, 0}, /* In */ + {66, 76, 78, 79, 0, 0, 0, 0, 0, 0} /* NotIn */ + }, + { + {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, /* In */ + {0, 0, 0, 0, 0, 0, 0, 0, 0, 0} /* NotIn */ + } +}; + + + +static void TestMSetHashlist (void) +{ + int nTest = 0; + int j; + StrBuf *MSetStr; + StrBuf *Assert; + MSet *OneMSet; + + + MSetStr = NewStrBuf(); + Assert = NewStrBuf(); + while (MSetStrings[nTest] != NULL) + { + StrBufPlain(MSetStr, MSetStrings[nTest], -1); + ParseMSet(&OneMSet, MSetStr); + +#ifdef VERBOSE_TEST + printf("---%s---\n", ChrPtr(MSetStr)); + { + const char *HashKey; + long HKLen; + HashList *ScanMe = (HashList*) OneMSet; + HashPos *at; + void *vMsg; + long *end; + + at = GetNewHashPos(ScanMe, 0); + while (GetNextHashPos(ScanMe, at, &HKLen, &HashKey, &vMsg)) { + /* Are you a new message, or an old message? */ + end = (long*) vMsg; + printf("[%ld][%ld]\n", *(long*)HashKey, *end); + } + DeleteHashPos(&at); + } +#endif + + j = 0; + while (MessageNumbers[nTest][InMSet][j] != 0) + { + if (!IsInMSetList(OneMSet, MessageNumbers[nTest][InMSet][j])) + { + StrBufPrintf(Assert, "InFail: %s <-> %ld\n", + ChrPtr(MSetStr), + MessageNumbers[nTest][InMSet][j]); + CU_FAIL(ChrPtr(Assert)); + } + else + { + StrBufPrintf(Assert, "InPass: %s <-> %ld\n", + ChrPtr(MSetStr), + MessageNumbers[nTest][InMSet][j]); + CU_PASS(ChrPtr(Assert)); + } + j++; + } + j = 0; + while (MessageNumbers[nTest][NotInMSet][j] != 0) + { + if (IsInMSetList(OneMSet, MessageNumbers[nTest][NotInMSet][j])) + { + StrBufPrintf(Assert, "NOT-InFail: %s <-> %ld\n", + ChrPtr(MSetStr), + MessageNumbers[nTest][NotInMSet][j]); + CU_FAIL(ChrPtr(Assert)); + } + else + { + StrBufPrintf(Assert, "NOT-InPass: %s <-> %ld\n", + ChrPtr(MSetStr), + MessageNumbers[nTest][InMSet][j]); + CU_PASS(ChrPtr(Assert)); + } + j++; + } + + + DeleteMSet(&OneMSet); + nTest++; + + } + FreeStrBuf(&MSetStr); + FreeStrBuf(&Assert); +} + static void AddHashlistTests(void) @@ -185,8 +301,7 @@ static void AddHashlistTests(void) pGroup = CU_add_suite("TestStringBufSimpleAppenders", NULL, NULL); pTest = CU_add_test(pGroup, "TestHashListIteratorForward", TestHashlistIteratorForward); pTest = CU_add_test(pGroup, "TestHashlistAddDelete", TestHashlistAddDelete); - - + pTest = CU_add_test(pGroup, "TestMSetHashlist", TestMSetHashlist); } -- 2.30.2