git.sesse.net Git - plocate/blob - plocate-build.cpp

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <algorithm>
   4 #include <unordered_map>
   5 #include <string>
   6 #include <vector>
   7 #include <chrono>
   8 #include <unistd.h>
   9 #include <fcntl.h>
  10 #include <sys/mman.h>
  11 #include <arpa/inet.h>
  12 #include <endian.h>
  13 #include <sys/types.h>
  14 #include <sys/stat.h>
  15
  16 #include "vp4.h"
  17
  18 #define P4NENC_BOUND(n) ((n+127)/128+(n+32)*sizeof(uint32_t))
  19 #define dprintf(...)
  20 //#define dprintf(...) fprintf(stderr, __VA_ARGS__);
  21
  22 using namespace std;
  23 using namespace std::chrono;
  24
  25 static inline uint32_t read_unigram(const string &s, size_t idx)
  26 {
  27         if (idx < s.size()) {
  28                 return (unsigned char)s[idx];
  29         } else {
  30                 return 0;
  31         }
  32 }
  33
  34 static inline uint32_t read_trigram(const string &s, size_t start)
  35 {
  36         return read_unigram(s, start) |
  37                 (read_unigram(s, start + 1) << 8) |
  38                 (read_unigram(s, start + 2) << 16);
  39 }
  40
  41 enum
  42 {
  43         DBE_NORMAL          = 0,    /* A non-directory file */
  44         DBE_DIRECTORY       = 1,    /* A directory */
  45         DBE_END             = 2   /* End of directory contents; contains no name */
  46 };
  47
  48 // From mlocate.
  49 struct db_header
  50 {
  51         uint8_t magic[8];
  52         uint32_t conf_size;
  53         uint8_t version;
  54         uint8_t check_visibility;
  55         uint8_t pad[2];
  56 };
  57
  58 // From mlocate.
  59 struct db_directory
  60 {
  61         uint64_t time_sec;
  62         uint32_t time_nsec;
  63         uint8_t pad[4];
  64 };
  65
  66 const char *handle_directory(const char *ptr, vector<string> *files)
  67 {
  68         ptr += sizeof(db_directory);
  69
  70         string dir_path = ptr;
  71         ptr += dir_path.size() + 1;
  72         if (dir_path == "/") {
  73                 dir_path = "";
  74         }
  75
  76         for ( ;; ) {
  77                 uint8_t type = *ptr++;
  78                 if (type == DBE_NORMAL) {
  79                         string filename = ptr;
  80                         files->push_back(dir_path + "/" + filename);
  81                         ptr += filename.size() + 1;
  82                 } else if (type == DBE_DIRECTORY) {
  83                         string dirname = ptr;
  84                         files->push_back(dir_path + "/" + dirname);
  85                         ptr += dirname.size() + 1;
  86                 } else {
  87                         return ptr;
  88                 }
  89         }
  90 }
  91
  92 void read_mlocate(const char *filename, vector<string> *files)
  93 {
  94         int fd = open(filename, O_RDONLY);
  95         if (fd == -1) {
  96                 perror(filename);
  97                 exit(1);
  98         }
  99         off_t len = lseek(fd, 0, SEEK_END);
 100         if (len == -1) {
 101                 perror("lseek");
 102                 exit(1);
 103         }
 104         const char *data = (char *)mmap(nullptr, len, PROT_READ, MAP_SHARED, fd, /*offset=*/0);
 105         if (data == MAP_FAILED) {
 106                 perror("mmap");
 107                 exit(1);
 108         }
 109
 110         const db_header *hdr = (const db_header *)data;
 111
 112         // TODO: Care about the base path.
 113         string path = data + sizeof(db_header);
 114         uint64_t offset = sizeof(db_header) + path.size() + 1 + ntohl(hdr->conf_size);
 115
 116         const char *ptr = data + offset;
 117         while (ptr < data + len) {
 118                 ptr = handle_directory(ptr, files);
 119         }
 120
 121         munmap((void *)data, len);
 122         close(fd);
 123 }
 124
 125 void do_build(const char *infile, const char *outfile)
 126 {
 127         //steady_clock::time_point start = steady_clock::now();
 128
 129         vector<string> files;
 130         read_mlocate(infile, &files);
 131         if (false) {  // To read a plain text file.
 132                 FILE *fp = fopen(infile, "r");
 133                 while (!feof(fp)) {
 134                         char buf[1024];
 135                         if (fgets(buf, 1024, fp) == nullptr || feof(fp)) {
 136                                 break;
 137                         }
 138                         string s(buf);
 139                         if (s.back() == '\n') s.pop_back();
 140                         files.push_back(move(s));
 141                 }
 142                 fclose(fp);
 143         }
 144         dprintf("Read %zu files from %s\n", files.size(), infile);
 145
 146         unordered_map<uint32_t, string> pl;
 147         size_t trigrams = 0, longest_posting_list = 0;
 148         unordered_map<uint32_t, vector<uint32_t>> invindex;
 149         for (size_t i = 0; i < files.size(); ++i) {
 150                 const string &s = files[i];
 151                 if (s.size() >= 3) {
 152                         for (size_t j = 0; j < s.size() - 2; ++j) {
 153                                 uint32_t trgm = read_trigram(s, j);
 154                                 invindex[trgm].push_back(i);
 155                         }
 156                 }
 157         }
 158         string buf;
 159         size_t bytes_used = 0;
 160         for (auto &[trigram, docids] : invindex) {
 161                 auto last = unique(docids.begin(), docids.end());
 162                 docids.erase(last, docids.end());
 163                 longest_posting_list = max(longest_posting_list, docids.size());
 164                 trigrams += docids.size();
 165
 166                 size_t bytes_needed = P4NENC_BOUND(docids.size());
 167                 if (buf.size() < bytes_needed) buf.resize(bytes_needed);
 168                 size_t bytes = p4nd1enc128v32(&docids[0], docids.size(), reinterpret_cast<unsigned char *>(&buf[0]));
 169                 pl[trigram] = string(buf.data(), bytes);
 170                 bytes_used += bytes;
 171         }
 172         dprintf("%zu files, %zu different trigrams, %zu entries, avg len %.2f, longest %zu\n",
 173                 files.size(), invindex.size(), trigrams, double(trigrams) / invindex.size(), longest_posting_list);
 174
 175         dprintf("%zu bytes used for posting lists (%.2f bits/entry)\n", bytes_used, 8 * bytes_used / double(trigrams));
 176         //steady_clock::time_point end = steady_clock::now();
 177         dprintf("Building posting lists took %.1f ms.\n\n", 1e3 * duration<float>(end - start).count());
 178
 179         vector<uint32_t> all_trigrams;
 180         for (auto &[trigram, docids] : invindex) {
 181                 all_trigrams.push_back(trigram);
 182         }
 183         sort(all_trigrams.begin(), all_trigrams.end());
 184
 185         umask(0027);
 186         FILE *outfp = fopen(outfile, "wb");
 187
 188         // Write the header.
 189         uint64_t num_trigrams = invindex.size();  // 64 to get alignment.
 190         fwrite(&num_trigrams, sizeof(num_trigrams), 1, outfp);
 191
 192         // Find out where the posting lists will end.
 193         uint64_t offset = sizeof(uint64_t) * 2 + 16 * all_trigrams.size();
 194         uint64_t filename_index_offset = offset;
 195         for (uint32_t trgm : all_trigrams) {
 196                 filename_index_offset += pl[trgm].size();
 197         }
 198         fwrite(&filename_index_offset, sizeof(filename_index_offset), 1, outfp);
 199
 200         size_t bytes_for_trigrams = 0, bytes_for_posting_lists = 0, bytes_for_filename_index = 0, bytes_for_filenames = 0;
 201
 202         for (uint32_t trgm : all_trigrams) {
 203                 // 16 bytes: trgm (4), number of docids (4), byte offset (8)
 204                 fwrite(&trgm, sizeof(trgm), 1, outfp);  // One byte wasted, but OK.
 205                 uint32_t num_docids = invindex[trgm].size();
 206                 fwrite(&num_docids, sizeof(num_docids), 1, outfp);
 207                 fwrite(&offset, sizeof(offset), 1, outfp);
 208                 offset += pl[trgm].size();
 209                 bytes_for_trigrams += 16;
 210         }
 211
 212         // Write the actual posting lists.
 213         for (uint32_t trgm : all_trigrams) {
 214                 fwrite(pl[trgm].data(), pl[trgm].size(), 1, outfp);
 215                 bytes_for_posting_lists += pl[trgm].size();
 216         }
 217
 218         // Write the offsets to the filenames.
 219         offset = filename_index_offset + files.size() * sizeof(offset);
 220         for (const string &filename : files) {
 221                 fwrite(&offset, sizeof(offset), 1, outfp);
 222                 offset += filename.size() + 1;
 223                 bytes_for_filename_index += sizeof(offset);
 224                 bytes_for_filenames += filename.size() + 1;
 225         }
 226
 227         // Write the actual filenames.
 228         for (const string &filename : files) {
 229                 fwrite(filename.c_str(), filename.size() + 1, 1, outfp);
 230         }
 231
 232         fclose(outfp);
 233
 234         dprintf("Trigrams:       %'7.1f MB\n", bytes_for_trigrams / 1048576.0);
 235         dprintf("Posting lists:  %'7.1f MB\n", bytes_for_posting_lists / 1048576.0);
 236         dprintf("Filename index: %'7.1f MB\n", bytes_for_filename_index / 1048576.0);
 237         dprintf("Filenames:      %'7.1f MB\n", bytes_for_filenames / 1048576.0);
 238         dprintf("\n");
 239 }
 240
 241 int main(int argc, char **argv)
 242 {
 243         do_build(argv[1], argv[2]);
 244         exit(EXIT_SUCCESS);
 245 }