1 /* 2 * Copyright (c) 2007, Novell Inc. 3 * 4 * This program is licensed under the BSD license, read LICENSE.BSD 5 * for further information 6 */ 7 8 #include <string.h> 9 #include "util.h" 10 #include "strpool.h" 11 12 #define STRING_BLOCK 2047 13 #define STRINGSPACE_BLOCK 65535 14 15 void 16 stringpool_init(Stringpool *ss, const char *strs[]) 17 { 18 unsigned totalsize = 0; 19 unsigned count; 20 21 memset(ss, 0, sizeof(*ss)); 22 /* count number and total size of predefined strings */ 23 for (count = 0; strs[count]; count++) 24 totalsize += strlen(strs[count]) + 1; 25 26 /* alloc appropriate space */ 27 ss->stringspace = solv_extend_resize(0, totalsize, 1, STRINGSPACE_BLOCK); 28 ss->strings = solv_extend_resize(0, count, sizeof(Offset), STRING_BLOCK); 29 30 /* now copy predefined strings into allocated space */ 31 ss->sstrings = 0; 32 for (count = 0; strs[count]; count++) 33 { 34 strcpy(ss->stringspace + ss->sstrings, strs[count]); 35 ss->strings[count] = ss->sstrings; 36 ss->sstrings += strlen(strs[count]) + 1; 37 } 38 ss->nstrings = count; 39 } 40 41 void 42 stringpool_free(Stringpool *ss) 43 { 44 solv_free(ss->strings); 45 solv_free(ss->stringspace); 46 solv_free(ss->stringhashtbl); 47 } 48 49 void 50 stringpool_freehash(Stringpool *ss) 51 { 52 ss->stringhashtbl = solv_free(ss->stringhashtbl); 53 ss->stringhashmask = 0; 54 } 55 56 void 57 stringpool_init_empty(Stringpool *ss) 58 { 59 const char *emptystrs[] = { 60 "<NULL>", 61 "", 62 0, 63 }; 64 stringpool_init(ss, emptystrs); 65 } 66 67 void 68 stringpool_clone(Stringpool *ss, Stringpool *from) 69 { 70 memset(ss, 0, sizeof(*ss)); 71 ss->strings = solv_extend_resize(0, from->nstrings, sizeof(Offset), STRING_BLOCK); 72 memcpy(ss->strings, from->strings, from->nstrings * sizeof(Offset)); 73 ss->stringspace = solv_extend_resize(0, from->sstrings, 1, STRINGSPACE_BLOCK); 74 memcpy(ss->stringspace, from->stringspace, from->sstrings); 75 ss->nstrings = from->nstrings; 76 ss->sstrings = from->sstrings; 77 } 78 79 Id 80 stringpool_strn2id(Stringpool *ss, const char *str, unsigned int len, int create) 81 { 82 Hashval h, hh, hashmask, oldhashmask; 83 int i; 84 Id id; 85 Hashtable hashtbl; 86 87 if (!str) 88 return STRID_NULL; 89 if (!len) 90 return STRID_EMPTY; 91 92 hashmask = oldhashmask = ss->stringhashmask; 93 hashtbl = ss->stringhashtbl; 94 95 /* expand hashtable if needed */ 96 if (ss->nstrings * 2 > hashmask) 97 { 98 solv_free(hashtbl); 99 100 /* realloc hash table */ 101 ss->stringhashmask = hashmask = mkmask(ss->nstrings + STRING_BLOCK); 102 ss->stringhashtbl = hashtbl = (Hashtable)solv_calloc(hashmask + 1, sizeof(Id)); 103 104 /* rehash all strings into new hashtable */ 105 for (i = 1; i < ss->nstrings; i++) 106 { 107 h = strhash(ss->stringspace + ss->strings[i]) & hashmask; 108 hh = HASHCHAIN_START; 109 while (hashtbl[h] != 0) 110 h = HASHCHAIN_NEXT(h, hh, hashmask); 111 hashtbl[h] = i; 112 } 113 } 114 115 /* compute hash and check for match */ 116 h = strnhash(str, len) & hashmask; 117 hh = HASHCHAIN_START; 118 while ((id = hashtbl[h]) != 0) 119 { 120 if(!memcmp(ss->stringspace + ss->strings[id], str, len) 121 && ss->stringspace[ss->strings[id] + len] == 0) 122 break; 123 h = HASHCHAIN_NEXT(h, hh, hashmask); 124 } 125 if (id || !create) /* exit here if string found */ 126 return id; 127 128 /* this should be a test for a flag that tells us if the 129 * correct blocking is used, but adding a flag would break 130 * the ABI. So we use the existance of the hash area as 131 * indication instead */ 132 if (!oldhashmask) 133 { 134 ss->stringspace = solv_extend_resize(ss->stringspace, ss->sstrings + len + 1, 1, STRINGSPACE_BLOCK); 135 ss->strings = solv_extend_resize(ss->strings, ss->nstrings + 1, sizeof(Offset), STRING_BLOCK); 136 } 137 138 /* generate next id and save in table */ 139 id = ss->nstrings++; 140 hashtbl[h] = id; 141 142 ss->strings = solv_extend(ss->strings, id, 1, sizeof(Offset), STRING_BLOCK); 143 ss->strings[id] = ss->sstrings; /* we will append to the end */ 144 145 /* append string to stringspace */ 146 ss->stringspace = solv_extend(ss->stringspace, ss->sstrings, len + 1, 1, STRINGSPACE_BLOCK); 147 memcpy(ss->stringspace + ss->sstrings, str, len); 148 ss->stringspace[ss->sstrings + len] = 0; 149 ss->sstrings += len + 1; 150 return id; 151 } 152 153 Id 154 stringpool_str2id(Stringpool *ss, const char *str, int create) 155 { 156 if (!str) 157 return STRID_NULL; 158 if (!*str) 159 return STRID_EMPTY; 160 return stringpool_strn2id(ss, str, (unsigned int)strlen(str), create); 161 } 162 163 void 164 stringpool_shrink(Stringpool *ss) 165 { 166 ss->stringspace = solv_extend_resize(ss->stringspace, ss->sstrings, 1, STRINGSPACE_BLOCK); 167 ss->strings = solv_extend_resize(ss->strings, ss->nstrings, sizeof(Offset), STRING_BLOCK); 168 } 169