- add SOLVER_NOAUTOSET to disable automatic SET deduction
[platform/upstream/libsolv.git] / src / strpool.c
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 = sat_extend_resize(0, totalsize, 1, STRINGSPACE_BLOCK);
28   ss->strings = sat_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   sat_free(ss->strings);
45   sat_free(ss->stringspace);
46   sat_free(ss->stringhashtbl);
47 }
48
49 void
50 stringpool_freehash(Stringpool *ss)
51 {
52   ss->stringhashtbl = sat_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 = sat_extend_resize(0, from->nstrings, sizeof(Offset), STRING_BLOCK);
72   memcpy(ss->strings, from->strings, from->nstrings * sizeof(Offset));
73   ss->stringspace = sat_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;
83   unsigned int hh;
84   Hashmask hashmask;
85   int i;
86   Id id;
87   Hashtable hashtbl;
88
89   // check string
90   if (!str)
91     return STRID_NULL;
92   if (!len)
93     return STRID_EMPTY;
94
95   hashmask = ss->stringhashmask;
96   hashtbl = ss->stringhashtbl;
97
98   // expand hashtable if needed
99   if (ss->nstrings * 2 > hashmask)
100     {
101       sat_free(hashtbl);
102
103       // realloc hash table
104       ss->stringhashmask = hashmask = mkmask(ss->nstrings + STRING_BLOCK);
105       ss->stringhashtbl = hashtbl = (Hashtable)sat_calloc(hashmask + 1, sizeof(Id));
106
107       // rehash all strings into new hashtable
108       for (i = 1; i < ss->nstrings; i++)
109         {
110           h = strhash(ss->stringspace + ss->strings[i]) & hashmask;
111           hh = HASHCHAIN_START;
112           while (hashtbl[h] != 0)  // follow overflow chain
113             h = HASHCHAIN_NEXT(h, hh, hashmask);
114           hashtbl[h] = i;
115         }
116     }
117
118   // compute hash and check for match
119   h = strnhash(str, len) & hashmask;
120   hh = HASHCHAIN_START;
121   while ((id = hashtbl[h]) != 0)  // follow hash overflow chain
122     {
123       // break if string already hashed
124       if(!memcmp(ss->stringspace + ss->strings[id], str, len)
125          && ss->stringspace[ss->strings[id] + len] == 0)
126         break;
127       h = HASHCHAIN_NEXT(h, hh, hashmask);
128     }
129   if (id || !create)    // exit here if string found
130     return id;
131
132   // generate next id and save in table
133   id = ss->nstrings++;
134   hashtbl[h] = id;
135
136   ss->strings = sat_extend(ss->strings, id, 1, sizeof(Offset), STRING_BLOCK);
137   ss->strings[id] = ss->sstrings;       /* we will append to the end */
138
139   // append string to stringspace
140   ss->stringspace = sat_extend(ss->stringspace, ss->sstrings, len + 1, 1, STRINGSPACE_BLOCK);
141   memcpy(ss->stringspace + ss->sstrings, str, len);
142   ss->stringspace[ss->sstrings + len] = 0;
143   ss->sstrings += len + 1;
144   return id;
145 }
146
147 Id
148 stringpool_str2id(Stringpool *ss, const char *str, int create)
149 {
150   if (!str)
151     return STRID_NULL;
152   if (!*str)
153     return STRID_EMPTY;
154   return stringpool_strn2id(ss, str, (unsigned int)strlen(str), create);
155 }
156
157 void
158 stringpool_shrink(Stringpool *ss)
159 {
160   ss->stringspace = sat_extend_resize(ss->stringspace, ss->sstrings, 1, STRINGSPACE_BLOCK);
161   ss->strings = sat_extend_resize(ss->strings, ss->nstrings, sizeof(Offset), STRING_BLOCK);
162 }