1 /*
2  * Copyright (c) 2022 Omar Polo <op@openbsd.org>
3  *
4  * Permission to use, copy, modify, and distribute this software for any
5  * purpose with or without fee is hereby granted, provided that the above
6  * copyright notice and this permission notice appear in all copies.
7  *
8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15  */
16 
17 #include <string.h>
18 #include <stdlib.h>
19 #include <stdint.h>
20 #include <unistd.h>
21 
22 #include "dictionary.h"
23 
24 int
25 dictionary_init(struct dictionary *dict)
26 {
27 	memset(dict, 0, sizeof(*dict));
28 	return 1;
29 }
30 
31 static inline int
32 add_docid(struct dict_entry *e, int docid)
33 {
34 	void *t;
35 	size_t newcap;
36 
37 	if (e->len > 0 && e->ids[e->len-1] == docid)
38 		return 1;
39 
40 	if (e->len == e->cap) {
41 		newcap = e->cap * 1.5;
42 		if (newcap == 0)
43 			newcap = 8;
44 		t = recallocarray(e->ids, e->cap, newcap, sizeof(*e->ids));
45 		if (t == NULL)
46 			return 0;
47 		e->ids = t;
48 		e->cap = newcap;
49 	}
50 
51 	e->ids[e->len++] = docid;
52 	return 1;
53 }
54 
55 int
56 dictionary_add(struct dictionary *dict, const char *word, int docid)
57 {
58 	struct dict_entry *e = NULL;
59 	void *newentr;
60 	size_t newcap, mid = 0, left = 0, right = dict->len;
61 	int r = 0;
62 
63 	while (left < right) {
64 		mid = (left + right) / 2;
65 		e = &dict->entries[mid];
66 		r = strcmp(word, e->word);
67 		if (r < 0)
68 			right = mid;
69 		else if (r > 0)
70 			left = mid + 1;
71 		else
72 			return add_docid(e, docid);
73 	}
74 
75 	if (r > 0)
76 		mid++;
77 
78 	if (dict->len == dict->cap) {
79 		newcap = dict->cap * 1.5;
80 		if (newcap == 0)
81 			newcap = 8;
82 		newentr = recallocarray(dict->entries, dict->cap, newcap,
83 		    sizeof(*dict->entries));
84 		if (newentr == NULL)
85 			return 0;
86 		dict->entries = newentr;
87 		dict->cap = newcap;
88 	}
89 
90 	e = &dict->entries[mid];
91 	if (e != dict->entries + dict->len) {
92 		size_t i = e - dict->entries;
93 		memmove(e+1, e, sizeof(*e) * (dict->len - i));
94 	}
95 
96 	dict->len++;
97 	memset(e, 0, sizeof(*e));
98 	if ((e->word = strdup(word)) == NULL)
99 		return 0;
100 	return add_docid(e, docid);
101 }
102 
103 int
104 dictionary_add_words(struct dictionary *dict, char **words, int docid)
105 {
106 	for (; *words != NULL; ++words) {
107 		if (!dictionary_add(dict, *words, docid))
108 			return 0;
109 	}
110 
111 	return 1;
112 }
113 
114 void
115 dictionary_free(struct dictionary *dict)
116 {
117 	size_t i;
118 
119 	for (i = 0; i < dict->len; ++i) {
120 		free(dict->entries[i].word);
121 		free(dict->entries[i].ids);
122 	}
123 
124 	free(dict->entries);
125 }