Debian Codegraph @

datrie/alpha-map.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 * alpha-map.c - map between character codes and trie alphabet
23 * Created: 2006-08-19
24 * Author: Theppitak Karoonboonyanan <[email protected]>
25 */
26
27 #include <ctype.h>
28 #include <string.h>
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <assert.h>
32
33 #include "alpha-map.h"
34 #include "alpha-map-private.h"
35 #include "trie-private.h"
36 #include "fileutils.h"
37 #include "trie-string.h"
38
39 /**
40 * @brief Alphabet string length
41 *
42 * @param str : the array of null-terminated AlphaChar string to measure
43 *
44 * @return the total characters in @a str.
45 */
46 int
47 alpha_char_strlen (const AlphaChar *str)
48 {
49 const AlphaChar *p;
50
51 for (p = str; *p; p++)
52 ;
53 return p - str;
54 }
55
56 /**
57 * @brief Compare alphabet strings
58 *
59 * @param str1, str2 : the arrays of null-terminated AlphaChar strings
60 * to compare
61 *
62 * @return negative if @a str1 < @a str2;
63 * 0 if @a str1 == @a str2;
64 * positive if @a str1 > @a str2
65 *
66 * Available since: 0.2.7
67 */
68 int
69 alpha_char_strcmp (const AlphaChar *str1, const AlphaChar *str2)
70 {
71 while (*str1 && *str1 == *str2) {
72 str1++; str2++;
73 }
74 if (*str1 < *str2)
75 return -1;
76 if (*str1 > *str2)
77 return 1;
78 return 0;
79 }
80
81 /*------------------------------*
82 * PRIVATE DATA DEFINITONS *
83 *------------------------------*/
84
85 typedef struct _AlphaRange {
86 struct _AlphaRange *next;
87
88 AlphaChar begin;
89 AlphaChar end;
90 } AlphaRange;
91
92 struct _AlphaMap {
93 AlphaRange *first_range;
94
95 /* work area */
96 /* alpha-to-trie map */
97 AlphaChar alpha_begin;
98 AlphaChar alpha_end;
99 int alpha_map_sz;
100 TrieIndex *alpha_to_trie_map;
101
102 /* trie-to-alpha map */
103 int trie_map_sz;
104 AlphaChar *trie_to_alpha_map;
105 };
106
107 /*-----------------------------------*
108 * PRIVATE METHODS DECLARATIONS *
109 *-----------------------------------*/
110 static int alpha_map_get_total_ranges (const AlphaMap *alpha_map);
111 static int alpha_map_add_range_only (AlphaMap *alpha_map,
112 AlphaChar begin, AlphaChar end);
113 static int alpha_map_recalc_work_area (AlphaMap *alpha_map);
114
115 /*-----------------------------*
116 * METHODS IMPLEMENTAIONS *
117 *-----------------------------*/
118
119 #define ALPHAMAP_SIGNATURE 0xD9FCD9FC
120
121 /* AlphaMap Header:
122 * - INT32: signature
123 * - INT32: total ranges
124 *
125 * Ranges:
126 * - INT32: range begin
127 * - INT32: range end
128 */
129
130 /**
131 * @brief Create new alphabet map
132 *
133 * @return a pointer to the newly created alphabet map, NULL on failure
134 *
135 * Create a new empty alphabet map. The map contents can then be added with
136 * alpha_map_add_range().
137 *
138 * The created object must be freed with alpha_map_free().
139 */
140 AlphaMap *
141 alpha_map_new (void)
142 {
143 AlphaMap *alpha_map;
144
145 alpha_map = (AlphaMap *) malloc (sizeof (AlphaMap));
146 if (UNLIKELY (!alpha_map))
147 return NULL;
148
149 alpha_map->first_range = NULL;
150
151 /* work area */
152 alpha_map->alpha_begin = 0;
153 alpha_map->alpha_end = 0;
154 alpha_map->alpha_map_sz = 0;
155 alpha_map->alpha_to_trie_map = NULL;
156
157 alpha_map->trie_map_sz = 0;
158 alpha_map->trie_to_alpha_map = NULL;
159
160 return alpha_map;
161 }
162
163 /**
164 * @brief Create a clone of alphabet map
165 *
166 * @param a_map : the source alphabet map to clone
167 *
168 * @return a pointer to the alphabet map clone, NULL on failure
169 *
170 * The created object must be freed with alpha_map_free().
171 */
172 AlphaMap *
173 alpha_map_clone (const AlphaMap *a_map)
174 {
175 AlphaMap *alpha_map;
176 AlphaRange *range;
177
178 alpha_map = alpha_map_new ();
179 if (UNLIKELY (!alpha_map))
180 return NULL;
181
182 for (range = a_map->first_range; range; range = range->next) {
183 if (alpha_map_add_range_only (alpha_map, range->begin, range->end) != 0)
184 goto exit_map_created;
185 }
186
187 if (alpha_map_recalc_work_area (alpha_map) != 0)
188 goto exit_map_created;
189
190 return alpha_map;
191
192 exit_map_created:
193 alpha_map_free (alpha_map);
194 return NULL;
195 }
196
197 /**
198 * @brief Free an alphabet map object
199 *
200 * @param alpha_map : the alphabet map object to free
201 *
202 * Destruct the @a alpha_map and free its allocated memory.
203 */
204 void
205 alpha_map_free (AlphaMap *alpha_map)
206 {
207 AlphaRange *p, *q;
208
209 p = alpha_map->first_range;
210 while (p) {
211 q = p->next;
212 free (p);
213 p = q;
214 }
215
216 /* work area */
217 if (alpha_map->alpha_to_trie_map)
218 free (alpha_map->alpha_to_trie_map);
219 if (alpha_map->trie_to_alpha_map)
220 free (alpha_map->trie_to_alpha_map);
221
222 free (alpha_map);
223 }
224
225 AlphaMap *
226 alpha_map_fread_bin (FILE *file)
227 {
228 long save_pos;
229 uint32 sig;
230 int32 total, i;
231 AlphaMap *alpha_map;
232
233 /* check signature */
234 save_pos = ftell (file);
235 if (!file_read_int32 (file, (int32 *) &sig) || ALPHAMAP_SIGNATURE != sig)
236 goto exit_file_read;
237
238 alpha_map = alpha_map_new ();
239 if (UNLIKELY (!alpha_map))
240 goto exit_file_read;
241
242 /* read number of ranges */
243 if (!file_read_int32 (file, &total))
244 goto exit_map_created;
245
246 /* read character ranges */
247 for (i = 0; i < total; i++) {
248 int32 b, e;
249
250 if (!file_read_int32 (file, &b) || !file_read_int32 (file, &e))
251 goto exit_map_created;
252 alpha_map_add_range_only (alpha_map, b, e);
253 }
254
255 /* work area */
256 if (UNLIKELY (alpha_map_recalc_work_area (alpha_map) != 0))
257 goto exit_map_created;
258
259 return alpha_map;
260
261 exit_map_created:
262 alpha_map_free (alpha_map);
263 exit_file_read:
264 fseek (file, save_pos, SEEK_SET);
265 return NULL;
266 }
267
268 static int
269 alpha_map_get_total_ranges (const AlphaMap *alpha_map)
270 {
271 int n;
272 AlphaRange *range;
273
274 for (n = 0, range = alpha_map->first_range; range; range = range->next) {
275 ++n;
276 }
277
278 return n;
279 }
280
281 int
282 alpha_map_fwrite_bin (const AlphaMap *alpha_map, FILE *file)
283 {
284 AlphaRange *range;
285
286 if (!file_write_int32 (file, ALPHAMAP_SIGNATURE) ||
287 !file_write_int32 (file, alpha_map_get_total_ranges (alpha_map)))
288 {
289 return -1;
290 }
291
292 for (range = alpha_map->first_range; range; range = range->next) {
293 if (!file_write_int32 (file, range->begin) ||
294 !file_write_int32 (file, range->end))
295 {
296 return -1;
297 }
298 }
299
300 return 0;
301 }
302
303 size_t
304 alpha_map_get_serialized_size (const AlphaMap *alpha_map)
305 {
306 int32 ranges_count = alpha_map_get_total_ranges (alpha_map);
307 return (
308 4 /* ALPHAMAP_SIGNATURE */
309 + sizeof (ranges_count)
310 + (sizeof (AlphaChar) * 2) * ranges_count /* range->begin, range->end */
311 );
312 }
313
314 void
315 alpha_map_serialize_bin (const AlphaMap *alpha_map, uint8 **ptr)
316 {
317 AlphaRange *range;
318 serialize_int32_be_incr (ptr, ALPHAMAP_SIGNATURE);
319 serialize_int32_be_incr (ptr, alpha_map_get_total_ranges (alpha_map));
320
321 for (range = alpha_map->first_range; range; range = range->next) {
322 serialize_int32_be_incr (ptr, range->begin);
323 serialize_int32_be_incr (ptr, range->end);
324 }
325 }
326
327 static int
328 alpha_map_add_range_only (AlphaMap *alpha_map, AlphaChar begin, AlphaChar end)
329 {
330 AlphaRange *q, *r, *begin_node, *end_node;
331
332 if (begin > end)
333 return -1;
334
335 begin_node = end_node = 0;
336
337 /* Skip first ranges till 'begin' is covered */
338 for (q = 0, r = alpha_map->first_range;
339 r && r->begin <= begin;
340 q = r, r = r->next)
341 {
342 if (begin <= r->end) {
343 /* 'r' covers 'begin' -> take 'r' as beginning point */
344 begin_node = r;
345 break;
346 }
347 if (r->end + 1 == begin) {
348 /* 'begin' is next to 'r'-end
349 * -> extend 'r'-end to cover 'begin'
350 */
351 r->end = begin;
352 begin_node = r;
353 break;
354 }
355 }
356 if (!begin_node && r && r->begin <= end + 1) {
357 /* ['begin', 'end'] overlaps into 'r'-begin
358 * or 'r' is next to 'end' if r->begin == end + 1
359 * -> extend 'r'-begin to include the range
360 */
361 r->begin = begin;
362 begin_node = r;
363 }
364 /* Run upto the first range that exceeds 'end' */
365 while (r && r->begin <= end + 1) {
366 if (end <= r->end) {
367 /* 'r' covers 'end' -> take 'r' as ending point */
368 end_node = r;
369 } else if (r != begin_node) {
370 /* ['begin', 'end'] covers the whole 'r' -> remove 'r' */
371 if (q) {
372 q->next = r->next;
373 free (r);
374 r = q->next;
375 } else {
376 alpha_map->first_range = r->next;
377 free (r);
378 r = alpha_map->first_range;
379 }
380 continue;
381 }
382 q = r;
383 r = r->next;
384 }
385 if (!end_node && q && begin <= q->end) {
386 /* ['begin', 'end'] overlaps 'q' at the end
387 * -> extend 'q'-end to include the range
388 */
389 q->end = end;
390 end_node = q;
391 }
392
393 if (begin_node && end_node) {
394 if (begin_node != end_node) {
395 /* Merge begin_node and end_node ranges together */
396 assert (begin_node->next == end_node);
397 begin_node->end = end_node->end;
398 begin_node->next = end_node->next;
399 free (end_node);
400 }
401 } else if (!begin_node && !end_node) {
402 /* ['begin', 'end'] overlaps with none of the ranges
403 * -> insert a new range
404 */
405 AlphaRange *range = (AlphaRange *) malloc (sizeof (AlphaRange));
406
407 if (UNLIKELY (!range))
408 return -1;
409
410 range->begin = begin;
411 range->end = end;
412
413 /* insert it between 'q' and 'r' */
414 if (q) {
415 q->next = range;
416 } else {
417 alpha_map->first_range = range;
418 }
419 range->next = r;
420 }
421
422 return 0;
423 }
424
425 static int
426 alpha_map_recalc_work_area (AlphaMap *alpha_map)
427 {
428 AlphaRange *range;
429
430 /* free old existing map */
431 if (alpha_map->alpha_to_trie_map) {
432 free (alpha_map->alpha_to_trie_map);
433 alpha_map->alpha_to_trie_map = NULL;
434 }
435 if (alpha_map->trie_to_alpha_map) {
436 free (alpha_map->trie_to_alpha_map);
437 alpha_map->trie_to_alpha_map = NULL;
438 }
439
440 range = alpha_map->first_range;
441 if (range) {
442 const AlphaChar alpha_begin = range->begin;
443 int n_alpha, n_trie, i;
444 AlphaChar a;
445 TrieIndex trie_char;
446
447 alpha_map->alpha_begin = alpha_begin;
448 n_trie = 0;
449 for ( ;; ) {
450 n_trie += range->end - range->begin + 1;
451 if (!range->next)
452 break;
453 range = range->next;
454 }
455 if (n_trie < TRIE_CHAR_TERM) {
456 n_trie = TRIE_CHAR_TERM + 1;
457 } else {
458 n_trie++;
459 }
460 alpha_map->alpha_end = range->end;
461
462 alpha_map->alpha_map_sz = n_alpha = range->end - alpha_begin + 1;
463 alpha_map->alpha_to_trie_map
464 = (TrieIndex *) malloc (n_alpha * sizeof (TrieIndex));
465 if (UNLIKELY (!alpha_map->alpha_to_trie_map))
466 goto error_alpha_map_not_created;
467 for (i = 0; i < n_alpha; i++) {
468 alpha_map->alpha_to_trie_map[i] = TRIE_INDEX_MAX;
469 }
470
471 alpha_map->trie_map_sz = n_trie;
472 alpha_map->trie_to_alpha_map
473 = (AlphaChar *) malloc (n_trie * sizeof (AlphaChar));
474 if (UNLIKELY (!alpha_map->trie_to_alpha_map))
475 goto error_alpha_map_created;
476
477 trie_char = 0;
478 for (range = alpha_map->first_range; range; range = range->next) {
479 for (a = range->begin; a <= range->end; a++) {
480 if (TRIE_CHAR_TERM == trie_char)
481 trie_char++;
482 alpha_map->alpha_to_trie_map[a - alpha_begin] = trie_char;
483 alpha_map->trie_to_alpha_map[trie_char] = a;
484 trie_char++;
485 }
486 }
487 while (trie_char < n_trie) {
488 alpha_map->trie_to_alpha_map[trie_char++] = ALPHA_CHAR_ERROR;
489 }
490 alpha_map->trie_to_alpha_map[TRIE_CHAR_TERM] = 0;
491 }
492
493 return 0;
494
495 error_alpha_map_created:
496 free (alpha_map->alpha_to_trie_map);
497 alpha_map->alpha_to_trie_map = NULL;
498 error_alpha_map_not_created:
499 return -1;
500 }
501
502 /**
503 * @brief Add a range to alphabet map
504 *
505 * @param alpha_map : the alphabet map object
506 * @param begin : the first character of the range
507 * @param end : the last character of the range
508 *
509 * @return 0 on success, non-zero on failure
510 *
511 * Add a range of character codes from @a begin to @a end to the
512 * alphabet set.
513 */
514 int
515 alpha_map_add_range (AlphaMap *alpha_map, AlphaChar begin, AlphaChar end)
516 {
517 int res = alpha_map_add_range_only (alpha_map, begin, end);
518 if (res != 0)
519 return res;
520 return alpha_map_recalc_work_area (alpha_map);
521 }
522
523 TrieIndex
524 alpha_map_char_to_trie (const AlphaMap *alpha_map, AlphaChar ac)
525 {
526 TrieIndex alpha_begin;
527
528 if (UNLIKELY (0 == ac))
529 return TRIE_CHAR_TERM;
530
531 if (UNLIKELY (!alpha_map->alpha_to_trie_map))
532 return TRIE_INDEX_MAX;
533
534 alpha_begin = alpha_map->alpha_begin;
535 if (alpha_begin <= ac && ac <= alpha_map->alpha_end)
536 {
537 return alpha_map->alpha_to_trie_map[ac - alpha_begin];
538 }
539
540 return TRIE_INDEX_MAX;
541 }
542
543 AlphaChar
544 alpha_map_trie_to_char (const AlphaMap *alpha_map, TrieChar tc)
545 {
546 if (tc < alpha_map->trie_map_sz)
547 return alpha_map->trie_to_alpha_map[tc];
548
549 return ALPHA_CHAR_ERROR;
550 }
551
552 TrieChar *
553 alpha_map_char_to_trie_str (const AlphaMap *alpha_map, const AlphaChar *str)
554 {
555 TrieChar *trie_str, *p;
556
557 trie_str = (TrieChar *) malloc (alpha_char_strlen (str) + 1);
558 if (UNLIKELY (!trie_str))
559 return NULL;
560
561 for (p = trie_str; *str; p++, str++) {
562 TrieIndex tc = alpha_map_char_to_trie (alpha_map, *str);
563 if (TRIE_INDEX_MAX == tc)
564 goto error_str_allocated;
565 *p = (TrieChar) tc;
566 }
567 *p = TRIE_CHAR_TERM;
568
569 return trie_str;
570
571 error_str_allocated:
572 free (trie_str);
573 return NULL;
574 }
575
576 AlphaChar *
577 alpha_map_trie_to_char_str (const AlphaMap *alpha_map, const TrieChar *str)
578 {
579 AlphaChar *alpha_str, *p;
580
581 alpha_str = (AlphaChar *) malloc ((trie_char_strlen (str) + 1)
582 * sizeof (AlphaChar));
583 if (UNLIKELY (!alpha_str))
584 return NULL;
585
586 for (p = alpha_str; *str; p++, str++) {
587 *p = (AlphaChar) alpha_map_trie_to_char (alpha_map, *str);
588 }
589 *p = 0;
590
591 return alpha_str;
592 }
593
594 /*
595 vi:ts=4:ai:expandtab
596 */