From 4709455db3891f6cad9a96a574296b4926f70cbe Mon Sep 17 00:00:00 2001 From: David Barr <david.barr@cordelta.com> Date: Mon, 9 Aug 2010 17:11:11 -0500 Subject: Add memory pool library Add a memory pool library implemented using C macros. The obj_pool_gen() macro creates a type-specific memory pool. The memory pool library is distinguished from the existing specialized allocators in alloc.c by using a contiguous block for all allocations. This means that on one hand, long-lived pointers have to be written as offsets, since the base address changes as the pool grows, but on the other hand, the entire pool can be easily written to the file system. This could allow the memory pool to persist between runs of an application. For the svn importer, such a facility is useful because each svn revision can copy trees and files from any previous revision. The relevant information for all revisions has to persist somehow to support incremental runs. [rr: minor cleanups] [jn: added tests; removed file system backing for now] Signed-off-by: David Barr <david.barr@cordelta.com> Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com> --- .gitignore | 1 + 1 file changed, 1 insertion(+) (limited to '.gitignore') diff --git a/.gitignore b/.gitignore index 14e2b6bde9..1e64a6a138 100644 --- a/.gitignore +++ b/.gitignore @@ -167,6 +167,7 @@ /test-genrandom /test-index-version /test-match-trees +/test-obj-pool /test-parse-options /test-path-utils /test-run-command -- cgit v1.2.1 From 951f316470acc7c785c460a4e40735b22822349f Mon Sep 17 00:00:00 2001 From: Jason Evans <jasone@canonware.com> Date: Mon, 9 Aug 2010 17:17:34 -0500 Subject: Add treap implementation Provide macros to generate a type-specific treap implementation and various functions to operate on it. It uses obj_pool.h to store memory nodes in a treap. Previously committed nodes are never removed from the pool; after any *_commit operation, it is assumed (correctly, in the case of svn-fast-export) that someone else must care about them. Treaps provide a memory-efficient binary search tree structure. Insertion/deletion/search are about as about as fast in the average case as red-black trees and the chances of worst-case behavior are vanishingly small, thanks to (pseudo-)randomness. The bad worst-case behavior is a small price to pay, given that treaps are much simpler to implement. >From http://www.canonware.com/download/trp/trp_hash/trp.h [db: Altered to reference nodes by offset from a common base pointer] [db: Bob Jenkins' hashing implementation dropped for Knuth's] [db: Methods unnecessary for search and insert dropped] [rr: Squelched compiler warnings] [db: Added support for immutable treap nodes] [jn: Reintroduced treap_nsearch(); with tests] Signed-off-by: David Barr <david.barr@cordelta.com> Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com> --- .gitignore | 1 + 1 file changed, 1 insertion(+) (limited to '.gitignore') diff --git a/.gitignore b/.gitignore index 1e64a6a138..af47653fed 100644 --- a/.gitignore +++ b/.gitignore @@ -173,6 +173,7 @@ /test-run-command /test-sha1 /test-sigchain +/test-treap /common-cmds.h *.tar.gz *.dsc -- cgit v1.2.1 From 1d73b52f5ba4184de6acf474f14668001304a10c Mon Sep 17 00:00:00 2001 From: David Barr <david.barr@cordelta.com> Date: Mon, 9 Aug 2010 17:34:42 -0500 Subject: Add string-specific memory pool Intern strings so they can be compared by address and stored without wasting space. This library uses the macros in the obj_pool.h and trp.h to create a memory pool for strings and expose an API for handling them. [rr: added API docs] [jn: with some API simplifications, new documentation and tests] Signed-off-by: David Barr <david.barr@cordelta.com> Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com> --- .gitignore | 1 + 1 file changed, 1 insertion(+) (limited to '.gitignore') diff --git a/.gitignore b/.gitignore index af47653fed..9f109db88e 100644 --- a/.gitignore +++ b/.gitignore @@ -173,6 +173,7 @@ /test-run-command /test-sha1 /test-sigchain +/test-string-pool /test-treap /common-cmds.h *.tar.gz -- cgit v1.2.1 From 3bbaec00a8ffc6ea7e71c3b707851fe663d93a45 Mon Sep 17 00:00:00 2001 From: David Barr <david.barr@cordelta.com> Date: Mon, 9 Aug 2010 17:39:43 -0500 Subject: Add stream helper library This library provides thread-unsafe fgets()- and fread()-like functions where the caller does not have to supply a buffer. It maintains a couple of static buffers and provides an API to use them. [rr: allow input from files other than stdin] [jn: with tests, documentation, and error handling improvements] Signed-off-by: David Barr <david.barr@cordelta.com> Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com> --- .gitignore | 1 + 1 file changed, 1 insertion(+) (limited to '.gitignore') diff --git a/.gitignore b/.gitignore index 9f109db88e..8c0512e03b 100644 --- a/.gitignore +++ b/.gitignore @@ -166,6 +166,7 @@ /test-dump-cache-tree /test-genrandom /test-index-version +/test-line-buffer /test-match-trees /test-obj-pool /test-parse-options -- cgit v1.2.1 From 21746aa34fc99d2c73634bc9829387c27c109dbe Mon Sep 17 00:00:00 2001 From: David Barr <david.barr@cordelta.com> Date: Mon, 9 Aug 2010 17:55:00 -0500 Subject: SVN dump parser svndump parses data that is in SVN dumpfile format produced by `svnadmin dump` with the help of line_buffer and uses repo_tree and fast_export to emit a git fast-import stream. Based roughly on com.hydrografix.svndump 0.92 from the SvnToCCase project at <http://svn2cc.sarovar.org/>, by Stefan Hegny and others. [rr: allow input from files other than stdin] [jn: with test, more error reporting] Signed-off-by: David Barr <david.barr@cordelta.com> Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com> --- .gitignore | 1 + 1 file changed, 1 insertion(+) (limited to '.gitignore') diff --git a/.gitignore b/.gitignore index 8c0512e03b..258723f681 100644 --- a/.gitignore +++ b/.gitignore @@ -175,6 +175,7 @@ /test-sha1 /test-sigchain /test-string-pool +/test-svn-fe /test-treap /common-cmds.h *.tar.gz -- cgit v1.2.1