/*----- Data structures ---------------------------------------------------*/
+typedef unsigned countmap[UCHAR_MAX + 1];
+
typedef struct node_gram {
node n;
size_t sz;
- unsigned f[UCHAR_MAX + 1];
+ countmap count;
} node_gram;
/*----- Main code ---------------------------------------------------------*/
* Arguments: @node_gram *n@ = pointer to node to fill in
* @const char *p@ = pointer to string to compile from
*
- * Returns: The length of the string.
+ * Returns: ---
*
* Use: Fills in an anagram node with letter frequencies.
*/
-static size_t compile(node_gram *n, const char *p)
+static void compile(const char *p, countmap count)
{
- size_t len = 0;
- unsigned i;
- memset(n->f, 0, sizeof(n->f));
- while (*p) {
- i = (unsigned char)*p++;
- n->f[i]++;
- len++;
- }
- return (len);
+ memset(count, 0, sizeof(countmap));
+ while (*p) count[(unsigned char)*p++]++;
}
/* --- Node matcher --- */
static int n_gram(node *nn, const char *p, size_t sz)
{
+ /* A string X is a subgram of Y unless, for some character CH, X has more
+ * characters of value CH than Y.
+ *
+ * Special feature: count `.' in the pattern as meaning `don't care'.
+ */
+
node_gram *n = (node_gram *)nn;
- unsigned f[UCHAR_MAX];
+ countmap count;
const char *q;
unsigned i;
- if (n->sz && sz != n->sz)
- return (0);
- memcpy(f, n->f, sizeof(f));
+ if (n->sz && sz != n->sz) return (0);
+ memcpy(count, n->count, sizeof(count));
q = p + sz;
while (p < q) {
i = (unsigned char)*p++;
- if (f[i])
- f[i]--;
- else if (f['.'])
- f['.']--;
- else
- return (0);
+ if (count[i]) count[i]--;
+ else if (count['.']) count['.']--;
+ else return (0);
}
return (1);
}
{
node_gram *n = xmalloc(sizeof(*n));
n->n.func = n_gram;
- n->sz = compile(n, av[0]);
+ compile(av[0], n->count);
+ n->sz = strlen(av[0]);
return (&n->n);
}
{
node_gram *n = xmalloc(sizeof(*n));
n->n.func = n_gram;
+ compile(av[0], n->count);
n->sz = 0;
- compile(n, av[0]);
return (&n->n);
}