]>
Commit | Line | Data |
---|---|---|
0326d73b FM |
1 | /* |
2 | * SARG Squid Analysis Report Generator http://sarg.sourceforge.net | |
110ce984 | 3 | * 1998, 2015 |
0326d73b FM |
4 | * |
5 | * SARG donations: | |
6 | * please look at http://sarg.sourceforge.net/donations.php | |
7 | * Support: | |
8 | * http://sourceforge.net/projects/sarg/forums/forum/363374 | |
9 | * --------------------------------------------------------------------- | |
10 | * | |
11 | * This program is free software; you can redistribute it and/or modify | |
12 | * it under the terms of the GNU General Public License as published by | |
13 | * the Free Software Foundation; either version 2 of the License, or | |
14 | * (at your option) any later version. | |
15 | * | |
16 | * This program is distributed in the hope that it will be useful, | |
17 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
18 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
19 | * GNU General Public License for more details. | |
20 | * | |
21 | * You should have received a copy of the GNU General Public License | |
22 | * along with this program; if not, write to the Free Software | |
23 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. | |
24 | * | |
25 | */ | |
26 | ||
27 | #include "include/conf.h" | |
28 | #include "include/defs.h" | |
29 | #include "include/dichotomic.h" | |
30 | ||
31 | /*! | |
32 | One key/value pair stored in the sorted list. | |
33 | */ | |
34 | struct DichotomicItemStruct | |
35 | { | |
36 | //! The key. | |
37 | const char *Key; | |
38 | //! The value. | |
39 | const char *Value; | |
40 | }; | |
41 | ||
42 | struct DichotomicStruct | |
43 | { | |
44 | //! The array containing the sorted pairs. | |
45 | struct DichotomicItemStruct *Items; | |
46 | //! The number of pairs in the array. | |
47 | int NItems; | |
48 | //! The size of the array. | |
49 | int NAllocated; | |
50 | }; | |
51 | ||
52 | /*! | |
53 | Create an object to store key/value pairs and | |
54 | retrieve them. | |
55 | ||
56 | \return The object to pass to the functions in this module. | |
57 | The returned pointer is NULL if there is not enough memory | |
58 | to allocate the object. The object must be freed with a call | |
59 | to Dichotomic_Destroy(). | |
60 | */ | |
61 | DichotomicObject Dichotomic_Create(void) | |
62 | { | |
63 | DichotomicObject Obj; | |
bd43d81f | 64 | |
0326d73b FM |
65 | Obj=malloc(sizeof(*Obj)); |
66 | if (!Obj) | |
67 | { | |
68 | return(NULL); | |
69 | } | |
70 | memset(Obj,0,sizeof(*Obj)); | |
71 | return(Obj); | |
72 | } | |
73 | ||
74 | /*! | |
75 | Destroy an object created by Dichotomic_Create(). | |
76 | ||
77 | \param ObjPtr The pointer to the variable containing | |
78 | the object to destroy. The pointer is reset to NULL | |
79 | by this function. It is safe to pass NULL or a NULL | |
80 | pointer. | |
81 | */ | |
82 | void Dichotomic_Destroy(DichotomicObject *ObjPtr) | |
83 | { | |
84 | DichotomicObject Obj; | |
85 | int i; | |
bd43d81f | 86 | |
0326d73b FM |
87 | if (!ObjPtr || !*ObjPtr) return; |
88 | Obj=*ObjPtr; | |
89 | *ObjPtr=NULL; | |
90 | if (Obj->Items) | |
91 | { | |
92 | for (i=0 ; i<Obj->NItems ; i++) | |
93 | { | |
94 | free((void*)Obj->Items[i].Key); | |
95 | free((void*)Obj->Items[i].Value); | |
96 | } | |
97 | free(Obj->Items); | |
98 | } | |
99 | free(Obj); | |
100 | } | |
101 | ||
102 | static int Dichotomic_FindKeyPos(DichotomicObject Obj,const char *key,bool *Found) | |
103 | { | |
104 | int down,up; | |
105 | int middle=0; | |
106 | int cmp=0; | |
bd43d81f | 107 | |
0326d73b FM |
108 | down=0; |
109 | up=Obj->NItems-1; | |
110 | while (up>=down) | |
111 | { | |
112 | middle=(down+up)/2; | |
113 | cmp=strcasecmp(key,Obj->Items[middle].Key); | |
b902df7e | 114 | if (!cmp) |
0326d73b FM |
115 | { |
116 | *Found=true; | |
117 | return(middle); | |
118 | } | |
119 | if (cmp<0) | |
120 | up=middle-1; | |
121 | else | |
122 | down=middle+1; | |
123 | } | |
124 | *Found=false; | |
125 | if (cmp>0) middle++; | |
126 | return(middle); | |
127 | } | |
128 | ||
129 | /*! | |
130 | Insert a key/value pair into the array. | |
131 | ||
132 | \param Obj The object created by Dichotomic_Create(). | |
133 | \param key The key of the pair. | |
134 | \param value The value of the pair. | |
135 | ||
136 | \return \c True if the pair was inserted or \c false if | |
137 | it failed. | |
138 | */ | |
139 | bool Dichotomic_Insert(DichotomicObject Obj,const char *key, const char *value) | |
140 | { | |
141 | int Position; | |
142 | bool Found; | |
143 | int i; | |
bd43d81f | 144 | |
0326d73b FM |
145 | if (!Obj) return(false); |
146 | if (Obj->Items) | |
147 | { | |
148 | Position=Dichotomic_FindKeyPos(Obj,key,&Found); | |
149 | if (Found) return(false); | |
150 | } | |
151 | else | |
152 | Position=0; | |
bd43d81f | 153 | |
0326d73b FM |
154 | if (Obj->NItems>=Obj->NAllocated) |
155 | { | |
156 | struct DichotomicItemStruct *Items; | |
157 | Obj->NAllocated+=25; | |
158 | Items=realloc(Obj->Items,Obj->NAllocated*sizeof(*Items)); | |
159 | if (!Items) | |
160 | { | |
af961877 | 161 | debuga(__FILE__,__LINE__,_("Not enough memory to store the key/value pair %s/%s\n"),key,value); |
0326d73b FM |
162 | exit(EXIT_FAILURE); |
163 | } | |
164 | Obj->Items=Items; | |
165 | } | |
bd43d81f | 166 | |
0326d73b FM |
167 | for (i=Obj->NItems ; i>Position ; i--) |
168 | { | |
169 | Obj->Items[i].Key=Obj->Items[i-1].Key; | |
170 | Obj->Items[i].Value=Obj->Items[i-1].Value; | |
171 | } | |
172 | Obj->Items[Position].Key=strdup(key); | |
173 | Obj->Items[Position].Value=strdup(value); | |
174 | if (!Obj->Items[Position].Key || !Obj->Items[Position].Value) | |
175 | { | |
af961877 | 176 | debuga(__FILE__,__LINE__,_("Not enough memory to store the key/value pair %s/%s\n"),key,value); |
0326d73b FM |
177 | exit(EXIT_FAILURE); |
178 | } | |
179 | Obj->NItems++; | |
bd43d81f | 180 | |
0326d73b FM |
181 | return(true); |
182 | } | |
183 | ||
184 | /*! | |
185 | Search for the value of a key. | |
186 | ||
187 | \param Obj The object created by Dichotomic_Create(). | |
188 | \param key The key to search for. | |
189 | ||
190 | \return The value of the key or NULL if the key was not found. | |
191 | */ | |
192 | const char *Dichotomic_Search(DichotomicObject Obj,const char *key) | |
193 | { | |
194 | int Position; | |
195 | bool Found; | |
bd43d81f | 196 | |
0326d73b FM |
197 | if (!Obj) return(NULL); |
198 | if (Obj->NItems==0 || !Obj->Items) return(NULL); | |
199 | Position=Dichotomic_FindKeyPos(Obj,key,&Found); | |
200 | if (!Found) return(NULL); | |
201 | return(Obj->Items[Position].Value); | |
202 | } |