Luciano Miguel Ferreira Rocha
2006-Oct-03 20:54 UTC
[klibc] strverscmp, scandir, alphasort and versionsort
Hello,
These are implementations of strverscmp, scandir, alphasort and
versionsort, and some test cases for them.
I know these aren't in POSIX, but they're useful, nonetheless, and
someone else might be interested in them.
Regards,
Luciano Rocha
--
lfr
0/0
-------------- next part --------------
/* ----------------------------------------------------------------------- *
*
* Copyright 2006 Luciano Rocha - All Rights Reserved
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or
* sell copies of the Software, and to permit persons to whom
* the Software is furnished to do so, subject to the following
* conditions:
*
* The above copyright notice and this permission notice shall
* be included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*
* ----------------------------------------------------------------------- */
#include <string.h>
#include <ctype.h>
/* strverscmp
from the manual:
What this function does is the following. If both strings are equal,
return 0. Otherwise find the position between two bytes with the prop-
erty that before it both strings are equal, while directly after it
there is a difference. Find the largest consecutive digit strings con-
taining (or starting at, or ending at) this position. If one or both of
these is empty, then return what strcmp() would have returned (numeri-
cal ordering of byte values). Otherwise, compare both digit strings
numerically, where digit strings with one or more leading zeroes are
interpreted as if they have a decimal point in front (so that in par-
ticular digit strings with more leading zeroes come before digit
strings with fewer leading zeroes). Thus, the ordering is 000, 00, 01,
010, 09, 0, 1, 9, 10.
*/
/* shift by ten, to the left */
static unsigned long shift10(unsigned long v, int n)
{
while (n--)
v *= 10;
return v;
}
/* strverscmp */
int strverscmp(const char *s1, const char *s2)
{
int i;
unsigned long v1, v2; /* numerical value */
int l1, l2, /* length of digit strings */
z1, z2, /* length of leading zeroes string */
j1, j2, /* pointers to the beginning of the digit strings */
k1, k2; /* pointers to after the digit strings */
for (i = 0; s1[i] && s1[i] == s2[i]; i++);
if (s1[i] == s2[i])
return 0;
/* s1[i] != s2[i] */
/* s1[i] or s2[i] not in a digit string, normal cmp */
if ((!isdigit(s1[i]) && (i == 0 || !isdigit(s1[i-1])))
|| (!isdigit(s2[i]) && (i == 0 || !isdigit(s2[i-1]))))
return (s1[i] - s2[i]);
/* find v1 */
for (j1 = i - 1; j1 >= 0 && isdigit(s1[j1]); j1--);
j1++; /* j1 now points to first digit */
/* find leading zeros */
for (z1 = j1; s1[z1] == '0'; z1++);
z1 -= j1;
/* find v2 */
for (j2 = i - 1; j2 >= 0 && isdigit(s2[j2]); j2--);
j2++; /* j2 now points to first digit */
/* find leading zeros */
for (z2 = j2; s2[z2] == '0'; z2++);
z2 -= j2;
/* "digit strings with more leading zeroes come before digit strings
* with fewer leading zeroes" */
/* but a "0" has no leading zeroes, get length first */
for (l1 = j1 + z1; isdigit(s1[l1]); l1++);
for (l2 = j2 + z2; isdigit(s2[l2]); l2++);
l1 -= j1 + z1;
l2 -= j2 + z2;
if (z1 == 1 && !l1) {
z1 = 0;
l1 = 1;
}
if (z2 == 1 && !l2) {
z2 = 0;
l2 = 1;
}
if (z1 > z2)
return -1;
if (z1 < z2)
return 1;
v1 = v2 = 0;
/* get v1 */
for (k1 = j1 + z1; isdigit(s1[k1]); k1++)
v1 = v1 * 10 + (s1[k1] - '0');
/* get v2 */
for (k2 = j2 + z2; isdigit(s2[k2]); k2++)
v2 = v2 * 10 + (s2[k2] - '0');
/* leading '0's? shift the difference of length */
if (z1) {
if (l1 > l2)
v2 = shift10(v2, l1 - l2);
else if (l2 > l1)
v1 = shift10(v1, l2 - l1);
}
/* check numerical value */
if (v1 < v2)
return -1;
if (v1 > v2)
return 1;
/* equal. check length, and then check the rest of the
* string */
if (l1 != l2)
return l1 - l2;
return strverscmp(s1 + k1, s2 + k2);
}
-------------- next part --------------
/* ----------------------------------------------------------------------- *
*
* Copyright 2006 Luciano Rocha - All Rights Reserved
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or
* sell copies of the Software, and to permit persons to whom
* the Software is furnished to do so, subject to the following
* conditions:
*
* The above copyright notice and this permission notice shall
* be included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*
* ----------------------------------------------------------------------- */
#include <stdio.h>
#include <dirent.h>
#include <stdlib.h>
#include <string.h>
/* from the manual:
* The scandir() function scans the directory dir, calling
* filter() on each directory entry. Entries for which filter()
* returns non-zero are stored in strings allocated via malloc(),
* sorted using qsort() with the comparison function compar(), and
* collected in array namelist which is allocated via malloc(). If
* filter is NULL, all entries are selected.
*/
int scandir(const char *dir,
struct dirent ***namelist,
int(*filter)(const struct dirent *),
int(*compar)(const void *, const void *))
{
DIR *d;
struct dirent *de, **list;
int nl;
if (!(d = opendir(dir)))
return -1;
list = NULL;
nl = 0;
while ((de = readdir(d))) {
if (filter && !filter(de)) continue;
if (!(list = realloc(list, sizeof(struct dirent *) * (nl+1)))
|| !(list[nl] = malloc(de->d_reclen)))
break;
memcpy(list[nl], de, de->d_reclen);
nl++;
}
closedir(d);
/* error allocating memory? */
if (de) {
while (nl > 0) {
free(list[--nl]);
}
free(list);
nl = -1;
} else {
qsort(list, nl, sizeof(struct dirent *), compar);
*namelist = list;
}
return nl;
}
-------------- next part --------------
/* ----------------------------------------------------------------------- *
*
* Copyright 2006 Luciano Rocha - All Rights Reserved
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or
* sell copies of the Software, and to permit persons to whom
* the Software is furnished to do so, subject to the following
* conditions:
*
* The above copyright notice and this permission notice shall
* be included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*
* ----------------------------------------------------------------------- */
#include <string.h>
#include <dirent.h>
/* sort using strcmp on *d->d_name */
int alphasort(const void *a, const void *b)
{
const struct dirent *const*_a = a, *const*_b = b;
return strcmp((*_a)->d_name, (*_b)->d_name);
}
/* sort using strverscmp on *d->d_name */
int versionsort(const void *a, const void *b)
{
struct dirent *const*_a = a, *const*_b = b;
return strverscmp((*_a)->d_name, (*_b)->d_name);
}
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tests.tar.gz
Type: application/x-tar-gz
Size: 2404 bytes
Desc: not available
Url :
http://www.zytor.com/pipermail/klibc/attachments/20061003/377dca47/attachment.bin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url :
http://www.zytor.com/pipermail/klibc/attachments/20061003/377dca47/attachment-0001.bin
H. Peter Anvin
2006-Oct-03 21:00 UTC
[klibc] strverscmp, scandir, alphasort and versionsort
Luciano Miguel Ferreira Rocha wrote:> Hello, > > These are implementations of strverscmp, scandir, alphasort and > versionsort, and some test cases for them. > > I know these aren't in POSIX, but they're useful, nonetheless, and > someone else might be interested in them. >What's the motivation for including them in klibc? -hpa
Luciano Miguel Ferreira Rocha
2006-Oct-03 22:25 UTC
[klibc] strverscmp, scandir, alphasort and versionsort
qsort blocks and consumes all cpu if nmemb == 0, so new scandir.c, changing:> } else { > qsort(list, nl, sizeof(struct dirent *), compar); > *namelist = list; > }to } else if (nl > 0) { qsort(list, nl, sizeof(struct dirent *), compar); *namelist = list; } -- lfr 0/0 -------------- next part -------------- /* ----------------------------------------------------------------------- * * * Copyright 2006 Luciano Rocha - All Rights Reserved * * Permission is hereby granted, free of charge, to any person * obtaining a copy of this software and associated documentation * files (the "Software"), to deal in the Software without * restriction, including without limitation the rights to use, * copy, modify, merge, publish, distribute, sublicense, and/or * sell copies of the Software, and to permit persons to whom * the Software is furnished to do so, subject to the following * conditions: * * The above copyright notice and this permission notice shall * be included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR * OTHER DEALINGS IN THE SOFTWARE. * * ----------------------------------------------------------------------- */ #include <stdio.h> #include <dirent.h> #include <stdlib.h> #include <string.h> /* from the manual: * The scandir() function scans the directory dir, calling * filter() on each directory entry. Entries for which filter() * returns non-zero are stored in strings allocated via malloc(), * sorted using qsort() with the comparison function compar(), and * collected in array namelist which is allocated via malloc(). If * filter is NULL, all entries are selected. */ int scandir(const char *dir, struct dirent ***namelist, int(*filter)(const struct dirent *), int(*compar)(const void *, const void *)) { DIR *d; struct dirent *de, **list; int nl; if (!(d = opendir(dir))) return -1; list = NULL; nl = 0; while ((de = readdir(d))) { if (filter && !filter(de)) continue; if (!(list = realloc(list, sizeof(struct dirent *) * (nl+1))) || !(list[nl] = malloc(de->d_reclen))) break; memcpy(list[nl], de, de->d_reclen); nl++; } closedir(d); /* error allocating memory? */ if (de) { while (nl > 0) { free(list[--nl]); } free(list); nl = -1; } else if (nl > 0) { qsort(list, nl, sizeof(struct dirent *), compar); *namelist = list; } return nl; } -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 189 bytes Desc: not available Url : http://www.zytor.com/pipermail/klibc/attachments/20061003/21b08555/attachment.bin