Implementation of LZ-index for extracting text

[SXSI/TextCollection.git] / lzindex / nodemap.c

diff --git a/lzindex/nodemap.c b/lzindex/nodemap.c
new file mode 100644 (file)
index 0000000..b72d474
--- /dev/null
+++ b/lzindex/nodemap.c
@@ -0,0 +1,61 @@
+
+// Implements the Map data structure, which maps block ids to lztrie nodes
+
+#include "nodemap.h"
+
+       // creates a nodemap structure from a mapping array, not owning it
+       // n is number of blocks
+       // max is the number of trie nodes
+
+nodemap createNodemap(uint *map, uint n, uint max)
+ { 
+    nodemap M;
+    uint i;
+    M = malloc(sizeof(struct snodemap));
+    M->nbits = bits(2*max-1);
+    M->n = n;
+    M->map = malloc(((n*M->nbits+W-1)/W)*sizeof(uint));
+    for (i=0;i<n;i++)
+       bitput(M->map,i*M->nbits,M->nbits,map[i]);
+    return M;
+ }
+
+       // frees revtrie structure, including the owned data
+
+void destroyNodemap(nodemap M)
+ { 
+    free(M->map);
+    free(M);
+ }
+
+       // mapping
+
+trieNode mapto(nodemap M, uint id)
+ { 
+    return bitget(M->map,id*M->nbits,M->nbits);
+ }
+
+void saveNodemap(FILE *f, nodemap M)
+ {
+    fwrite(&M->nbits, sizeof(uint), 1, f);
+    fwrite(&M->n, sizeof(uint), 1, f);
+    fwrite(M->map, sizeof(uint), (M->n*M->nbits+W-1)/W, f);
+ }
+
+nodemap loadNodemap(FILE *f)
+ {
+    nodemap M;
+
+    M = malloc(sizeof(struct snodemap));
+    fread(&M->nbits, sizeof(uint), 1, f);
+    fread(&M->n, sizeof(uint), 1, f);
+    M->map = malloc(((M->n*M->nbits+W-1)/W)*sizeof(uint));
+    fread(M->map, sizeof(uint), (M->n*M->nbits+W-1)/W, f);
+    return M;
+ }
+
+uint sizeofNodemap(nodemap M)
+ {
+    return sizeof(struct snodemap) + ((M->n*M->nbits+W-1)/W)*sizeof(uint); 
+ }
+