xapian-core  1.4.21
keyword.cc
Go to the documentation of this file.
1 
4 /* Copyright (C) 2012,2016 Olly Betts
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a copy
7  * of this software and associated documentation files (the "Software"), to
8  * deal in the Software without restriction, including without limitation the
9  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10  * sell copies of the Software, and to permit persons to whom the Software is
11  * furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22  * IN THE SOFTWARE.
23  */
24 
25 #include <config.h>
26 
27 #include "keyword.h"
28 
29 #include <string.h>
30 
31 int
32 keyword(const unsigned char * p, const char * s, size_t len)
33 {
34  if (len == 0 || len > p[0] || p[len] == 1)
35  return -1;
36  p = p + p[0] + p[len] + 3;
37  size_t n = len + 1;
38  const unsigned char * q = p + n * (p[-2] + 1);
39  /* Binary chop between p and q */
40  size_t d = n * 2;
41  while (p < q) {
42  const unsigned char * m = p + (q - p) / d * n;
43  int cmp = memcmp(s, m, len);
44  if (cmp < 0) {
45  q = m;
46  } else if (cmp > 0) {
47  p = m + n;
48  } else {
49  return m[-1];
50  }
51  }
52  return -1;
53 }
54 
55 int
56 keyword2(const unsigned char * p, const char * s, size_t len)
57 {
58  if (len == 0 || len > p[0])
59  return -1;
60  unsigned offset = (p[len * 2 - 1] | p[len * 2] << 8);
61  if (offset == 1)
62  return -1;
63  p = p + 2 * p[0] + offset + 3;
64  size_t n = len + 1;
65  const unsigned char * q = p + n * (p[-2] + 1);
66  /* Binary chop between p and q */
67  size_t d = n * 2;
68  while (p < q) {
69  const unsigned char * m = p + (q - p) / d * n;
70  int cmp = memcmp(s, m, len);
71  if (cmp < 0) {
72  q = m;
73  } else if (cmp > 0) {
74  p = m + n;
75  } else {
76  return m[-1];
77  }
78  }
79  return -1;
80 }
int keyword2(const unsigned char *p, const char *s, size_t len)
2 byte offset variant.
Definition: keyword.cc:56
int keyword(const unsigned char *p, const char *s, size_t len)
Definition: keyword.cc:32
Efficient keyword to enum lookup.