satsolver 0.16.3
|
00001 /* 00002 * Copyright (c) 2007, Novell Inc. 00003 * 00004 * This program is licensed under the BSD license, read LICENSE.BSD 00005 * for further information 00006 */ 00007 00008 #include <string.h> 00009 #include "util.h" 00010 #include "strpool.h" 00011 00012 #define STRING_BLOCK 2047 00013 #define STRINGSPACE_BLOCK 65535 00014 00015 void 00016 stringpool_init(Stringpool *ss, const char *strs[]) 00017 { 00018 unsigned totalsize = 0; 00019 unsigned count; 00020 00021 memset(ss, 0, sizeof(*ss)); 00022 // count number and total size of predefined strings 00023 for (count = 0; strs[count]; count++) 00024 totalsize += strlen(strs[count]) + 1; 00025 00026 // alloc appropriate space 00027 ss->stringspace = sat_extend_resize(0, totalsize, 1, STRINGSPACE_BLOCK); 00028 ss->strings = sat_extend_resize(0, count, sizeof(Offset), STRING_BLOCK); 00029 00030 // now copy predefined strings into allocated space 00031 ss->sstrings = 0; 00032 for (count = 0; strs[count]; count++) 00033 { 00034 strcpy(ss->stringspace + ss->sstrings, strs[count]); 00035 ss->strings[count] = ss->sstrings; 00036 ss->sstrings += strlen(strs[count]) + 1; 00037 } 00038 ss->nstrings = count; 00039 } 00040 00041 void 00042 stringpool_free(Stringpool *ss) 00043 { 00044 sat_free(ss->strings); 00045 sat_free(ss->stringspace); 00046 sat_free(ss->stringhashtbl); 00047 } 00048 00049 void 00050 stringpool_freehash(Stringpool *ss) 00051 { 00052 ss->stringhashtbl = sat_free(ss->stringhashtbl); 00053 ss->stringhashmask = 0; 00054 } 00055 00056 void 00057 stringpool_init_empty(Stringpool *ss) 00058 { 00059 const char *emptystrs[] = { 00060 "<NULL>", 00061 "", 00062 0, 00063 }; 00064 stringpool_init(ss, emptystrs); 00065 } 00066 00067 void 00068 stringpool_clone(Stringpool *ss, Stringpool *from) 00069 { 00070 memset(ss, 0, sizeof(*ss)); 00071 ss->strings = sat_extend_resize(0, from->nstrings, sizeof(Offset), STRING_BLOCK); 00072 memcpy(ss->strings, from->strings, from->nstrings * sizeof(Offset)); 00073 ss->stringspace = sat_extend_resize(0, from->sstrings, 1, STRINGSPACE_BLOCK); 00074 memcpy(ss->stringspace, from->stringspace, from->sstrings); 00075 ss->nstrings = from->nstrings; 00076 ss->sstrings = from->sstrings; 00077 } 00078 00079 Id 00080 stringpool_strn2id(Stringpool *ss, const char *str, unsigned int len, int create) 00081 { 00082 Hashval h; 00083 unsigned int hh; 00084 Hashmask hashmask; 00085 int i; 00086 Id id; 00087 Hashtable hashtbl; 00088 00089 // check string 00090 if (!str) 00091 return STRID_NULL; 00092 if (!len) 00093 return STRID_EMPTY; 00094 00095 hashmask = ss->stringhashmask; 00096 hashtbl = ss->stringhashtbl; 00097 00098 // expand hashtable if needed 00099 if (ss->nstrings * 2 > hashmask) 00100 { 00101 sat_free(hashtbl); 00102 00103 // realloc hash table 00104 ss->stringhashmask = hashmask = mkmask(ss->nstrings + STRING_BLOCK); 00105 ss->stringhashtbl = hashtbl = (Hashtable)sat_calloc(hashmask + 1, sizeof(Id)); 00106 00107 // rehash all strings into new hashtable 00108 for (i = 1; i < ss->nstrings; i++) 00109 { 00110 h = strhash(ss->stringspace + ss->strings[i]) & hashmask; 00111 hh = HASHCHAIN_START; 00112 while (hashtbl[h] != 0) // follow overflow chain 00113 h = HASHCHAIN_NEXT(h, hh, hashmask); 00114 hashtbl[h] = i; 00115 } 00116 } 00117 00118 // compute hash and check for match 00119 h = strnhash(str, len) & hashmask; 00120 hh = HASHCHAIN_START; 00121 while ((id = hashtbl[h]) != 0) // follow hash overflow chain 00122 { 00123 // break if string already hashed 00124 if(!memcmp(ss->stringspace + ss->strings[id], str, len) 00125 && ss->stringspace[ss->strings[id] + len] == 0) 00126 break; 00127 h = HASHCHAIN_NEXT(h, hh, hashmask); 00128 } 00129 if (id || !create) // exit here if string found 00130 return id; 00131 00132 // generate next id and save in table 00133 id = ss->nstrings++; 00134 hashtbl[h] = id; 00135 00136 ss->strings = sat_extend(ss->strings, id, 1, sizeof(Offset), STRING_BLOCK); 00137 ss->strings[id] = ss->sstrings; /* we will append to the end */ 00138 00139 // append string to stringspace 00140 ss->stringspace = sat_extend(ss->stringspace, ss->sstrings, len + 1, 1, STRINGSPACE_BLOCK); 00141 memcpy(ss->stringspace + ss->sstrings, str, len); 00142 ss->stringspace[ss->sstrings + len] = 0; 00143 ss->sstrings += len + 1; 00144 return id; 00145 } 00146 00147 Id 00148 stringpool_str2id(Stringpool *ss, const char *str, int create) 00149 { 00150 if (!str) 00151 return STRID_NULL; 00152 if (!*str) 00153 return STRID_EMPTY; 00154 return stringpool_strn2id(ss, str, (unsigned int)strlen(str), create); 00155 } 00156 00157 void 00158 stringpool_shrink(Stringpool *ss) 00159 { 00160 ss->stringspace = sat_extend_resize(ss->stringspace, ss->sstrings, 1, STRINGSPACE_BLOCK); 00161 ss->strings = sat_extend_resize(ss->strings, ss->nstrings, sizeof(Offset), STRING_BLOCK); 00162 }