Function hashTableInsert

sbhash.cpp:268–332

}

bool hashTableInsert(hashTable_t * ht, UINT64 value)
{
    // See if we have reached our size limit.
    if (ht->entries == ht->size) resizeHashTable(ht);
    int bucket = hash(value) % ht->size;
    // We need to empty the low order bit so that we can tell the difference between values and ptrs.
    value = makeValue(value);
    UINT64 curvalue = ht->table[bucket];
    // The empty case should be most common.
    if (isEmpty(curvalue))
    {
        ht->table[bucket] = value;
        ht->entries += 1;
        return true;
    }
    // The value case should be next most common.
    if (isValue(curvalue))
    {
        // The value is already here.
        if (curvalue == value) return false;
        // We have a collision and need to add an overflow node.
        hashNode_t * node = getHashNode();
        ht->table[bucket] = (UINT64)node;
        node->values[0] = curvalue;
        // Note that this test doesn't cost us anything as it happens at compile time.
        if (HASHNODE_PAYLOAD_SIZE >= 2)
        {
            node->values[1] = value;
        }
        else
        {
            // We need to add a second new node.
            hashNode_t * secondNode = getHashNode();
            node->next = secondNode;
            secondNode->values[0] = value;
        }
        ht->entries += 1;
        return true;
    }
    // The overflow node case.
    hashNode_t * curNode = makePtr(curvalue);
    while (true)
    {
        for (int i=0; i<HASHNODE_PAYLOAD_SIZE; i++)
        {
            // Check if we have an empty slot.
            if (curNode->values[i] == 0)
            {
                curNode->values[i] = value;
                ht->entries += 1;
                return true;
            }
            // Check if the value matches the current value.
            if (curNode->values[i] == value) return false;
        }
        if (curNode->next == NULL) break;
        curNode = curNode->next;
    }