/*
* dnsutl - utilities to make DNS easier to configure
* Copyright (C) 1991-1994, 1996, 1999, 2006, 2007 Peter Miller
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or (at
* your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
* ------------
*
* Strings are the most heavily used resource in cook. They are manipulated
* inside the match functions, and hence are in the inside loop. For this
* reason they must be fast.
*
* A literal pool is maintained. Each string has a reference count. The
* string stays in the literal pool for as long as it hash a positive
* reference count. To determine if a string is already in the literal pool,
* linear dynamic hashing is used to guarantee an O(1) search. That all equal
* strings are the same item in the literal pool means that string equality is
* a pointer test, and thus very fast.
*/
#include <ac/ctype.h>
#include <ac/stddef.h>
#include <ac/stdio.h>
#include <ac/stdlib.h>
#include <ac/string.h>
#include <error.h>
#include <mem.h>
#include <mprintf.h>
#include <str.h>
/*
* maximum conversion width for numbers
*/
#define MAX_WIDTH 509
static string_ty **hash_table;
static str_hash_ty hash_modulus;
static str_hash_ty hash_cutover;
static str_hash_ty hash_cutover_mask;
static str_hash_ty hash_cutover_split_mask;
static str_hash_ty hash_split;
static str_hash_ty hash_load;
#define MAX_HASH_LEN 20
/*
* NAME
* hash_generate - hash string to number
*
* SYNOPSIS
* str_hash_ty hash_generate(char *s, size_t n);
*
* DESCRIPTION
* The hash_generate function is used to make a number from a string.
*
* RETURNS
* str_hash_ty - the magic number
*
* CAVEAT
* Only the last MAX_HASH_LEN characters are used.
* It is important that str_hash_ty be unsigned (int or long).
*/
static str_hash_ty
hash_generate(const char *s, size_t n)
{
str_hash_ty retval;
if (n > MAX_HASH_LEN)
{
s += n - MAX_HASH_LEN;
n = MAX_HASH_LEN;
}
retval = 0;
while (n > 0)
{
retval = (retval + (retval << 1)) ^ *s++;
--n;
}
return retval;
}
/*
* NAME
* str_valid - test a string
*
* SYNOPSIS
* int str_valid(string_ty *s);
*
* DESCRIPTION
* The str_valid function is used to test if a pointer points to a valid
* string.
*
* RETURNS
* int: zero if the string is not valid, nonzero if the string is valid.
*
* CAVEAT
* This function is only available then the DEBUG symbol is #define'd.
*/
#ifdef DEBUG
int
str_valid(string_ty *s)
{
return
(
s
&&
s->str_references > 0
&&
strlen(s->str_text) == s->str_length
&&
s->str_hash == hash_generate(s->str_text, s->str_length)
);
}
#endif
/*
* NAME
* str_initialize - start up string table
*
* SYNOPSIS
* void str_initialize(void);
*
* DESCRIPTION
* The str_initialize function is used to create the hash table and
* initialize it to empty.
*
* RETURNS
* void
*
* CAVEAT
* This function must be called before any other defined in this file.
*/
static void
str_initialize(void)
{
str_hash_ty j;
hash_modulus = 1 << 8; /* MUST be a power of 2 */
hash_cutover = hash_modulus;
hash_split = hash_modulus - hash_cutover;
hash_cutover_mask = hash_cutover - 1;
hash_cutover_split_mask = (hash_cutover * 2) - 1;
hash_load = 0;
hash_table = mem_alloc(hash_modulus * sizeof(string_ty *));
for (j = 0; j < hash_modulus; ++j)
hash_table[j] = 0;
}
/*
* NAME
* split - reduce table loading
*
* SYNOPSIS
* void split(void);
*
* DESCRIPTION
* The split function is used to reduce the load factor on the hash table.
*
* RETURNS
* void
*
* CAVEAT
* A load factor of about 80% is suggested.
*/
static void
split(void)
{
string_ty *p;
string_ty *p2;
str_hash_ty idx;
/*
* get the list to be split across buckets
*/
p = hash_table[hash_split];
hash_table[hash_split] = 0;
/*
* increase the modulus by one
*/
hash_modulus++;
hash_table =
mem_change_size
(
hash_table,
hash_modulus * sizeof(string_ty *)
);
hash_table[hash_modulus - 1] = 0;
hash_split = hash_modulus - hash_cutover;
if (hash_split >= hash_cutover)
{
hash_cutover = hash_modulus;
hash_split = 0;
hash_cutover_mask = hash_cutover - 1;
hash_cutover_split_mask = (hash_cutover * 2) - 1;
}
/*
* now redistribute the list elements
*/
while (p)
{
p2 = p;
p = p->str_next;
idx = p2->str_hash & hash_cutover_mask;
if (idx < hash_split)
idx = p2->str_hash & hash_cutover_split_mask;
assert(idx < hash_modulus);
p2->str_next = hash_table[idx];
hash_table[idx] = p2;
}
}
/*
* NAME
* str_from_c - make string from C string
*
* SYNOPSIS
* string_ty *str_from_c(char*);
*
* DESCRIPTION
* The str_from_c function is used to make a string from a null terminated
* C string.
*
* RETURNS
* string_ty * - a pointer to a string in dynamic memory. Use
* str_free when finished with.
*
* CAVEAT
* The contents of the structure pointed to MUST NOT be altered.
*/
string_ty *
str_from_c(const char *s)
{
return str_n_from_c(s, strlen(s));
}
/*
* NAME
* str_n_from_c - make string
*
* SYNOPSIS
* string_ty *str_n_from_c(char *s, size_t n);
*
* DESCRIPTION
* The str_n_from_c function is used to make a string from an array of
* characters. No null terminator is assumed.
*
* RETURNS
* string_ty * - a pointer to a string in dynamic memory. Use
* str_free when finished with.
*
* CAVEAT
* The contents of the structure pointed to MUST NOT be altered.
*/
string_ty *
str_n_from_c(const char *s, size_t length)
{
str_hash_ty hash;
str_hash_ty idx;
string_ty *p;
hash = hash_generate(s, length);
if (!hash_table)
str_initialize();
idx = hash & hash_cutover_mask;
if (idx < hash_split)
idx = hash & hash_cutover_split_mask;
assert(idx < hash_modulus);
for (p = hash_table[idx]; p; p = p->str_next)
{
if
(
p->str_hash == hash
&&
p->str_length == length
&&
!memcmp(p->str_text, s, length)
)
{
p->str_references++;
return p;
}
}
p = mem_alloc(sizeof(string_ty) + length);
p->str_hash = hash;
p->str_length = length;
p->str_references = 1;
p->str_next = hash_table[idx];
hash_table[idx] = p;
memcpy(p->str_text, s, length);
p->str_text[length] = 0;
hash_load++;
while (hash_load * 10 > hash_modulus * 8)
split();
return p;
}
/*
* NAME
* str_copy - make a copy of a string
*
* SYNOPSIS
* string_ty *str_copy(string_ty *s);
*
* DESCRIPTION
* The str_copy function is used to make a copy of a string.
*
* RETURNS
* string_ty * - a pointer to a string in dynamic memory. Use
* str_free when finished with.
*
* CAVEAT
* The contents of the structure pointed to MUST NOT be altered.
*/
string_ty *
str_copy(string_ty *s)
{
assert(str_valid(s));
s->str_references++;
return s;
}
/*
* NAME
* str_free - release a string
*
* SYNOPSIS
* void str_free(string_ty *s);
*
* DESCRIPTION
* The str_free function is used to indicate that a string hash been
* finished with.
*
* RETURNS
* void
*
* CAVEAT
* This is the only way to release strings DO NOT use the free function.
*/
void
str_free(string_ty *s)
{
str_hash_ty idx;
string_ty **spp;
assert(str_valid(s));
if (s->str_references > 1)
{
s->str_references--;
return;
}
assert(s->str_references == 1);
/*
* find the hash bucket it was in,
* and remove it
*/
idx = s->str_hash & hash_cutover_mask;
if (idx < hash_split)
idx = s->str_hash & hash_cutover_split_mask;
assert(idx < hash_modulus);
for (spp = &hash_table[idx]; *spp; spp = &(*spp)->str_next)
{
if (*spp == s)
{
*spp = s->str_next;
free(s);
--hash_load;
return;
}
}
/* should never reach here! */
fatal("attempted to free non-existent string (bug)");
}
/*
* NAME
* str_catenate - join two strings
*
* SYNOPSIS
* string_ty *str_catenate(string_ty *, string_ty *);
*
* DESCRIPTION
* The str_catenate function is used to concatenate two strings to
* form a new string.
*
* RETURNS
* string_ty * - a pointer to a string in dynamic memory. Use
* str_free when finished with.
*
* CAVEAT
* The contents of the structure pointed to MUST NOT be altered.
*/
string_ty *
str_catenate(string_ty *s1, string_ty *s2)
{
static char *tmp;
static size_t tmplen;
string_ty *s;
size_t length;
length = s1->str_length + s2->str_length;
if (tmplen < length)
{
tmplen = length;
tmp = mem_change_size(tmp, tmplen);
}
memcpy(tmp, s1->str_text, s1->str_length);
memcpy(tmp + s1->str_length, s2->str_text, s2->str_length);
s = str_n_from_c(tmp, length);
return s;
}
/*
* NAME
* str_cat_three - join three strings
*
* SYNOPSIS
* string_ty *str_cat_three(string_ty *, string_ty *, string_ty *);
*
* DESCRIPTION
* The str_cat_three function is used to concatenate three strings
* to form a new string.
*
* RETURNS
* string_ty * - a pointer to a string in dynamic memory. Use
* str_free when finished with.
*
* CAVEAT
* The contents of the structure pointed to MUST NOT be altered.
*/
string_ty *
str_cat_three(string_ty *s1, string_ty *s2, string_ty *s3)
{
static char *tmp;
static size_t tmplen;
string_ty *s;
size_t length;
length = s1->str_length + s2->str_length + s3->str_length;
if (tmplen < length)
{
tmplen = length;
tmp = mem_change_size(tmp, tmplen);
}
memcpy(tmp, s1->str_text, s1->str_length);
memcpy(tmp + s1->str_length, s2->str_text, s2->str_length);
memcpy
(
tmp + s1->str_length + s2->str_length,
s3->str_text,
s3->str_length
);
s = str_n_from_c(tmp, length);
return s;
}
/*
* NAME
* str_equal - test equality of strings
*
* SYNOPSIS
* int str_equal(string_ty *, string_ty *);
*
* DESCRIPTION
* The str_equal function is used to test if two strings are equal.
*
* RETURNS
* int; zero if the strings are not equal, nonzero if the strings are
* equal.
*
* CAVEAT
* This function is implemented as a macro in strings.h
*/
#ifndef str_equal
int
str_equal(string_ty *s1, string_ty *s2)
{
return (s1 == s2);
}
#endif
/*
* NAME
* str_upcase - upcase a string
*
* SYNOPSIS
* string_ty *str_upcase(string_ty *);
*
* DESCRIPTION
* The str_upcase function is used to form a string which is an upper case
* form of the supplied string.
*
* RETURNS
* string_ty * - a pointer to a string in dynamic memory. Use
* str_free when finished with.
*
* CAVEAT
* The contents of the structure pointed to MUST NOT be altered.
*/
string_ty *
str_upcase(string_ty *s)
{
static char *tmp;
static size_t tmplen;
string_ty *retval;
char *cp1;
char *cp2;
if (tmplen < s->str_length)
{
tmplen = s->str_length;
tmp = mem_change_size(tmp, tmplen);
}
for (cp1 = s->str_text, cp2 = tmp; *cp1; ++cp1, ++cp2)
{
unsigned char c;
c = *cp1;
if (islower(c))
c = toupper(c);
*cp2 = c;
}
retval = str_n_from_c(tmp, s->str_length);
return retval;
}
/*
* NAME
* str_downcase - lowercase string
*
* SYNOPSIS
* string_ty *str_downcase(string_ty *);
*
* DESCRIPTION
* The str_downcase function is used to form a string which is a lowercase
* form of the supplied string.
*
* RETURNS
* string_ty * - a pointer to a string in dynamic memory. Use
* str_free when finished with.
*
* CAVEAT
* The contents of the structure pointed to MUST NOT be altered.
*/
string_ty *
str_downcase(string_ty *s)
{
static char *tmp;
static size_t tmplen;
string_ty *retval;
char *cp1;
char *cp2;
if (tmplen < s->str_length)
{
tmplen = s->str_length;
tmp = mem_change_size(tmp, tmplen);
}
for (cp1 = s->str_text, cp2 = tmp; *cp1; ++cp1, ++cp2)
{
unsigned char c;
c = *cp1;
if (isupper(c))
c = tolower(c);
*cp2 = c;
}
retval = str_n_from_c(tmp, s->str_length);
return retval;
}
/*
* NAME
* str_bool - get boolean value
*
* SYNOPSIS
* int str_bool(string_ty *s);
*
* DESCRIPTION
* The str_bool function is used to determine the boolean value of the
* given string. A "false" result is if the string is empty or
* 0 or blank, and "true" otherwise.
*
* RETURNS
* int: zero to indicate a "false" result, nonzero to indicate a "true"
* result.
*/
int
str_bool(string_ty *s)
{
char *cp;
cp = s->str_text;
while (*cp)
{
if (*cp != ' ' && *cp != '0')
return 1;
++cp;
}
return 0;
}
/*
* NAME
* str_field - extract a field from a string
*
* SYNOPSIS
* string_ty *str_field(string_ty *, char separator, int field_number);
*
* DESCRIPTION
* The str_field functipon is used to erxtract a field from a string.
* Fields of the string are separated by ``separator'' characters.
* Fields are numbered from 0.
*
* RETURNS
* Asking for a field off the end of the string will result in a null
* pointer return. The null string is considered to have one empty field.
*/
string_ty *
str_field(string_ty *s, int sep, int fldnum)
{
char *cp;
char *ep;
cp = s->str_text;
while (fldnum > 0)
{
ep = strchr(cp, sep);
if (!ep)
return 0;
cp = ep + 1;
--fldnum;
}
ep = strchr(cp, sep);
if (ep)
return str_n_from_c(cp, ep - cp);
return str_from_c(cp);
}
/*
* NAME
* str_format - analog of sprintf
*
* SYNOPSIS
* string_ty *str_format(char *, ...);
*
* DESCRIPTION
* The str_format function is used to create new strings
* using a format specification similar to printf(3).
* The "%S" specifier is used to mean a ``string_ty *'' string.
*
* RETURNS
* string_ty * - a pointer to a string in dynamic memory. Use
* str_free when finished with.
*/
string_ty *
str_format(const char *fmt, ...)
{
va_list ap;
string_ty *result;
va_start(ap, fmt);
result = vmprintfes(fmt, ap);
va_end(ap);
return result;
}
string_ty *
str_vformat(const char *fmt, va_list ap)
{
return vmprintfes(fmt, ap);
}
string_ty *
str_substitute(string_ty *a, string_ty *b, string_ty *c)
{
char *cp;
char *ep;
static char *buf;
static size_t buf_max;
size_t len;
cp = c->str_text;
ep = cp + c->str_length;
len = 0;
while (cp < ep)
{
if (memcmp(a->str_text, cp, a->str_length))
{
if (len >= buf_max)
{
buf_max = buf_max * 2 + 16;
buf = mem_change_size(buf, buf_max);
}
buf[len++] = *cp++;
}
else
{
while (len + b->str_length > buf_max)
{
buf_max = buf_max * 2 + 16;
buf = mem_change_size(buf, buf_max);
}
memcpy(buf + len, b->str_text, b->str_length);
len += b->str_length;
cp += a->str_length;
}
}
return str_n_from_c(buf, len);
}
syntax highlighted by Code2HTML, v. 0.9.1