1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
/* Chrysalide - Outil d'analyse de fichiers binaires
* sort.c - opérations sur des tableaux triés
*
* Copyright (C) 2016 Cyrille Bagard
*
* This file is part of Chrysalide.
*
* Chrysalide is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or
* (at your option) any later version.
*
* Chrysalide is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Foobar. If not, see <http://www.gnu.org/licenses/>.
*/
#include "sort.h"
#include <malloc.h>
#include <string.h>
/******************************************************************************
* *
* Paramètres : key = élément de comparaison à retrouver ou approcher. *
* base = adresse du tableau à parcourir. *
* nmemb = nombre d'éléments présents au total. *
* size = taille de chaque élément du tableau. *
* compar = méthode de comparaison entre éléments. *
* index = indice de cellule d'insertion. *
* *
* Description : Effectue une recherche dichotomique dans un tableau. *
* *
* Retour : true si l'élément visé à été trouvé, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
bool bsearch_index(const void *key, const void *base, size_t nmemb, size_t size, __compar_fn_t compar, size_t *index)
{
bool result; /* Bilan à faire remonter */
size_t lower; /* Borne inférieure de fenêtre */
size_t upper; /* Borne supérieure qde fenêtre*/
size_t idx; /* Indice de cellule analysée */
const void *cell; /* Cellule en question */
int status; /* Bilan d'une comparaison */
if (nmemb == 0)
{
*index = 0;
return false;
}
/* Parcours minimal */
lower = 0;
upper = nmemb;
while (lower < upper)
{
idx = (lower + upper) / 2;
cell = (void *)(((const char *)base) + (idx * size));
status = (*compar)(key, cell);
if (status < 0)
upper = idx;
else if (status > 0)
lower = idx + 1;
else
break;
}
/* Bilan des recherches */
result = (status == 0);
if (status < 0)
*index = idx;
else if (status > 0)
*index = idx + 1;
else
*index = idx;
return result;
}
/******************************************************************************
* *
* Paramètres : base = adresse du tableau à parcourir. *
* nmemb = nombre d'éléments présents au total. [OUT] *
* size = taille de chaque élément du tableau. *
* compar = méthode de comparaison entre éléments. *
* new = nouvel élément à insérer. *
* *
* Description : Ajoute au bon endroit un élément dans un tableau trié. *
* *
* Retour : Nouvel emplacement du tableau agrandi. *
* *
* Remarques : - *
* *
******************************************************************************/
void *qinsert(void *base, size_t *nmemb, size_t size, __compar_fn_t compar, void *new)
{
void *result; /* Tableau trié à retourner */
size_t index; /* Indice du point d'insertion */
bsearch_index(new, base, *nmemb, size, compar, &index);
result = realloc(base, (*nmemb + 1) * size);
if (index < *nmemb)
memmove((char *)result + (index + 1) * size, (char *)result + index * size, (*nmemb - index) * size);
(*nmemb)++;
memcpy((char *)result + index * size, new, size);
return result;
}
|
