/[rucksack]/rucksack/p-btrees.lisp
ViewVC logotype

Log of /rucksack/p-btrees.lisp

Parent Directory Parent Directory | Revision Log Revision Log


Links to HEAD: (view) (annotate)
Sticky Tag:

Revision 1.19 - (view) (annotate) - [select for diffs]
Tue Feb 19 22:44:06 2008 UTC (6 years, 2 months ago) by alemmens
Branch: MAIN
CVS Tags: HEAD
Changes since 1.18: +249 -104 lines
Diff to previous 1.18
Version 0.1.17: add some list functions and replace persistent lists
by persistent btrees for non-unique slot indexes.

Revision 1.18 - (view) (annotate) - [select for diffs]
Mon Feb 11 12:47:52 2008 UTC (6 years, 2 months ago) by alemmens
Branch: MAIN
Changes since 1.17: +339 -285 lines
Diff to previous 1.17
Version 0.1.16: improved performance by decreasing persistent consing for btrees
and using a lazy-cache.  Fixed some small bugs.  Added a few handy functions and
macros.

In detail:

Added P-PUSH and P-POP.

Improved btree efficiency by switching to a different data structure
for the bindings.  Instead of using a persistent cons for each key/
value pair, we now put the keys and values directly into the bnode
vector.  This speeds up most btree operations because it reduces
persistent consing when adding new values and it reduces indirections
when searching for keys.

Renamed BTREE-NODE to BNODE, BTREE-NODE-INDEX to BNODE-BINDINGS,
BTREE-NODE-INDEX-COUNT to BNODE-NR-BINDINGS, FIND-BINDING-IN-NODE to
FIND-KEY-IN-NODE.

Fix a missing argument bug in REMOVE-CLASS-INDEX.

Added a LAZY-CACHE which just clears the entire hash table whenever
the cache gets full.  This improves memory usage, because the normal
cache queue kept track of a lot of objects that for some reason
couldn't be cleaned up by the implementation's garbage collector.

Added the convenience macros RUCKSACK-DO-CLASS and RUCKSACK-DO-SLOT.

Made RUCKSACK-DELETE-OBJECT an exported symbol of the RUCKSACK
package.

Fix a bug in TEST-NON-UNIQUE-BTREE: it should call
CHECK-NON-UNIQUE-CONTENTS instead of CHECK-CONTENTS.

Revision 1.17 - (view) (annotate) - [select for diffs]
Tue Jan 22 15:59:24 2008 UTC (6 years, 2 months ago) by alemmens
Branch: MAIN
Changes since 1.16: +39 -30 lines
Diff to previous 1.16
- Fix bug caused by LEAF-DELETE-KEY.  Reported and fixed by Brad Beveridge.
- Fix some typos (:VALUE should be :VALUE=) in index.lisp.
- Version 0.1.11.

Revision 1.16 - (view) (annotate) - [select for diffs]
Wed Jan 16 15:08:20 2008 UTC (6 years, 3 months ago) by alemmens
Branch: MAIN
Changes since 1.15: +9 -8 lines
Diff to previous 1.15
When deleting a key from a btree, use the BTREE-KEY= function (not P-EQL) to determine
the position of the key.  Reported and fixed by Leonid Novikov.

Revision 1.15 - (view) (annotate) - [select for diffs]
Sun Aug 12 13:01:14 2007 UTC (6 years, 8 months ago) by alemmens
Branch: MAIN
Changes since 1.14: +82 -20 lines
Diff to previous 1.14
Fix btree bug during btree-delete: if we're deleting the biggest key
from a leaf, we should update the parents so they'll use the key that
has now become the biggest.  (Henrik Hjelte.)

Try to signal an error when an incompatible value is given to indexed
slots, e.g. trying to put a string into a slot with a :symbol-index.
(Henrik Hjelte)

Signal an error during when putting duplicate values into a slot for
which duplicate values are not allowed.  (Henrik Hjelte)

Use BTREE-VALUE-TYPE, not BTREE-KEY-TYPE, when type checking a value
during BTREE-INSERT.  (Henrik Hjelte)

Wrap COMPILE-FILE calls in a WITH-COMPILATION-UNIT to prevent
superfluous warnings about undefined functions.

Revision 1.14 - (view) (annotate) - [select for diffs]
Tue Mar 13 13:13:00 2007 UTC (7 years, 1 month ago) by alemmens
Branch: MAIN
Changes since 1.13: +2 -2 lines
Diff to previous 1.13
Fix a bug in LEAF-DELETE-KEY (thanks to Henrik Hjelte).

Add RUCKSACK-DELETE-OBJECT, RUCKSACK-DELETE-OBJECTS and
RUCKSACK-ROOT-P (suggested by Henrik Hjelte).  I haven't
tested these functions yet.

Revision 1.13 - (view) (annotate) - [select for diffs]
Sat Jan 20 18:17:55 2007 UTC (7 years, 3 months ago) by alemmens
Branch: MAIN
Changes since 1.12: +1074 -1074 lines
Diff to previous 1.12
Version 0.1.5: removed ^M line terminators from all source files
(thanks to Attila Lendvai).

Revision 1.12 - (view) (annotate) - [select for diffs]
Tue Jan 16 08:47:36 2007 UTC (7 years, 3 months ago) by charmon
Branch: MAIN
Changes since 1.11: +38 -21 lines
Diff to previous 1.11
rucksack 0.1.3
 * use binary search instead of linear search in find-subnode and
   find-binding-in-node

Revision 1.11 - (view) (annotate) - [select for diffs]
Tue Jan 16 08:42:24 2007 UTC (7 years, 3 months ago) by charmon
Branch: MAIN
Changes since 1.10: +2 -2 lines
Diff to previous 1.10
rucksack 0.1.2
 * btree-max-node-size now defaults to 32 instead of 100

Revision 1.10 - (view) (annotate) - [select for diffs]
Sat Aug 26 12:55:34 2006 UTC (7 years, 7 months ago) by alemmens
Branch: MAIN
Changes since 1.9: +3 -2 lines
Diff to previous 1.9
Make sure that indexing works correctly with subclasses.
Fix some more indexing bugs.

Revision 1.9 - (view) (annotate) - [select for diffs]
Thu Aug 10 12:36:16 2006 UTC (7 years, 8 months ago) by alemmens
Branch: MAIN
Changes since 1.8: +54 -18 lines
Diff to previous 1.8
Do a FINISH-OUTPUT at the end of a transaction commit (suggested by Marco Baringer).

Add :KEY-KEY and :VALUE-KEY initargs to btrees.

Add some standard slot indexes.

Add :UNIQUE initarg for persistent slots (not finished yet).

Revision 1.8 - (view) (annotate) - [select for diffs]
Tue Aug 8 13:35:18 2006 UTC (7 years, 8 months ago) by alemmens
Branch: MAIN
Changes since 1.7: +416 -107 lines
Diff to previous 1.7
Fix bugs in BTREE-DELETE and SPLIT-BTREE-NODE.

Rename BTREE-DELETE to BTREE-DELETE-KEY and implement BTREE-DELETE for
btrees with non-unique keys.

Add stress test for btrees.

Implement the :MIN, :MAX, :INCLUDE-MIN, :INCLUDE-MAX and :ORDER arguments
for BTREE-MAP.

Add some more CL mirror functions like P-MAPCAR, P-MAPC, P-DELETE-IF, etcetera.

Revision 1.7 - (view) (annotate) - [select for diffs]
Fri Aug 4 22:04:43 2006 UTC (7 years, 8 months ago) by alemmens
Branch: MAIN
Changes since 1.6: +292 -86 lines
Diff to previous 1.6
Clean up btree code.  Add BTREE-DELETE.  (From Edi Weitz.)

Revision 1.6 - (view) (annotate) - [select for diffs]
Fri Aug 4 11:06:04 2006 UTC (7 years, 8 months ago) by alemmens
Branch: MAIN
Changes since 1.5: +10 -3 lines
Diff to previous 1.5
Improve error reporting for btree errors (from Edi Weitz).

Revision 1.5 - (view) (annotate) - [select for diffs]
Fri Aug 4 10:59:10 2006 UTC (7 years, 8 months ago) by alemmens
Branch: MAIN
Changes since 1.4: +20 -6 lines
Diff to previous 1.4
Provide restarts for BTREE-SEARCH (from Edi Weitz).

Revision 1.4 - (view) (annotate) - [select for diffs]
Thu May 25 13:01:38 2006 UTC (7 years, 10 months ago) by alemmens
Branch: MAIN
Changes since 1.3: +5 -8 lines
Diff to previous 1.3
Move tests from obsolete test files to test.lisp and adapt them to the
current Rucksack version.  Start testing btrees: the basics work, but
with large btrees (20,000 nodes or more?) I get GC errors again.  It
seems that blocks are deallocated that shouldn be, so my guess is that
these are due to a mismatch between the liveness of objects that are
on disk and their corresponding in-memory versions.

Revision 1.3 - (view) (annotate) - [select for diffs]
Thu May 18 12:46:57 2006 UTC (7 years, 11 months ago) by alemmens
Branch: MAIN
Changes since 1.2: +2 -1 lines
Diff to previous 1.2
Merged patches for OpenMCL from Marco Baringer.

Revision 1.2 - (view) (annotate) - [select for diffs]
Tue May 16 22:01:27 2006 UTC (7 years, 11 months ago) by alemmens
Branch: MAIN
Changes since 1.1: +1 -1 lines
Diff to previous 1.1
Some trivial CVS header changes.

Revision 1.1 - (view) (annotate) - [select for diffs]
Tue May 16 21:16:34 2006 UTC (7 years, 11 months ago) by alemmens
Branch: MAIN
Created Rucksack CVS repository on common-lisp.net.

This form allows you to request diffs between any two revisions of this file. For each of the two "sides" of the diff, select a symbolic revision name using the selection box, or choose 'Use Text Field' and enter a numeric revision.

  Diffs between and
  Type of Diff should be a

Sort log by:

  ViewVC Help
Powered by ViewVC 1.1.5