htab: prevent filling up of table with tombstones

as pointed out by @craigbarnes [0], using the latest fix for
the tombstone issue, it's possible to provoke a situation
that causes an endless loop when all free slots in the table
are filled up with tombstones and htab_find() is called.

therefore we need to account for those as well when deciding
if there's a need to call resize() so there's never more than
75% of the table used by either dead or live items.
the resize() serves as a rehash which gets rid of all deleted
entries, and it might cause the table size to shrink if
htab_insert() is called after a lot of items have been removed.

[0]: https://github.com/rofl0r/htab/issues/1#issuecomment-800094442

testcase:

    #include <assert.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "hsearch.h"

    #define HTAB_OOM_TEST
    #include "hsearch.c"

    static char *xstrdup(const char *str)
    {
        char *dup = strdup(str);
        assert(dup);
        return dup;
    }

    void utoa(unsigned number, char* buffer) {
            int lentest, len = 0, i, start = 0;

            lentest = number;
            do {
                    len++;
                    lentest /= 10;
            } while(lentest);
            buffer[start+len] = 0;
            do {
                    i = number % 10;
                    buffer[start+len - 1] = '0' + i;
                    number -= i;
                    len -= 1;
                    number /= 10;
            } while (number);
    }

    #define TESTSIZE 8
    #define KEEP 1

    static char* notorious[TESTSIZE];

    static void prep() {
    	srand(0);
    	char buf[16];
    	size_t filled = 0;
    	while(filled < TESTSIZE) {
    		utoa(rand(), buf);
    		size_t idx = keyhash(buf) & (TESTSIZE-1);
    		if(!notorious[idx]) {
    			notorious[idx] = xstrdup(buf);
    			++filled;
    		}
    	}
    }

    int main(void)
    {
    	struct htab *h = htab_create(TESTSIZE);
    	size_t i;
    	assert(h);

    	prep();
    	for(i=0; i<TESTSIZE; ++i) {
    		char *key = notorious[i];
    		printf("[%zu] = \"%s\"\n", i, key);
    		int r = htab_insert(h, key, HTV_N(42));
    		if(!r == 1) {
    			printf("element %zu couldn't be inserted\n", i);
    			break;
    		}
    		assert(r == 1);
    		// Ensure newly inserted entry can be found
    		assert(htab_find(h, key));
    		if(i >= KEEP) htab_delete(h, key);
    	}

    	htab_find(h, "looooop");

    	return 0;
    }

0 files changed, 0 insertions, 0 deletions