Debian Codegraph @

modules/gcide/idx.c

raw
1 /* This file is part of GNU Dico.
2 Copyright (C) 2012-2024 Sergey Poznyakoff
3
4 GNU Dico is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 3, or (at your option)
7 any later version.
8
9 GNU Dico is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with GNU Dico. If not, see <http://www.gnu.org/licenses/>. */
16
17 #include <config.h>
18 #include <stdlib.h>
19 #include <unistd.h>
20 #include <fcntl.h>
21 #include <sys/file.h>
22 #include <sys/stat.h>
23 #include <sys/wait.h>
24 #include <dico.h>
25 #include "gcide.h"
26 #include <errno.h>
27 #include <appi18n.h>
28 #include <assert.h>
29
30 struct gcide_idx_cache {
31 size_t pageno;
32 unsigned refcount;
33 struct gcide_idx_page *page;
34 };
35
36 struct gcide_idx_file {
37 char *name;
38 int fd;
39 struct gcide_idx_header header;
40 size_t cache_size;
41 size_t cache_used;
42 struct gcide_idx_cache **cache;
43 size_t compare_count;
44 };
45
46 #define REF_NOT_FOUND ((size_t)-1)
47
48 static void
49 _free_cache(struct gcide_idx_file *file)
50 {
51 size_t i;
52 for (i = 0; i < file->cache_used; i++) {
53 free(file->cache[i]->page);
54 free(file->cache[i]);
55 }
56 free(file->cache);
57 file->cache = NULL;
58 file->cache_used = 0;
59 }
60
61 static void
62 _free_index(struct gcide_idx_file *file)
63 {
64 _free_cache(file);
65 free(file->name);
66 free(file);
67 }
68
69 static int
70 _idx_full_read(struct gcide_idx_file *file, void *buf, size_t size)
71 {
72 char *p = buf;
73 while (size) {
74 ssize_t rc = read(file->fd, p, size);
75 if (rc == -1) {
76 if (errno == EAGAIN)
77 continue;
78 dico_log(L_ERR, errno, _("error reading from `%s'"), file->name);
79 return -1;
80 } else if (rc == 0) {
81 dico_log(L_ERR, 0, _("short read while reading from `%s'"),
82 file->name);
83 errno = 0;
84 return -1;
85 }
86 p += rc;
87 size -= rc;
88 }
89 return 0;
90 }
91
92 int
93 gcide_idx_fileno(struct gcide_idx_file *file)
94 {
95 return file->fd;
96 }
97
98 int
99 gcide_idx_reopen(struct gcide_idx_file *file)
100 {
101 off_t total;
102 struct stat st;
103
104 _free_cache(file);
105
106 if (lseek(file->fd, 0, SEEK_SET)) {
107 dico_log(L_ERR, errno, _("error rewinding `%s'"), file->name);
108 return IDXE_SYSERR;
109 }
110
111 if (_idx_full_read(file, &file->header, sizeof(file->header)))
112 return errno ? IDXE_SYSERR : IDXE_CORRUPT;
113 if (memcmp(file->header.ihdr_magic, GCIDE_IDX_MAGIC,
114 GCIDE_IDX_MAGIC_LEN))
115 return IDXE_BADFILE;
116
117 if (file->header.ihdr_version != GCIDE_IDX_VERSION)
118 return IDXE_BADVER;
119
120 if (fstat(file->fd, &st))
121 return IDXE_SYSERR;
122
123 total = (file->header.ihdr_num_pages + 1) * file->header.ihdr_pagesize;
124 if (total != st.st_size)
125 return IDXE_CORRUPT;
126
127 return IDXE_OK;
128 }
129
130 int
131 gcide_idx_file_open(const char *name, size_t cachesize, int rw,
132 struct gcide_idx_file **ret_file)
133 {
134 int rc, ec;
135 struct gcide_idx_file *file;
136
137 file = calloc(1, sizeof(*file));
138 if (!file)
139 return IDXE_SYSERR;
140
141 rc = IDXE_SYSERR;
142 file->name = strdup(name);
143 if (file->name) {
144 int fd = open(name, rw ? O_RDWR : O_RDONLY);
145 if (fd != -1) {
146 file->fd = fd;
147 rc = gcide_idx_reopen(file);
148 if (rc == IDXE_OK) {
149 file->cache_size = cachesize;
150 *ret_file = file;
151 return rc;
152 }
153 }
154 }
155
156 /* Error exit */
157 ec = errno;
158 _free_index(file);
159 errno = ec;
160 return rc;
161 }
162
163 void
164 gcide_idx_file_close(struct gcide_idx_file *file)
165 {
166 if (file) {
167 close(file->fd);
168 _free_index(file);
169 }
170 }
171
172 int
173 gcide_idx_lock(struct gcide_idx_file *file, int ex)
174 {
175 struct flock fl;
176 fl.l_type = ex ? F_WRLCK : F_RDLCK;
177 fl.l_whence = SEEK_SET;
178 fl.l_start = fl.l_len = (off_t)0;
179 return fcntl (file->fd, F_SETLKW, &fl);
180 }
181
182 int
183 gcide_idx_unlock(struct gcide_idx_file *file)
184 {
185 struct flock fl;
186 fl.l_type = F_UNLCK;
187 fl.l_whence = SEEK_SET;
188 fl.l_start = fl.l_len = (off_t)0;
189 return fcntl (file->fd, F_SETLK, &fl);
190 }
191
192 size_t
193 gcide_idx_headwords(struct gcide_idx_file *file)
194 {
195 return file->header.ihdr_num_headwords;
196 }
197
198 size_t
199 gcide_idx_defs(struct gcide_idx_file *file)
200 {
201 return file->header.ihdr_num_defs;
202 }
203
204 static struct gcide_idx_cache *
205 _cache_alloc(struct gcide_idx_file *file)
206 {
207 struct gcide_idx_cache *cp;
208
209 if (!file->cache) {
210 file->cache = calloc(file->cache_size, sizeof(file->cache[0]));
211 if (!file->cache) {
212 DICO_LOG_ERRNO();
213 return NULL;
214 }
215 }
216 if (file->cache_used < file->cache_size) {
217 if (file->cache_used &&
218 file->cache[file->cache_used - 1]->refcount == 0)
219 return file->cache[file->cache_used - 1];
220 cp = calloc(1, sizeof(*cp));
221 if (!cp) {
222 DICO_LOG_ERRNO();
223 return NULL;
224 }
225 cp->page = malloc(file->header.ihdr_pagesize);
226 if (!cp->page) {
227 DICO_LOG_ERRNO();
228 free(cp);
229 return NULL;
230 }
231 file->cache[file->cache_used++] = cp;
232 } else
233 cp = file->cache[file->cache_used - 1];
234 cp->pageno = 0;
235 cp->refcount = 0;
236 return cp;
237 }
238
239 static void
240 _cache_promote(struct gcide_idx_file *file, int n)
241 {
242 int i;
243 unsigned refcount = ++file->cache[n]->refcount;
244
245 if (n == 0)
246 return;
247 for (i = n - 1; i >= 0; i--)
248 if (file->cache[i]->refcount >= refcount)
249 break;
250 i++;
251 if (i != n) {
252 struct gcide_idx_cache *tmp = file->cache[n];
253 file->cache[n] = file->cache[i];
254 file->cache[i] = tmp;
255 }
256 }
257
258 static struct gcide_idx_cache *
259 _cache_find_page(struct gcide_idx_file *file, size_t n)
260 {
261 size_t i;
262
263 for (i = 0; i < file->cache_used; i++) {
264 if (file->cache[i]->pageno == n) {
265 struct gcide_idx_cache *cp = file->cache[i];
266 _cache_promote(file, n);
267 return cp;
268 }
269 }
270
271 return NULL;
272 }
273
274 struct gcide_idx_page *
275 _idx_get_page(struct gcide_idx_file *file, size_t n)
276 {
277 off_t off;
278 struct gcide_idx_cache *cp;
279 struct gcide_idx_page *page;
280 size_t i;
281
282 cp = _cache_find_page(file, n);
283 if (cp)
284 return cp->page;
285
286 off = (n + 1) * file->header.ihdr_pagesize;
287 if (lseek(file->fd, off, SEEK_SET) != off) {
288 dico_log(L_ERR, errno,
289 _("seek error on `%s' while positioning to %lu"),
290 file->name, (unsigned long) off);
291 return NULL;
292 }
293 cp = _cache_alloc(file);
294 if (!cp)
295 return NULL;
296 if (_idx_full_read(file, cp->page, file->header.ihdr_pagesize))
297 return NULL;
298 cp->refcount++;
299 page = cp->page;
300 for (i = 0; i < page->ipg_header.hdr.phdr_numentries; i++)
301 page->ipg_ref[i].ref_headword =
302 (char*)page + page->ipg_ref[i].ref_hwoff;
303 return page;
304 }
305
306
307 int
308 gcide_idx_enumerate(struct gcide_idx_file *file,
309 int (*fun)(struct gcide_ref *, void *),
310 void *data)
311 {
312 size_t i;
313
314 for (i = 0; i < file->header.ihdr_num_pages; i++) {
315 int j;
316
317 struct gcide_idx_page *page = _idx_get_page(file, i);
318 if (!page)
319 return -1;
320 for (j = 0; j < page->ipg_header.hdr.phdr_numentries; j++)
321 if (fun(&page->ipg_ref[j], data))
322 break;
323 }
324 return 0;
325 }
326
327 static int
328 _compare(struct gcide_idx_file *file, char *hw, struct gcide_ref *ref,
329 size_t hwlen)
330 {
331 file->compare_count++;
332 if (hwlen) {
333 if (hwlen > ref->ref_hwlen)
334 hwlen = ref->ref_hwlen;
335 return utf8_strncasecmp(hw, ref->ref_headword, hwlen);
336 }
337 return utf8_strcasecmp(hw, ref->ref_headword);
338 }
339
340 static size_t
341 _idx_ref_locate(struct gcide_idx_file *file,
342 struct gcide_idx_page *page, char *headword, size_t hwlen)
343 {
344 size_t l, u, idx;
345 int res;
346
347 l = 0;
348 u = page->ipg_header.hdr.phdr_numentries;
349 while (l < u) {
350 idx = (l + u) / 2;
351 res = _compare(file, headword, &page->ipg_ref[idx], hwlen);
352 if (res < 0)
353 u = idx;
354 else if (res > 0)
355 l = idx + 1;
356 else
357 return idx;
358 }
359 return REF_NOT_FOUND;
360 }
361
362 static size_t
363 _idx_page_locate(struct gcide_idx_file *file, char *headword, size_t hwlen)
364 {
365 size_t l, u, idx;
366 int res;
367
368 l = 0;
369 u = file->header.ihdr_num_pages;
370 while (l < u) {
371 struct gcide_idx_page *page;
372
373 idx = (l + u) / 2;
374 page = _idx_get_page(file, idx);
375 if (!page)
376 return REF_NOT_FOUND;
377
378 res = _compare(file, headword, &page->ipg_ref[0], hwlen);
379 if (res < 0)
380 u = idx;
381 else if (res == 0)
382 return idx;
383 else {
384 res = _compare(file, headword,
385 &page->ipg_ref[page->ipg_header.hdr.phdr_numentries-1],
386 hwlen);
387 if (res > 0)
388 l = idx + 1;
389 else
390 return idx;
391 }
392 }
393 return REF_NOT_FOUND;
394 }
395
396 struct gcide_iterator {
397 struct gcide_idx_file *file; /* Index file */
398 char *headword; /* Headword this iterator tracks */
399 size_t hwlen; /* Length of the headword */
400 size_t start_pageno; /* Number of start page */
401 size_t start_refno; /* Number of start reference in page */
402 size_t cur_pageno; /* Number of current page */
403 size_t cur_refno; /* Number of current reference in page */
404 size_t page_numrefs; /* Total number of references in cur. page */
405 size_t compare_count; /* Number of comparisons */
406 /* */
407 size_t numrefs; /* Number of references to headword. Zero
408 if not yet determined. */
409 size_t curref; /* Position in iterator */
410
411 char *prevbuf; /* Previous match */
412 size_t prevsize;
413
414 int flags; /* User-defined flags. */
415 };
416
417 gcide_iterator_t
418 gcide_idx_locate(struct gcide_idx_file *file, char *headword, size_t hwlen)
419 {
420 size_t pageno, refno;
421 struct gcide_idx_page *page;
422 struct gcide_iterator *itr;
423
424 file->compare_count = 0;
425 pageno = _idx_page_locate(file, headword, hwlen);
426 if (pageno == REF_NOT_FOUND)
427 return NULL;
428 page = _idx_get_page(file, pageno);
429 if (!page)
430 return NULL;
431 refno = _idx_ref_locate(file, page, headword, hwlen);
432 if (refno == REF_NOT_FOUND)
433 return NULL;
434
435 for (;;) {
436 if (refno > 0) {
437 if (_compare(file, headword, &page->ipg_ref[refno-1], hwlen) > 0)
438 break;
439 --refno;
440 }
441 if (refno == 0) {
442 if (pageno == 0)
443 break;
444 page = _idx_get_page(file, --pageno);
445 if (!page)
446 return NULL;
447 refno = page->ipg_header.hdr.phdr_numentries;
448 }
449 }
450 if (refno == page->ipg_header.hdr.phdr_numentries) {
451 pageno++;
452 refno = 0;
453 }
454
455 itr = malloc(sizeof(*itr));
456 if (!itr) {
457 DICO_LOG_ERRNO();
458 return NULL;
459 }
460 if (hwlen) {
461 itr->headword = malloc(hwlen);
462 if (itr->headword)
463 memcpy(itr->headword, headword, hwlen);
464 } else
465 itr->headword = strdup(headword);
466
467 if (!itr->headword) {
468 DICO_LOG_ERRNO();
469 free(itr);
470 return NULL;
471 }
472
473 itr->hwlen = hwlen;
474
475 itr->file = file;
476 itr->start_pageno = itr->cur_pageno = pageno;
477 itr->start_refno = itr->cur_refno = refno;
478 itr->page_numrefs = page->ipg_header.hdr.phdr_numentries;
479 itr->curref = itr->numrefs = 0;
480 itr->compare_count = file->compare_count;
481
482 return itr;
483 }
484
485 void
486 gcide_iterator_free(gcide_iterator_t itr)
487 {
488 if (itr) {
489 free(itr->headword);
490 free(itr);
491 }
492 }
493
494 int
495 gcide_iterator_next(gcide_iterator_t itr)
496 {
497 struct gcide_idx_page *page;
498 size_t pageno, refno;
499
500 if (!itr)
501 return -1;
502
503 if (itr->numrefs && itr->curref == itr->numrefs-1)
504 return -1;
505
506 if (itr->cur_refno < itr->page_numrefs-1) {
507 pageno = itr->cur_pageno;
508 refno = itr->cur_refno + 1;
509 } else if (itr->cur_pageno == itr->file->header.ihdr_num_pages) {
510 if (!itr->numrefs)
511 itr->numrefs = itr->curref + 1;
512 return -1;
513 } else {
514 pageno = itr->cur_pageno + 1;
515 refno = 0;
516 }
517
518 page = _idx_get_page(itr->file, pageno);
519 if (!page)
520 return -1;
521 if (!itr->numrefs &&
522 _compare(itr->file, itr->headword, &page->ipg_ref[refno],
523 itr->hwlen)) {
524 if (!itr->numrefs)
525 itr->numrefs = itr->curref + 1;
526 return -1;
527 }
528 itr->page_numrefs = page->ipg_header.hdr.phdr_numentries;
529 itr->cur_pageno = pageno;
530 itr->cur_refno = refno;
531 itr->curref++;
532 return 0;
533 }
534
535 int
536 gcide_iterator_rewind(gcide_iterator_t itr)
537 {
538 struct gcide_idx_page *page;
539
540 if (!itr)
541 return -1;
542 itr->cur_pageno = itr->start_pageno;
543 itr->cur_refno = itr->start_refno;
544 itr->curref = 0;
545 page = _idx_get_page(itr->file, itr->cur_pageno);
546 if (!page)
547 return -1;
548 itr->page_numrefs = page->ipg_header.hdr.phdr_numentries;
549 return 0;
550 }
551
552 struct gcide_ref *
553 gcide_iterator_ref(gcide_iterator_t itr)
554 {
555 struct gcide_idx_page *page;
556
557 if (!itr)
558 return NULL;
559 page = _idx_get_page(itr->file, itr->cur_pageno);
560 if (!page)
561 return NULL;
562 return &page->ipg_ref[itr->cur_refno];
563 }
564
565 size_t
566 gcide_iterator_count(gcide_iterator_t itr)
567 {
568 if (!itr)
569 return 0;
570 if (!itr->numrefs) {
571 while (gcide_iterator_next(itr) == 0)
572 ;
573 gcide_iterator_rewind(itr);
574 }
575 return itr->numrefs;
576 }
577
578 size_t
579 gcide_iterator_compare_count(gcide_iterator_t itr)
580 {
581 return itr->compare_count;
582 }
583
584 void
585 gcide_iterator_store_flags(gcide_iterator_t itr, int flags)
586 {
587 itr->flags = flags;
588 }
589
590 int
591 gcide_iterator_flags(gcide_iterator_t itr)
592 {
593 if (!itr)
594 return 0;
595 return itr->flags;
596 }