tests/tests_HTMLparser_htmlAttrHashInsert.c

#include "unity/unity.h"
#include <libxml/HTMLparser.h>

#include <libxml/parser.h>
#include <libxml/parserInternals.h>
#include <libxml/xmlmemory.h>
#include <libxml/xmlstring.h>
#include <limits.h>
#include <string.h>
#include <stdlib.h>

/* Prototype of the provided test wrapper */
int test_htmlAttrHashInsert(xmlParserCtxtPtr ctxt, unsigned size, const xmlChar *name,
                            unsigned hashValue, int aindex);

static void *alloc_attr_hash(unsigned size) {
    /* Allocate a generously large buffer per bucket to avoid needing the private struct size */
    size_t per_bucket_bytes = 64; /* ample for the real struct which should be much smaller */
    size_t total = (size_t)size * per_bucket_bytes;
    void *buf = xmlMalloc(total);
    if (buf != NULL) {
        memset(buf, 0xFF, total); /* ensure index fields (ints) are -1 */
    }
    return buf;
}

static const xmlChar **alloc_atts(size_t count) {
    const xmlChar **atts = (const xmlChar **) xmlMalloc(sizeof(const xmlChar *) * count);
    if (atts != NULL) {
        memset(atts, 0, sizeof(const xmlChar *) * count);
    }
    return atts;
}

void setUp(void) {
    /* Setup code here, or leave empty */
}

void tearDown(void) {
    /* Cleanup code here, or leave empty */
}

static void cleanup_ctxt_custom_buffers(xmlParserCtxtPtr ctxt,
                                        void *savedHash, const xmlChar **savedAtts,
                                        void *ourHash, const xmlChar **ourAtts) {
    /* Restore originals so xmlFreeParserCtxt doesn't free our allocations, then free ours */
    ctxt->attrHash = (void *)savedHash;
    ctxt->atts = (const xmlChar **)savedAtts;
    if (ourHash) xmlFree(ourHash);
    if (ourAtts) xmlFree((void *)ourAtts);
}

void test_htmlAttrHashInsert_inserts_and_detects_duplicate(void) {
    htmlParserCtxtPtr ctxt = htmlNewParserCtxt();
    TEST_ASSERT_NOT_NULL(ctxt);

    /* Save original pointers to avoid double free */
    void *savedHash = (void *)ctxt->attrHash;
    const xmlChar **savedAtts = ctxt->atts;

    unsigned size = 8; /* power of two */
    void *hashTable = alloc_attr_hash(size);
    TEST_ASSERT_NOT_NULL(hashTable);

    size_t attsCap = 16;
    const xmlChar **atts = alloc_atts(attsCap);
    TEST_ASSERT_NOT_NULL(atts);

    ctxt->attrHash = (void *)hashTable;
    ctxt->atts = (const xmlChar **)atts;

    /* Prepare attribute */
    const xmlChar *name1 = BAD_CAST "foo";
    int aindex1 = 5;
    TEST_ASSERT_TRUE(aindex1 >= 0 && (size_t)aindex1 < attsCap);
    atts[aindex1] = name1;

    /* Insert into empty table */
    int r1 = test_htmlAttrHashInsert(ctxt, size, name1, /*hash*/ 3U, aindex1);
    TEST_ASSERT_EQUAL_INT(INT_MAX, r1);

    /* Re-insert same pointer; expect previous index */
    int r2 = test_htmlAttrHashInsert(ctxt, size, name1, /*same hash*/ 3U, /*different aindex*/ 11);
    TEST_ASSERT_EQUAL_INT(aindex1, r2);

    cleanup_ctxt_custom_buffers((xmlParserCtxtPtr)ctxt, savedHash, savedAtts, hashTable, atts);
    xmlFreeParserCtxt((xmlParserCtxtPtr)ctxt);
}

void test_htmlAttrHashInsert_linear_probe_collision(void) {
    htmlParserCtxtPtr ctxt = htmlNewParserCtxt();
    TEST_ASSERT_NOT_NULL(ctxt);

    void *savedHash = (void *)ctxt->attrHash;
    const xmlChar **savedAtts = ctxt->atts;

    unsigned size = 4; /* small to force collisions */
    void *hashTable = alloc_attr_hash(size);
    TEST_ASSERT_NOT_NULL(hashTable);

    size_t attsCap = 16;
    const xmlChar **atts = alloc_atts(attsCap);
    TEST_ASSERT_NOT_NULL(atts);

    ctxt->attrHash = (void *)hashTable;
    ctxt->atts = (const xmlChar **)atts;

    /* First entry at hindex = 3 & (4 - 1) == 3 */
    const xmlChar *name1 = BAD_CAST "a";
    int aindex1 = 2;
    atts[aindex1] = name1;
    int r1 = test_htmlAttrHashInsert(ctxt, size, name1, 3U, aindex1);
    TEST_ASSERT_EQUAL_INT(INT_MAX, r1);

    /* Second entry collides (same hindex), should probe to next bucket and insert */
    const xmlChar *name2 = BAD_CAST "b";
    int aindex2 = 3;
    atts[aindex2] = name2;
    int r2 = test_htmlAttrHashInsert(ctxt, size, name2, 7U /* 7 & 3 == 3 */, aindex2);
    TEST_ASSERT_EQUAL_INT(INT_MAX, r2);

    /* Re-insert name2: should find it and return aindex2 */
    int r3 = test_htmlAttrHashInsert(ctxt, size, name2, 7U, /*ignored on hit*/ 9);
    TEST_ASSERT_EQUAL_INT(aindex2, r3);

    /* Re-insert name1: should still be found and return aindex1 */
    int r4 = test_htmlAttrHashInsert(ctxt, size, name1, 3U, /*ignored on hit*/ 8);
    TEST_ASSERT_EQUAL_INT(aindex1, r4);

    cleanup_ctxt_custom_buffers((xmlParserCtxtPtr)ctxt, savedHash, savedAtts, hashTable, atts);
    xmlFreeParserCtxt((xmlParserCtxtPtr)ctxt);
}

void test_htmlAttrHashInsert_wraps_around_table(void) {
    htmlParserCtxtPtr ctxt = htmlNewParserCtxt();
    TEST_ASSERT_NOT_NULL(ctxt);

    void *savedHash = (void *)ctxt->attrHash;
    const xmlChar **savedAtts = ctxt->atts;

    unsigned size = 4;
    void *hashTable = alloc_attr_hash(size);
    TEST_ASSERT_NOT_NULL(hashTable);

    size_t attsCap = 32;
    const xmlChar **atts = alloc_atts(attsCap);
    TEST_ASSERT_NOT_NULL(atts);

    ctxt->attrHash = (void *)hashTable;
    ctxt->atts = (const xmlChar **)atts;

    /* Fill bucket 3 */
    const xmlChar *name1 = BAD_CAST "x";
    int aindex1 = 5;
    atts[aindex1] = name1;
    int r1 = test_htmlAttrHashInsert(ctxt, size, name1, 3U, aindex1);
    TEST_ASSERT_EQUAL_INT(INT_MAX, r1);

    /* Fill bucket 0 to force wrap-around to continue further */
    const xmlChar *name0 = BAD_CAST "y";
    int aindex0 = 6;
    atts[aindex0] = name0;
    int r0 = test_htmlAttrHashInsert(ctxt, size, name0, 0U, aindex0);
    TEST_ASSERT_EQUAL_INT(INT_MAX, r0);

    /* Now insert another that collides at bucket 3; it must wrap to 1 */
    const xmlChar *name2 = BAD_CAST "z";
    int aindex2 = 7;
    atts[aindex2] = name2;
    int r2 = test_htmlAttrHashInsert(ctxt, size, name2, 7U /* 7&3==3 */, aindex2);
    TEST_ASSERT_EQUAL_INT(INT_MAX, r2);

    /* Verify we can find name2 again (wherever it was inserted after wrap) */
    int r2b = test_htmlAttrHashInsert(ctxt, size, name2, 7U, 99);
    TEST_ASSERT_EQUAL_INT(aindex2, r2b);

    cleanup_ctxt_custom_buffers((xmlParserCtxtPtr)ctxt, savedHash, savedAtts, hashTable, atts);
    xmlFreeParserCtxt((xmlParserCtxtPtr)ctxt);
}

void test_htmlAttrHashInsert_pointer_equality_only(void) {
    htmlParserCtxtPtr ctxt = htmlNewParserCtxt();
    TEST_ASSERT_NOT_NULL(ctxt);

    void *savedHash = (void *)ctxt->attrHash;
    const xmlChar **savedAtts = ctxt->atts;

    unsigned size = 8;
    void *hashTable = alloc_attr_hash(size);
    TEST_ASSERT_NOT_NULL(hashTable);

    size_t attsCap = 16;
    const xmlChar **atts = alloc_atts(attsCap);
    TEST_ASSERT_NOT_NULL(atts);

    ctxt->attrHash = (void *)hashTable;
    ctxt->atts = (const xmlChar **)atts;

    /* Two equal-content names with different pointers */
    const xmlChar *nameA1 = BAD_CAST "href";
    xmlChar *nameA2dup = xmlStrdup(nameA1); /* distinct pointer, same content */
    TEST_ASSERT_NOT_NULL(nameA2dup);

    int idx1 = 1;
    int idx2 = 2;

    atts[idx1] = nameA1;
    atts[idx2] = nameA2dup;

    /* Insert first */
    int r1 = test_htmlAttrHashInsert(ctxt, size, nameA1, 5U, idx1);
    TEST_ASSERT_EQUAL_INT(INT_MAX, r1);

    /* Insert second with same content but different pointer: should NOT match existing */
    int r2 = test_htmlAttrHashInsert(ctxt, size, nameA2dup, 5U, idx2);
    TEST_ASSERT_EQUAL_INT(INT_MAX, r2);

    /* Now duplicate lookups return their respective indices */
    int r3 = test_htmlAttrHashInsert(ctxt, size, nameA1, 5U, 99);
    TEST_ASSERT_EQUAL_INT(idx1, r3);
    int r4 = test_htmlAttrHashInsert(ctxt, size, nameA2dup, 5U, 99);
    TEST_ASSERT_EQUAL_INT(idx2, r4);

    xmlFree(nameA2dup);
    cleanup_ctxt_custom_buffers((xmlParserCtxtPtr)ctxt, savedHash, savedAtts, hashTable, atts);
    xmlFreeParserCtxt((xmlParserCtxtPtr)ctxt);
}

int main(void) {
    xmlInitParser();
    UNITY_BEGIN();

    RUN_TEST(test_htmlAttrHashInsert_inserts_and_detects_duplicate);
    RUN_TEST(test_htmlAttrHashInsert_linear_probe_collision);
    RUN_TEST(test_htmlAttrHashInsert_wraps_around_table);
    RUN_TEST(test_htmlAttrHashInsert_pointer_equality_only);

    int res = UNITY_END();
    xmlCleanupParser();
    return res;
}