Annotation of src/usr.bin/cvs/strtab.c, Revision 1.1
1.1 ! jfb 1: /* $OpenBSD$ */
! 2: /*
! 3: * Copyright (c) 2005 Jean-Francois Brousseau <jfb@openbsd.org>
! 4: * All rights reserved.
! 5: *
! 6: * Redistribution and use in source and binary forms, with or without
! 7: * modification, are permitted provided that the following conditions
! 8: * are met:
! 9: *
! 10: * 1. Redistributions of source code must retain the above copyright
! 11: * notice, this list of conditions and the following disclaimer.
! 12: * 2. The name of the author may not be used to endorse or promote products
! 13: * derived from this software without specific prior written permission.
! 14: *
! 15: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
! 16: * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
! 17: * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
! 18: * THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
! 19: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
! 20: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
! 21: * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
! 22: * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
! 23: * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
! 24: * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
! 25: */
! 26: /*
! 27: * The hash table code uses the 32-bit Fowler/Noll/Vo (FNV-1) hash algorithm
! 28: * for indexing.
! 29: * http://www.isthe.com/chongo/tech/comp/fnv/
! 30: */
! 31:
! 32: #include <sys/types.h>
! 33: #include <sys/queue.h>
! 34:
! 35: #include <errno.h>
! 36: #include <stdio.h>
! 37: #include <stdlib.h>
! 38: #include <unistd.h>
! 39: #include <string.h>
! 40:
! 41: #include "cvs.h"
! 42: #include "log.h"
! 43:
! 44: #define CVS_STRTAB_HASHBITS 8
! 45: #define CVS_STRTAB_NBUCKETS (1 << CVS_STRTAB_HASHBITS)
! 46: #define CVS_STRTAB_FNVPRIME 0x01000193
! 47: #define CVS_STRTAB_FNVINIT 0x811c9dc5
! 48:
! 49: struct cvs_str {
! 50: char *cs_str;
! 51: int cs_ref;
! 52: SLIST_ENTRY(cvs_str) cs_link;
! 53: };
! 54:
! 55: SLIST_HEAD(cvs_slist, cvs_str);
! 56:
! 57: static struct cvs_slist cvs_strtab[CVS_STRTAB_NBUCKETS];
! 58:
! 59:
! 60: static struct cvs_str* cvs_strtab_insert (const char *);
! 61: static struct cvs_str* cvs_strtab_lookup (const char *);
! 62: static u_int32_t cvs_strtab_hash (const char *);
! 63: static void cvs_strtab_free (const char *);
! 64:
! 65:
! 66:
! 67: /*
! 68: * cvs_strdup()
! 69: *
! 70: * Simple interface to the string table.
! 71: */
! 72: char*
! 73: cvs_strdup(const char *s)
! 74: {
! 75: struct cvs_str *csp;
! 76:
! 77: if ((csp = cvs_strtab_lookup(s)) == NULL)
! 78: csp = cvs_strtab_insert(s);
! 79: else
! 80: csp->cs_ref++;
! 81:
! 82: return (csp->cs_str);
! 83: }
! 84:
! 85: /*
! 86: * cvs_strfree()
! 87: */
! 88: void
! 89: cvs_strfree(char *s)
! 90: {
! 91: cvs_strtab_free(s);
! 92: }
! 93:
! 94: /*
! 95: *
! 96: */
! 97: void
! 98: cvs_strtab_init(void)
! 99: {
! 100: int i;
! 101:
! 102: for (i = 0; i < CVS_STRTAB_NBUCKETS; i++)
! 103: SLIST_INIT(&cvs_strtab[i]);
! 104: }
! 105:
! 106: /*
! 107: * cvs_strtab_cleanup()
! 108: *
! 109: */
! 110: void
! 111: cvs_strtab_cleanup(void)
! 112: {
! 113: int i, unfreed;
! 114: struct cvs_str *sp;
! 115:
! 116: unfreed = 0;
! 117: for (i = 0; i < CVS_STRTAB_NBUCKETS; i++) {
! 118: SLIST_FOREACH(sp, &cvs_strtab[i], cs_link)
! 119: unfreed++;
! 120: }
! 121:
! 122: if (unfreed > 0)
! 123: cvs_log(LP_WARN, "%d unfreed string references in string table",
! 124: unfreed);
! 125: }
! 126:
! 127: /*
! 128: * cvs_strtab_insert()
! 129: *
! 130: * Insert the string <str> in the string table.
! 131: */
! 132: static struct cvs_str*
! 133: cvs_strtab_insert(const char *str)
! 134: {
! 135: u_int32_t h;
! 136: struct cvs_str *sp;
! 137:
! 138: if ((sp = (struct cvs_str *)malloc(sizeof(*sp))) == NULL) {
! 139: cvs_log(LP_ERRNO, "failed to insert string `%s'", str);
! 140: return (NULL);
! 141: }
! 142:
! 143: if ((sp->cs_str = strdup(str)) == NULL) {
! 144: free(sp);
! 145: return (NULL);
! 146: }
! 147:
! 148: h = cvs_strtab_hash(str);
! 149:
! 150: SLIST_INSERT_HEAD(&cvs_strtab[h], sp, cs_link);
! 151:
! 152: sp->cs_ref = 1;
! 153: return (sp);
! 154: }
! 155:
! 156: /*
! 157: * cvs_strtab_hash()
! 158: *
! 159: * Generate a hash value from the string <str>.
! 160: * The resulting hash value is bitwise AND'ed with the appropriate mask so
! 161: * the returned index does not go out of the boundaries of the hash table.
! 162: */
! 163: static u_int32_t
! 164: cvs_strtab_hash(const char *str)
! 165: {
! 166: const char *np;
! 167: u_int32_t h;
! 168:
! 169: h = CVS_STRTAB_FNVINIT;
! 170: for (np = str; *np != '\0'; np++) {
! 171: h *= CVS_STRTAB_FNVPRIME;
! 172: h ^= (u_int32_t)*np;
! 173: }
! 174:
! 175: return (h & (CVS_STRTAB_NBUCKETS - 1));
! 176: }
! 177:
! 178: /*
! 179: * cvs_strtab_lookup()
! 180: *
! 181: * Lookup the string <str> in the string table. If the corresponding entry
! 182: * is found, a pointer to the string is returned and the entry's reference
! 183: * count is increased.
! 184: */
! 185: static struct cvs_str*
! 186: cvs_strtab_lookup(const char *str)
! 187: {
! 188: u_int32_t h;
! 189: struct cvs_str *sp;
! 190:
! 191: h = cvs_strtab_hash(str);
! 192:
! 193: SLIST_FOREACH(sp, &(cvs_strtab[h]), cs_link)
! 194: if (strcmp(str, sp->cs_str) == 0) {
! 195: break;
! 196: }
! 197:
! 198: return (sp);
! 199: }
! 200:
! 201: /*
! 202: * cvs_strtab_free()
! 203: *
! 204: * Release a reference to the string <str>. If the reference count reaches 0,
! 205: * the string is removed from the table and freed.
! 206: */
! 207: static void
! 208: cvs_strtab_free(const char *str)
! 209: {
! 210: u_int32_t h;
! 211: struct cvs_str *sp;
! 212:
! 213: if ((sp = cvs_strtab_lookup(str)) == NULL) {
! 214: cvs_log(LP_WARN, "attempt to free unregistered string `%s'",
! 215: str);
! 216: return;
! 217: }
! 218:
! 219: sp->cs_ref--;
! 220: if (sp->cs_ref == 0) {
! 221: /* no more references, free the file */
! 222: h = cvs_file_hashname(sp->cs_str);
! 223:
! 224: SLIST_REMOVE(&(cvs_strtab[h]), sp, cvs_str, cs_link);
! 225: free(sp->cs_str);
! 226: free(sp);
! 227: }
! 228: }
![[BACK]](/icons/back.gif){kind=icon}
Return to strtab.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / cvs