Hi, Bram,
I have fixed stylistic issues with this patch and wrote a couple of
tests for it:
mfhash_testdir.patch - a simple test for existing test suite which
inserts many lines into a buffer and verifies the buffer's contents,
as you suggested to do earlier.
mfhash_unittest.patch - a more comprehensive test in C which directly
tests new functions introduced in this patch. I've added 'make
unittest' build target which compiles and runs it and which is invoked
as part of 'make test'. I'm building this test by linking it with all
vim sources which seems to be the easiest way to satisfy various link
dependencies between vim sources. 'make depend' needs to be re-run
after applying this patch.
--
Ivan
On Wed, Feb 16, 2011 at 22:07, Bram Moolenaar <[email protected]> wrote:
>
> Ivan -
>
>> Hi, I haven't written a test yet. Thank you for reminding me, I'll
>> look into writing it this week.
>>
>> So far vim built with this patch has been working fine for me.
>>
>> What do you think if I make a unit-test for mf_hash_* functions? I'd
>> write a memfile_test.c with a main() that will be conditionally
>> #included at the end of memfile.c (because tested functions are
>> static), and it'll be compiled and run by 'make test'.
>
> Well, we don't have tests like that yet. But I always thought of
> starting that, should be much faster than doing with scripts in testdir.
> And much easier to test specific parts of the code.
>
> Using #ifdef and #include makes sense. Although it can be done the
> other way around, include memline.c from the test. That could be a more
> flexible solution.
>
> We will also have to add something for "make test". I hope you can
> figure out something that can be extended for other tests later.
>
> - Bram
>
> --
> We're knights of the round table
> We dance whene'er we're able
> We do routines and chorus scenes
> With footwork impeccable.
> We dine well here in Camelot
> We eat ham and jam and spam a lot.
> "Monty Python and the Holy Grail" PYTHON (MONTY) PICTURES LTD
>
> /// Bram Moolenaar -- [email protected] -- http://www.Moolenaar.net \\\
> /// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
> \\\ an exciting new programming language -- http://www.Zimbu.org ///
> \\\ help me help AIDS victims -- http://ICCF-Holland.org ///
>
--
You received this message from the "vim_dev" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php
diff -r 0139403c8eb0 src/memfile.c
--- a/src/memfile.c Fri Feb 25 18:38:36 2011 +0100
+++ b/src/memfile.c Mon Feb 28 17:01:09 2011 +0300
@@ -84,6 +84,13 @@
static int mf_write_block __ARGS((memfile_T *mfp, bhdr_T *hp, off_t offset, unsigned size));
static int mf_trans_add __ARGS((memfile_T *, bhdr_T *));
static void mf_do_open __ARGS((memfile_T *, char_u *, int));
+static void mf_hash_init __ARGS((mf_hashtab_T *));
+static void mf_hash_clear __ARGS((mf_hashtab_T *));
+static void mf_hash_clear_all __ARGS((mf_hashtab_T *));
+static mf_hashitem_T *mf_hash_find __ARGS((mf_hashtab_T *, blocknr_T));
+static void mf_hash_add_item __ARGS((mf_hashtab_T *, mf_hashitem_T *));
+static void mf_hash_rem_item __ARGS((mf_hashtab_T *, mf_hashitem_T *));
+static int mf_hash_grow __ARGS((mf_hashtab_T *));
/*
* The functions for using a memfile:
@@ -119,7 +126,6 @@
int flags;
{
memfile_T *mfp;
- int i;
off_t size;
#if defined(STATFS) && defined(UNIX) && !defined(__QNX__)
# define USE_FSTATFS
@@ -152,11 +158,8 @@
mfp->mf_used_last = NULL;
mfp->mf_dirty = FALSE;
mfp->mf_used_count = 0;
- for (i = 0; i < MEMHASHSIZE; ++i)
- {
- mfp->mf_hash[i] = NULL; /* hash lists are empty */
- mfp->mf_trans[i] = NULL; /* trans lists are empty */
- }
+ mf_hash_init(&mfp->mf_hash);
+ mf_hash_init(&mfp->mf_trans);
mfp->mf_page_size = MEMFILE_PAGE_SIZE;
#ifdef FEAT_CRYPT
mfp->mf_old_key = NULL;
@@ -242,8 +245,6 @@
int del_file;
{
bhdr_T *hp, *nextp;
- NR_TRANS *tp, *tpnext;
- int i;
if (mfp == NULL) /* safety check */
return;
@@ -263,12 +264,8 @@
}
while (mfp->mf_free_first != NULL) /* free entries in free list */
vim_free(mf_rem_free(mfp));
- for (i = 0; i < MEMHASHSIZE; ++i) /* free entries in trans lists */
- for (tp = mfp->mf_trans[i]; tp != NULL; tp = tpnext)
- {
- tpnext = tp->nt_next;
- vim_free(tp);
- }
+ mf_hash_clear(&mfp->mf_hash);
+ mf_hash_clear_all(&mfp->mf_trans); /* free hashtable and its items */
vim_free(mfp->mf_fname);
vim_free(mfp->mf_ffname);
vim_free(mfp);
@@ -743,16 +740,7 @@
memfile_T *mfp;
bhdr_T *hp;
{
- bhdr_T *hhp;
- int hash;
-
- hash = MEMHASH(hp->bh_bnum);
- hhp = mfp->mf_hash[hash];
- hp->bh_hash_next = hhp;
- hp->bh_hash_prev = NULL;
- if (hhp != NULL)
- hhp->bh_hash_prev = hp;
- mfp->mf_hash[hash] = hp;
+ mf_hash_add_item(&mfp->mf_hash, (mf_hashitem_T *)hp);
}
/*
@@ -763,13 +751,7 @@
memfile_T *mfp;
bhdr_T *hp;
{
- if (hp->bh_hash_prev == NULL)
- mfp->mf_hash[MEMHASH(hp->bh_bnum)] = hp->bh_hash_next;
- else
- hp->bh_hash_prev->bh_hash_next = hp->bh_hash_next;
-
- if (hp->bh_hash_next)
- hp->bh_hash_next->bh_hash_prev = hp->bh_hash_prev;
+ mf_hash_rem_item(&mfp->mf_hash, (mf_hashitem_T *)hp);
}
/*
@@ -780,12 +762,7 @@
memfile_T *mfp;
blocknr_T nr;
{
- bhdr_T *hp;
-
- for (hp = mfp->mf_hash[MEMHASH(nr)]; hp != NULL; hp = hp->bh_hash_next)
- if (hp->bh_bnum == nr)
- break;
- return hp;
+ return (bhdr_T *)mf_hash_find(&mfp->mf_hash, nr);
}
/*
@@ -1187,7 +1164,6 @@
{
bhdr_T *freep;
blocknr_T new_bnum;
- int hash;
NR_TRANS *np;
int page_count;
@@ -1235,12 +1211,8 @@
hp->bh_bnum = new_bnum;
mf_ins_hash(mfp, hp); /* insert in new hash list */
- hash = MEMHASH(np->nt_old_bnum); /* insert in trans list */
- np->nt_next = mfp->mf_trans[hash];
- mfp->mf_trans[hash] = np;
- if (np->nt_next != NULL)
- np->nt_next->nt_prev = np;
- np->nt_prev = NULL;
+ /* Insert "np" into "mf_trans" hashtable with key "np->nt_old_bnum" */
+ mf_hash_add_item(&mfp->mf_trans, (mf_hashitem_T *)np);
return OK;
}
@@ -1255,25 +1227,20 @@
memfile_T *mfp;
blocknr_T old_nr;
{
- int hash;
NR_TRANS *np;
blocknr_T new_bnum;
- hash = MEMHASH(old_nr);
- for (np = mfp->mf_trans[hash]; np != NULL; np = np->nt_next)
- if (np->nt_old_bnum == old_nr)
- break;
- if (np == NULL) /* not found */
+ np = (NR_TRANS *)mf_hash_find(&mfp->mf_trans, old_nr);
+
+ if (np == NULL) /* not found */
return old_nr;
mfp->mf_neg_count--;
new_bnum = np->nt_new_bnum;
- if (np->nt_prev != NULL) /* remove entry from the trans list */
- np->nt_prev->nt_next = np->nt_next;
- else
- mfp->mf_trans[hash] = np->nt_next;
- if (np->nt_next != NULL)
- np->nt_next->nt_prev = np->nt_prev;
+
+ /* remove entry from the trans list */
+ mf_hash_rem_item(&mfp->mf_trans, (mf_hashitem_T *)np);
+
vim_free(np);
return new_bnum;
@@ -1397,3 +1364,216 @@
mch_hide(mfp->mf_fname); /* try setting the 'hidden' flag */
}
}
+
+/*
+ * Implementation of mf_hashtab_T follows.
+ */
+
+/*
+ * Number of buckets in hashtable is increased by a factor of
+ * MHT_GROWTH_FACTOR when average number of items per bucket
+ * exceeds 2^MHT_LOG_LOAD_FACTOR.
+ */
+#define MHT_LOG_LOAD_FACTOR 6
+#define MHT_GROWTH_FACTOR 2 /* must be a power of two */
+
+/*
+ * Initialize an empty hash table.
+ */
+ static void
+mf_hash_init(mht)
+ mf_hashtab_T *mht;
+{
+ vim_memset(mht, 0, sizeof(mf_hashtab_T));
+ mht->mht_buckets = mht->mht_small_buckets;
+ mht->mht_mask = MHT_INIT_SIZE - 1;
+}
+
+/*
+ * Free the array of a hash table. Does not free the items it contains!
+ * Hash table may not be used again without another mf_hash_init() call.
+ */
+ static void
+mf_hash_clear(mht)
+ mf_hashtab_T *mht;
+{
+ if (mht->mht_buckets != mht->mht_small_buckets)
+ vim_free(mht->mht_buckets);
+}
+
+/*
+ * Free the array of a hash table and all the items it contains
+ * using vim_free().
+ */
+ static void
+mf_hash_clear_all(mht)
+ mf_hashtab_T *mht;
+{
+ long_u idx;
+ mf_hashitem_T *mhi;
+ mf_hashitem_T *next;
+
+ for (idx = 0; idx <= mht->mht_mask; idx++)
+ {
+ mhi = mht->mht_buckets[idx];
+ while (mhi != NULL)
+ {
+ next = mhi->mhi_next;
+ vim_free(mhi);
+ mhi = next;
+ }
+ }
+
+ mf_hash_clear(mht);
+}
+
+/*
+ * Find "key" in hashtable "mht".
+ * Returns a pointer to a mf_hashitem_T or NULL if the item was not found.
+ */
+ static mf_hashitem_T *
+mf_hash_find(mht, key)
+ mf_hashtab_T *mht;
+ blocknr_T key;
+{
+ mf_hashitem_T *mhi;
+
+ mhi = mht->mht_buckets[key & mht->mht_mask];
+
+ while (mhi != NULL && mhi->mhi_key != key)
+ mhi = mhi->mhi_next;
+
+ return mhi;
+}
+
+/*
+ * Add item "mhi" to hashtable "mht".
+ * "mhi" must not be NULL.
+ */
+ static void
+mf_hash_add_item(mht, mhi)
+ mf_hashtab_T *mht;
+ mf_hashitem_T *mhi;
+{
+ long_u idx;
+
+ idx = mhi->mhi_key & mht->mht_mask;
+ mhi->mhi_next = mht->mht_buckets[idx];
+ mhi->mhi_prev = NULL;
+ if (mhi->mhi_next != NULL)
+ mhi->mhi_next->mhi_prev = mhi;
+ mht->mht_buckets[idx] = mhi;
+
+ mht->mht_count++;
+
+ /*
+ * Grow hashtable when we have more thank 2^MHT_LOG_LOAD_FACTOR
+ * items per bucket on average
+ */
+ if (!mht->mht_fixed &&
+ (mht->mht_count >> MHT_LOG_LOAD_FACTOR) > mht->mht_mask)
+ {
+ if (mf_hash_grow(mht) == FAIL)
+ {
+ /* stop trying to grow after first failure to allocate memory */
+ mht->mht_fixed = 1;
+ }
+ }
+}
+
+/*
+ * Remove item "mhi" from hashtable "mht".
+ * "mhi" must not be NULL and must have been inserted into "mht".
+ */
+ static void
+mf_hash_rem_item(mht, mhi)
+ mf_hashtab_T *mht;
+ mf_hashitem_T *mhi;
+{
+ if (mhi->mhi_prev == NULL)
+ mht->mht_buckets[mhi->mhi_key & mht->mht_mask] = mhi->mhi_next;
+ else
+ mhi->mhi_prev->mhi_next = mhi->mhi_next;
+
+ if (mhi->mhi_next != NULL)
+ mhi->mhi_next->mhi_prev = mhi->mhi_prev;
+
+ mht->mht_count--;
+
+ /*
+ * TODO: can shrink the table here, but it typically takes little memory,
+ * so why bother?
+ */
+}
+
+/*
+ * Increase number of buckets in the hashtable by MHT_GROWTH_FACTOR and
+ * rehash items. Returns FAIL when out of memory.
+ */
+ static int
+mf_hash_grow(mht)
+ mf_hashtab_T *mht;
+{
+ long_u i, j;
+ int shift;
+ mf_hashitem_T *mhi;
+ mf_hashitem_T *tails[MHT_GROWTH_FACTOR];
+ mf_hashitem_T **buckets;
+ size_t size;
+
+ size = (mht->mht_mask + 1) * MHT_GROWTH_FACTOR * sizeof(void *);
+ buckets = (mf_hashitem_T **)lalloc_clear(size, FALSE);
+ if (buckets == NULL)
+ return FAIL;
+
+ shift = 0;
+ while ((mht->mht_mask >> shift) != 0)
+ shift++;
+
+ for (i = 0; i <= mht->mht_mask; i++)
+ {
+ /*
+ * Traverse the items in the i-th original bucket and move them into
+ * MHT_GROWTH_FACTOR new buckets, preserving their relative order
+ * within each new bucket. Preserving the order is important because
+ * mf_get() tries to keep most recently used items at the front of
+ * each bucket.
+ *
+ * Here we strongly rely on the fact the hashes are computed modulo
+ * a power of two.
+ */
+
+ vim_memset(tails, 0, sizeof(tails));
+
+ for (mhi = mht->mht_buckets[i]; mhi != NULL; mhi = mhi->mhi_next)
+ {
+ j = (mhi->mhi_key >> shift) & (MHT_GROWTH_FACTOR - 1);
+ if (tails[j] == NULL)
+ {
+ buckets[i + (j << shift)] = mhi;
+ tails[j] = mhi;
+ mhi->mhi_prev = NULL;
+ }
+ else
+ {
+ tails[j]->mhi_next = mhi;
+ mhi->mhi_prev = tails[j];
+ tails[j] = mhi;
+ }
+ }
+
+ for (j = 0; j < MHT_GROWTH_FACTOR; j++)
+ {
+ if (tails[j] != NULL)
+ tails[j]->mhi_next = NULL;
+ }
+ }
+
+ if (mht->mht_buckets != mht->mht_small_buckets)
+ vim_free(mht->mht_buckets);
+
+ mht->mht_buckets = buckets;
+ mht->mht_mask = (mht->mht_mask + 1) * MHT_GROWTH_FACTOR - 1;
+
+ return OK;
+}
diff -r 0139403c8eb0 src/structs.h
--- a/src/structs.h Fri Feb 25 18:38:36 2011 +0100
+++ b/src/structs.h Mon Feb 28 17:01:09 2011 +0300
@@ -378,6 +378,35 @@
typedef long blocknr_T;
/*
+ * mf_hashtab_T is a chained hashtable with blocknr_T key and arbitrary
+ * structures as items. This is an intrusive data structure: we require
+ * that items begin with mf_hashitem_T which contains the key and linked
+ * list pointers. List of items in each bucket is doubly-linked.
+ */
+
+typedef struct mf_hashitem_S mf_hashitem_T;
+
+struct mf_hashitem_S
+{
+ mf_hashitem_T *mhi_next;
+ mf_hashitem_T *mhi_prev;
+ blocknr_T mhi_key;
+};
+
+#define MHT_INIT_SIZE 64
+
+typedef struct mf_hashtab_S
+{
+ long_u mht_mask; /* mask used for hash value (nr of items in
+ array is "mht_mask" + 1) */
+ long_u mht_count; /* number of items inserted into hashtable */
+ mf_hashitem_T **mht_buckets; /* points to mht_small_buckets or
+ dynamically allocated array */
+ mf_hashitem_T *mht_small_buckets[MHT_INIT_SIZE]; /* initial buckets */
+ char mht_fixed; /* non-zero values forbids growth */
+} mf_hashtab_T;
+
+/*
* for each (previously) used block in the memfile there is one block header.
*
* The block may be linked in the used list OR in the free list.
@@ -394,11 +423,11 @@
struct block_hdr
{
+ mf_hashitem_T bh_hashitem; /* header for hash table and key */
+#define bh_bnum bh_hashitem.mhi_key /* block number, part of bh_hashitem */
+
bhdr_T *bh_next; /* next block_hdr in free or used list */
bhdr_T *bh_prev; /* previous block_hdr in used list */
- bhdr_T *bh_hash_next; /* next block_hdr in hash list */
- bhdr_T *bh_hash_prev; /* previous block_hdr in hash list */
- blocknr_T bh_bnum; /* block number */
char_u *bh_data; /* pointer to memory (for used block) */
int bh_page_count; /* number of pages in this block */
@@ -417,9 +446,9 @@
struct nr_trans
{
- NR_TRANS *nt_next; /* next nr_trans in hash list */
- NR_TRANS *nt_prev; /* previous nr_trans in hash list */
- blocknr_T nt_old_bnum; /* old, negative, number */
+ mf_hashitem_T nt_hashitem; /* header for hash table and key */
+#define nt_old_bnum nt_hashitem.mhi_key /* old, negative, number */
+
blocknr_T nt_new_bnum; /* new, positive, number */
};
@@ -499,12 +528,6 @@
typedef struct file_buffer buf_T; /* forward declaration */
-/*
- * Simplistic hashing scheme to quickly locate the blocks in the used list.
- * 64 blocks are found directly (64 * 4K = 256K, most files are smaller).
- */
-#define MEMHASHSIZE 64
-#define MEMHASH(nr) ((nr) & (MEMHASHSIZE - 1))
#define MF_SEED_LEN 8
struct memfile
@@ -517,8 +540,8 @@
bhdr_T *mf_used_last; /* lru block_hdr in used list */
unsigned mf_used_count; /* number of pages in used list */
unsigned mf_used_count_max; /* maximum number of pages in memory */
- bhdr_T *mf_hash[MEMHASHSIZE]; /* array of hash lists */
- NR_TRANS *mf_trans[MEMHASHSIZE]; /* array of trans lists */
+ mf_hashtab_T mf_hash; /* hash lists */
+ mf_hashtab_T mf_trans; /* trans lists */
blocknr_T mf_blocknr_max; /* highest positive block number + 1*/
blocknr_T mf_blocknr_min; /* lowest negative block number - 1 */
blocknr_T mf_neg_count; /* number of negative blocks numbers */
diff -r 0139403c8eb0 src/testdir/Makefile
--- a/src/testdir/Makefile Fri Feb 25 18:38:36 2011 +0100
+++ b/src/testdir/Makefile Mon Feb 28 17:01:35 2011 +0300
@@ -25,7 +25,7 @@
test59.out test60.out test61.out test62.out test63.out \
test64.out test65.out test66.out test67.out test68.out \
test69.out test70.out test71.out test72.out test73.out \
- test74.out test75.out test76.out
+ test74.out test75.out test76.out test77.out
SCRIPTS_GUI = test16.out
diff -r 0139403c8eb0 src/testdir/test77.in
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/testdir/test77.in Mon Feb 28 17:01:35 2011 +0300
@@ -0,0 +1,23 @@
+Inserts 2 million lines with consecutive integers starting from 1
+(essentially, the output of GNU's seq 1 2000000), writes them to test.out
+and replaces test.out with its cksum.
+
+cksum is part of POSIX and so should be available on most Unixes.
+If it isn't available then the test will be skipped.
+
+STARTTEST
+:so small.vim
+:if !executable("cksum")
+: e! test.ok
+: w! test.out
+: qa!
+:endif
+:set ff=unix
+ggdG
+:for i in range(1, 2000000) | put =i | endfor
+ggdd
+:w! test.out
+:%!cksum test.out
+:wq! test.out
+ENDTEST
+
diff -r 0139403c8eb0 src/testdir/test77.ok
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/testdir/test77.ok Mon Feb 28 17:01:35 2011 +0300
@@ -0,0 +1,1 @@
+3678979763 14888896 test.out
diff -r 0139403c8eb0 src/Makefile
--- a/src/Makefile Fri Feb 25 18:38:36 2011 +0100
+++ b/src/Makefile Mon Feb 28 17:01:58 2011 +0300
@@ -902,6 +902,8 @@
EVIEWNAME = e$(VIEWNAME)
EVIEWTARGET = $(EVIEWNAME)$(LNKEXT)
+TEST_TARGETS = memfile_test$(EXEEXT)
+
### Names of the tools that are also made {{{1
TOOLS = xxd/xxd$(EXEEXT)
@@ -1476,12 +1478,14 @@
TAGS_SRC = *.c *.cpp if_perl.xs
+TEST_SRC = memfile_test.c
+
EXTRA_SRC = hangulin.c if_lua.c if_mzsch.c auto/if_perl.c if_perlsfio.c \
if_python.c if_python3.c if_tcl.c if_ruby.c if_sniff.c \
gui_beval.c workshop.c wsdebug.c integration.c netbeans.c
# All sources, also the ones that are not configured
-ALL_SRC = $(BASIC_SRC) $(ALL_GUI_SRC) $(EXTRA_SRC)
+ALL_SRC = $(BASIC_SRC) $(ALL_GUI_SRC) $(TEST_SRC) $(EXTRA_SRC)
# Which files to check with lint. Select one of these three lines. ALL_SRC
# checks more, but may not work well for checking a GUI that wasn't configured.
@@ -1541,6 +1545,7 @@
objects/term.o \
objects/ui.o \
objects/undo.o \
+ objects/version.o \
objects/window.o \
$(GUI_OBJ) \
$(LUA_OBJ) \
@@ -1625,6 +1630,8 @@
tools: $(TOOLS)
+build-unittests: $(TEST_TARGETS)
+
# Run configure with all the setting from above.
#
# Note: auto/config.h doesn't depend on configure, because running configure
@@ -1697,10 +1704,9 @@
# Link the target for normal use or debugging.
# A shell script is used to try linking without unneccesary libraries.
-$(VIMTARGET): auto/config.mk objects $(OBJ) version.c version.h
- $(CCC) version.c -o objects/version.o
+$(VIMTARGET): auto/config.mk objects $(OBJ)
@LINK="$(PURIFY) $(SHRPENV) $(CClink) $(ALL_LIB_DIRS) $(LDFLAGS) \
- -o $(VIMTARGET) $(OBJ) objects/version.o $(ALL_LIBS)" \
+ -o $(VIMTARGET) $(OBJ) $(ALL_LIBS)" \
MAKE="$(MAKE)" LINK_AS_NEEDED=$(LINK_AS_NEEDED) \
sh $(srcdir)/link.sh
@@ -1708,6 +1714,16 @@
cd xxd; CC="$(CC)" CFLAGS="$(CPPFLAGS) $(CFLAGS)" \
$(MAKE) -f Makefile
+memfile_test$(EXEEXT): auto/config.mk objects $(OBJ) objects/memfile_test.o
+ @LINK="$(PURIFY) $(SHRPENV) $(CClink) $(ALL_LIB_DIRS) $(LDFLAGS) \
+ -o memfile_test$(EXEEXT) \
+ `echo '$(OBJ)' | \
+ sed -e 's|objects/memfile.o|objects/memfile_test.o|' \
+ -e 's|objects/main.o||'` \
+ $(ALL_LIBS)" \
+ MAKE="$(MAKE)" LINK_AS_NEEDED=yes \
+ sh $(srcdir)/link.sh
+
# Build the language specific files if they were unpacked.
# Generate the converted .mo files separately, it's no problem if this fails.
languages:
@@ -1825,6 +1841,12 @@
ln -s $(VIMTARGET) vim; \
fi
cd testdir; $(MAKE) -f Makefile $(GUI_TESTTARGET) VIMPROG=../$(VIMTARGET) $(GUI_TESTARG)
+ $(MAKE) -f Makefile unittest
+
+unittest unittests: build-unittests
+ @for t in $(TEST_TARGETS); do \
+ ./$$t || exit 1; echo $$t passed; \
+ done
testclean:
cd testdir; $(MAKE) -f Makefile clean
@@ -2264,6 +2286,7 @@
clean celan: testclean
-rm -f *.o objects/* core $(VIMTARGET).core $(VIMTARGET) vim xxd/*.o
-rm -f $(TOOLS) auto/osdef.h auto/pathdef.c auto/if_perl.c
+ -rm -f $(TEST_TARGETS)
-rm -f conftest* *~ auto/link.sed
-rm -f runtime pixmaps
-rm -rf $(APPDIR)
@@ -2559,6 +2582,9 @@
objects/memfile.o: memfile.c
$(CCC) -o $@ memfile.c
+objects/memfile_test.o: memfile_test.c
+ $(CCC) -o $@ memfile_test.c
+
objects/memline.o: memline.c
$(CCC) -o $@ memline.c
@@ -2646,6 +2672,9 @@
objects/undo.o: undo.c
$(CCC) -o $@ undo.c
+objects/version.o: version.c
+ $(CCC) -o $@ version.c
+
objects/window.o: window.c
$(CCC) -o $@ window.c
diff -r 0139403c8eb0 src/main.c
--- a/src/main.c Fri Feb 25 18:38:36 2011 +0100
+++ b/src/main.c Mon Feb 28 17:01:58 2011 +0300
@@ -145,6 +145,7 @@
#define ME_INVALID_ARG 5
};
+#ifndef NO_VIM_MAIN
#ifndef PROTO /* don't want a prototype for main() */
int
# ifdef VIMDLL
@@ -966,6 +967,7 @@
return 0;
}
#endif /* PROTO */
+#endif /* NO_VIM_MAIN */
/*
* Main loop: Execute Normal mode commands until exiting Vim.
diff -r 0139403c8eb0 src/memfile_test.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/memfile_test.c Mon Feb 28 17:01:58 2011 +0300
@@ -0,0 +1,130 @@
+#undef NDEBUG
+#include <assert.h>
+
+/* Must include main.c because it contains much more than just main() */
+#define NO_VIM_MAIN
+#include "main.c"
+
+/* This file has to be included because the tested functions are static */
+#include "memfile.c"
+
+#define index_to_key(i) ((i) ^ 15167)
+
+/*
+ * Test mf_hash_*() functions.
+ */
+ void
+test_mf_hash()
+{
+ enum { N = 50000 };
+
+ mf_hashtab_T ht;
+ mf_hashitem_T *item;
+ blocknr_T key;
+ long_u i;
+ long_u num_buckets;
+
+ mf_hash_init(&ht);
+
+ /* insert some items and check invariants */
+ for (i = 0; i < N; i++)
+ {
+ assert(ht.mht_count == i);
+
+ /* check that number of buckets is a power of 2 */
+ num_buckets = ht.mht_mask + 1;
+ assert(num_buckets > 0 && (num_buckets & (num_buckets - 1)) == 0);
+
+ /* check load factor */
+ assert(ht.mht_count <= (num_buckets << MHT_LOG_LOAD_FACTOR));
+
+ if (i < (MHT_INIT_SIZE << MHT_LOG_LOAD_FACTOR))
+ {
+ /* first expansion shouldn't have occurred yet */
+ assert(num_buckets == MHT_INIT_SIZE);
+ assert(ht.mht_buckets == ht.mht_small_buckets);
+ }
+ else
+ {
+ assert(num_buckets > MHT_INIT_SIZE);
+ assert(ht.mht_buckets != ht.mht_small_buckets);
+ }
+
+ key = index_to_key(i);
+ assert(mf_hash_find(&ht, key) == NULL);
+
+ /* allocate and add new item */
+ item = (mf_hashitem_T *)lalloc_clear(sizeof(mf_hashtab_T), FALSE);
+ assert(item != NULL);
+ item->mhi_key = key;
+ mf_hash_add_item(&ht, item);
+
+ assert(mf_hash_find(&ht, key) == item);
+
+ if (ht.mht_mask + 1 != num_buckets)
+ {
+ /* hash table was expanded */
+ assert(ht.mht_mask + 1 == num_buckets * MHT_GROWTH_FACTOR);
+ assert(i + 1 == (num_buckets << MHT_LOG_LOAD_FACTOR));
+ }
+ }
+
+ /* check presence of inserted items */
+ for (i = 0; i < N; i++)
+ {
+ key = index_to_key(i);
+ item = mf_hash_find(&ht, key);
+ assert(item != NULL);
+ assert(item->mhi_key == key);
+ }
+
+ /* delete some items */
+ for (i = 0; i < N; i++)
+ {
+ if (i % 100 < 70)
+ {
+ key = index_to_key(i);
+ item = mf_hash_find(&ht, key);
+ assert(item != NULL);
+ assert(item->mhi_key == key);
+
+ mf_hash_rem_item(&ht, item);
+ assert(mf_hash_find(&ht, key) == NULL);
+
+ mf_hash_add_item(&ht, item);
+ assert(mf_hash_find(&ht, key) == item);
+
+ mf_hash_rem_item(&ht, item);
+ assert(mf_hash_find(&ht, key) == NULL);
+
+ vim_free(item);
+ }
+ }
+
+ /* check again */
+ for (i = 0; i < N; i++)
+ {
+ key = index_to_key(i);
+ item = mf_hash_find(&ht, key);
+
+ if (i % 100 < 70)
+ {
+ assert(item == NULL);
+ }
+ else
+ {
+ assert(item != NULL);
+ assert(item->mhi_key == key);
+ }
+ }
+
+ /* free hash table and all remaining items */
+ mf_hash_clear_all(&ht);
+}
+
+ int
+main()
+{
+ test_mf_hash();
+ return 0;
+}
