]> ruderich.org/simon Gitweb - nsscash/nsscash.git/blob - nss/search.c
nsscash: main_test: use existing t variable instead of a.t
[nsscash/nsscash.git] / nss / search.c
1 /*
2  * Search entries in nsscash files by using indices and binary search
3  *
4  * Copyright (C) 2019  Simon Ruderich
5  *
6  * This program is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU Affero General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * This program 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
14  * GNU Affero General Public License for more details.
15  *
16  * You should have received a copy of the GNU Affero General Public License
17  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
18  */
19
20 #include "search.h"
21
22 #include <stdlib.h>
23 #include <string.h>
24
25
26 static int bsearch_callback(const void *x, const void *y) {
27     const struct search_key *key = x;
28
29     uint64_t offset = *(const uint64_t *)y; // from index
30     const void *member = (const char *)key->data + offset + key->offset;
31
32     // Lookup by name (char *)
33     if (key->name != NULL) {
34         const char *name = member;
35         return strcmp(key->name, name);
36
37     // Lookup by ID (uint64_t)
38     } else {
39         const uint64_t *id = member;
40         if (key->id < *id) {
41             return -1;
42         } else if (key->id == *id) {
43             return 0;
44         } else {
45             return +1;
46         }
47     }
48 }
49
50 // search performs a binary search on an index, described by key and index.
51 uint64_t *search(const struct search_key *key, const void *index, uint64_t count) {
52     return bsearch(key, index, count, sizeof(uint64_t), bsearch_callback);
53 }