++struct keyval
++{
++ const char *key;
++ char *val;
++};
++
++static struct bls_entry *entries = NULL;
++
++#define FOR_BLS_ENTRIES(var) FOR_LIST_ELEMENTS (var, entries)
++
++static int bls_add_keyval(struct bls_entry *entry, char *key, char *val)
++{
++ char *k, *v;
++ struct keyval **kvs, *kv;
++ int new_n = entry->nkeyvals + 1;
++
++ kvs = grub_realloc (entry->keyvals, new_n * sizeof (struct keyval *));
++ if (!kvs)
++ return grub_error (GRUB_ERR_OUT_OF_MEMORY,
++ "couldn't find space for BLS entry");
++ entry->keyvals = kvs;
++
++ kv = grub_malloc (sizeof (struct keyval));
++ if (!kv)
++ return grub_error (GRUB_ERR_OUT_OF_MEMORY,
++ "couldn't find space for BLS entry");
++
++ k = grub_strdup (key);
++ if (!k)
++ {
++ grub_free (kv);
++ return grub_error (GRUB_ERR_OUT_OF_MEMORY,
++ "couldn't find space for BLS entry");
++ }
++
++ v = grub_strdup (val);
++ if (!v)
++ {
++ grub_free (k);
++ grub_free (kv);
++ return grub_error (GRUB_ERR_OUT_OF_MEMORY,
++ "couldn't find space for BLS entry");
++ }
++
++ kv->key = k;
++ kv->val = v;
++
++ entry->keyvals[entry->nkeyvals] = kv;
++ grub_dprintf("blscfg", "new keyval at %p:%s:%s\n", entry->keyvals[entry->nkeyvals], k, v);
++ entry->nkeyvals = new_n;
++
++ return 0;
++}
++
++/* Find they value of the key named by keyname. If there are allowed to be
++ * more than one, pass a pointer to an int set to -1 the first time, and pass
++ * the same pointer through each time after, and it'll return them in sorted
++ * order as defined in the BLS fragment file */
++static char *bls_get_val(struct bls_entry *entry, const char *keyname, int *last)
++{
++ int idx, start = 0;
++ struct keyval *kv = NULL;
++
++ if (last)
++ start = *last + 1;
++
++ for (idx = start; idx < entry->nkeyvals; idx++) {
++ kv = entry->keyvals[idx];
++
++ if (!grub_strcmp (keyname, kv->key))
++ break;
++ }
++
++ if (idx == entry->nkeyvals) {
++ if (last)
++ *last = -1;
++ return NULL;
++ }
++
++ if (last)
++ *last = idx;
++
++ return kv->val;
++}
++
++#define goto_return(x) ({ ret = (x); goto finish; })
++
++/* compare alpha and numeric segments of two versions */
++/* return 1: a is newer than b */
++/* 0: a and b are the same version */
++/* -1: b is newer than a */
++static int vercmp(const char * a, const char * b)
++{
++ char oldch1, oldch2;
++ char *abuf, *bbuf;
++ char *str1, *str2;
++ char * one, * two;
++ int rc;
++ int isnum;
++ int ret = 0;
++
++ grub_dprintf("blscfg", "%s comparing %s and %s\n", __func__, a, b);
++ if (!grub_strcmp(a, b))
++ return 0;
++
++ abuf = grub_malloc(grub_strlen(a) + 1);
++ bbuf = grub_malloc(grub_strlen(b) + 1);
++ str1 = abuf;
++ str2 = bbuf;
++ grub_strcpy(str1, a);
++ grub_strcpy(str2, b);
++
++ one = str1;
++ two = str2;
++
++ /* loop through each version segment of str1 and str2 and compare them */
++ while (*one || *two) {
++ while (*one && !grub_isalnum(*one) && *one != '~') one++;
++ while (*two && !grub_isalnum(*two) && *two != '~') two++;
++
++ /* handle the tilde separator, it sorts before everything else */
++ if (*one == '~' || *two == '~') {
++ if (*one != '~') goto_return (1);
++ if (*two != '~') goto_return (-1);
++ one++;
++ two++;
++ continue;
++ }
++
++ /* If we ran to the end of either, we are finished with the loop */
++ if (!(*one && *two)) break;
++
++ str1 = one;
++ str2 = two;
++
++ /* grab first completely alpha or completely numeric segment */
++ /* leave one and two pointing to the start of the alpha or numeric */
++ /* segment and walk str1 and str2 to end of segment */
++ if (grub_isdigit(*str1)) {
++ while (*str1 && grub_isdigit(*str1)) str1++;
++ while (*str2 && grub_isdigit(*str2)) str2++;
++ isnum = 1;
++ } else {
++ while (*str1 && grub_isalpha(*str1)) str1++;
++ while (*str2 && grub_isalpha(*str2)) str2++;
++ isnum = 0;
++ }
++
++ /* save character at the end of the alpha or numeric segment */
++ /* so that they can be restored after the comparison */
++ oldch1 = *str1;
++ *str1 = '\0';
++ oldch2 = *str2;
++ *str2 = '\0';
++
++ /* this cannot happen, as we previously tested to make sure that */
++ /* the first string has a non-null segment */
++ if (one == str1) goto_return(-1); /* arbitrary */
++
++ /* take care of the case where the two version segments are */
++ /* different types: one numeric, the other alpha (i.e. empty) */
++ /* numeric segments are always newer than alpha segments */
++ /* XXX See patch #60884 (and details) from bugzilla #50977. */
++ if (two == str2) goto_return (isnum ? 1 : -1);
++
++ if (isnum) {
++ grub_size_t onelen, twolen;
++ /* this used to be done by converting the digit segments */
++ /* to ints using atoi() - it's changed because long */
++ /* digit segments can overflow an int - this should fix that. */
++
++ /* throw away any leading zeros - it's a number, right? */
++ while (*one == '0') one++;
++ while (*two == '0') two++;
++
++ /* whichever number has more digits wins */
++ onelen = grub_strlen(one);
++ twolen = grub_strlen(two);
++ if (onelen > twolen) goto_return (1);
++ if (twolen > onelen) goto_return (-1);
++ }
++
++ /* grub_strcmp will return which one is greater - even if the two */
++ /* segments are alpha or if they are numeric. don't return */
++ /* if they are equal because there might be more segments to */
++ /* compare */
++ rc = grub_strcmp(one, two);
++ if (rc) goto_return (rc < 1 ? -1 : 1);
++
++ /* restore character that was replaced by null above */
++ *str1 = oldch1;
++ one = str1;
++ *str2 = oldch2;
++ two = str2;
++ }
++
++ /* this catches the case where all numeric and alpha segments have */
++ /* compared identically but the segment sepparating characters were */
++ /* different */
++ if ((!*one) && (!*two)) goto_return (0);
++
++ /* whichever version still has characters left over wins */
++ if (!*one) goto_return (-1); else goto_return (1);
++
++finish:
++ grub_free (abuf);
++ grub_free (bbuf);
++ return ret;
++}
++
++/* returns name/version/release */
++/* NULL string pointer returned if nothing found */
++static void
++split_package_string (char *package_string, char **name,
++ char **version, char **release)
++{
++ char *package_version, *package_release;
++
++ /* Release */
++ package_release = grub_strrchr (package_string, '-');
++
++ if (package_release != NULL)
++ *package_release++ = '\0';
++
++ *release = package_release;
++
++ if (name == NULL)
++ {
++ *version = package_string;
++ }
++ else
++ {
++ /* Version */
++ package_version = grub_strrchr(package_string, '-');
++
++ if (package_version != NULL)
++ *package_version++ = '\0';
++
++ *version = package_version;
++ /* Name */
++ *name = package_string;
++ }
++
++ /* Bubble up non-null values from release to name */
++ if (name != NULL && *name == NULL)
++ {
++ *name = (*version == NULL ? *release : *version);
++ *version = *release;
++ *release = NULL;
++ }
++ if (*version == NULL)
++ {
++ *version = *release;
++ *release = NULL;
++ }
++}
++
++static int
++split_cmp(char *nvr0, char *nvr1, int has_name)
++{
++ int ret = 0;
++ char *name0, *version0, *release0;
++ char *name1, *version1, *release1;
++
++ split_package_string(nvr0, has_name ? &name0 : NULL, &version0, &release0);
++ split_package_string(nvr1, has_name ? &name1 : NULL, &version1, &release1);
++
++ if (has_name)
++ {
++ ret = vercmp(name0 == NULL ? "" : name0,
++ name1 == NULL ? "" : name1);
++ if (ret != 0)
++ return ret;
++ }
++
++ ret = vercmp(version0 == NULL ? "" : version0,
++ version1 == NULL ? "" : version1);
++ if (ret != 0)
++ return ret;
++
++ ret = vercmp(release0 == NULL ? "" : release0,
++ release1 == NULL ? "" : release1);
++ return ret;
++}
++
++/* return 1: e0 is newer than e1 */
++/* 0: e0 and e1 are the same version */
++/* -1: e1 is newer than e0 */
++static int bls_cmp(const struct bls_entry *e0, const struct bls_entry *e1)
++{
++ char *id0, *id1;
++ int r;
++
++ id0 = grub_strdup(e0->filename);
++ id1 = grub_strdup(e1->filename);
++
++ r = split_cmp(id0, id1, 1);
++
++ grub_free(id0);
++ grub_free(id1);
++
++ return r;
++}
++
++static void list_add_tail(struct bls_entry *head, struct bls_entry *item)
++{
++ item->next = head;
++ if (head->prev)
++ head->prev->next = item;
++ item->prev = head->prev;
++ head->prev = item;
++}
++
++static int bls_add_entry(struct bls_entry *entry)
++{
++ struct bls_entry *e, *last = NULL;
++ int rc;
++
++ if (!entries) {
++ grub_dprintf ("blscfg", "Add entry with id \"%s\"\n", entry->filename);
++ entries = entry;
++ return 0;
++ }
++
++ FOR_BLS_ENTRIES(e) {
++ rc = bls_cmp(entry, e);
++
++ if (!rc)
++ return GRUB_ERR_BAD_ARGUMENT;
++
++ if (rc == 1) {
++ grub_dprintf ("blscfg", "Add entry with id \"%s\"\n", entry->filename);
++ list_add_tail (e, entry);
++ if (e == entries) {
++ entries = entry;
++ entry->prev = NULL;
++ }
++ return 0;
++ }
++ last = e;
++ }
++
++ if (last) {
++ grub_dprintf ("blscfg", "Add entry with id \"%s\"\n", entry->filename);
++ last->next = entry;
++ entry->prev = last;
++ }
++
++ return 0;
++}
++
++struct read_entry_info {
++ const char *devid;
++ const char *dirname;
++ grub_file_t file;
++};
++
++static int read_entry (