sarg  2.4.0
About: SARG ia a Squid Analysis Report Generator.
  Fossies Dox: sarg-2.4.0.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

dichotomic.c
Go to the documentation of this file.
1 /*
2  * SARG Squid Analysis Report Generator http://sarg.sourceforge.net
3  * 1998, 2015
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 
35 {
37  const char *Key;
39  const char *Value;
40 };
41 
43 {
47  int NItems;
50 };
51 
62 {
63  DichotomicObject Obj;
64 
65  Obj=malloc(sizeof(*Obj));
66  if (!Obj)
67  {
68  return(NULL);
69  }
70  memset(Obj,0,sizeof(*Obj));
71  return(Obj);
72 }
73 
83 {
84  DichotomicObject Obj;
85  int i;
86 
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;
107 
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);
114  if (!cmp)
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 
139 bool Dichotomic_Insert(DichotomicObject Obj,const char *key, const char *value)
140 {
141  int Position;
142  bool Found;
143  int i;
144 
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;
153 
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  {
161  debuga(__FILE__,__LINE__,_("Not enough memory to store the key/value pair %s/%s\n"),key,value);
162  exit(EXIT_FAILURE);
163  }
164  Obj->Items=Items;
165  }
166 
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  {
176  debuga(__FILE__,__LINE__,_("Not enough memory to store the key/value pair %s/%s\n"),key,value);
177  exit(EXIT_FAILURE);
178  }
179  Obj->NItems++;
180 
181  return(true);
182 }
183 
192 const char *Dichotomic_Search(DichotomicObject Obj,const char *key)
193 {
194  int Position;
195  bool Found;
196 
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 }
Dichotomic_FindKeyPos
static int Dichotomic_FindKeyPos(DichotomicObject Obj, const char *key, bool *Found)
Definition: dichotomic.c:102
debuga
void debuga(const char *File, int Line, const char *msg,...)
Definition: util.c:601
DichotomicStruct::Items
struct DichotomicItemStruct * Items
The array containing the sorted pairs.
Definition: dichotomic.c:45
DichotomicStruct
Definition: dichotomic.c:42
Dichotomic_Search
const char * Dichotomic_Search(DichotomicObject Obj, const char *key)
Definition: dichotomic.c:192
DichotomicItemStruct
Definition: dichotomic.c:34
_
#define _(String)
Definition: conf.h:155
Dichotomic_Destroy
void Dichotomic_Destroy(DichotomicObject *ObjPtr)
Definition: dichotomic.c:82
DichotomicItemStruct::Value
const char * Value
The value.
Definition: dichotomic.c:39
dichotomic.h
DichotomicStruct::NItems
int NItems
The number of pairs in the array.
Definition: dichotomic.c:47
conf.h
Include headers and define global variables. */.
DichotomicItemStruct::Key
const char * Key
The key.
Definition: dichotomic.c:37
Dichotomic_Create
DichotomicObject Dichotomic_Create(void)
Definition: dichotomic.c:61
DichotomicStruct::NAllocated
int NAllocated
The size of the array.
Definition: dichotomic.c:49
defs.h
Declaration of the structures and functions.
Dichotomic_Insert
bool Dichotomic_Insert(DichotomicObject Obj, const char *key, const char *value)
Definition: dichotomic.c:139