include/postings.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	wordLocation
struct	finalList
Functions
void	postings_initialize ()
void	postings_addEntry (unsigned char *word, uint4 wordLength, uint4 sequenceNumber, uint4 offset)
void	postings_print ()
finalList *	postings_getSortedLists ()
uint4	postings_decodeList (struct finalList finalList, struct wordLocation *wordLocations)
Variables
uint4	postings_numLists

---

Function Documentation

void postings_addEntry	(	unsigned char *	word,
		uint4	wordLength,
		uint4	sequenceNumber,
		uint4	offset
	)

Definition at line 56 of file postings.c.

References global_malloc(), postingsList::hash64bit, postingsList::next, postings_addPosting(), postings_hash32bit(), postings_hash64bit(), postings_hashtable, postings_hashtableSize, postings_numLists, postings_seed, postings_size, uint4, and uint8.

Referenced by cluster_spexClusterSequences(), and rsdb_spexClusterSequences().

{
        struct postingsList* postingsList;
        uint4 hash32bit;
    uint8 hash64bit;

    // Calculate 32 and 64 bit hash values
        hash32bit = postings_hash32bit(word, wordLength, postings_hashtableSize, postings_seed);
        hash64bit = postings_hash64bit(word, wordLength, postings_seed);

    // Look for matching entry in hashtable
    postingsList = postings_hashtable[hash32bit];
    while (postingsList != NULL)
    {
        if (postingsList->hash64bit == hash64bit)
        {
                // Add new entry to postings list
                        postings_addPosting(postingsList, sequenceNumber, offset);
                return;
        }
        postingsList = postingsList->next;
    }

    // Create a new entry
    postingsList = (struct postingsList*)global_malloc(sizeof(struct postingsList));
        postingsList->hash64bit = hash64bit;
        postingsList->list = NULL;
    postingsList->length = 0;
    postingsList->malloced = 0;
    postingsList->numEntries = 0;
    postingsList->lastSequenceNumber = 0;
        postings_size += sizeof(struct postingsList);
    postings_numLists++;

    // Add to start of list
        postingsList->next = postings_hashtable[hash32bit];
    postings_hashtable[hash32bit] = postingsList;

    // Add new entry to postings list
        postings_addPosting(postingsList, sequenceNumber, offset);
}

Here is the call graph for this function:

Here is the caller graph for this function:

uint4 postings_decodeList	(	struct finalList	finalList,
		struct wordLocation *	wordLocations
	)

Definition at line 171 of file postings.c.

References finalList::list, finalList::numEntries, wordLocation::offset, wordLocation::sequenceNumber, uint4, and vbyte_getVbyte.

Referenced by cluster_spexClusterSequences(), and rsdb_spexClusterSequences().

{
        unsigned char* list;
        uint4 numEntries, sGap, offset, sequenceNumber = 0, entry = 0;

    list = finalList.list;
    numEntries = finalList.numEntries;

    while (entry < numEntries)
    {
        vbyte_getVbyte(list, &sGap);
        sequenceNumber += sGap;
        vbyte_getVbyte(list, &offset);

                wordLocations[entry].sequenceNumber = sequenceNumber;
                wordLocations[entry].offset = offset;

//        printf("%d,%d (%d/%d entries)\n", sequenceNumber, offset, entry, numEntries); fflush(stdout);

        entry++;
    }

    free(finalList.list);

    return numEntries;
}

Here is the caller graph for this function:

struct finalList* postings_getSortedLists

(

)

[read]

Definition at line 121 of file postings.c.

References global_malloc(), postingsList::length, postingsList::list, finalList::list, postingsList::next, postingsList::numEntries, finalList::numEntries, postings_compareLists(), postings_hashtable, postings_hashtableSize, postings_numLists, and uint4.

Referenced by cluster_spexClusterSequences(), and rsdb_spexClusterSequences().

{
        struct finalList* finalLists;
    struct postingsList* postingsList, *previousPostingsList;
    uint4 listCount = 0, totalSize = 0;
        uint4 hash32bit;

    finalLists = (struct finalList*)global_malloc(sizeof(struct finalList) * postings_numLists);

    // For each list
        hash32bit = 0;
    while (hash32bit < postings_hashtableSize)
    {
        postingsList = postings_hashtable[hash32bit];
        while (postingsList != NULL)
        {
                // Add to new list of final lists
                        finalLists[listCount].numEntries = postingsList->numEntries;
                        finalLists[listCount].list = postingsList->list;

                        totalSize += postingsList->length;

                        listCount++;
            previousPostingsList = postingsList;
            postingsList = postingsList->next;

            free(previousPostingsList);
        }

        hash32bit++;
    }

    free(postings_hashtable);

    // Sort the lists in order of number of entries
        qsort(finalLists, postings_numLists, sizeof(struct finalList), postings_compareLists);

    // Remove lists with less than 2 entries
    while (postings_numLists > 0 && finalLists[postings_numLists - 1].numEntries < 2)
    {
                postings_numLists--;
        free(finalLists[postings_numLists].list);
    }

//      printf("Total postings size=%d\n", totalSize);

    return finalLists;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void postings_initialize

(

)

Definition at line 36 of file postings.c.

References global_malloc(), postings_hashtable, postings_hashtableSize, postings_numLists, postings_seed, postings_size, and uint4.

Referenced by cluster_spexClusterSequences(), and rsdb_spexClusterSequences().

{
        uint4 count;

        postings_hashtableSize = pow(2,20);
    postings_hashtable = (struct postingsList**)global_malloc(sizeof(struct postingsList*)
                       * postings_hashtableSize);
        postings_seed = rand();
    postings_size = sizeof(struct postingsList*) * postings_hashtableSize;
    postings_numLists = 0;

    count = 0;
    while (count < postings_hashtableSize)
    {
                postings_hashtable[count] = NULL;
        count++;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void postings_print

(

)

Definition at line 247 of file postings.c.

References postings_numLists, and postings_size.

Referenced by rsdb_spexClusterSequences().

{
        printf("%d lists. Postings size=%.2f Mb\n", postings_numLists, (float)postings_size / 1024.0 / 1024.0);
}

Here is the caller graph for this function:

---

Variable Documentation

uint4 postings_numLists

Definition at line 22 of file postings.c.

Referenced by cluster_spexClusterSequences(), postings_addEntry(), postings_getSortedLists(), postings_initialize(), postings_print(), and rsdb_spexClusterSequences().

---