]>
git.ipfire.org Git - thirdparty/sarg.git/blob - dichotomic.c
2 * SARG Squid Analysis Report Generator http://sarg.sourceforge.net
6 * please look at http://sarg.sourceforge.net/donations.php
8 * http://sourceforge.net/projects/sarg/forums/forum/363374
9 * ---------------------------------------------------------------------
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.
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.
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.
27 #include "include/conf.h"
28 #include "include/defs.h"
29 #include "include/dichotomic.h"
32 One key/value pair stored in the sorted list.
34 struct DichotomicItemStruct
42 struct DichotomicStruct
44 //! The array containing the sorted pairs.
45 struct DichotomicItemStruct
*Items
;
46 //! The number of pairs in the array.
48 //! The size of the array.
53 Create an object to store key/value pairs and
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().
61 DichotomicObject
Dichotomic_Create(void)
65 Obj
=malloc(sizeof(*Obj
));
70 memset(Obj
,0,sizeof(*Obj
));
75 Destroy an object created by Dichotomic_Create().
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
82 void Dichotomic_Destroy(DichotomicObject
*ObjPtr
)
87 if (!ObjPtr
|| !*ObjPtr
) return;
92 for (i
=0 ; i
<Obj
->NItems
; i
++)
94 free((void*)Obj
->Items
[i
].Key
);
95 free((void*)Obj
->Items
[i
].Value
);
102 static int Dichotomic_FindKeyPos(DichotomicObject Obj
,const char *key
,bool *Found
)
113 cmp
=strcasecmp(key
,Obj
->Items
[middle
].Key
);
130 Insert a key/value pair into the array.
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.
136 \return \c True if the pair was inserted or \c false if
139 bool Dichotomic_Insert(DichotomicObject Obj
,const char *key
, const char *value
)
145 if (!Obj
) return(false);
148 Position
=Dichotomic_FindKeyPos(Obj
,key
,&Found
);
149 if (Found
) return(false);
154 if (Obj
->NItems
>=Obj
->NAllocated
)
156 struct DichotomicItemStruct
*Items
;
158 Items
=realloc(Obj
->Items
,Obj
->NAllocated
*sizeof(*Items
));
161 debuga(_("Not enough memory to store the key/value pair %s/%s\n"),key
,value
);
167 for (i
=Obj
->NItems
; i
>Position
; i
--)
169 Obj
->Items
[i
].Key
=Obj
->Items
[i
-1].Key
;
170 Obj
->Items
[i
].Value
=Obj
->Items
[i
-1].Value
;
172 Obj
->Items
[Position
].Key
=strdup(key
);
173 Obj
->Items
[Position
].Value
=strdup(value
);
174 if (!Obj
->Items
[Position
].Key
|| !Obj
->Items
[Position
].Value
)
176 debuga(_("Not enough memory to store the key/value pair %s/%s\n"),key
,value
);
185 Search for the value of a key.
187 \param Obj The object created by Dichotomic_Create().
188 \param key The key to search for.
190 \return The value of the key or NULL if the key was not found.
192 const char *Dichotomic_Search(DichotomicObject Obj
,const char *key
)
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
);