147 lines
2.7 KiB
C
147 lines
2.7 KiB
C
/*
|
|
* id.c - Registry of unique and alphabetically sorted identifiers
|
|
*
|
|
* Written 2010 by Werner Almesberger
|
|
* Copyright 2010 Werner Almesberger
|
|
*
|
|
* This program 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 2 of the License, or
|
|
* (at your option) any later version.
|
|
*/
|
|
|
|
|
|
#include <string.h>
|
|
#include <ctype.h>
|
|
|
|
#include "jrb.h"
|
|
|
|
#include "util.h"
|
|
#include "id.h"
|
|
|
|
|
|
static struct id *free_id = NULL;
|
|
|
|
|
|
/* ----- ID comparison (regular string compare) ---------------------------- */
|
|
|
|
|
|
static int do_comp_id(const struct id *a, const struct id *b)
|
|
{
|
|
int len = a->len < b->len ? a->len : b->len;
|
|
int cmp;
|
|
|
|
cmp = memcmp(a->s, b->s, len);
|
|
if (cmp)
|
|
return cmp;
|
|
return a->len < b->len ? -1 : a->len > b->len;
|
|
}
|
|
|
|
|
|
int comp_id(const void *a, const void *b)
|
|
{
|
|
return do_comp_id(a, b);
|
|
}
|
|
|
|
|
|
/* ----- Version comparison ------------------------------------------------ */
|
|
|
|
|
|
static int epoch(const char **s, const struct id *id)
|
|
{
|
|
const char *end = id->s+id->len;
|
|
int n = 0;
|
|
|
|
while (*s != end && isdigit(**s)) {
|
|
n = 10*n+**s-'0';
|
|
(*s)++;
|
|
}
|
|
if (*s == id->s || (*s != end && **s == ':'))
|
|
return n;
|
|
*s = id->s;
|
|
return 0;
|
|
}
|
|
|
|
|
|
int comp_versions(const struct id *va, const struct id *vb)
|
|
{
|
|
int epoch_a = 0, epoch_b = 0;
|
|
const char *a = va->s;
|
|
const char *b = vb->s;
|
|
const char *ea = a+va->len;
|
|
const char *eb = b+vb->len;
|
|
|
|
epoch_a = epoch(&a, va);
|
|
epoch_b = epoch(&b, vb);
|
|
if (epoch_a != epoch_b)
|
|
return epoch_a-epoch_b;
|
|
|
|
while (1) {
|
|
if (a == ea || b == eb)
|
|
return (a != ea)-(b != eb);
|
|
if (isdigit(*a) && isdigit(*b)) {
|
|
int na = 0, nb = 0;
|
|
|
|
while (a != ea && isdigit(*a)) {
|
|
na = na*10+*a-'0';
|
|
a++;
|
|
}
|
|
while (b != eb && isdigit(*b)) {
|
|
nb = nb*10+*b-'0';
|
|
b++;
|
|
}
|
|
if (na == nb)
|
|
continue;
|
|
|
|
return na-nb;
|
|
}
|
|
if (*a > *b)
|
|
return 1;
|
|
if (*a < *b)
|
|
return 1;
|
|
a++;
|
|
b++;
|
|
}
|
|
}
|
|
|
|
|
|
/* ----- Tree maintenance -------------------------------------------------- */
|
|
|
|
|
|
struct tree *make_tree(int (*comp)(const void *a, const void *b))
|
|
{
|
|
struct tree *tree;
|
|
|
|
tree = alloc_type(struct tree);
|
|
tree->comp = comp;
|
|
tree->root = make_jrb();
|
|
return tree;
|
|
}
|
|
|
|
|
|
struct jrb *make_id(struct tree *tree, const char *s, size_t len)
|
|
{
|
|
struct id *id;
|
|
|
|
if (!free_id)
|
|
free_id = alloc_type(struct id);
|
|
id = free_id;
|
|
id->s = s;
|
|
id->len = len;
|
|
id->jrb = jrb_find_or_insert(tree->root, id, NULL, tree->comp);
|
|
if (id->jrb->key == id)
|
|
free_id = NULL;
|
|
return id->jrb;
|
|
}
|
|
|
|
|
|
const struct jrb *find_id(const struct tree *tree, const char *s, size_t len)
|
|
{
|
|
struct id id = {
|
|
.s = s,
|
|
.len = len
|
|
};
|
|
|
|
return jrb_find(tree->root, &id, tree->comp);
|
|
}
|