1. rcrnstn/fzy
  2. src
  3. choices.c
Browse code

Check return value from allocations in choices.c

Co-authored-by: mooon04 <mirae.kim040506@gmail.com>

John Hawthorn authored on 27/07/2025 07:00:58
Showing 1 changed files
src/choices.c
History View file @ 0b97373
... ... 
@@ -265,6 +265,10 @@ void choices_search(choices_t *c, const char *search) {
265 265 
 	choices_reset_search(c);
266 266
267 267 
 	struct search_job *job = calloc(1, sizeof(struct search_job));
268 
+	if (!job) {
269 
+		fprintf(stderr, "Error: Can't allocate memory\n");
270 
+		abort();
271 
+	}
268 272 
 	job->search = search;
269 273 
 	job->choices = c;
270 274 
 	if (pthread_mutex_init(&job->lock, NULL) != 0) {
... ... 
@@ -272,6 +276,10 @@ void choices_search(choices_t *c, const char *search) {
272 276 
 		abort();
273 277 
 	}
274 278 
 	job->workers = calloc(c->worker_count, sizeof(struct worker));
279 
+	if (!job->workers) {
280 
+		fprintf(stderr, "Error: Can't allocate memory\n");
281 
+		abort();
282 
+	}
275 283
276 284 
 	struct worker *workers = job->workers;
277 285 
 	for (int i = c->worker_count - 1; i >= 0; i--) {
... ... 
@@ -279,6 +287,10 @@ void choices_search(choices_t *c, const char *search) {
279 287 
 		workers[i].worker_num = i;
280 288 
 		workers[i].result.size = 0;
281 289 
 		workers[i].result.list = malloc(c->size * sizeof(struct scored_result)); /* FIXME: This is overkill */
290 
+		if (!workers[i].result.list) {
291 
+			fprintf(stderr, "Error: Can't allocate memory\n");
292 
+			abort();
293 
+		}
282 294
283 295 
 		/* These must be created last-to-first to avoid a race condition when fanning in */
284 296 
 		if ((errno = pthread_create(&workers[i].thread_id, NULL, &choices_search_worker, &workers[i]))) {
Browse code

Simplify input_delimiter handling

John Hawthorn authored on 16/08/2019 08:09:29
Showing 1 changed files
src/choices.c
History View file @ 79e4808
... ... 
@@ -46,7 +46,7 @@ static void *safe_realloc(void *buffer, size_t size) {
46 46 
 	return buffer;
47 47 
 }
48 48
49 
-void choices_fread(choices_t *c, FILE *file) {
49 
+void choices_fread(choices_t *c, FILE *file, char input_delimiter) {
50 50 
 	/* Save current position for parsing later */
51 51 
 	size_t buffer_start = c->buffer_size;
52 52
... ... 
@@ -75,7 +75,7 @@ void choices_fread(choices_t *c, FILE *file) {
75 75 
 	const char *line_end = c->buffer + c->buffer_size;
76 76 
 	char *line = c->buffer + buffer_start;
77 77 
 	do {
78 
-		char *nl = strchr(line, c->input_delimiter);
78 
+		char *nl = strchr(line, input_delimiter);
79 79 
 		if (nl)
80 80 
 			*nl++ = '\0';
81 81
... ... 
@@ -114,12 +114,6 @@ void choices_init(choices_t *c, options_t *options) {
114 114 
 		c->worker_count = (int)sysconf(_SC_NPROCESSORS_ONLN);
115 115 
 	}
116 116
117 
-	if (options->read_null) {
118 
-		c->input_delimiter = '\0';
119 
-	} else {
120 
-		c->input_delimiter = '\n';
121 
-	}
122 
-
123 117 
 	choices_reset_search(c);
124 118 
 }
125 119
Browse code

Add ability to use null as input delimiter.

Update tty to print newline as space
Add tty_putc

Ashkan Kiani authored on 03/05/2019 10:30:13 • John Hawthorn committed on 16/08/2019 08:05:01
Showing 1 changed files
src/choices.c
History View file @ c4524ae
... ... 
@@ -72,9 +72,10 @@ void choices_fread(choices_t *c, FILE *file) {
72 72 
 	 */
73 73
74 74 
 	/* Tokenize input and add to choices */
75 
+	const char *line_end = c->buffer + c->buffer_size;
75 76 
 	char *line = c->buffer + buffer_start;
76 77 
 	do {
77 
-		char *nl = strchr(line, '\n');
78 
+		char *nl = strchr(line, c->input_delimiter);
78 79 
 		if (nl)
79 80 
 			*nl++ = '\0';
80 81
... ... 
@@ -83,7 +84,7 @@ void choices_fread(choices_t *c, FILE *file) {
83 84 
 			choices_add(c, line);
84 85
85 86 
 		line = nl;
86 
-	} while (line);
87 
+	} while (line && line < line_end);
87 88 
 }
88 89
89 90 
 static void choices_resize(choices_t *c, size_t new_capacity) {
... ... 
@@ -113,6 +114,12 @@ void choices_init(choices_t *c, options_t *options) {
113 114 
 		c->worker_count = (int)sysconf(_SC_NPROCESSORS_ONLN);
114 115 
 	}
115 116
117 
+	if (options->read_null) {
118 
+		c->input_delimiter = '\0';
119 
+	} else {
120 
+		c->input_delimiter = '\n';
121 
+	}
122 
+
116 123 
 	choices_reset_search(c);
117 124 
 }
118 125
Browse code

choices: Fix a typo ("stings")

Jonathan Neuschäfer authored on 17/06/2018 20:45:24
Showing 1 changed files
src/choices.c
History View file @ 631c9dd
... ... 
@@ -21,7 +21,7 @@ static int cmpchoice(const void *_idx1, const void *_idx2) {
21 21
22 22 
 	if (a->score == b->score) {
23 23 
 		/* To ensure a stable sort, we must also sort by the string
24 
-		 * pointers. We can do this since we know all the stings are
24 
+		 * pointers. We can do this since we know all the strings are
25 25 
 		 * from a contiguous memory segment (buffer in choices_t).
26 26 
 		 */
27 27 
 		if (a->str < b->str) {
Browse code

Add -j option to control parallelism

John Hawthorn authored on 01/02/2017 02:13:27
Showing 1 changed files
src/choices.c
History View file @ 5aeaaa3
... ... 
@@ -107,7 +107,11 @@ void choices_init(choices_t *c, options_t *options) {
107 107 
 	c->capacity = c->size = 0;
108 108 
 	choices_resize(c, INITIAL_CHOICE_CAPACITY);
109 109
110 
-	c->worker_count = (int)sysconf(_SC_NPROCESSORS_ONLN);
110 
+	if (options->workers) {
111 
+		c->worker_count = options->workers;
112 
+	} else {
113 
+		c->worker_count = (int)sysconf(_SC_NPROCESSORS_ONLN);
114 
+	}
111 115
112 116 
 	choices_reset_search(c);
113 117 
 }
Browse code

Pass options to choices_init

John Hawthorn authored on 01/02/2017 02:06:42
Showing 1 changed files
src/choices.c
History View file @ 15b29a4
... ... 
@@ -5,6 +5,7 @@
5 5 
 #include <unistd.h>
6 6 
 #include <errno.h>
7 7
8 
+#include "options.h"
8 9 
 #include "choices.h"
9 10 
 #include "match.h"
10 11
... ... 
@@ -96,7 +97,7 @@ static void choices_reset_search(choices_t *c) {
96 97 
 	c->results = NULL;
97 98 
 }
98 99
99 
-void choices_init(choices_t *c) {
100 
+void choices_init(choices_t *c, options_t *options) {
100 101 
 	c->strings = NULL;
101 102 
 	c->results = NULL;
102 103
Browse code

Merge partially sorted lists in parallel

John Hawthorn authored on 15/01/2017 06:10:16
Showing 1 changed files
src/choices.c
History View file @ 1f77253
... ... 
@@ -3,6 +3,7 @@
3 3 
 #include <string.h>
4 4 
 #include <pthread.h>
5 5 
 #include <unistd.h>
6 
+#include <errno.h>
6 7
7 8 
 #include "choices.h"
8 9 
 #include "match.h"
... ... 
@@ -150,14 +151,14 @@ struct search_job {
150 151 
 	choices_t *choices;
151 152 
 	const char *search;
152 153 
 	size_t processed;
154 
+	struct worker *workers;
153 155 
 };
154 156
155 157 
 struct worker {
156 158 
 	pthread_t thread_id;
157 159 
 	struct search_job *job;
158 
-	size_t worker_num;
159 
-	struct scored_result *results;
160 
-	size_t available;
160 
+	unsigned int worker_num;
161 
+	struct result_list result;
161 162 
 };
162 163
163 164 
 static void worker_get_next_batch(struct search_job *job, size_t *start, size_t *end) {
... ... 
@@ -175,35 +176,6 @@ static void worker_get_next_batch(struct search_job *job, size_t *start, size_t
175 176 
 	pthread_mutex_unlock(&job->lock);
176 177 
 }
177 178
178 
-static void *choices_search_worker(void *data) {
179 
-	struct worker *w = (struct worker *)data;
180 
-	struct search_job *job = w->job;
181 
-	const choices_t *c = job->choices;
182 
-
183 
-	size_t start, end;
184 
-
185 
-	for(;;) {
186 
-		worker_get_next_batch(job, &start, &end);
187 
-
188 
-		if(start == end) {
189 
-			break;
190 
-		}
191 
-
192 
-		for(size_t i = start; i < end; i++) {
193 
-			if (has_match(job->search, c->strings[i])) {
194 
-				w->results[w->available].str = c->strings[i];
195 
-				w->results[w->available].score = match(job->search, c->strings[i]);
196 
-				w->available++;
197 
-			}
198 
-		}
199 
-	}
200 
-
201 
-	/* Sort the partial result */
202 
-	qsort(w->results, w->available, sizeof(struct scored_result), cmpchoice);
203 
-
204 
-	return w;
205 
-}
206 
-
207 179 
 static struct result_list merge2(struct result_list list1, struct result_list list2) {
208 180 
 	size_t result_index = 0, index1 = 0, index2 = 0;
209 181
... ... 
@@ -236,25 +208,51 @@ static struct result_list merge2(struct result_list list1, struct result_list li
236 208 
 	return result;
237 209 
 }
238 210
239 
-static void merge_step(struct search_job *job, struct worker *workers) {
240 
-	/* Merge our sorted partial-results */
241 
-	choices_t *c = job->choices;
211 
+static void *choices_search_worker(void *data) {
212 
+	struct worker *w = (struct worker *)data;
213 
+	struct search_job *job = w->job;
214 
+	const choices_t *c = job->choices;
215 
+	struct result_list *result = &w->result;
242 216
243 
-	struct result_list result = {NULL, 0};
217 
+	size_t start, end;
218 
+
219 
+	for(;;) {
220 
+		worker_get_next_batch(job, &start, &end);
221 
+
222 
+		if(start == end) {
223 
+			break;
224 
+		}
225 
+
226 
+		for(size_t i = start; i < end; i++) {
227 
+			if (has_match(job->search, c->strings[i])) {
228 
+				result->list[result->size].str = c->strings[i];
229 
+				result->list[result->size].score = match(job->search, c->strings[i]);
230 
+				result->size++;
231 
+			}
232 
+		}
233 
+	}
244 234
245 
-	for (unsigned int w = 0; w < c->worker_count; w++) {
246 
-		struct result_list new_result;
247 
-		struct worker *worker = &workers[w];
235 
+	/* Sort the partial result */
236 
+	qsort(result->list, result->size, sizeof(struct scored_result), cmpchoice);
237 
+
238 
+	/* Fan-in, merging results */
239 
+	for(unsigned int step = 0;; step++) {
240 
+		if (w->worker_num % (2 << step))
241 
+			break;
248 242
249 
-		struct result_list worker_result = {worker->results, worker->available};
250 
-		new_result = merge2(result, worker_result);
243 
+		unsigned int next_worker = w->worker_num | (1 << step);
244 
+		if (next_worker >= c->worker_count)
245 
+			break;
246 
+
247 
+		if ((errno = pthread_join(job->workers[next_worker].thread_id, NULL))) {
248 
+			perror("pthread_join");
249 
+			exit(EXIT_FAILURE);
250 
+		}
251 251
252 
-		free(result.list);
253 
-		result = new_result;
252 
+		w->result = merge2(w->result, job->workers[next_worker].result);
254 253 
 	}
255 254
256 
-	c->results = result.list;
257 
-	c->available = result.size;
255 
+	return NULL;
258 256 
 }
259 257
260 258 
 void choices_search(choices_t *c, const char *search) {
... ... 
@@ -267,31 +265,30 @@ void choices_search(choices_t *c, const char *search) {
267 265 
 		fprintf(stderr, "Error: pthread_mutex_init failed\n");
268 266 
 		abort();
269 267 
 	}
268 
+	job->workers = calloc(c->worker_count, sizeof(struct worker));
270 269
271 
-	struct worker *workers = calloc(c->worker_count, sizeof(struct worker));
272 
-	for (unsigned int i = 0; i < c->worker_count; i++) {
270 
+	struct worker *workers = job->workers;
271 
+	for (int i = c->worker_count - 1; i >= 0; i--) {
273 272 
 		workers[i].job = job;
274 273 
 		workers[i].worker_num = i;
275 
-		workers[i].results = malloc(c->size * sizeof(struct scored_result)); /* FIXME: This is overkill */
276 
-		if (pthread_create(&workers[i].thread_id, NULL, &choices_search_worker, &workers[i])) {
274 
+		workers[i].result.size = 0;
275 
+		workers[i].result.list = malloc(c->size * sizeof(struct scored_result)); /* FIXME: This is overkill */
276 
+
277 
+		/* These must be created last-to-first to avoid a race condition when fanning in */
278 
+		if ((errno = pthread_create(&workers[i].thread_id, NULL, &choices_search_worker, &workers[i]))) {
277 279 
 			perror("pthread_create");
278 280 
 			exit(EXIT_FAILURE);
279 281 
 		}
280 282 
 	}
281 283
282 
-	for (unsigned int i = 0; i < c->worker_count; i++) {
283 
-		if (pthread_join(workers[i].thread_id, NULL)) {
284 
-			perror("pthread_join");
285 
-			exit(EXIT_FAILURE);
286 
-		}
287 
-
284 
+	if (pthread_join(workers[0].thread_id, NULL)) {
285 
+		perror("pthread_join");
286 
+		exit(EXIT_FAILURE);
288 287 
 	}
289 288
290 
-	merge_step(job, workers);
289 
+	c->results = workers[0].result.list;
290 
+	c->available = workers[0].result.size;
291 291
292 
-	for (unsigned int i = 0; i < c->worker_count; i++) {
293 
-		free(workers[i].results);
294 
-	}
295 292 
 	free(workers);
296 293 
 	pthread_mutex_destroy(&job->lock);
297 294 
 	free(job);
Browse code

Replace k-way-merge with 2-way merge

John Hawthorn authored on 15/01/2017 05:46:55
Showing 1 changed files
src/choices.c
History View file @ 9bd9d1f
... ... 
@@ -140,6 +140,11 @@ size_t choices_available(choices_t *c) {
140 140
141 141 
 #define BATCH_SIZE 512
142 142
143 
+struct result_list {
144 
+	struct scored_result *list;
145 
+	size_t size;
146 
+};
147 
+
143 148 
 struct search_job {
144 149 
 	pthread_mutex_t lock;
145 150 
 	choices_t *choices;
... ... 
@@ -199,40 +204,57 @@ static void *choices_search_worker(void *data) {
199 204 
 	return w;
200 205 
 }
201 206
202 
-static void merge_step(struct search_job *job, struct worker *all_workers) {
203 
-	/* Merge our sorted partial-results */
204 
-	choices_t *c = job->choices;
205 
-	size_t worker_count = 0;
206 
-	struct worker *workers[c->worker_count];
207 
-	size_t indexes[c->worker_count];
207 
+static struct result_list merge2(struct result_list list1, struct result_list list2) {
208 
+	size_t result_index = 0, index1 = 0, index2 = 0;
208 209
209 
-	for (unsigned int w = 0; w < c->worker_count; w++) {
210 
-		indexes[w] = 0;
211 
-		if (all_workers[w].available) {
212 
-			workers[worker_count++] = &all_workers[w];
213 
-		}
210 
+	struct result_list result;
211 
+	result.size = list1.size + list2.size;
212 
+	result.list = malloc(result.size * sizeof(struct scored_result));
213 
+	if (!result.list) {
214 
+		fprintf(stderr, "Error: Can't allocate memory\n");
215 
+		abort();
214 216 
 	}
215 217
216 
-	while (worker_count) {
217 
-		/* Loop over each sorted block to find the lowest scoring result */
218 
-		unsigned int min_w = 0;
219 
-		for (unsigned int w = 0; w < worker_count; w++) {
220 
-			if (cmpchoice(&workers[w]->results[indexes[w]], &workers[min_w]->results[indexes[min_w]]) < 0) {
221 
-				min_w = w;
222 
-			}
218 
+	while(index1 < list1.size && index2 < list2.size) {
219 
+		if (cmpchoice(&list1.list[index1], &list2.list[index2]) < 0) {
220 
+			result.list[result_index++] = list1.list[index1++];
221 
+		} else {
222 
+			result.list[result_index++] = list2.list[index2++];
223 223 
 		}
224 
+	}
224 225
225 
-		/* Move that result onto our global list */
226 
-		c->results[c->available++] = workers[min_w]->results[indexes[min_w]++];
226 
+	while(index1 < list1.size) {
227 
+		result.list[result_index++] = list1.list[index1++];
228 
+	}
229 
+	while(index2 < list2.size) {
230 
+		result.list[result_index++] = list2.list[index2++];
231 
+	}
227 232
228 
-		/* If we have merged all the results for this worker, shuffle it
229 
-		 * out of our list */
230 
-		if (indexes[min_w] == workers[min_w]->available) {
231 
-			indexes[min_w] = indexes[worker_count - 1];
232 
-			workers[min_w] = workers[worker_count - 1];
233 
-			worker_count--;
234 
-		}
233 
+	free(list1.list);
234 
+	free(list2.list);
235 
+
236 
+	return result;
237 
+}
238 
+
239 
+static void merge_step(struct search_job *job, struct worker *workers) {
240 
+	/* Merge our sorted partial-results */
241 
+	choices_t *c = job->choices;
242 
+
243 
+	struct result_list result = {NULL, 0};
244 
+
245 
+	for (unsigned int w = 0; w < c->worker_count; w++) {
246 
+		struct result_list new_result;
247 
+		struct worker *worker = &workers[w];
248 
+
249 
+		struct result_list worker_result = {worker->results, worker->available};
250 
+		new_result = merge2(result, worker_result);
251 
+
252 
+		free(result.list);
253 
+		result = new_result;
235 254 
 	}
255 
+
256 
+	c->results = result.list;
257 
+	c->available = result.size;
236 258 
 }
237 259
238 260 
 void choices_search(choices_t *c, const char *search) {
... ... 
@@ -246,13 +268,6 @@ void choices_search(choices_t *c, const char *search) {
246 268 
 		abort();
247 269 
 	}
248 270
249 
-	/* allocate storage for our results */
250 
-	c->results = malloc(c->size * sizeof(struct scored_result));
251 
-	if (!c->results) {
252 
-		fprintf(stderr, "Error: Can't allocate memory\n");
253 
-		abort();
254 
-	}
255 
-
256 271 
 	struct worker *workers = calloc(c->worker_count, sizeof(struct worker));
257 272 
 	for (unsigned int i = 0; i < c->worker_count; i++) {
258 273 
 		workers[i].job = job;
Browse code

Perform sort in parallel

John Hawthorn authored on 15/01/2017 05:19:45
Showing 1 changed files
src/choices.c
History View file @ 267e6a4
... ... 
@@ -193,9 +193,48 @@ static void *choices_search_worker(void *data) {
193 193 
 		}
194 194 
 	}
195 195
196 
+	/* Sort the partial result */
197 
+	qsort(w->results, w->available, sizeof(struct scored_result), cmpchoice);
198 
+
196 199 
 	return w;
197 200 
 }
198 201
202 
+static void merge_step(struct search_job *job, struct worker *all_workers) {
203 
+	/* Merge our sorted partial-results */
204 
+	choices_t *c = job->choices;
205 
+	size_t worker_count = 0;
206 
+	struct worker *workers[c->worker_count];
207 
+	size_t indexes[c->worker_count];
208 
+
209 
+	for (unsigned int w = 0; w < c->worker_count; w++) {
210 
+		indexes[w] = 0;
211 
+		if (all_workers[w].available) {
212 
+			workers[worker_count++] = &all_workers[w];
213 
+		}
214 
+	}
215 
+
216 
+	while (worker_count) {
217 
+		/* Loop over each sorted block to find the lowest scoring result */
218 
+		unsigned int min_w = 0;
219 
+		for (unsigned int w = 0; w < worker_count; w++) {
220 
+			if (cmpchoice(&workers[w]->results[indexes[w]], &workers[min_w]->results[indexes[min_w]]) < 0) {
221 
+				min_w = w;
222 
+			}
223 
+		}
224 
+
225 
+		/* Move that result onto our global list */
226 
+		c->results[c->available++] = workers[min_w]->results[indexes[min_w]++];
227 
+
228 
+		/* If we have merged all the results for this worker, shuffle it
229 
+		 * out of our list */
230 
+		if (indexes[min_w] == workers[min_w]->available) {
231 
+			indexes[min_w] = indexes[worker_count - 1];
232 
+			workers[min_w] = workers[worker_count - 1];
233 
+			worker_count--;
234 
+		}
235 
+	}
236 
+}
237 
+
199 238 
 void choices_search(choices_t *c, const char *search) {
200 239 
 	choices_reset_search(c);
201 240
... ... 
@@ -226,26 +265,21 @@ void choices_search(choices_t *c, const char *search) {
226 265 
 	}
227 266
228 267 
 	for (unsigned int i = 0; i < c->worker_count; i++) {
229 
-		struct worker *w = &workers[i];
230 
-
231 
-		if (pthread_join(w->thread_id, NULL)) {
268 
+		if (pthread_join(workers[i].thread_id, NULL)) {
232 269 
 			perror("pthread_join");
233 270 
 			exit(EXIT_FAILURE);
234 271 
 		}
235 272
236 
-		memcpy(&c->results[c->available], w->results,  w->available * sizeof(struct scored_result));
237 
-		c->available += w->available;
238 
-
239 
-		free(w->results);
240 273 
 	}
241 274
242 
-	pthread_mutex_destroy(&job->lock);
243 
-	free(workers);
244 
-	free(job);
275 
+	merge_step(job, workers);
245 276
246 
-	if(*search) {
247 
-		qsort(c->results, c->available, sizeof(struct scored_result), cmpchoice);
277 
+	for (unsigned int i = 0; i < c->worker_count; i++) {
278 
+		free(workers[i].results);
248 279 
 	}
280 
+	free(workers);
281 
+	pthread_mutex_destroy(&job->lock);
282 
+	free(job);
249 283 
 }
250 284
251 285 
 const char *choices_get(choices_t *c, size_t n) {
Browse code

Fix memory leak of job

John Hawthorn authored on 15/01/2017 02:18:23
Showing 1 changed files
src/choices.c
History View file @ 77a2eb5
... ... 
@@ -241,6 +241,7 @@ void choices_search(choices_t *c, const char *search) {
241 241
242 242 
 	pthread_mutex_destroy(&job->lock);
243 243 
 	free(workers);
244 
+	free(job);
244 245
245 246 
 	if(*search) {
246 247 
 		qsort(c->results, c->available, sizeof(struct scored_result), cmpchoice);
Browse code

Improve parallelism of search workers

Previously the list of candidates was split between threads a priori,
with each thread being evenly distributed a contiguous range from the
search candidates.

This did a bad job of distributing the work evenly. There are likely to
be areas with significantly more matches than others (ex. files within
directories which match the search terms), as well as areas with longer
strings than others (ex. deep directories).

Because of the type of data fzy receives, work allocation needs to be
dynamic.

This commit changes the workers to operate on the candidates in batches,
until they have all been processed. Batches are allocated by locking a
mutex and grabbing the next available range of BATCH_SIZE candidates.

BATCH_SIZE is currently set at 512, which worked best on my laptop in a
quick test. This will always be a compromise. Small batch sizes will
distribute the work more evenly, but larger batch sizes will be
friendlier to CPU caches.

Quick testing:

Before:
./fzy -e drivers --benchmark < linux_files.txt 1.69s user 0.03s system 163% cpu 1.053 total

After:
./fzy -e drivers --benchmark < linux_files.txt 2.12s user 0.02s system 296% cpu 0.721 total

John Hawthorn authored on 08/01/2017 09:18:43
Showing 1 changed files
src/choices.c
History View file @ 5df8c7c
... ... 
@@ -138,9 +138,13 @@ size_t choices_available(choices_t *c) {
138 138 
 	return c->available;
139 139 
 }
140 140
141 
+#define BATCH_SIZE 512
142 
+
141 143 
 struct search_job {
144 
+	pthread_mutex_t lock;
142 145 
 	choices_t *choices;
143 146 
 	const char *search;
147 
+	size_t processed;
144 148 
 };
145 149
146 150 
 struct worker {
... ... 
@@ -151,19 +155,41 @@ struct worker {
151 155 
 	size_t available;
152 156 
 };
153 157
158 
+static void worker_get_next_batch(struct search_job *job, size_t *start, size_t *end) {
159 
+	pthread_mutex_lock(&job->lock);
160 
+
161 
+	*start = job->processed;
162 
+
163 
+	job->processed += BATCH_SIZE;
164 
+	if (job->processed > job->choices->size) {
165 
+		job->processed = job->choices->size;
166 
+	}
167 
+
168 
+	*end = job->processed;
169 
+
170 
+	pthread_mutex_unlock(&job->lock);
171 
+}
172 
+
154 173 
 static void *choices_search_worker(void *data) {
155 174 
 	struct worker *w = (struct worker *)data;
156 175 
 	struct search_job *job = w->job;
157 176 
 	const choices_t *c = job->choices;
158 177
159 
-	size_t start = (w->worker_num) * c->size / c->worker_count;
160 
-	size_t end = (w->worker_num + 1) * c->size / c->worker_count;
178 
+	size_t start, end;
179 
+
180 
+	for(;;) {
181 
+		worker_get_next_batch(job, &start, &end);
182 
+
183 
+		if(start == end) {
184 
+			break;
185 
+		}
161 186
162 
-	for(size_t i = start; i < end; i++) {
163 
-		if (has_match(job->search, c->strings[i])) {
164 
-			w->results[w->available].str = c->strings[i];
165 
-			w->results[w->available].score = match(job->search, c->strings[i]);
166 
-			w->available++;
187 
+		for(size_t i = start; i < end; i++) {
188 
+			if (has_match(job->search, c->strings[i])) {
189 
+				w->results[w->available].str = c->strings[i];
190 
+				w->results[w->available].score = match(job->search, c->strings[i]);
191 
+				w->available++;
192 
+			}
167 193 
 		}
168 194 
 	}
169 195
... ... 
@@ -176,6 +202,10 @@ void choices_search(choices_t *c, const char *search) {
176 202 
 	struct search_job *job = calloc(1, sizeof(struct search_job));
177 203 
 	job->search = search;
178 204 
 	job->choices = c;
205 
+	if (pthread_mutex_init(&job->lock, NULL) != 0) {
206 
+		fprintf(stderr, "Error: pthread_mutex_init failed\n");
207 
+		abort();
208 
+	}
179 209
180 210 
 	/* allocate storage for our results */
181 211 
 	c->results = malloc(c->size * sizeof(struct scored_result));
... ... 
@@ -208,6 +238,8 @@ void choices_search(choices_t *c, const char *search) {
208 238
209 239 
 		free(w->results);
210 240 
 	}
241 
+
242 
+	pthread_mutex_destroy(&job->lock);
211 243 
 	free(workers);
212 244
213 245 
 	if(*search) {
Browse code

Store choices on job struct

John Hawthorn authored on 08/01/2017 09:04:34
Showing 1 changed files
src/choices.c
History View file @ 66d2c52
... ... 
@@ -139,12 +139,12 @@ size_t choices_available(choices_t *c) {
139 139 
 }
140 140
141 141 
 struct search_job {
142 
+	choices_t *choices;
142 143 
 	const char *search;
143 144 
 };
144 145
145 146 
 struct worker {
146 147 
 	pthread_t thread_id;
147 
-	choices_t *choices;
148 148 
 	struct search_job *job;
149 149 
 	size_t worker_num;
150 150 
 	struct scored_result *results;
... ... 
@@ -154,7 +154,7 @@ struct worker {
154 154 
 static void *choices_search_worker(void *data) {
155 155 
 	struct worker *w = (struct worker *)data;
156 156 
 	struct search_job *job = w->job;
157 
-	const choices_t *c = w->choices;
157 
+	const choices_t *c = job->choices;
158 158
159 159 
 	size_t start = (w->worker_num) * c->size / c->worker_count;
160 160 
 	size_t end = (w->worker_num + 1) * c->size / c->worker_count;
... ... 
@@ -175,6 +175,7 @@ void choices_search(choices_t *c, const char *search) {
175 175
176 176 
 	struct search_job *job = calloc(1, sizeof(struct search_job));
177 177 
 	job->search = search;
178 
+	job->choices = c;
178 179
179 180 
 	/* allocate storage for our results */
180 181 
 	c->results = malloc(c->size * sizeof(struct scored_result));
... ... 
@@ -185,7 +186,6 @@ void choices_search(choices_t *c, const char *search) {
185 186
186 187 
 	struct worker *workers = calloc(c->worker_count, sizeof(struct worker));
187 188 
 	for (unsigned int i = 0; i < c->worker_count; i++) {
188 
-		workers[i].choices = c;
189 189 
 		workers[i].job = job;
190 190 
 		workers[i].worker_num = i;
191 191 
 		workers[i].results = malloc(c->size * sizeof(struct scored_result)); /* FIXME: This is overkill */
Browse code

Create search_job struct

John Hawthorn authored on 08/01/2017 08:55:11
Showing 1 changed files
src/choices.c
History View file @ 47dee6d
... ... 
@@ -138,10 +138,14 @@ size_t choices_available(choices_t *c) {
138 138 
 	return c->available;
139 139 
 }
140 140
141 
+struct search_job {
142 
+	const char *search;
143 
+};
144 
+
141 145 
 struct worker {
142 146 
 	pthread_t thread_id;
143 147 
 	choices_t *choices;
144 
-	const char *search;
148 
+	struct search_job *job;
145 149 
 	size_t worker_num;
146 150 
 	struct scored_result *results;
147 151 
 	size_t available;
... ... 
@@ -149,15 +153,16 @@ struct worker {
149 153
150 154 
 static void *choices_search_worker(void *data) {
151 155 
 	struct worker *w = (struct worker *)data;
156 
+	struct search_job *job = w->job;
152 157 
 	const choices_t *c = w->choices;
153 158
154 159 
 	size_t start = (w->worker_num) * c->size / c->worker_count;
155 160 
 	size_t end = (w->worker_num + 1) * c->size / c->worker_count;
156 161
157 162 
 	for(size_t i = start; i < end; i++) {
158 
-		if (has_match(w->search, c->strings[i])) {
163 
+		if (has_match(job->search, c->strings[i])) {
159 164 
 			w->results[w->available].str = c->strings[i];
160 
-			w->results[w->available].score = match(w->search, c->strings[i]);
165 
+			w->results[w->available].score = match(job->search, c->strings[i]);
161 166 
 			w->available++;
162 167 
 		}
163 168 
 	}
... ... 
@@ -168,6 +173,9 @@ static void *choices_search_worker(void *data) {
168 173 
 void choices_search(choices_t *c, const char *search) {
169 174 
 	choices_reset_search(c);
170 175
176 
+	struct search_job *job = calloc(1, sizeof(struct search_job));
177 
+	job->search = search;
178 
+
171 179 
 	/* allocate storage for our results */
172 180 
 	c->results = malloc(c->size * sizeof(struct scored_result));
173 181 
 	if (!c->results) {
... ... 
@@ -178,7 +186,7 @@ void choices_search(choices_t *c, const char *search) {
178 186 
 	struct worker *workers = calloc(c->worker_count, sizeof(struct worker));
179 187 
 	for (unsigned int i = 0; i < c->worker_count; i++) {
180 188 
 		workers[i].choices = c;
181 
-		workers[i].search = search;
189 
+		workers[i].job = job;
182 190 
 		workers[i].worker_num = i;
183 191 
 		workers[i].results = malloc(c->size * sizeof(struct scored_result)); /* FIXME: This is overkill */
184 192 
 		if (pthread_create(&workers[i].thread_id, NULL, &choices_search_worker, &workers[i])) {
Browse code

Remove unused and uninitialized worker struct var

John Hawthorn authored on 08/01/2017 08:50:19
Showing 1 changed files
src/choices.c
History View file @ 00123bf
... ... 
@@ -142,7 +142,6 @@ struct worker {
142 142 
 	pthread_t thread_id;
143 143 
 	choices_t *choices;
144 144 
 	const char *search;
145 
-	size_t worker_count;
146 145 
 	size_t worker_num;
147 146 
 	struct scored_result *results;
148 147 
 	size_t available;
Browse code

Use score_t instead of double

John Hawthorn authored on 27/06/2016 08:14:44
Showing 1 changed files
src/choices.c
History View file @ 7d3b5c1
... ... 
@@ -216,7 +216,7 @@ const char *choices_get(choices_t *c, size_t n) {
216 216 
 	}
217 217 
 }
218 218
219 
-double choices_getscore(choices_t *c, size_t n) {
219 
+score_t choices_getscore(choices_t *c, size_t n) {
220 220 
 	return c->results[n].score;
221 221 
 }
222 222
Browse code

Use number of processors as worker count

Since we're dividing the search set equally between processors, we want
to run with the same number of workers that we have CPU execution
threads. This avoids having a worker which is starved until the end of
execution.

John Hawthorn authored on 23/06/2016 04:43:48
Showing 1 changed files
src/choices.c
History View file @ 2142a44
... ... 
@@ -2,6 +2,7 @@
2 2 
 #include <stdio.h>
3 3 
 #include <string.h>
4 4 
 #include <pthread.h>
5 
+#include <unistd.h>
5 6
6 7 
 #include "choices.h"
7 8 
 #include "match.h"
... ... 
@@ -104,7 +105,7 @@ void choices_init(choices_t *c) {
104 105 
 	c->capacity = c->size = 0;
105 106 
 	choices_resize(c, INITIAL_CHOICE_CAPACITY);
106 107
107 
-	c->worker_count = 8;
108 
+	c->worker_count = (int)sysconf(_SC_NPROCESSORS_ONLN);
108 109
109 110 
 	choices_reset_search(c);
110 111 
 }
Browse code

Store worker_count on choices_t

John Hawthorn authored on 23/06/2016 04:26:21
Showing 1 changed files
src/choices.c
History View file @ 471431c
... ... 
@@ -104,6 +104,8 @@ void choices_init(choices_t *c) {
104 104 
 	c->capacity = c->size = 0;
105 105 
 	choices_resize(c, INITIAL_CHOICE_CAPACITY);
106 106
107 
+	c->worker_count = 8;
108 
+
107 109 
 	choices_reset_search(c);
108 110 
 }
109 111
... ... 
@@ -149,8 +151,8 @@ static void *choices_search_worker(void *data) {
149 151 
 	struct worker *w = (struct worker *)data;
150 152 
 	const choices_t *c = w->choices;
151 153
152 
-	size_t start = (w->worker_num) * c->size / w->worker_count;
153 
-	size_t end = (w->worker_num + 1) * c->size / w->worker_count;
154 
+	size_t start = (w->worker_num) * c->size / c->worker_count;
155 
+	size_t end = (w->worker_num + 1) * c->size / c->worker_count;
154 156
155 157 
 	for(size_t i = start; i < end; i++) {
156 158 
 		if (has_match(w->search, c->strings[i])) {
... ... 
@@ -173,12 +175,10 @@ void choices_search(choices_t *c, const char *search) {
173 175 
 		abort();
174 176 
 	}
175 177
176 
-	int worker_count = 8;
177 
-	struct worker *workers = calloc(worker_count, sizeof(struct worker));
178 
-	for (int i = 0; i < worker_count; i++) {
178 
+	struct worker *workers = calloc(c->worker_count, sizeof(struct worker));
179 
+	for (unsigned int i = 0; i < c->worker_count; i++) {
179 180 
 		workers[i].choices = c;
180 181 
 		workers[i].search = search;
181 
-		workers[i].worker_count = worker_count;
182 182 
 		workers[i].worker_num = i;
183 183 
 		workers[i].results = malloc(c->size * sizeof(struct scored_result)); /* FIXME: This is overkill */
184 184 
 		if (pthread_create(&workers[i].thread_id, NULL, &choices_search_worker, &workers[i])) {
... ... 
@@ -187,7 +187,7 @@ void choices_search(choices_t *c, const char *search) {
187 187 
 		}
188 188 
 	}
189 189
190 
-	for (int i = 0; i < worker_count; i++) {
190 
+	for (unsigned int i = 0; i < c->worker_count; i++) {
191 191 
 		struct worker *w = &workers[i];
192 192
193 193 
 		if (pthread_join(w->thread_id, NULL)) {
Browse code

Use threading when matching/scoring

John Hawthorn authored on 23/06/2016 04:43:37
Showing 1 changed files
src/choices.c
History View file @ 3cf9d22
... ... 
@@ -1,6 +1,7 @@
1 1 
 #include <stdlib.h>
2 2 
 #include <stdio.h>
3 3 
 #include <string.h>
4 
+#include <pthread.h>
4 5
5 6 
 #include "choices.h"
6 7 
 #include "match.h"
... ... 
@@ -134,8 +135,6 @@ size_t choices_available(choices_t *c) {
134 135 
 	return c->available;
135 136 
 }
136 137
137 
-#include <pthread.h>
138 
-
139 138 
 struct worker {
140 139 
 	pthread_t thread_id;
141 140 
 	choices_t *choices;
... ... 
@@ -182,8 +181,7 @@ void choices_search(choices_t *c, const char *search) {
182 181 
 		workers[i].worker_count = worker_count;
183 182 
 		workers[i].worker_num = i;
184 183 
 		workers[i].results = malloc(c->size * sizeof(struct scored_result)); /* FIXME: This is overkill */
185 
-		int ret = pthread_create(&workers[i].thread_id, NULL, &choices_search_worker, &workers[i]);
186 
-		if (ret != 0) {
184 
+		if (pthread_create(&workers[i].thread_id, NULL, &choices_search_worker, &workers[i])) {
187 185 
 			perror("pthread_create");
188 186 
 			exit(EXIT_FAILURE);
189 187 
 		}
... ... 
@@ -192,8 +190,7 @@ void choices_search(choices_t *c, const char *search) {
192 190 
 	for (int i = 0; i < worker_count; i++) {
193 191 
 		struct worker *w = &workers[i];
194 192
195 
-		int ret = pthread_join(w->thread_id, NULL);
196 
-		if (ret != 0) {
193 
+		if (pthread_join(w->thread_id, NULL)) {
197 194 
 			perror("pthread_join");
198 195 
 			exit(EXIT_FAILURE);
199 196 
 		}
Browse code

Use threading when matching/scoring

John Hawthorn authored on 18/06/2016 05:56:38
Showing 1 changed files
src/choices.c
History View file @ 6519dd4
... ... 
@@ -134,23 +134,77 @@ size_t choices_available(choices_t *c) {
134 134 
 	return c->available;
135 135 
 }
136 136
137 
+#include <pthread.h>
138 
+
139 
+struct worker {
140 
+	pthread_t thread_id;
141 
+	choices_t *choices;
142 
+	const char *search;
143 
+	size_t worker_count;
144 
+	size_t worker_num;
145 
+	struct scored_result *results;
146 
+	size_t available;
147 
+};
148 
+
149 
+static void *choices_search_worker(void *data) {
150 
+	struct worker *w = (struct worker *)data;
151 
+	const choices_t *c = w->choices;
152 
+
153 
+	size_t start = (w->worker_num) * c->size / w->worker_count;
154 
+	size_t end = (w->worker_num + 1) * c->size / w->worker_count;
155 
+
156 
+	for(size_t i = start; i < end; i++) {
157 
+		if (has_match(w->search, c->strings[i])) {
158 
+			w->results[w->available].str = c->strings[i];
159 
+			w->results[w->available].score = match(w->search, c->strings[i]);
160 
+			w->available++;
161 
+		}
162 
+	}
163 
+
164 
+	return w;
165 
+}
166 
+
137 167 
 void choices_search(choices_t *c, const char *search) {
138 168 
 	choices_reset_search(c);
139 169
170 
+	/* allocate storage for our results */
140 171 
 	c->results = malloc(c->size * sizeof(struct scored_result));
141 172 
 	if (!c->results) {
142 173 
 		fprintf(stderr, "Error: Can't allocate memory\n");
143 174 
 		abort();
144 175 
 	}
145 176
146 
-	for (size_t i = 0; i < c->size; i++) {
147 
-		if (has_match(search, c->strings[i])) {
148 
-			c->results[c->available].str = c->strings[i];
149 
-			c->results[c->available].score = match(search, c->strings[i]);
150 
-			c->available++;
177 
+	int worker_count = 8;
178 
+	struct worker *workers = calloc(worker_count, sizeof(struct worker));
179 
+	for (int i = 0; i < worker_count; i++) {
180 
+		workers[i].choices = c;
181 
+		workers[i].search = search;
182 
+		workers[i].worker_count = worker_count;
183 
+		workers[i].worker_num = i;
184 
+		workers[i].results = malloc(c->size * sizeof(struct scored_result)); /* FIXME: This is overkill */
185 
+		int ret = pthread_create(&workers[i].thread_id, NULL, &choices_search_worker, &workers[i]);
186 
+		if (ret != 0) {
187 
+			perror("pthread_create");
188 
+			exit(EXIT_FAILURE);
151 189 
 		}
152 190 
 	}
153 191
192 
+	for (int i = 0; i < worker_count; i++) {
193 
+		struct worker *w = &workers[i];
194 
+
195 
+		int ret = pthread_join(w->thread_id, NULL);
196 
+		if (ret != 0) {
197 
+			perror("pthread_join");
198 
+			exit(EXIT_FAILURE);
199 
+		}
200 
+
201 
+		memcpy(&c->results[c->available], w->results,  w->available * sizeof(struct scored_result));
202 
+		c->available += w->available;
203 
+
204 
+		free(w->results);
205 
+	}
206 
+	free(workers);
207 
+
154 208 
 	if(*search) {
155 209 
 		qsort(c->results, c->available, sizeof(struct scored_result), cmpchoice);
156 210 
 	}
Browse code

Skip sorting on empty search string

For the empty query, sorting can be the slowest part of the search.
Since the empty query gives no scores, and we've now made our sort
stable, in this case we can simply skip sorting.

A sort of 250000 entries took about ~10ms on my laptop, which is not a
huge amount. However it's not 0 and is free to skip.

John Hawthorn authored on 07/06/2016 09:03:48
Showing 1 changed files
src/choices.c
History View file @ e6f8353
... ... 
@@ -151,7 +151,9 @@ void choices_search(choices_t *c, const char *search) {
151 151 
 		}
152 152 
 	}
153 153
154 
-	qsort(c->results, c->available, sizeof(struct scored_result), cmpchoice);
154 
+	if(*search) {
155 
+		qsort(c->results, c->available, sizeof(struct scored_result), cmpchoice);
156 
+	}
155 157 
 }
156 158
157 159 
 const char *choices_get(choices_t *c, size_t n) {
Browse code

Make sorting stable

C's stdlib's qsort isn't a stable sort. We want it to be so that any
equivalent matches are stored in the order they came in.

John Hawthorn authored on 07/06/2016 08:58:41
Showing 1 changed files
src/choices.c
History View file @ 3b23f57
... ... 
@@ -15,12 +15,21 @@ static int cmpchoice(const void *_idx1, const void *_idx2) {
15 15 
 	const struct scored_result *a = _idx1;
16 16 
 	const struct scored_result *b = _idx2;
17 17
18 
-	if (a->score == b->score)
19 
-		return 0;
20 
-	else if (a->score < b->score)
18 
+	if (a->score == b->score) {
19 
+		/* To ensure a stable sort, we must also sort by the string
20 
+		 * pointers. We can do this since we know all the stings are
21 
+		 * from a contiguous memory segment (buffer in choices_t).
22 
+		 */
23 
+		if (a->str < b->str) {
24 
+			return -1;
25 
+		} else {
26 
+			return 1;
27 
+		}
28 
+	} else if (a->score < b->score) {
21 29 
 		return 1;
22 
-	else
30 
+	} else {
23 31 
 		return -1;
32 
+	}
24 33 
 }
25 34
26 35 
 static void *safe_realloc(void *buffer, size_t size) {
Browse code

Move sources into src directory

John Hawthorn authored on 21/05/2016 21:56:03
Showing 1 changed files
src/choices.c
History View file @ 2b3c3a8
1 1 
new file mode 100644
... ... 
@@ -0,0 +1,168 @@
1 
+#include <stdlib.h>
2 
+#include <stdio.h>
3 
+#include <string.h>
4 
+
5 
+#include "choices.h"
6 
+#include "match.h"
7 
+
8 
+/* Initial size of buffer for storing input in memory */
9 
+#define INITIAL_BUFFER_CAPACITY 4096
10 
+
11 
+/* Initial size of choices array */
12 
+#define INITIAL_CHOICE_CAPACITY 128
13 
+
14 
+static int cmpchoice(const void *_idx1, const void *_idx2) {
15 
+	const struct scored_result *a = _idx1;
16 
+	const struct scored_result *b = _idx2;
17 
+
18 
+	if (a->score == b->score)
19 
+		return 0;
20 
+	else if (a->score < b->score)
21 
+		return 1;
22 
+	else
23 
+		return -1;
24 
+}
25 
+
26 
+static void *safe_realloc(void *buffer, size_t size) {
27 
+	buffer = realloc(buffer, size);
28 
+	if (!buffer) {
29 
+		fprintf(stderr, "Error: Can't allocate memory (%zu bytes)\n", size);
30 
+		abort();
31 
+	}
32 
+
33 
+	return buffer;
34 
+}
35 
+
36 
+void choices_fread(choices_t *c, FILE *file) {
37 
+	/* Save current position for parsing later */
38 
+	size_t buffer_start = c->buffer_size;
39 
+
40 
+	/* Resize buffer to at least one byte more capacity than our current
41 
+	 * size. This uses a power of two of INITIAL_BUFFER_CAPACITY.
42 
+	 * This must work even when c->buffer is NULL and c->buffer_size is 0
43 
+	 */
44 
+	size_t capacity = INITIAL_BUFFER_CAPACITY;
45 
+	while (capacity <= c->buffer_size)
46 
+		capacity *= 2;
47 
+	c->buffer = safe_realloc(c->buffer, capacity);
48 
+
49 
+	/* Continue reading until we get a "short" read, indicating EOF */
50 
+	while ((c->buffer_size += fread(c->buffer + c->buffer_size, 1, capacity - c->buffer_size, file)) == capacity) {
51 
+		capacity *= 2;
52 
+		c->buffer = safe_realloc(c->buffer, capacity);
53 
+	}
54 
+	c->buffer = safe_realloc(c->buffer, c->buffer_size + 1);
55 
+	c->buffer[c->buffer_size++] = '\0';
56 
+
57 
+	/* Truncate buffer to used size, (maybe) freeing some memory for
58 
+	 * future allocations.
59 
+	 */
60 
+
61 
+	/* Tokenize input and add to choices */
62 
+	char *line = c->buffer + buffer_start;
63 
+	do {
64 
+		char *nl = strchr(line, '\n');
65 
+		if (nl)
66 
+			*nl++ = '\0';
67 
+
68 
+		/* Skip empty lines */
69 
+		if (*line)
70 
+			choices_add(c, line);
71 
+
72 
+		line = nl;
73 
+	} while (line);
74 
+}
75 
+
76 
+static void choices_resize(choices_t *c, size_t new_capacity) {
77 
+	c->strings = safe_realloc(c->strings, new_capacity * sizeof(const char *));
78 
+	c->capacity = new_capacity;
79 
+}
80 
+
81 
+static void choices_reset_search(choices_t *c) {
82 
+	free(c->results);
83 
+	c->selection = c->available = 0;
84 
+	c->results = NULL;
85 
+}
86 
+
87 
+void choices_init(choices_t *c) {
88 
+	c->strings = NULL;
89 
+	c->results = NULL;
90 
+
91 
+	c->buffer_size = 0;
92 
+	c->buffer = NULL;
93 
+
94 
+	c->capacity = c->size = 0;
95 
+	choices_resize(c, INITIAL_CHOICE_CAPACITY);
96 
+
97 
+	choices_reset_search(c);
98 
+}
99 
+
100 
+void choices_destroy(choices_t *c) {
101 
+	free(c->buffer);
102 
+	c->buffer = NULL;
103 
+	c->buffer_size = 0;
104 
+
105 
+	free(c->strings);
106 
+	c->strings = NULL;
107 
+	c->capacity = c->size = 0;
108 
+
109 
+	free(c->results);
110 
+	c->results = NULL;
111 
+	c->available = c->selection = 0;
112 
+}
113 
+
114 
+void choices_add(choices_t *c, const char *choice) {
115 
+	/* Previous search is now invalid */
116 
+	choices_reset_search(c);
117 
+
118 
+	if (c->size == c->capacity) {
119 
+		choices_resize(c, c->capacity * 2);
120 
+	}
121 
+	c->strings[c->size++] = choice;
122 
+}
123 
+
124 
+size_t choices_available(choices_t *c) {
125 
+	return c->available;
126 
+}
127 
+
128 
+void choices_search(choices_t *c, const char *search) {
129 
+	choices_reset_search(c);
130 
+
131 
+	c->results = malloc(c->size * sizeof(struct scored_result));
132 
+	if (!c->results) {
133 
+		fprintf(stderr, "Error: Can't allocate memory\n");
134 
+		abort();
135 
+	}
136 
+
137 
+	for (size_t i = 0; i < c->size; i++) {
138 
+		if (has_match(search, c->strings[i])) {
139 
+			c->results[c->available].str = c->strings[i];
140 
+			c->results[c->available].score = match(search, c->strings[i]);
141 
+			c->available++;
142 
+		}
143 
+	}
144 
+
145 
+	qsort(c->results, c->available, sizeof(struct scored_result), cmpchoice);
146 
+}
147 
+
148 
+const char *choices_get(choices_t *c, size_t n) {
149 
+	if (n < c->available) {
150 
+		return c->results[n].str;
151 
+	} else {
152 
+		return NULL;
153 
+	}
154 
+}
155 
+
156 
+double choices_getscore(choices_t *c, size_t n) {
157 
+	return c->results[n].score;
158 
+}
159 
+
160 
+void choices_prev(choices_t *c) {
161 
+	if (c->available)
162 
+		c->selection = (c->selection + c->available - 1) % c->available;
163 
+}
164 
+
165 
+void choices_next(choices_t *c) {
166 
+	if (c->available)
167 
+		c->selection = (c->selection + 1) % c->available;
168 
+}