Debian Codegraph @

datrie/tail.c

raw
1 /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3 * libdatrie - Double-Array Trie Library
4 * Copyright (C) 2006 Theppitak Karoonboonyanan <[email protected]>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21 /*
22 * tail.c - trie tail for keeping suffixes
23 * Created: 2006-08-15
24 * Author: Theppitak Karoonboonyanan <[email protected]>
25 */
26
27 #include <string.h>
28 #include <stdlib.h>
29 #ifndef _MSC_VER /* for SIZE_MAX */
30 # include <stdint.h>
31 #endif
32 #include <stdio.h>
33
34 #include "tail.h"
35 #include "trie-private.h"
36 #include "fileutils.h"
37 #include "trie-string.h"
38
39 /*----------------------------------*
40 * INTERNAL TYPES DECLARATIONS *
41 *----------------------------------*/
42
43 /*-----------------------------------*
44 * PRIVATE METHODS DECLARATIONS *
45 *-----------------------------------*/
46
47 static TrieIndex tail_alloc_block (Tail *t);
48 static void tail_free_block (Tail *t, TrieIndex block);
49
50 /* ==================== BEGIN IMPLEMENTATION PART ==================== */
51
52 /*------------------------------------*
53 * INTERNAL TYPES IMPLEMENTATIONS *
54 *------------------------------------*/
55
56 /*------------------------------*
57 * PRIVATE DATA DEFINITONS *
58 *------------------------------*/
59
60 typedef struct {
61 TrieIndex next_free;
62 TrieData data;
63 TrieChar *suffix;
64 } TailBlock;
65
66 struct _Tail {
67 TrieIndex num_tails;
68 TailBlock *tails;
69 TrieIndex first_free;
70 };
71
72 /*-----------------------------*
73 * METHODS IMPLEMENTAIONS *
74 *-----------------------------*/
75
76 #define TAIL_SIGNATURE 0xDFFCDFFC
77 #define TAIL_START_BLOCKNO 1
78
79 /* Tail Header:
80 * INT32: signature
81 * INT32: pointer to first free slot
82 * INT32: number of tail blocks
83 *
84 * Tail Blocks:
85 * INT32: pointer to next free block (-1 for allocated blocks)
86 * INT32: data for the key
87 * INT16: length
88 * BYTES[length]: suffix string (no terminating '\0')
89 */
90
91 /**
92 * @brief Create a new tail object
93 *
94 * Create a new empty tail object.
95 */
96 Tail *
97 tail_new (void)
98 {
99 Tail *t;
100
101 t = (Tail *) malloc (sizeof (Tail));
102 if (UNLIKELY (!t))
103 return NULL;
104
105 t->first_free = 0;
106 t->num_tails = 0;
107 t->tails = NULL;
108
109 return t;
110 }
111
112 /**
113 * @brief Read tail data from file
114 *
115 * @param file : the file to read
116 *
117 * @return a pointer to the openned tail data, NULL on failure
118 *
119 * Read tail data from the opened file, starting from the current
120 * file pointer until the end of tail data block. On return, the
121 * file pointer is left at the position after the read block.
122 */
123 Tail *
124 tail_fread (FILE *file)
125 {
126 long save_pos;
127 Tail *t;
128 TrieIndex i;
129 uint32 sig;
130
131 /* check signature */
132 save_pos = ftell (file);
133 if (!file_read_int32 (file, (int32 *) &sig) || TAIL_SIGNATURE != sig)
134 goto exit_file_read;
135
136 t = (Tail *) malloc (sizeof (Tail));
137 if (UNLIKELY (!t))
138 goto exit_file_read;
139
140 if (!file_read_int32 (file, &t->first_free) ||
141 !file_read_int32 (file, &t->num_tails))
142 {
143 goto exit_tail_created;
144 }
145 if (t->num_tails > SIZE_MAX / sizeof (TailBlock))
146 goto exit_tail_created;
147 t->tails = (TailBlock *) malloc (t->num_tails * sizeof (TailBlock));
148 if (UNLIKELY (!t->tails))
149 goto exit_tail_created;
150 for (i = 0; i < t->num_tails; i++) {
151 int16 length;
152
153 if (!file_read_int32 (file, &t->tails[i].next_free) ||
154 !file_read_int32 (file, &t->tails[i].data) ||
155 !file_read_int16 (file, &length))
156 {
157 goto exit_in_loop;
158 }
159
160 t->tails[i].suffix = (TrieChar *) malloc (length + 1);
161 if (UNLIKELY (!t->tails[i].suffix))
162 goto exit_in_loop;
163 if (length > 0) {
164 if (!file_read_chars (file, (char *)t->tails[i].suffix, length)) {
165 free (t->tails[i].suffix);
166 goto exit_in_loop;
167 }
168 }
169 t->tails[i].suffix[length] = TRIE_CHAR_TERM;
170 }
171
172 return t;
173
174 exit_in_loop:
175 while (i > 0) {
176 free (t->tails[--i].suffix);
177 }
178 free (t->tails);
179 exit_tail_created:
180 free (t);
181 exit_file_read:
182 fseek (file, save_pos, SEEK_SET);
183 return NULL;
184 }
185
186 /**
187 * @brief Free tail data
188 *
189 * @param t : the tail data
190 *
191 * @return 0 on success, non-zero on failure
192 *
193 * Free the given tail data.
194 */
195 void
196 tail_free (Tail *t)
197 {
198 TrieIndex i;
199
200 if (t->tails) {
201 for (i = 0; i < t->num_tails; i++)
202 if (t->tails[i].suffix)
203 free (t->tails[i].suffix);
204 free (t->tails);
205 }
206 free (t);
207 }
208
209 /**
210 * @brief Write tail data
211 *
212 * @param t : the tail data
213 * @param file : the file to write to
214 *
215 * @return 0 on success, non-zero on failure
216 *
217 * Write tail data to the given @a file, starting from the current file
218 * pointer. On return, the file pointer is left after the tail data block.
219 */
220 int
221 tail_fwrite (const Tail *t, FILE *file)
222 {
223 TrieIndex i;
224
225 if (!file_write_int32 (file, TAIL_SIGNATURE) ||
226 !file_write_int32 (file, t->first_free) ||
227 !file_write_int32 (file, t->num_tails))
228 {
229 return -1;
230 }
231 for (i = 0; i < t->num_tails; i++) {
232 int16 length;
233
234 if (!file_write_int32 (file, t->tails[i].next_free) ||
235 !file_write_int32 (file, t->tails[i].data))
236 {
237 return -1;
238 }
239
240 length = t->tails[i].suffix ? trie_char_strlen (t->tails[i].suffix)
241 : 0;
242 if (!file_write_int16 (file, length))
243 return -1;
244 if (length > 0 &&
245 !file_write_chars (file, (char *)t->tails[i].suffix, length))
246 {
247 return -1;
248 }
249 }
250
251 return 0;
252 }
253
254
255 size_t
256 tail_get_serialized_size (const Tail *t)
257 {
258 size_t static_count = (
259 sizeof (int32) /* sizeof (TAIL_SIGNATURE) */
260 + sizeof (t->first_free)
261 + sizeof (t->num_tails)
262 );
263 size_t dynamic_count = 0u;
264 if (t->num_tails > 0) {
265 TrieIndex i = 0;
266 dynamic_count += (
267 sizeof (t->tails[i].next_free) + sizeof (t->tails[i].data)
268 + sizeof (int16) /* length */
269 ) * t->num_tails;
270 for (; i < t->num_tails; i++) {
271 if (t->tails[i].suffix)
272 {
273 dynamic_count += trie_char_strsize (t->tails[i].suffix);
274 }
275 }
276 }
277 return static_count + dynamic_count;
278 }
279
280
281 int
282 tail_serialize (const Tail *t, uint8 **ptr)
283 {
284 TrieIndex i;
285
286 serialize_int32_be_incr (ptr, TAIL_SIGNATURE);
287 serialize_int32_be_incr (ptr, t->first_free);
288 serialize_int32_be_incr (ptr, t->num_tails);
289
290 for (i = 0; i < t->num_tails; i++) {
291 int16 length;
292 serialize_int32_be_incr (ptr, t->tails[i].next_free);
293 serialize_int32_be_incr (ptr, t->tails[i].data);
294
295 length = t->tails[i].suffix ? trie_char_strsize (t->tails[i].suffix)
296 : 0;
297 serialize_int16_be_incr (ptr, length);
298 if (length)
299 {
300 memcpy (*ptr, (char *)t->tails[i].suffix, length);
301 *ptr += length;
302 }
303 }
304
305 return 0;
306 }
307
308
309 /**
310 * @brief Get suffix
311 *
312 * @param t : the tail data
313 * @param index : the index of the suffix
314 *
315 * @return pointer to the indexed suffix string.
316 *
317 * Get suffix from tail with given @a index. The returned string is a pointer
318 * to internal storage, which should be accessed read-only by the caller.
319 * No need to free() it.
320 */
321 const TrieChar *
322 tail_get_suffix (const Tail *t, TrieIndex index)
323 {
324 index -= TAIL_START_BLOCKNO;
325 return LIKELY (index < t->num_tails) ? t->tails[index].suffix : NULL;
326 }
327
328 /**
329 * @brief Set suffix of existing entry
330 *
331 * @param t : the tail data
332 * @param index : the index of the suffix
333 * @param suffix : the new suffix
334 *
335 * Set suffix of existing entry of given @a index in tail.
336 */
337 Bool
338 tail_set_suffix (Tail *t, TrieIndex index, const TrieChar *suffix)
339 {
340 index -= TAIL_START_BLOCKNO;
341 if (LIKELY (index < t->num_tails)) {
342 /* suffix and t->tails[index].suffix may overlap;
343 * so, dup it before it's overwritten
344 */
345 TrieChar *tmp = NULL;
346 if (suffix) {
347 tmp = trie_char_strdup (suffix);
348 if (UNLIKELY (!tmp))
349 return FALSE;
350 }
351 if (t->tails[index].suffix)
352 free (t->tails[index].suffix);
353 t->tails[index].suffix = tmp;
354
355 return TRUE;
356 }
357 return FALSE;
358 }
359
360 /**
361 * @brief Add a new suffix
362 *
363 * @param t : the tail data
364 * @param suffix : the new suffix
365 *
366 * @return the index of the newly added suffix,
367 * or TRIE_INDEX_ERROR on failure.
368 *
369 * Add a new suffix entry to tail.
370 */
371 TrieIndex
372 tail_add_suffix (Tail *t, const TrieChar *suffix)
373 {
374 TrieIndex new_block;
375
376 new_block = tail_alloc_block (t);
377 if (UNLIKELY (TRIE_INDEX_ERROR == new_block))
378 return TRIE_INDEX_ERROR;
379
380 tail_set_suffix (t, new_block, suffix);
381
382 return new_block;
383 }
384
385 static TrieIndex
386 tail_alloc_block (Tail *t)
387 {
388 TrieIndex block;
389
390 if (0 != t->first_free) {
391 block = t->first_free;
392 t->first_free = t->tails[block].next_free;
393 } else {
394 void *new_block;
395
396 block = t->num_tails;
397
398 new_block = realloc (t->tails, (t->num_tails + 1) * sizeof (TailBlock));
399 if (UNLIKELY (!new_block))
400 return TRIE_INDEX_ERROR;
401
402 t->tails = (TailBlock *) new_block;
403 ++t->num_tails;
404 }
405 t->tails[block].next_free = -1;
406 t->tails[block].data = TRIE_DATA_ERROR;
407 t->tails[block].suffix = NULL;
408
409 return block + TAIL_START_BLOCKNO;
410 }
411
412 static void
413 tail_free_block (Tail *t, TrieIndex block)
414 {
415 TrieIndex i, j;
416
417 block -= TAIL_START_BLOCKNO;
418
419 if (block >= t->num_tails)
420 return;
421
422 t->tails[block].data = TRIE_DATA_ERROR;
423 if (NULL != t->tails[block].suffix) {
424 free (t->tails[block].suffix);
425 t->tails[block].suffix = NULL;
426 }
427
428 /* find insertion point */
429 j = 0;
430 for (i = t->first_free; i != 0 && i < block; i = t->tails[i].next_free)
431 j = i;
432
433 /* insert free block between j and i */
434 t->tails[block].next_free = i;
435 if (0 != j)
436 t->tails[j].next_free = block;
437 else
438 t->first_free = block;
439 }
440
441 /**
442 * @brief Get data associated to suffix entry
443 *
444 * @param t : the tail data
445 * @param index : the index of the suffix
446 *
447 * @return the data associated to the suffix entry
448 *
449 * Get data associated to suffix entry @a index in tail data.
450 */
451 TrieData
452 tail_get_data (const Tail *t, TrieIndex index)
453 {
454 index -= TAIL_START_BLOCKNO;
455 return LIKELY (index < t->num_tails)
456 ? t->tails[index].data : TRIE_DATA_ERROR;
457 }
458
459 /**
460 * @brief Set data associated to suffix entry
461 *
462 * @param t : the tail data
463 * @param index : the index of the suffix
464 * @param data : the data to set
465 *
466 * @return boolean indicating success
467 *
468 * Set data associated to suffix entry @a index in tail data.
469 */
470 Bool
471 tail_set_data (Tail *t, TrieIndex index, TrieData data)
472 {
473 index -= TAIL_START_BLOCKNO;
474 if (LIKELY (index < t->num_tails)) {
475 t->tails[index].data = data;
476 return TRUE;
477 }
478 return FALSE;
479 }
480
481 /**
482 * @brief Delete suffix entry
483 *
484 * @param t : the tail data
485 * @param index : the index of the suffix to delete
486 *
487 * Delete suffix entry from the tail data.
488 */
489 void
490 tail_delete (Tail *t, TrieIndex index)
491 {
492 tail_free_block (t, index);
493 }
494
495 /**
496 * @brief Walk in tail with a string
497 *
498 * @param t : the tail data
499 * @param s : the tail data index
500 * @param suffix_idx : pointer to current character index in suffix
501 * @param str : the string to use in walking
502 * @param len : total characters in @a str to walk
503 *
504 * @return total number of characters successfully walked
505 *
506 * Walk in the tail data @a t at entry @a s, from given character position
507 * @a *suffix_idx, using @a len characters of given string @a str. On return,
508 * @a *suffix_idx is updated to the position after the last successful walk,
509 * and the function returns the total number of character succesfully walked.
510 */
511 int
512 tail_walk_str (const Tail *t,
513 TrieIndex s,
514 short *suffix_idx,
515 const TrieChar *str,
516 int len)
517 {
518 const TrieChar *suffix;
519 int i;
520 short j;
521
522 suffix = tail_get_suffix (t, s);
523 if (UNLIKELY (!suffix))
524 return FALSE;
525
526 i = 0; j = *suffix_idx;
527 while (i < len) {
528 if (str[i] != suffix[j])
529 break;
530 ++i;
531 /* stop and stay at null-terminator */
532 if (TRIE_CHAR_TERM == suffix[j])
533 break;
534 ++j;
535 }
536 *suffix_idx = j;
537 return i;
538 }
539
540 /**
541 * @brief Walk in tail with a character
542 *
543 * @param t : the tail data
544 * @param s : the tail data index
545 * @param suffix_idx : pointer to current character index in suffix
546 * @param c : the character to use in walking
547 *
548 * @return boolean indicating success
549 *
550 * Walk in the tail data @a t at entry @a s, from given character position
551 * @a *suffix_idx, using given character @a c. If the walk is successful,
552 * it returns TRUE, and @a *suffix_idx is updated to the next character.
553 * Otherwise, it returns FALSE, and @a *suffix_idx is left unchanged.
554 */
555 Bool
556 tail_walk_char (const Tail *t,
557 TrieIndex s,
558 short *suffix_idx,
559 TrieChar c)
560 {
561 const TrieChar *suffix;
562 TrieChar suffix_char;
563
564 suffix = tail_get_suffix (t, s);
565 if (UNLIKELY (!suffix))
566 return FALSE;
567
568 suffix_char = suffix[*suffix_idx];
569 if (suffix_char == c) {
570 if (TRIE_CHAR_TERM != suffix_char)
571 ++*suffix_idx;
572 return TRUE;
573 }
574 return FALSE;
575 }
576
577 /*
578 vi:ts=4:ai:expandtab
579 */