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