Menu
▾
▴
[Xsb-commits] CVS: XSB/lib storage.H, 1.13, 1.14 storage.P, 1.16, 1.17
|
From: Michael K. <ki...@us...> - 2010-06-23 02:28:48
|
Update of /cvsroot/xsb/XSB/lib In directory sfp-cvsdas-3.v30.ch3.sourceforge.com:/tmp/cvs-serv25623/lib Modified Files: storage.H storage.P Log Message: added operations for incremental tries Index: storage.H =================================================================== RCS file: /cvsroot/xsb/XSB/lib/storage.H,v retrieving revision 1.13 retrieving revision 1.14 diff -u -r1.13 -r1.14 --- storage.H 21 May 2010 23:58:11 -0000 1.13 +++ storage.H 23 Jun 2010 02:28:37 -0000 1.14 @@ -24,22 +24,34 @@ :- export + storage_commit/1, + storage_reclaim_space/1, + incr_storage_update/1, + storage_find_fact/2, + storage_find_keypair/3, + storage_handle/4, + %% this is for debugging/profiling + storage_show_table_state/0. + +:- export storage_insert_fact_bt/3, storage_delete_fact_bt/3, storage_insert_fact_bt/5, storage_delete_fact_bt/5, storage_insert_fact/3, storage_delete_fact/3, - storage_find_fact/2, - storage_reclaim_space/1, - storage_commit/1, storage_insert_keypair_bt/4, storage_delete_keypair_bt/3, storage_insert_keypair_bt/6, storage_delete_keypair_bt/5, storage_insert_keypair/4, storage_delete_keypair/3, - storage_find_keypair/3, - storage_delete_all/1, - storage_handle/4, - %% this is for debugging/profiling - storage_show_table_state/0. + storage_delete_all/1. -:- import trie_intern/5, trie_unintern_nr/2, +:- export + incr_storage_insert_fact_bt/3, incr_storage_delete_fact_bt/3, + incr_storage_insert_fact_bt/5, incr_storage_delete_fact_bt/5, + incr_storage_insert_fact/3, incr_storage_delete_fact/3, + incr_storage_insert_keypair_bt/4, incr_storage_delete_keypair_bt/3, + incr_storage_insert_keypair_bt/6, incr_storage_delete_keypair_bt/5, + incr_storage_insert_keypair/4, incr_storage_delete_keypair/3, + incr_storage_delete_all/1. + +:- import unmark_uninterned_nr/2, delete_trie/1, trie_reclaim_uninterned_nr/1 Index: storage.P =================================================================== RCS file: /cvsroot/xsb/XSB/lib/storage.P,v retrieving revision 1.16 retrieving revision 1.17 diff -u -r1.16 -r1.17 --- storage.P 27 May 2010 00:00:21 -0000 1.16 +++ storage.P 23 Jun 2010 02:28:37 -0000 1.17 @@ -36,9 +36,20 @@ %% Local version of trie_intern %%find_in_trie(Fact,TrieRoot,Leaf) :- intern:trie_interned(Fact,TrieRoot,Leaf,_). -find_in_trie(Fact,TrieRoot,Leaf) :- intern:fast_trie_interned(TrieRoot,Fact,Leaf). +find_in_trie(Fact,TrieRoot,Leaf) :- + intern:fast_trie_interned(TrieRoot,Fact,Leaf). +put_in_trie(Fact,Handle,Leaf,Flag) :- + intern:trie_intern(Fact,Handle,Leaf,Flag,_). +delete_from_trie(Handle,Leaf) :- + intern:trie_unintern_nr(Handle,Leaf). +incr_put_in_trie(Fact,Handle,Leaf,Flag) :- + intern:incr_trie_intern(Fact,Handle,Leaf,Flag). +incr_delete_from_trie(Handle,Leaf) :- + intern:incr_trie_unintern_nr(Handle,Leaf). +%%%%%%%%%%%%%%%%%%%%%%%%% Insertion %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %% Inserts facts. On backtracking, the fact is deleted. storage_insert_fact_bt(StorageName,Fact,Inserted) :- storage_insert_fact_bt(StorageName,Fact,Inserted,true,true). @@ -46,17 +57,17 @@ %% ForwAction - hook to call on forward execution %% BackAction - hook to call on backward execution storage_insert_fact_bt(StorageName,Fact,Inserted,ForwAction,BackAction) :- - storage_handle(StorageName,H,Snapshot), - trie_intern(Fact, H, Leaf, New, _), + storage_handle(StorageName,NON_INCREMENTAL_TRIE,H,Snapshot), + put_in_trie(Fact, H, Leaf, New), (New == 0 -> Inserted=1, % new fact inserted mark_storage_changed_bt(StorageName), ( call(ForwAction) ; %% On backtracking - storage_handle(StorageName,_,NewSnapshot), + storage_handle(StorageName,NON_INCREMENTAL_TRIE,_,NewSnapshot), (NewSnapshot =< Snapshot -> - trie_unintern_nr(H, Leaf), + delete_from_trie(H, Leaf), call(BackAction), fail ) @@ -67,8 +78,8 @@ %% Nonbacktrackable insert storage_insert_fact(StorageName,Fact,Inserted) :- - storage_handle(StorageName,H,_), - trie_intern(Fact, H, _Leaf, New, _), + storage_handle(StorageName,NON_INCREMENTAL_TRIE,H,_), + put_in_trie(Fact, H, _Leaf, New), !, (New == 0 -> Inserted=1 % new fact inserted @@ -76,6 +87,45 @@ ). +%% Inserts facts. On backtracking, the fact is deleted. +incr_storage_insert_fact_bt(StorageName,Fact,Inserted) :- + incr_storage_insert_fact_bt(StorageName,Fact,Inserted,true,true). + +%% ForwAction - hook to call on forward execution +%% BackAction - hook to call on backward execution +incr_storage_insert_fact_bt(StorageName,Fact,Inserted,ForwAction,BackAction) :- + storage_handle(StorageName,INCREMENTAL_TRIE,H,Snapshot), + incr_put_in_trie(Fact, H, Leaf, New), + (New == 0 + -> Inserted=1, % new fact inserted + mark_storage_changed_bt(StorageName), + ( call(ForwAction) + ; %% On backtracking + storage_handle(StorageName,INCREMENTAL_TRIE,_,NewSnapshot), + (NewSnapshot =< Snapshot + -> + incr_delete_from_trie(H, Leaf), + call(BackAction), + fail + ) + ) + ; Inserted=0 % fact was already there: no action + ). + + +%% Nonbacktrackable insert +incr_storage_insert_fact(StorageName,Fact,Inserted) :- + storage_handle(StorageName,INCREMENTAL_TRIE,H,_), + incr_put_in_trie(Fact, H, _Leaf, New), + !, + (New == 0 + -> Inserted=1 % new fact inserted + ; Inserted=0 % fact was already there: no action + ). + + +%%%%%%%%%%%%%%%%%%%%%%%%% Deletion %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %% Backtrackable delete. %% Doesn't remove anything, but instead "marks" for deletion. %% On backtracking: unmarks facts that are marked for deletion @@ -85,14 +135,14 @@ %% ForwAction - hook to call on forward execution %% BackAction - hook to call on backward execution storage_delete_fact_bt(StorageName,Fact,Deleted,ForwAction,BackAction) :- - storage_handle(StorageName,H,Snapshot), + storage_handle(StorageName,NON_INCREMENTAL_TRIE,H,Snapshot), (find_in_trie(Fact, H, Leaf) -> Deleted=1, % existing fact deleted mark_storage_changed_bt(StorageName), - ( trie_unintern_nr(H, Leaf), + ( delete_from_trie(H, Leaf), call(ForwAction) ; %% On backtracking - storage_handle(StorageName,_,NewSnapshot), + storage_handle(StorageName,NON_INCREMENTAL_TRIE,_,NewSnapshot), (NewSnapshot =< Snapshot -> unmark_uninterned_nr(H, Leaf), @@ -105,29 +155,66 @@ %% Nonbacktrackable delete storage_delete_fact(StorageName,Fact,Deleted) :- - storage_handle(StorageName,H,_), + storage_handle(StorageName,NON_INCREMENTAL_TRIE,H,_), !, (find_in_trie(Fact, H, Leaf) -> Deleted=1, % existing fact deleted - trie_unintern_nr(H, Leaf) + delete_from_trie(H, Leaf) ; Deleted=0 % non-existing fact: no action ). %% deletes the whole trie storage_delete_all(StorageName) :- - storage_handle(StorageName,H,_), + storage_handle(StorageName,NON_INCREMENTAL_TRIE,H,_), !, storage_builtin(DESTROY_STORAGE_HANDLE,StorageName,_,_,_,_), delete_trie(H). +%% Backtrackable delete. +%% Doesn't remove anything, but instead "marks" for deletion. +%% On backtracking: unmarks facts that are marked for deletion +incr_storage_delete_fact_bt(StorageName,Fact,Deleted) :- + incr_storage_delete_fact_bt(StorageName,Fact,Deleted,true,true). -%% Find fact in storage -storage_find_fact(StorageName,Fact) :- - storage_handle(StorageName,H,_), +%% ForwAction - hook to call on forward execution +%% BackAction - hook to call on backward execution +incr_storage_delete_fact_bt(StorageName,Fact,Deleted,ForwAction,BackAction) :- + storage_handle(StorageName,INCREMENTAL_TRIE,H,Snapshot), + (find_in_trie(Fact, H, Leaf) + -> Deleted=1, % existing fact deleted + mark_storage_changed_bt(StorageName), + ( incr_delete_from_trie(H, Leaf), + call(ForwAction) + ; %% On backtracking + storage_handle(StorageName,INCREMENTAL_TRIE,_,NewSnapshot), + (NewSnapshot =< Snapshot + -> + unmark_uninterned_nr(H, Leaf), + call(BackAction), + fail + ) + ) + ; Deleted=0 % non-existing fact: no action + ). + +%% Nonbacktrackable delete +incr_storage_delete_fact(StorageName,Fact,Deleted) :- + storage_handle(StorageName,INCREMENTAL_TRIE,H,_), !, - find_in_trie(Fact, H, _). + (find_in_trie(Fact, H, Leaf) + -> Deleted=1, % existing fact deleted + incr_delete_from_trie(H, Leaf) + ; Deleted=0 % non-existing fact: no action + ). +%% deletes the whole trie +incr_storage_delete_all(StorageName) :- + storage_handle(StorageName,INCREMENTAL_TRIE,H,_), + !, + storage_builtin(DESTROY_STORAGE_HANDLE,StorageName,_,_,_,_), + delete_trie(H). +%%%%%%%%%%%%%%%%%%%%%%%%% Insert keypair %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% The folowing two functions insert key-value pairs %% If inserting an already existing keypair, then return 0 @@ -140,21 +227,82 @@ %% ForwAction - hook to call on forward execution %% BackAction - hook to call on backward execution storage_insert_keypair_bt(StorageName,Key,Value,Inserted,ForwAction,BackAction) :- - storage_handle(StorageName,H,Snapshot), + storage_handle(StorageName,NON_INCREMENTAL_TRIE,H,Snapshot), + %% If this key already exists, then don't insert and return -1 + (find_in_trie(pair(Key,Val), H, _Leaf) + -> (Val==Value -> Inserted=0 ; Inserted = -1) + ; + %% Key doesn't exist + put_in_trie(pair(Key,Value), H, Leaf_Pair, _New), + Inserted = 1, % new fact: insert it + mark_storage_changed_bt(StorageName), + ( call(ForwAction) + ; %% On backtracking + storage_handle(StorageName,NON_INCREMENTAL_TRIE,_,NewSnapshot), + (NewSnapshot =< Snapshot + -> + delete_from_trie(H, Leaf_Pair), + call(BackAction), + fail + ) + ) + ). + + +%% Like keypair_insert_bt +%% but these are not backtrackable. +storage_insert_keypair(StorageName,Key, Value, Inserted):- + storage_handle(StorageName,NON_INCREMENTAL_TRIE,H,_), + %% If this key already exists, then don't insert and return -1 + ( find_in_trie(pair(Key,Val), H, _Leaf) + -> (Val==Value -> Inserted=0 ; Inserted = -1) + ; + %% Key doesn't exist + put_in_trie(pair(Key,Value), H, _Leaf_Pair, _New), + Inserted = 1 % new fact: insert it + ). + + + +%% Like keypair_insert_bt, keypair_delete_bt, +%% but these are not backtrackable. +incr_storage_insert_keypair(StorageName,Key, Value, Inserted):- + storage_handle(StorageName,INCREMENTAL_TRIE,H,_), + %% If this key already exists, then don't insert and return -1 + ( find_in_trie(pair(Key,Val), H, _Leaf) + -> (Val==Value -> Inserted=0 ; Inserted = -1) + ; + %% Key doesn't exist + incr_put_in_trie(pair(Key,Value), H, _Leaf_Pair, _New), + Inserted = 1 % new fact: insert it + ). + +%% The folowing two functions insert key-value pairs +%% If inserting an already existing keypair, then return 0 +%% If inserting a non-existing keypair with an existing key, then return -1. +%% In both cases don't insert anything. +%% If keypair is new, return 1 and insert pair(Key,Val) +incr_storage_insert_keypair_bt(StorageName,Key,Value,Inserted):- + incr_storage_insert_keypair_bt(StorageName,Key,Value,Inserted,true,true). + +%% ForwAction - hook to call on forward execution +%% BackAction - hook to call on backward execution +incr_storage_insert_keypair_bt(StorageName,Key,Value,Inserted,ForwAction,BackAction) :- + storage_handle(StorageName,INCREMENTAL_TRIE,H,Snapshot), %% If this key already exists, then don't insert and return -1 (find_in_trie(pair(Key,Val), H, _Leaf) -> (Val==Value -> Inserted=0 ; Inserted = -1) ; %% Key doesn't exist - trie_intern(pair(Key,Value), H, Leaf_Pair, _New, _ ), + incr_put_in_trie(pair(Key,Value), H, Leaf_Pair, _New), Inserted = 1, % new fact: insert it mark_storage_changed_bt(StorageName), ( call(ForwAction) ; %% On backtracking - storage_handle(StorageName,_,NewSnapshot), + storage_handle(StorageName,INCREMENTAL_TRIE,_,NewSnapshot), (NewSnapshot =< Snapshot -> - trie_unintern_nr(H, Leaf_Pair), + incr_delete_from_trie(H, Leaf_Pair), call(BackAction), fail ) @@ -170,14 +318,14 @@ %% ForwAction - hook to call on forward execution %% BackAction - hook to call on backward execution storage_delete_keypair_bt(StorageName,Key,Deleted,ForwAction,BackAction) :- - storage_handle(StorageName,H,Snapshot), + storage_handle(StorageName,NON_INCREMENTAL_TRIE,H,Snapshot), (find_in_trie(pair(Key,_Value), H, Leaf) -> Deleted = 1, % this is an existing fact: delete it mark_storage_changed_bt(StorageName), - ( trie_unintern_nr(H, Leaf), + ( delete_from_trie(H, Leaf), call(ForwAction) ; %% On backtracking - storage_handle(StorageName,_,NewSnapshot), + storage_handle(StorageName,NON_INCREMENTAL_TRIE,_,NewSnapshot), (NewSnapshot =< Snapshot -> unmark_uninterned_nr(H, Leaf), @@ -189,36 +337,69 @@ ). +%% If key exists, then delete the pair and return 1; otherwise, return 0 +storage_delete_keypair(StorageName,Key, Deleted):- + storage_handle(StorageName,NON_INCREMENTAL_TRIE,H,_), + (find_in_trie(pair(Key,_Value), H, Leaf) + -> Deleted = 1, % this is an existing fact: delete it + delete_from_trie(H, Leaf) + ; Deleted = 0 % no such fact -- no action + ). -%% Like keypair_insert_bt, keypair_delete_bt, -%% but these are not backtrackable. -storage_insert_keypair(StorageName,Key, Value, Inserted):- - storage_handle(StorageName,H,_), - %% If this key already exists, then don't insert and return -1 - ( find_in_trie(pair(Key,Val), H, _Leaf) - -> (Val==Value -> Inserted=0 ; Inserted = -1) - ; - %% Key doesn't exist - trie_intern(pair(Key,Value), H, _Leaf_Pair, _New, _ ), - Inserted = 1 % new fact: insert it + +%% If key exists, then delete the pair and return 1; otherwise, return 0 +incr_storage_delete_keypair_bt(StorageName,Key,Deleted) :- + incr_storage_delete_keypair_bt(StorageName,Key,Deleted,true,true). + +%% ForwAction - hook to call on forward execution +%% BackAction - hook to call on backward execution +incr_storage_delete_keypair_bt(StorageName,Key,Deleted,ForwAction,BackAction) :- + storage_handle(StorageName,INCREMENTAL_TRIE,H,Snapshot), + (find_in_trie(pair(Key,_Value), H, Leaf) + -> Deleted = 1, % this is an existing fact: delete it + mark_storage_changed_bt(StorageName), + ( incr_delete_from_trie(H, Leaf), + call(ForwAction) + ; %% On backtracking + storage_handle(StorageName,INCREMENTAL_TRIE,_,NewSnapshot), + (NewSnapshot =< Snapshot + -> + unmark_uninterned_nr(H, Leaf), + call(BackAction), + fail + ) + ) + ; Deleted = 0 % no such fact -- no action ). %% If key exists, then delete the pair and return 1; otherwise, return 0 -storage_delete_keypair(StorageName,Key, Deleted):- - storage_handle(StorageName,H,_), +incr_storage_delete_keypair(StorageName,Key, Deleted):- + storage_handle(StorageName,INCREMENTAL_TRIE,H,_), (find_in_trie(pair(Key,_Value), H, Leaf) -> Deleted = 1, % this is an existing fact: delete it - trie_unintern_nr(H, Leaf) + incr_delete_from_trie(H, Leaf) ; Deleted = 0 % no such fact -- no action ). + +%%%%%%%%%%%%%%%%%%%%%%%%%% Retrieval %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%% Find fact in storage +storage_find_fact(StorageName,Fact) :- + storage_handle(StorageName,NON_INCREMENTAL_TRIE,H,_), + !, + find_in_trie(Fact, H, _). + + storage_find_keypair(StorageName,Key,Value) :- - storage_handle(StorageName,H,_), + storage_handle(StorageName,NON_INCREMENTAL_TRIE,H,_), find_in_trie(pair(Key,Value),H,_). +%%%%%%%%%%%%%%%%%%%%%%%%%%%% Commit %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %% Commit changes to the storage trie associated with StorageName %% (only if storage has been changed) storage_commit(StorageName) :- @@ -228,11 +409,24 @@ ; fail ). + +%% Update tables for incremental tabling +incr_storage_update(StorageName) :- + ( storage_builtin(INCREMENT_STORAGE_SNAPSHOT,StorageName,_,_,_,_), + increval:incr_table_update, + ! + %% don't backtrack over it + ; fail + ). + + +%%%%%%%%%%%%%%%%%%%%%%%%%% Reclaim, handle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %% Reclaims space by removing nodes from the backtrackable insert/keypair trie %% which were marked for deletion. This should be done only at the top %% level of a query. storage_reclaim_space(StorageName) :- - storage_handle(StorageName,H,_), + storage_handle(StorageName,NON_INCREMENTAL_TRIE,H,_), !, trie_reclaim_uninterned_nr(H). @@ -244,11 +438,6 @@ ; throw(error(storage('Invalid storage name', StorageName)))), storage_builtin(GET_STORAGE_HANDLE,StorageName,TrieType,Handle,Snapshot,_). -%% This is used by all calls here. The try type argument -%% does not matter if the try has been already created. -storage_handle(StorageName,Handle,Snapshot) :- - storage_handle(StorageName,NON_INCREMENTAL_TRIE,Handle,Snapshot). - mark_storage_changed_bt(StorageName) :- storage_builtin(MARK_STORAGE_CHANGED,StorageName,_,_,_,_). |