aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Makemodule.am4
-rw-r--r--lib/dictionary.c428
-rw-r--r--lib/libiniparser.c502
-rw-r--r--lib/libubi.c11
-rw-r--r--lib/list_sort.c246
-rw-r--r--lib/rbtree.c428
6 files changed, 1247 insertions, 372 deletions
diff --git a/lib/Makemodule.am b/lib/Makemodule.am
index 570896b..441532d 100644
--- a/lib/Makemodule.am
+++ b/lib/Makemodule.am
@@ -5,6 +5,10 @@ libmtd_a_SOURCES = \
include/libfec.h \
lib/common.c \
include/common.h \
+ lib/list_sort.c \
+ include/list.h \
+ lib/rbtree.c \
+ include/rbtree.h \
lib/libcrc32.c \
include/crc32.h \
lib/libmtd_legacy.c \
diff --git a/lib/dictionary.c b/lib/dictionary.c
index f4b7468..85dfdc0 100644
--- a/lib/dictionary.c
+++ b/lib/dictionary.c
@@ -1,10 +1,8 @@
/*-------------------------------------------------------------------------*/
/**
- @file dictionary.c
- @author N. Devillard
- @date Sep 2007
- @version $Revision: 1.27 $
- @brief Implements a dictionary for string variables.
+ @file dictionary.c
+ @author N. Devillard
+ @brief Implements a dictionary for string variables.
This module implements a simple dictionary object, i.e. a list
of string/string associations. This object is useful to store e.g.
@@ -12,48 +10,22 @@
*/
/*--------------------------------------------------------------------------*/
-/*
- $Id: dictionary.c,v 1.27 2007-11-23 21:39:18 ndevilla Exp $
- $Revision: 1.27 $
-*/
/*---------------------------------------------------------------------------
- Includes
+ Includes
---------------------------------------------------------------------------*/
#include "dictionary.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
-#include <unistd.h>
-
-/** Maximum value size for integers and doubles. */
-#define MAXVALSZ 1024
/** Minimal allocated number of entries in a dictionary */
-#define DICTMINSZ 128
-
-/** Invalid key token */
-#define DICT_INVALID_KEY ((char*)-1)
+#define DICTMINSZ 128
/*---------------------------------------------------------------------------
- Private functions
+ Private functions
---------------------------------------------------------------------------*/
-/* Doubles the allocated size associated to a pointer */
-/* 'size' is the current allocated size. */
-static void * mem_double(void * ptr, int size)
-{
- void * newptr ;
-
- newptr = calloc(2*size, 1);
- if (newptr==NULL) {
- return NULL ;
- }
- memcpy(newptr, ptr, size);
- free(ptr);
- return newptr ;
-}
-
/*-------------------------------------------------------------------------*/
/**
@brief Duplicate a string
@@ -64,26 +36,71 @@ static void * mem_double(void * ptr, int size)
for systems that do not have it.
*/
/*--------------------------------------------------------------------------*/
-static char * xstrdup(char * s)
+static char * xstrdup(const char * s)
{
char * t ;
+ size_t len ;
if (!s)
return NULL ;
- t = malloc(strlen(s)+1) ;
+
+ len = strlen(s) + 1 ;
+ t = (char*) malloc(len) ;
if (t) {
- strcpy(t,s);
+ memcpy(t, s, len) ;
}
return t ;
}
+/*-------------------------------------------------------------------------*/
+/**
+ @brief Double the size of the dictionary
+ @param d Dictionary to grow
+ @return This function returns non-zero in case of failure
+ */
+/*--------------------------------------------------------------------------*/
+static int dictionary_grow(dictionary * d)
+{
+ char ** new_val ;
+ char ** new_key ;
+ unsigned * new_hash ;
+
+ new_val = (char**) calloc(d->size * 2, sizeof *d->val);
+ new_key = (char**) calloc(d->size * 2, sizeof *d->key);
+ new_hash = (unsigned*) calloc(d->size * 2, sizeof *d->hash);
+ if (!new_val || !new_key || !new_hash) {
+ /* An allocation failed, leave the dictionary unchanged */
+ if (new_val)
+ free(new_val);
+ if (new_key)
+ free(new_key);
+ if (new_hash)
+ free(new_hash);
+ return -1 ;
+ }
+ /* Initialize the newly allocated space */
+ memcpy(new_val, d->val, d->size * sizeof(char *));
+ memcpy(new_key, d->key, d->size * sizeof(char *));
+ memcpy(new_hash, d->hash, d->size * sizeof(unsigned));
+ /* Delete previous data */
+ free(d->val);
+ free(d->key);
+ free(d->hash);
+ /* Actually update the dictionary */
+ d->size *= 2 ;
+ d->val = new_val;
+ d->key = new_key;
+ d->hash = new_hash;
+ return 0 ;
+}
+
/*---------------------------------------------------------------------------
- Function codes
+ Function codes
---------------------------------------------------------------------------*/
/*-------------------------------------------------------------------------*/
/**
- @brief Compute the hash key for a string.
- @param key Character string to use for key.
- @return 1 unsigned int on at least 32 bits.
+ @brief Compute the hash key for a string.
+ @param key Character string to use for key.
+ @return 1 unsigned int on at least 32 bits.
This hash function has been taken from an Article in Dr Dobbs Journal.
This is normally a collision-free function, distributing keys evenly.
@@ -91,86 +108,97 @@ static char * xstrdup(char * s)
by comparing the key itself in last resort.
*/
/*--------------------------------------------------------------------------*/
-unsigned dictionary_hash(char * key)
+unsigned dictionary_hash(const char * key)
{
- int len ;
- unsigned hash ;
- int i ;
-
- len = strlen(key);
- for (hash=0, i=0 ; i<len ; i++) {
- hash += (unsigned)key[i] ;
- hash += (hash<<10);
- hash ^= (hash>>6) ;
- }
- hash += (hash <<3);
- hash ^= (hash >>11);
- hash += (hash <<15);
- return hash ;
+ size_t len ;
+ unsigned hash ;
+ size_t i ;
+
+ if (!key)
+ return 0 ;
+
+ len = strlen(key);
+ for (hash=0, i=0 ; i<len ; i++) {
+ hash += (unsigned)key[i] ;
+ hash += (hash<<10);
+ hash ^= (hash>>6) ;
+ }
+ hash += (hash <<3);
+ hash ^= (hash >>11);
+ hash += (hash <<15);
+ return hash ;
}
/*-------------------------------------------------------------------------*/
/**
- @brief Create a new dictionary object.
- @param size Optional initial size of the dictionary.
- @return 1 newly allocated dictionary objet.
+ @brief Create a new dictionary object.
+ @param size Optional initial size of the dictionary.
+ @return 1 newly allocated dictionary object.
This function allocates a new dictionary object of given size and returns
it. If you do not know in advance (roughly) the number of entries in the
dictionary, give size=0.
*/
-/*--------------------------------------------------------------------------*/
-dictionary * dictionary_new(int size)
+/*-------------------------------------------------------------------------*/
+dictionary * dictionary_new(size_t size)
{
- dictionary * d ;
-
- /* If no size was specified, allocate space for DICTMINSZ */
- if (size<DICTMINSZ) size=DICTMINSZ ;
-
- if (!(d = (dictionary *)calloc(1, sizeof(dictionary)))) {
- return NULL;
- }
- d->size = size ;
- d->val = (char **)calloc(size, sizeof(char*));
- d->key = (char **)calloc(size, sizeof(char*));
- d->hash = (unsigned int *)calloc(size, sizeof(unsigned));
- return d ;
+ dictionary * d ;
+
+ /* If no size was specified, allocate space for DICTMINSZ */
+ if (size<DICTMINSZ) size=DICTMINSZ ;
+
+ d = (dictionary*) calloc(1, sizeof *d) ;
+
+ if (d) {
+ d->size = size ;
+ d->val = (char**) calloc(size, sizeof *d->val);
+ d->key = (char**) calloc(size, sizeof *d->key);
+ d->hash = (unsigned*) calloc(size, sizeof *d->hash);
+ if (!d->size || !d->val || !d->hash) {
+ free((void *) d->size);
+ free((void *) d->val);
+ free((void *) d->hash);
+ free(d);
+ d = NULL;
+ }
+ }
+ return d ;
}
/*-------------------------------------------------------------------------*/
/**
- @brief Delete a dictionary object
- @param d dictionary object to deallocate.
- @return void
+ @brief Delete a dictionary object
+ @param d dictionary object to deallocate.
+ @return void
Deallocate a dictionary object and all memory associated to it.
*/
/*--------------------------------------------------------------------------*/
void dictionary_del(dictionary * d)
{
- int i ;
-
- if (d==NULL) return ;
- for (i=0 ; i<d->size ; i++) {
- if (d->key[i]!=NULL)
- free(d->key[i]);
- if (d->val[i]!=NULL)
- free(d->val[i]);
- }
- free(d->val);
- free(d->key);
- free(d->hash);
- free(d);
- return ;
+ size_t i ;
+
+ if (d==NULL) return ;
+ for (i=0 ; i<d->size ; i++) {
+ if (d->key[i]!=NULL)
+ free(d->key[i]);
+ if (d->val[i]!=NULL)
+ free(d->val[i]);
+ }
+ free(d->val);
+ free(d->key);
+ free(d->hash);
+ free(d);
+ return ;
}
/*-------------------------------------------------------------------------*/
/**
- @brief Get a value from a dictionary.
- @param d dictionary object to search.
- @param key Key to look for in the dictionary.
+ @brief Get a value from a dictionary.
+ @param d dictionary object to search.
+ @param key Key to look for in the dictionary.
@param def Default value to return if key not found.
- @return 1 pointer to internally allocated character string.
+ @return 1 pointer to internally allocated character string.
This function locates a key in a dictionary and returns a pointer to its
value, or the passed 'def' pointer if no such key can be found in
@@ -178,24 +206,27 @@ void dictionary_del(dictionary * d)
dictionary object, you should not try to free it or modify it.
*/
/*--------------------------------------------------------------------------*/
-char * dictionary_get(dictionary * d, char * key, char * def)
+const char * dictionary_get(const dictionary * d, const char * key, const char * def)
{
- unsigned hash ;
- int i ;
+ unsigned hash ;
+ size_t i ;
- hash = dictionary_hash(key);
- for (i=0 ; i<d->size ; i++) {
+ if(d == NULL || key == NULL)
+ return def ;
+
+ hash = dictionary_hash(key);
+ for (i=0 ; i<d->size ; i++) {
if (d->key[i]==NULL)
continue ;
/* Compare hash */
- if (hash==d->hash[i]) {
+ if (hash==d->hash[i]) {
/* Compare string, to avoid hash collisions */
if (!strcmp(key, d->key[i])) {
- return d->val[i] ;
- }
- }
- }
- return def ;
+ return d->val[i] ;
+ }
+ }
+ }
+ return def ;
}
/*-------------------------------------------------------------------------*/
@@ -224,96 +255,87 @@ char * dictionary_get(dictionary * d, char * key, char * def)
This function returns non-zero in case of failure.
*/
/*--------------------------------------------------------------------------*/
-int dictionary_set(dictionary * d, char * key, char * val)
+int dictionary_set(dictionary * d, const char * key, const char * val)
{
- int i ;
- unsigned hash ;
+ size_t i ;
+ unsigned hash ;
- if (d==NULL || key==NULL) return -1 ;
+ if (d==NULL || key==NULL) return -1 ;
- /* Compute hash for this key */
- hash = dictionary_hash(key) ;
- /* Find if value is already in dictionary */
- if (d->n>0) {
- for (i=0 ; i<d->size ; i++) {
+ /* Compute hash for this key */
+ hash = dictionary_hash(key) ;
+ /* Find if value is already in dictionary */
+ if (d->n>0) {
+ for (i=0 ; i<d->size ; i++) {
if (d->key[i]==NULL)
continue ;
- if (hash==d->hash[i]) { /* Same hash value */
- if (!strcmp(key, d->key[i])) { /* Same key */
- /* Found a value: modify and return */
- if (d->val[i]!=NULL)
- free(d->val[i]);
- d->val[i] = val ? xstrdup(val) : NULL ;
+ if (hash==d->hash[i]) { /* Same hash value */
+ if (!strcmp(key, d->key[i])) { /* Same key */
+ /* Found a value: modify and return */
+ if (d->val[i]!=NULL)
+ free(d->val[i]);
+ d->val[i] = (val ? xstrdup(val) : NULL);
/* Value has been modified: return */
- return 0 ;
- }
- }
- }
- }
- /* Add a new value */
- /* See if dictionary needs to grow */
- if (d->n==d->size) {
-
- /* Reached maximum size: reallocate dictionary */
- d->val = (char **)mem_double(d->val, d->size * sizeof(char*)) ;
- d->key = (char **)mem_double(d->key, d->size * sizeof(char*)) ;
- d->hash = (unsigned int *)mem_double(d->hash, d->size * sizeof(unsigned)) ;
- if ((d->val==NULL) || (d->key==NULL) || (d->hash==NULL)) {
- /* Cannot grow dictionary */
- return -1 ;
+ return 0 ;
+ }
+ }
}
- /* Double size */
- d->size *= 2 ;
- }
+ }
+ /* Add a new value */
+ /* See if dictionary needs to grow */
+ if (d->n==d->size) {
+ /* Reached maximum size: reallocate dictionary */
+ if (dictionary_grow(d) != 0)
+ return -1;
+ }
- /* Insert key in the first empty slot */
- for (i=0 ; i<d->size ; i++) {
- if (d->key[i]==NULL) {
- /* Add key here */
- break ;
- }
+ /* Insert key in the first empty slot. Start at d->n and wrap at
+ d->size. Because d->n < d->size this will necessarily
+ terminate. */
+ for (i=d->n ; d->key[i] ; ) {
+ if(++i == d->size) i = 0;
}
- /* Copy key */
- d->key[i] = xstrdup(key);
- d->val[i] = val ? xstrdup(val) : NULL ;
- d->hash[i] = hash;
- d->n ++ ;
- return 0 ;
+ /* Copy key */
+ d->key[i] = xstrdup(key);
+ d->val[i] = (val ? xstrdup(val) : NULL) ;
+ d->hash[i] = hash;
+ d->n ++ ;
+ return 0 ;
}
/*-------------------------------------------------------------------------*/
/**
- @brief Delete a key in a dictionary
- @param d dictionary object to modify.
- @param key Key to remove.
+ @brief Delete a key in a dictionary
+ @param d dictionary object to modify.
+ @param key Key to remove.
@return void
This function deletes a key in a dictionary. Nothing is done if the
key cannot be found.
*/
/*--------------------------------------------------------------------------*/
-void dictionary_unset(dictionary * d, char * key)
+void dictionary_unset(dictionary * d, const char * key)
{
- unsigned hash ;
- int i ;
+ unsigned hash ;
+ size_t i ;
- if (key == NULL) {
- return;
- }
+ if (key == NULL || d == NULL) {
+ return;
+ }
- hash = dictionary_hash(key);
- for (i=0 ; i<d->size ; i++) {
+ hash = dictionary_hash(key);
+ for (i=0 ; i<d->size ; i++) {
if (d->key[i]==NULL)
continue ;
/* Compare hash */
- if (hash==d->hash[i]) {
+ if (hash==d->hash[i]) {
/* Compare string, to avoid hash collisions */
if (!strcmp(key, d->key[i])) {
/* Found key */
break ;
- }
- }
- }
+ }
+ }
+ }
if (i>=d->size)
/* Key not found */
return ;
@@ -331,75 +353,31 @@ void dictionary_unset(dictionary * d, char * key)
/*-------------------------------------------------------------------------*/
/**
- @brief Dump a dictionary to an opened file pointer.
- @param d Dictionary to dump
- @param f Opened file pointer.
- @return void
+ @brief Dump a dictionary to an opened file pointer.
+ @param d Dictionary to dump
+ @param f Opened file pointer.
+ @return void
Dumps a dictionary onto an opened file pointer. Key pairs are printed out
as @c [Key]=[Value], one per line. It is Ok to provide stdout or stderr as
output file pointers.
*/
/*--------------------------------------------------------------------------*/
-void dictionary_dump(dictionary * d, FILE * out)
+void dictionary_dump(const dictionary * d, FILE * out)
{
- int i ;
-
- if (d==NULL || out==NULL) return ;
- if (d->n<1) {
- fprintf(out, "empty dictionary\n");
- return ;
- }
- for (i=0 ; i<d->size ; i++) {
+ size_t i ;
+
+ if (d==NULL || out==NULL) return ;
+ if (d->n<1) {
+ fprintf(out, "empty dictionary\n");
+ return ;
+ }
+ for (i=0 ; i<d->size ; i++) {
if (d->key[i]) {
fprintf(out, "%20s\t[%s]\n",
d->key[i],
d->val[i] ? d->val[i] : "UNDEF");
}
- }
- return ;
-}
-
-
-/* Test code */
-#ifdef TESTDIC
-#define NVALS 20000
-int main(int argc, char *argv[])
-{
- dictionary * d ;
- char * val ;
- int i ;
- char cval[90] ;
-
- /* Allocate dictionary */
- printf("allocating...\n");
- d = dictionary_new(0);
-
- /* Set values in dictionary */
- printf("setting %d values...\n", NVALS);
- for (i=0 ; i<NVALS ; i++) {
- sprintf(cval, "%04d", i);
- dictionary_set(d, cval, "salut");
- }
- printf("getting %d values...\n", NVALS);
- for (i=0 ; i<NVALS ; i++) {
- sprintf(cval, "%04d", i);
- val = dictionary_get(d, cval, DICT_INVALID_KEY);
- if (val==DICT_INVALID_KEY) {
- printf("cannot get value for key [%s]\n", cval);
- }
- }
- printf("unsetting %d values...\n", NVALS);
- for (i=0 ; i<NVALS ; i++) {
- sprintf(cval, "%04d", i);
- dictionary_unset(d, cval);
- }
- if (d->n != 0) {
- printf("error deleting values\n");
}
- printf("deallocating...\n");
- dictionary_del(d);
- return 0 ;
+ return ;
}
-#endif
-/* vim: set ts=4 et sw=4 tw=75 */
diff --git a/lib/libiniparser.c b/lib/libiniparser.c
index a6ddcc7..4b21b34 100644
--- a/lib/libiniparser.c
+++ b/lib/libiniparser.c
@@ -3,19 +3,16 @@
/**
@file iniparser.c
@author N. Devillard
- @date Sep 2007
- @version 3.0
@brief Parser for ini files.
*/
/*--------------------------------------------------------------------------*/
-/*
- $Id: iniparser.c,v 2.18 2008-01-03 18:35:39 ndevilla Exp $
- $Revision: 2.18 $
- $Date: 2008-01-03 18:35:39 $
-*/
/*---------------------------- Includes ------------------------------------*/
#include <ctype.h>
-#include <libiniparser.h>
+#include <stdarg.h>
+#include <stdlib.h>
+#include <string.h>
+#include <inttypes.h>
+#include "libiniparser.h"
/*---------------------------- Defines -------------------------------------*/
#define ASCIILINESZ (1024)
@@ -38,68 +35,101 @@ typedef enum _line_status_ {
/*-------------------------------------------------------------------------*/
/**
- @brief Convert a string to lowercase.
- @param s String to convert.
- @return ptr to statically allocated string.
-
- This function returns a pointer to a statically allocated string
- containing a lowercased version of the input string. Do not free
- or modify the returned string! Since the returned string is statically
- allocated, it will be modified at each function call (not re-entrant).
+ @brief Convert a string to lowercase.
+ @param in String to convert.
+ @param out Output buffer.
+ @param len Size of the out buffer.
+ @return ptr to the out buffer or NULL if an error occured.
+
+ This function convert a string into lowercase.
+ At most len - 1 elements of the input string will be converted.
*/
/*--------------------------------------------------------------------------*/
-static char * strlwc(const char * s)
+static const char * strlwc(const char * in, char *out, unsigned len)
{
- static char l[ASCIILINESZ+1];
- int i ;
+ unsigned i ;
- if (s==NULL) return NULL ;
- memset(l, 0, ASCIILINESZ+1);
+ if (in==NULL || out == NULL || len==0) return NULL ;
i=0 ;
- while (s[i] && i<ASCIILINESZ) {
- l[i] = (char)tolower((int)s[i]);
+ while (in[i] != '\0' && i < len-1) {
+ out[i] = (char)tolower((int)in[i]);
i++ ;
}
- l[ASCIILINESZ]=(char)0;
- return l ;
+ out[i] = '\0';
+ return out ;
+}
+
+/*-------------------------------------------------------------------------*/
+/**
+ @brief Duplicate a string
+ @param s String to duplicate
+ @return Pointer to a newly allocated string, to be freed with free()
+
+ This is a replacement for strdup(). This implementation is provided
+ for systems that do not have it.
+ */
+/*--------------------------------------------------------------------------*/
+static char * xstrdup(const char * s)
+{
+ char * t ;
+ size_t len ;
+ if (!s)
+ return NULL ;
+
+ len = strlen(s) + 1 ;
+ t = (char*) malloc(len) ;
+ if (t) {
+ memcpy(t, s, len) ;
+ }
+ return t ;
}
/*-------------------------------------------------------------------------*/
/**
- @brief Remove blanks at the beginning and the end of a string.
- @param s String to parse.
- @return ptr to statically allocated string.
-
- This function returns a pointer to a statically allocated string,
- which is identical to the input string, except that all blank
- characters at the end and the beg. of the string have been removed.
- Do not free or modify the returned string! Since the returned string
- is statically allocated, it will be modified at each function call
- (not re-entrant).
+ @brief Remove blanks at the beginning and the end of a string.
+ @param str String to parse and alter.
+ @return unsigned New size of the string.
*/
/*--------------------------------------------------------------------------*/
-static char * strstrip(char * s)
+static unsigned strstrip(char * s)
{
- static char l[ASCIILINESZ+1];
- char * last ;
-
- if (s==NULL) return NULL ;
-
- while (isspace((int)*s) && *s) s++;
- memset(l, 0, ASCIILINESZ+1);
- strcpy(l, s);
- last = l + strlen(l);
- while (last > l) {
- if (!isspace((int)*(last-1)))
- break ;
- last -- ;
- }
- *last = (char)0;
- return (char*)l ;
+ char *last = NULL ;
+ char *dest = s;
+
+ if (s==NULL) return 0;
+
+ last = s + strlen(s);
+ while (isspace((int)*s) && *s) s++;
+ while (last > s) {
+ if (!isspace((int)*(last-1)))
+ break ;
+ last -- ;
+ }
+ *last = (char)0;
+
+ memmove(dest,s,last - s + 1);
+ return last - s;
}
/*-------------------------------------------------------------------------*/
/**
+ @brief Default error callback for iniparser: wraps `fprintf(stderr, ...)`.
+ */
+/*--------------------------------------------------------------------------*/
+static int default_error_callback(const char *format, ...)
+{
+ int ret;
+ va_list argptr;
+ va_start(argptr, format);
+ ret = vfprintf(stderr, format, argptr);
+ va_end(argptr);
+ return ret;
+}
+
+static int (*iniparser_error_callback)(const char*, ...) = default_error_callback;
+
+/*-------------------------------------------------------------------------*/
+/**
@brief Get number of sections in a dictionary
@param d Dictionary to examine
@return int Number of sections found in dictionary
@@ -116,9 +146,9 @@ static char * strstrip(char * s)
This function returns -1 in case of error.
*/
/*--------------------------------------------------------------------------*/
-int iniparser_getnsec(dictionary * d)
+int iniparser_getnsec(const dictionary * d)
{
- int i ;
+ size_t i ;
int nsec ;
if (d==NULL) return -1 ;
@@ -147,9 +177,9 @@ int iniparser_getnsec(dictionary * d)
This function returns NULL in case of error.
*/
/*--------------------------------------------------------------------------*/
-char * iniparser_getsecname(dictionary * d, int n)
+const char * iniparser_getsecname(const dictionary * d, int n)
{
- int i ;
+ size_t i ;
int foundsec ;
if (d==NULL || n<0) return NULL ;
@@ -182,9 +212,9 @@ char * iniparser_getsecname(dictionary * d, int n)
purposes mostly.
*/
/*--------------------------------------------------------------------------*/
-void iniparser_dump(dictionary * d, FILE * f)
+void iniparser_dump(const dictionary * d, FILE * f)
{
- int i ;
+ size_t i ;
if (d==NULL || f==NULL) return ;
for (i=0 ; i<d->size ; i++) {
@@ -199,6 +229,26 @@ void iniparser_dump(dictionary * d, FILE * f)
return ;
}
+static void escape_value(char *escaped, char *value) {
+ char c;
+ int v = 0;
+ int e = 0;
+
+ if(!escaped || !value)
+ return;
+
+ while((c = value[v]) != '\0') {
+ if(c == '\\' || c == '"') {
+ escaped[e] = '\\';
+ e++;
+ }
+ escaped[e] = c;
+ v++;
+ e++;
+ }
+ escaped[e] = '\0';
+}
+
/*-------------------------------------------------------------------------*/
/**
@brief Save a dictionary to a loadable ini file
@@ -210,13 +260,12 @@ void iniparser_dump(dictionary * d, FILE * f)
It is Ok to specify @c stderr or @c stdout as output files.
*/
/*--------------------------------------------------------------------------*/
-void iniparser_dump_ini(dictionary * d, FILE * f)
+void iniparser_dump_ini(const dictionary * d, FILE * f)
{
- int i, j ;
- char keym[ASCIILINESZ+1];
- int nsec ;
- char * secname ;
- int seclen ;
+ size_t i ;
+ size_t nsec ;
+ const char * secname ;
+ char escaped[ASCIILINESZ+1] = "";
if (d==NULL || f==NULL) return ;
@@ -226,24 +275,50 @@ void iniparser_dump_ini(dictionary * d, FILE * f)
for (i=0 ; i<d->size ; i++) {
if (d->key[i]==NULL)
continue ;
- fprintf(f, "%s = %s\n", d->key[i], d->val[i]);
+ escape_value(escaped, d->val[i]);
+ fprintf(f, "%s = \"%s\"\n", d->key[i], escaped);
}
return ;
}
for (i=0 ; i<nsec ; i++) {
secname = iniparser_getsecname(d, i) ;
- seclen = (int)strlen(secname);
- fprintf(f, "\n[%s]\n", secname);
- sprintf(keym, "%s:", secname);
- for (j=0 ; j<d->size ; j++) {
- if (d->key[j]==NULL)
- continue ;
- if (!strncmp(d->key[j], keym, seclen+1)) {
- fprintf(f,
- "%-30s = %s\n",
- d->key[j]+seclen+1,
- d->val[j] ? d->val[j] : "");
- }
+ iniparser_dumpsection_ini(d, secname, f);
+ }
+ fprintf(f, "\n");
+ return ;
+}
+
+/*-------------------------------------------------------------------------*/
+/**
+ @brief Save a dictionary section to a loadable ini file
+ @param d Dictionary to dump
+ @param s Section name of dictionary to dump
+ @param f Opened file pointer to dump to
+ @return void
+
+ This function dumps a given section of a given dictionary into a loadable ini
+ file. It is Ok to specify @c stderr or @c stdout as output files.
+ */
+/*--------------------------------------------------------------------------*/
+void iniparser_dumpsection_ini(const dictionary * d, const char * s, FILE * f)
+{
+ size_t j ;
+ char keym[ASCIILINESZ+1];
+ int seclen ;
+ char escaped[ASCIILINESZ+1] = "";
+
+ if (d==NULL || f==NULL) return ;
+ if (! iniparser_find_entry(d, s)) return ;
+
+ seclen = (int)strlen(s);
+ fprintf(f, "\n[%s]\n", s);
+ sprintf(keym, "%s:", s);
+ for (j=0 ; j<d->size ; j++) {
+ if (d->key[j]==NULL)
+ continue ;
+ if (!strncmp(d->key[j], keym, seclen+1)) {
+ escape_value(escaped, d->val[j]);
+ fprintf(f, "%-30s = \"%s\"\n", d->key[j]+seclen+1, escaped);
}
}
fprintf(f, "\n");
@@ -265,26 +340,27 @@ void iniparser_dump_ini(dictionary * d, FILE * f)
the dictionary, do not free or modify it.
*/
/*--------------------------------------------------------------------------*/
-char * iniparser_getstring(dictionary * d, const char * key, char * def)
+const char * iniparser_getstring(const dictionary * d, const char * key, const char * def)
{
- char * lc_key ;
- char * sval ;
+ const char * lc_key ;
+ const char * sval ;
+ char tmp_str[ASCIILINESZ+1];
if (d==NULL || key==NULL)
return def ;
- lc_key = strlwc(key);
+ lc_key = strlwc(key, tmp_str, sizeof(tmp_str));
sval = dictionary_get(d, lc_key, def);
return sval ;
}
/*-------------------------------------------------------------------------*/
/**
- @brief Get the string associated to a key, convert to an int
+ @brief Get the string associated to a key, convert to an long int
@param d Dictionary to search
@param key Key string to look for
@param notfound Value to return in case of error
- @return integer
+ @return long integer
This function queries a dictionary for a key. A key as read from an
ini file is given as "section:key". If the key cannot be found,
@@ -305,13 +381,65 @@ char * iniparser_getstring(dictionary * d, const char * key, char * def)
Credits: Thanks to A. Becker for suggesting strtol()
*/
/*--------------------------------------------------------------------------*/
-int iniparser_getint(dictionary * d, const char * key, int notfound)
+long int iniparser_getlongint(const dictionary * d, const char * key, long int notfound)
{
- char * str ;
+ const char * str ;
str = iniparser_getstring(d, key, INI_INVALID_KEY);
- if (str==INI_INVALID_KEY) return notfound ;
- return (int)strtol(str, NULL, 0);
+ if (str==NULL || str==INI_INVALID_KEY) return notfound ;
+ return strtol(str, NULL, 0);
+}
+
+int64_t iniparser_getint64(const dictionary * d, const char * key, int64_t notfound)
+{
+ const char * str ;
+
+ str = iniparser_getstring(d, key, INI_INVALID_KEY);
+ if (str==NULL || str==INI_INVALID_KEY) return notfound ;
+ return strtoimax(str, NULL, 0);
+}
+
+uint64_t iniparser_getuint64(const dictionary * d, const char * key, uint64_t notfound)
+{
+ const char * str ;
+
+ str = iniparser_getstring(d, key, INI_INVALID_KEY);
+ if (str==NULL || str==INI_INVALID_KEY) return notfound ;
+ return strtoumax(str, NULL, 0);
+}
+
+
+
+/*-------------------------------------------------------------------------*/
+/**
+ @brief Get the string associated to a key, convert to an int
+ @param d Dictionary to search
+ @param key Key string to look for
+ @param notfound Value to return in case of error
+ @return integer
+
+ This function queries a dictionary for a key. A key as read from an
+ ini file is given as "section:key". If the key cannot be found,
+ the notfound value is returned.
+
+ Supported values for integers include the usual C notation
+ so decimal, octal (starting with 0) and hexadecimal (starting with 0x)
+ are supported. Examples:
+
+ "42" -> 42
+ "042" -> 34 (octal -> decimal)
+ "0x42" -> 66 (hexa -> decimal)
+
+ Warning: the conversion may overflow in various ways. Conversion is
+ totally outsourced to strtol(), see the associated man page for overflow
+ handling.
+
+ Credits: Thanks to A. Becker for suggesting strtol()
+ */
+/*--------------------------------------------------------------------------*/
+int iniparser_getint(const dictionary * d, const char * key, int notfound)
+{
+ return (int)iniparser_getlongint(d, key, notfound);
}
/*-------------------------------------------------------------------------*/
@@ -346,13 +474,13 @@ int iniparser_getint(dictionary * d, const char * key, int notfound)
necessarily have to be 0 or 1.
*/
/*--------------------------------------------------------------------------*/
-int iniparser_getboolean(dictionary * d, const char * key, int notfound)
+int iniparser_getboolean(const dictionary * d, const char * key, int notfound)
{
- char * c ;
- int ret ;
+ int ret ;
+ const char * c ;
c = iniparser_getstring(d, key, INI_INVALID_KEY);
- if (c==INI_INVALID_KEY) return notfound ;
+ if (c==NULL || c==INI_INVALID_KEY) return notfound ;
if (c[0]=='y' || c[0]=='Y' || c[0]=='1' || c[0]=='t' || c[0]=='T') {
ret = 1 ;
} else if (c[0]=='n' || c[0]=='N' || c[0]=='0' || c[0]=='f' || c[0]=='F') {
@@ -375,10 +503,7 @@ int iniparser_getboolean(dictionary * d, const char * key, int notfound)
of querying for the presence of sections in a dictionary.
*/
/*--------------------------------------------------------------------------*/
-int iniparser_find_entry(
- dictionary * ini,
- char * entry
-)
+int iniparser_find_entry(const dictionary * ini, const char * entry)
{
int found=0 ;
if (iniparser_getstring(ini, entry, INI_INVALID_KEY)!=INI_INVALID_KEY) {
@@ -397,14 +522,53 @@ int iniparser_find_entry(
If the given entry can be found, it is deleted from the dictionary.
*/
/*--------------------------------------------------------------------------*/
-void iniparser_unset(dictionary * ini, char * entry)
+void iniparser_unset(dictionary * ini, const char * entry)
{
- dictionary_unset(ini, strlwc(entry));
+ char tmp_str[ASCIILINESZ+1];
+ dictionary_unset(ini, strlwc(entry, tmp_str, sizeof(tmp_str)));
+}
+
+static void parse_quoted_value(char *value, char quote) {
+ char c;
+ char *quoted;
+ int q = 0, v = 0;
+ int esc = 0;
+
+ if(!value)
+ return;
+
+ quoted = xstrdup(value);
+
+ if(!quoted) {
+ iniparser_error_callback("iniparser: memory allocation failure\n");
+ goto end_of_value;
+ }
+
+ while((c = quoted[q]) != '\0') {
+ if(!esc) {
+ if(c == '\\') {
+ esc = 1;
+ q++;
+ continue;
+ }
+
+ if(c == quote) {
+ goto end_of_value;
+ }
+ }
+ esc = 0;
+ value[v] = c;
+ v++;
+ q++;
+ }
+end_of_value:
+ value[v] = '\0';
+ free(quoted);
}
/*-------------------------------------------------------------------------*/
/**
- @brief Load a single line from an INI file
+ @brief Load a single line from an INI file
@param input_line Input line, may be concatenated multi-line input
@param section Output space to store section
@param key Output space to store key
@@ -413,38 +577,54 @@ void iniparser_unset(dictionary * ini, char * entry)
*/
/*--------------------------------------------------------------------------*/
static line_status iniparser_line(
- char * input_line,
+ const char * input_line,
char * section,
char * key,
char * value)
{
line_status sta ;
- char line[ASCIILINESZ+1];
- int len ;
+ char * line = NULL;
+ size_t len ;
+ int d_quote;
- strcpy(line, strstrip(input_line));
- len = (int)strlen(line);
+ line = xstrdup(input_line);
+ len = strstrip(line);
sta = LINE_UNPROCESSED ;
if (len<1) {
/* Empty line */
sta = LINE_EMPTY ;
- } else if (line[0]=='#') {
+ } else if (line[0]=='#' || line[0]==';') {
/* Comment line */
sta = LINE_COMMENT ;
} else if (line[0]=='[' && line[len-1]==']') {
- /* Section name */
- sscanf(line, "[%[^]]", section);
- strcpy(section, strstrip(section));
- strcpy(section, strlwc(section));
+ /* Section name without opening square bracket */
+ sscanf(line, "[%[^\n]", section);
+ len = strlen(section);
+ /* Section name without closing square bracket */
+ if(section[len-1] == ']')
+ {
+ section[len-1] = '\0';
+ }
+ strstrip(section);
+ strlwc(section, section, len);
sta = LINE_SECTION ;
- } else if (sscanf (line, "%[^=] = \"%[^\"]\"", key, value) == 2
- || sscanf (line, "%[^=] = '%[^\']'", key, value) == 2
- || sscanf (line, "%[^=] = %[^;#]", key, value) == 2) {
- /* Usual key=value, with or without comments */
- strcpy(key, strstrip(key));
- strcpy(key, strlwc(key));
- strcpy(value, strstrip(value));
+ } else if ((d_quote = sscanf (line, "%[^=] = \"%[^\n]\"", key, value)) == 2
+ || sscanf (line, "%[^=] = '%[^\n]'", key, value) == 2) {
+ /* Usual key=value with quotes, with or without comments */
+ strstrip(key);
+ strlwc(key, key, len);
+ if(d_quote == 2)
+ parse_quoted_value(value, '"');
+ else
+ parse_quoted_value(value, '\'');
+ /* Don't strip spaces from values surrounded with quotes */
+ sta = LINE_VALUE ;
+ } else if (sscanf (line, "%[^=] = %[^;#]", key, value) == 2) {
+ /* Usual key=value without quotes, with or without comments */
+ strstrip(key);
+ strlwc(key, key, len);
+ strstrip(value);
/*
* sscanf cannot handle '' or "" as empty values
* this is done here
@@ -461,56 +641,51 @@ static line_status iniparser_line(
* key=;
* key=#
*/
- strcpy(key, strstrip(key));
- strcpy(key, strlwc(key));
+ strstrip(key);
+ strlwc(key, key, len);
value[0]=0 ;
sta = LINE_VALUE ;
} else {
/* Generate syntax error */
sta = LINE_ERROR ;
}
+
+ free(line);
return sta ;
}
/*-------------------------------------------------------------------------*/
/**
@brief Parse an ini file and return an allocated dictionary object
- @param ininame Name of the ini file to read.
+ @param in File to read.
+ @param ininame Name of the ini file to read (only used for nicer error messages)
@return Pointer to newly allocated dictionary
This is the parser for ini files. This function is called, providing
- the name of the file to be read. It returns a dictionary object that
- should not be accessed directly, but through accessor functions
- instead.
+ the file to be read. It returns a dictionary object that should not
+ be accessed directly, but through accessor functions instead.
The returned dictionary must be freed using iniparser_freedict().
*/
/*--------------------------------------------------------------------------*/
-dictionary * iniparser_load(const char * ininame)
+dictionary * iniparser_load_file(FILE * in, const char * ininame)
{
- FILE * in ;
-
char line [ASCIILINESZ+1] ;
char section [ASCIILINESZ+1] ;
char key [ASCIILINESZ+1] ;
- char tmp [ASCIILINESZ+1] ;
+ char tmp [(ASCIILINESZ * 2) + 2] ;
char val [ASCIILINESZ+1] ;
int last=0 ;
int len ;
int lineno=0 ;
int errs=0;
+ int mem_err=0;
dictionary * dict ;
- if ((in=fopen(ininame, "r"))==NULL) {
- fprintf(stderr, "iniparser: cannot open %s\n", ininame);
- return NULL ;
- }
-
dict = dictionary_new(0) ;
if (!dict) {
- fclose(in);
return NULL ;
}
@@ -523,14 +698,15 @@ dictionary * iniparser_load(const char * ininame)
while (fgets(line+last, ASCIILINESZ-last, in)!=NULL) {
lineno++ ;
len = (int)strlen(line)-1;
+ if (len<=0)
+ continue;
/* Safety check against buffer overflows */
- if (line[len]!='\n') {
- fprintf(stderr,
- "iniparser: input line too long in %s (%d)\n",
- ininame,
- lineno);
+ if (line[len]!='\n' && !feof(in)) {
+ iniparser_error_callback(
+ "iniparser: input line too long in %s (%d)\n",
+ ininame,
+ lineno);
dictionary_del(dict);
- fclose(in);
return NULL ;
}
/* Get rid of \n and spaces at end of line */
@@ -539,6 +715,9 @@ dictionary * iniparser_load(const char * ininame)
line[len]=0 ;
len-- ;
}
+ if (len < 0) { /* Line was entirely \n and/or spaces */
+ len = 0;
+ }
/* Detect multi-line */
if (line[len]=='\\') {
/* Multi-line value */
@@ -553,19 +732,20 @@ dictionary * iniparser_load(const char * ininame)
break ;
case LINE_SECTION:
- errs = dictionary_set(dict, section, NULL);
+ mem_err = dictionary_set(dict, section, NULL);
break ;
case LINE_VALUE:
sprintf(tmp, "%s:%s", section, key);
- errs = dictionary_set(dict, tmp, val) ;
+ mem_err = dictionary_set(dict, tmp, val);
break ;
case LINE_ERROR:
- fprintf(stderr, "iniparser: syntax error in %s (%d):\n",
- ininame,
- lineno);
- fprintf(stderr, "-> %s\n", line);
+ iniparser_error_callback(
+ "iniparser: syntax error in %s (%d):\n-> %s\n",
+ ininame,
+ lineno,
+ line);
errs++ ;
break;
@@ -574,8 +754,8 @@ dictionary * iniparser_load(const char * ininame)
}
memset(line, 0, ASCIILINESZ);
last=0;
- if (errs<0) {
- fprintf(stderr, "iniparser: memory allocation failure\n");
+ if (mem_err<0) {
+ iniparser_error_callback("iniparser: memory allocation failure\n");
break ;
}
}
@@ -583,10 +763,40 @@ dictionary * iniparser_load(const char * ininame)
dictionary_del(dict);
dict = NULL ;
}
+ return dict ;
+}
+
+/*-------------------------------------------------------------------------*/
+/**
+ @brief Parse an ini file and return an allocated dictionary object
+ @param ininame Name of the ini file to read.
+ @return Pointer to newly allocated dictionary
+
+ This is the parser for ini files. This function is called, providing
+ the name of the file to be read. It returns a dictionary object that
+ should not be accessed directly, but through accessor functions
+ instead.
+
+ The returned dictionary must be freed using iniparser_freedict().
+ */
+/*--------------------------------------------------------------------------*/
+dictionary * iniparser_load(const char * ininame)
+{
+ FILE * in ;
+ dictionary * dict ;
+
+ if ((in=fopen(ininame, "r"))==NULL) {
+ iniparser_error_callback("iniparser: cannot open %s\n", ininame);
+ return NULL ;
+ }
+
+ dict = iniparser_load_file(in, ininame);
fclose(in);
+
return dict ;
}
+
/*-------------------------------------------------------------------------*/
/**
@brief Free all memory associated to an ini dictionary
@@ -602,5 +812,3 @@ void iniparser_freedict(dictionary * d)
{
dictionary_del(d);
}
-
-/* vim: set ts=4 et sw=4 tw=75 */
diff --git a/lib/libubi.c b/lib/libubi.c
index 410d104..86736dd 100644
--- a/lib/libubi.c
+++ b/lib/libubi.c
@@ -768,6 +768,7 @@ int ubi_attach(libubi_t desc, const char *node, struct ubi_attach_request *req)
r.mtd_num = req->mtd_num;
r.vid_hdr_offset = req->vid_hdr_offset;
r.disable_fm = req->disable_fm ? 1 : 0;
+ r.need_resv_pool = req->need_resv_pool ? 1 : 0;
if (req->max_beb_per1024) {
/*
@@ -1363,3 +1364,13 @@ int ubi_is_mapped(int fd, int lnum)
{
return ioctl(fd, UBI_IOCEBISMAP, &lnum);
}
+
+int ubi_leb_map(int fd, int lnum)
+{
+ struct ubi_map_req r;
+
+ memset(&r, 0, sizeof(struct ubi_map_req));
+ r.lnum = lnum;
+
+ return ioctl(fd, UBI_IOCEBMAP, &r);
+}
diff --git a/lib/list_sort.c b/lib/list_sort.c
new file mode 100644
index 0000000..d873438
--- /dev/null
+++ b/lib/list_sort.c
@@ -0,0 +1,246 @@
+// SPDX-License-Identifier: GPL-2.0
+#include "list.h"
+
+/*
+ * Returns a list organized in an intermediate format suited
+ * to chaining of merge() calls: null-terminated, no reserved or
+ * sentinel head node, "prev" links not maintained.
+ */
+__attribute__((nonnull(2,3,4)))
+static struct list_head *merge(void *priv, list_cmp_func_t cmp,
+ struct list_head *a, struct list_head *b)
+{
+ struct list_head *head, **tail = &head;
+
+ for (;;) {
+ /* if equal, take 'a' -- important for sort stability */
+ if (cmp(priv, a, b) <= 0) {
+ *tail = a;
+ tail = &a->next;
+ a = a->next;
+ if (!a) {
+ *tail = b;
+ break;
+ }
+ } else {
+ *tail = b;
+ tail = &b->next;
+ b = b->next;
+ if (!b) {
+ *tail = a;
+ break;
+ }
+ }
+ }
+ return head;
+}
+
+/*
+ * Combine final list merge with restoration of standard doubly-linked
+ * list structure. This approach duplicates code from merge(), but
+ * runs faster than the tidier alternatives of either a separate final
+ * prev-link restoration pass, or maintaining the prev links
+ * throughout.
+ */
+__attribute__((nonnull(2,3,4,5)))
+static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
+ struct list_head *a, struct list_head *b)
+{
+ struct list_head *tail = head;
+ unsigned int count = 0;
+
+ for (;;) {
+ /* if equal, take 'a' -- important for sort stability */
+ if (cmp(priv, a, b) <= 0) {
+ tail->next = a;
+ a->prev = tail;
+ tail = a;
+ a = a->next;
+ if (!a)
+ break;
+ } else {
+ tail->next = b;
+ b->prev = tail;
+ tail = b;
+ b = b->next;
+ if (!b) {
+ b = a;
+ break;
+ }
+ }
+ }
+
+ /* Finish linking remainder of list b on to tail */
+ tail->next = b;
+ do {
+ /*
+ * If the merge is highly unbalanced (e.g. the input is
+ * already sorted), this loop may run many iterations.
+ * Continue callbacks to the client even though no
+ * element comparison is needed, so the client's cmp()
+ * routine can invoke cond_resched() periodically.
+ */
+ if (!++count)
+ cmp(priv, b, b);
+ b->prev = tail;
+ tail = b;
+ b = b->next;
+ } while (b);
+
+ /* And the final links to make a circular doubly-linked list */
+ tail->next = head;
+ head->prev = tail;
+}
+
+/**
+ * list_sort - sort a list
+ * @priv: private data, opaque to list_sort(), passed to @cmp
+ * @head: the list to sort
+ * @cmp: the elements comparison function
+ *
+ * The comparison function @cmp must return > 0 if @a should sort after
+ * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
+ * sort before @b *or* their original order should be preserved. It is
+ * always called with the element that came first in the input in @a,
+ * and list_sort is a stable sort, so it is not necessary to distinguish
+ * the @a < @b and @a == @b cases.
+ *
+ * This is compatible with two styles of @cmp function:
+ * - The traditional style which returns <0 / =0 / >0, or
+ * - Returning a boolean 0/1.
+ * The latter offers a chance to save a few cycles in the comparison
+ * (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c).
+ *
+ * A good way to write a multi-word comparison is::
+ *
+ * if (a->high != b->high)
+ * return a->high > b->high;
+ * if (a->middle != b->middle)
+ * return a->middle > b->middle;
+ * return a->low > b->low;
+ *
+ *
+ * This mergesort is as eager as possible while always performing at least
+ * 2:1 balanced merges. Given two pending sublists of size 2^k, they are
+ * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
+ *
+ * Thus, it will avoid cache thrashing as long as 3*2^k elements can
+ * fit into the cache. Not quite as good as a fully-eager bottom-up
+ * mergesort, but it does use 0.2*n fewer comparisons, so is faster in
+ * the common case that everything fits into L1.
+ *
+ *
+ * The merging is controlled by "count", the number of elements in the
+ * pending lists. This is beautifully simple code, but rather subtle.
+ *
+ * Each time we increment "count", we set one bit (bit k) and clear
+ * bits k-1 .. 0. Each time this happens (except the very first time
+ * for each bit, when count increments to 2^k), we merge two lists of
+ * size 2^k into one list of size 2^(k+1).
+ *
+ * This merge happens exactly when the count reaches an odd multiple of
+ * 2^k, which is when we have 2^k elements pending in smaller lists,
+ * so it's safe to merge away two lists of size 2^k.
+ *
+ * After this happens twice, we have created two lists of size 2^(k+1),
+ * which will be merged into a list of size 2^(k+2) before we create
+ * a third list of size 2^(k+1), so there are never more than two pending.
+ *
+ * The number of pending lists of size 2^k is determined by the
+ * state of bit k of "count" plus two extra pieces of information:
+ *
+ * - The state of bit k-1 (when k == 0, consider bit -1 always set), and
+ * - Whether the higher-order bits are zero or non-zero (i.e.
+ * is count >= 2^(k+1)).
+ *
+ * There are six states we distinguish. "x" represents some arbitrary
+ * bits, and "y" represents some arbitrary non-zero bits:
+ * 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k
+ * 1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
+ * 2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k
+ * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
+ * 4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k
+ * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
+ * (merge and loop back to state 2)
+ *
+ * We gain lists of size 2^k in the 2->3 and 4->5 transitions (because
+ * bit k-1 is set while the more significant bits are non-zero) and
+ * merge them away in the 5->2 transition. Note in particular that just
+ * before the 5->2 transition, all lower-order bits are 11 (state 3),
+ * so there is one list of each smaller size.
+ *
+ * When we reach the end of the input, we merge all the pending
+ * lists, from smallest to largest. If you work through cases 2 to
+ * 5 above, you can see that the number of elements we merge with a list
+ * of size 2^k varies from 2^(k-1) (cases 3 and 5 when x == 0) to
+ * 2^(k+1) - 1 (second merge of case 5 when x == 2^(k-1) - 1).
+ */
+__attribute__((nonnull(2,3)))
+void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
+{
+ struct list_head *list = head->next, *pending = NULL;
+ size_t count = 0; /* Count of pending */
+
+ if (list == head->prev) /* Zero or one elements */
+ return;
+
+ /* Convert to a null-terminated singly-linked list. */
+ head->prev->next = NULL;
+
+ /*
+ * Data structure invariants:
+ * - All lists are singly linked and null-terminated; prev
+ * pointers are not maintained.
+ * - pending is a prev-linked "list of lists" of sorted
+ * sublists awaiting further merging.
+ * - Each of the sorted sublists is power-of-two in size.
+ * - Sublists are sorted by size and age, smallest & newest at front.
+ * - There are zero to two sublists of each size.
+ * - A pair of pending sublists are merged as soon as the number
+ * of following pending elements equals their size (i.e.
+ * each time count reaches an odd multiple of that size).
+ * That ensures each later final merge will be at worst 2:1.
+ * - Each round consists of:
+ * - Merging the two sublists selected by the highest bit
+ * which flips when count is incremented, and
+ * - Adding an element from the input as a size-1 sublist.
+ */
+ do {
+ size_t bits;
+ struct list_head **tail = &pending;
+
+ /* Find the least-significant clear bit in count */
+ for (bits = count; bits & 1; bits >>= 1)
+ tail = &(*tail)->prev;
+ /* Do the indicated merge */
+ if (bits) {
+ struct list_head *a = *tail, *b = a->prev;
+
+ a = merge(priv, cmp, b, a);
+ /* Install the merged result in place of the inputs */
+ a->prev = b->prev;
+ *tail = a;
+ }
+
+ /* Move one element from input list to pending */
+ list->prev = pending;
+ pending = list;
+ list = list->next;
+ pending->next = NULL;
+ count++;
+ } while (list);
+
+ /* End of input; merge together all the pending lists. */
+ list = pending;
+ pending = pending->prev;
+ for (;;) {
+ struct list_head *next = pending->prev;
+
+ if (!next)
+ break;
+ list = merge(priv, cmp, pending, list);
+ pending = next;
+ }
+ /* The final merge, rebuilding prev links */
+ merge_final(priv, cmp, head, pending, list);
+}
diff --git a/lib/rbtree.c b/lib/rbtree.c
new file mode 100644
index 0000000..32c8755
--- /dev/null
+++ b/lib/rbtree.c
@@ -0,0 +1,428 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea@suse.de>
+ (C) 2002 David Woodhouse <dwmw2@infradead.org>
+
+ 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.
+
+ This program 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 this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/lib/rbtree.c
+*/
+
+#include <stdlib.h>
+#include "rbtree.h"
+
+static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *right = node->rb_right;
+ struct rb_node *parent = rb_parent(node);
+
+ if ((node->rb_right = right->rb_left))
+ rb_set_parent(right->rb_left, node);
+ right->rb_left = node;
+
+ rb_set_parent(right, parent);
+
+ if (parent)
+ {
+ if (node == parent->rb_left)
+ parent->rb_left = right;
+ else
+ parent->rb_right = right;
+ }
+ else
+ root->rb_node = right;
+ rb_set_parent(node, right);
+}
+
+static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *left = node->rb_left;
+ struct rb_node *parent = rb_parent(node);
+
+ if ((node->rb_left = left->rb_right))
+ rb_set_parent(left->rb_right, node);
+ left->rb_right = node;
+
+ rb_set_parent(left, parent);
+
+ if (parent)
+ {
+ if (node == parent->rb_right)
+ parent->rb_right = left;
+ else
+ parent->rb_left = left;
+ }
+ else
+ root->rb_node = left;
+ rb_set_parent(node, left);
+}
+
+void rb_insert_color(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *parent, *gparent;
+
+ while ((parent = rb_parent(node)) && rb_is_red(parent))
+ {
+ gparent = rb_parent(parent);
+
+ if (parent == gparent->rb_left)
+ {
+ {
+ register struct rb_node *uncle = gparent->rb_right;
+ if (uncle && rb_is_red(uncle))
+ {
+ rb_set_black(uncle);
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ node = gparent;
+ continue;
+ }
+ }
+
+ if (parent->rb_right == node)
+ {
+ register struct rb_node *tmp;
+ __rb_rotate_left(parent, root);
+ tmp = parent;
+ parent = node;
+ node = tmp;
+ }
+
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ __rb_rotate_right(gparent, root);
+ } else {
+ {
+ register struct rb_node *uncle = gparent->rb_left;
+ if (uncle && rb_is_red(uncle))
+ {
+ rb_set_black(uncle);
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ node = gparent;
+ continue;
+ }
+ }
+
+ if (parent->rb_left == node)
+ {
+ register struct rb_node *tmp;
+ __rb_rotate_right(parent, root);
+ tmp = parent;
+ parent = node;
+ node = tmp;
+ }
+
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ __rb_rotate_left(gparent, root);
+ }
+ }
+
+ rb_set_black(root->rb_node);
+}
+
+static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
+ struct rb_root *root)
+{
+ struct rb_node *other;
+
+ while ((!node || rb_is_black(node)) && node != root->rb_node)
+ {
+ if (parent->rb_left == node)
+ {
+ other = parent->rb_right;
+ if (rb_is_red(other))
+ {
+ rb_set_black(other);
+ rb_set_red(parent);
+ __rb_rotate_left(parent, root);
+ other = parent->rb_right;
+ }
+ if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+ (!other->rb_right || rb_is_black(other->rb_right)))
+ {
+ rb_set_red(other);
+ node = parent;
+ parent = rb_parent(node);
+ }
+ else
+ {
+ if (!other->rb_right || rb_is_black(other->rb_right))
+ {
+ struct rb_node *o_left;
+ if ((o_left = other->rb_left))
+ rb_set_black(o_left);
+ rb_set_red(other);
+ __rb_rotate_right(other, root);
+ other = parent->rb_right;
+ }
+ rb_set_color(other, rb_color(parent));
+ rb_set_black(parent);
+ if (other->rb_right)
+ rb_set_black(other->rb_right);
+ __rb_rotate_left(parent, root);
+ node = root->rb_node;
+ break;
+ }
+ }
+ else
+ {
+ other = parent->rb_left;
+ if (rb_is_red(other))
+ {
+ rb_set_black(other);
+ rb_set_red(parent);
+ __rb_rotate_right(parent, root);
+ other = parent->rb_left;
+ }
+ if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+ (!other->rb_right || rb_is_black(other->rb_right)))
+ {
+ rb_set_red(other);
+ node = parent;
+ parent = rb_parent(node);
+ }
+ else
+ {
+ if (!other->rb_left || rb_is_black(other->rb_left))
+ {
+ register struct rb_node *o_right;
+ if ((o_right = other->rb_right))
+ rb_set_black(o_right);
+ rb_set_red(other);
+ __rb_rotate_left(other, root);
+ other = parent->rb_left;
+ }
+ rb_set_color(other, rb_color(parent));
+ rb_set_black(parent);
+ if (other->rb_left)
+ rb_set_black(other->rb_left);
+ __rb_rotate_right(parent, root);
+ node = root->rb_node;
+ break;
+ }
+ }
+ }
+ if (node)
+ rb_set_black(node);
+}
+
+void rb_erase(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *child, *parent;
+ int color;
+
+ if (!node->rb_left)
+ child = node->rb_right;
+ else if (!node->rb_right)
+ child = node->rb_left;
+ else
+ {
+ struct rb_node *old = node, *left;
+
+ node = node->rb_right;
+ while ((left = node->rb_left) != NULL)
+ node = left;
+ child = node->rb_right;
+ parent = rb_parent(node);
+ color = rb_color(node);
+
+ if (child)
+ rb_set_parent(child, parent);
+ if (parent == old) {
+ parent->rb_right = child;
+ parent = node;
+ } else
+ parent->rb_left = child;
+
+ node->rb_parent_color = old->rb_parent_color;
+ node->rb_right = old->rb_right;
+ node->rb_left = old->rb_left;
+
+ if (rb_parent(old))
+ {
+ if (rb_parent(old)->rb_left == old)
+ rb_parent(old)->rb_left = node;
+ else
+ rb_parent(old)->rb_right = node;
+ } else
+ root->rb_node = node;
+
+ rb_set_parent(old->rb_left, node);
+ if (old->rb_right)
+ rb_set_parent(old->rb_right, node);
+ goto color;
+ }
+
+ parent = rb_parent(node);
+ color = rb_color(node);
+
+ if (child)
+ rb_set_parent(child, parent);
+ if (parent)
+ {
+ if (parent->rb_left == node)
+ parent->rb_left = child;
+ else
+ parent->rb_right = child;
+ }
+ else
+ root->rb_node = child;
+
+ color:
+ if (color == RB_BLACK)
+ __rb_erase_color(child, parent, root);
+}
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct rb_node *rb_first(struct rb_root *root)
+{
+ struct rb_node *n;
+
+ n = root->rb_node;
+ if (!n)
+ return NULL;
+ while (n->rb_left)
+ n = n->rb_left;
+ return n;
+}
+
+struct rb_node *rb_last(struct rb_root *root)
+{
+ struct rb_node *n;
+
+ n = root->rb_node;
+ if (!n)
+ return NULL;
+ while (n->rb_right)
+ n = n->rb_right;
+ return n;
+}
+
+struct rb_node *rb_next(struct rb_node *node)
+{
+ struct rb_node *parent;
+
+ if (rb_parent(node) == node)
+ return NULL;
+
+ /* If we have a right-hand child, go down and then left as far
+ as we can. */
+ if (node->rb_right) {
+ node = node->rb_right;
+ while (node->rb_left)
+ node=node->rb_left;
+ return node;
+ }
+
+ /* No right-hand children. Everything down and left is
+ smaller than us, so any 'next' node must be in the general
+ direction of our parent. Go up the tree; any time the
+ ancestor is a right-hand child of its parent, keep going
+ up. First time it's a left-hand child of its parent, said
+ parent is our 'next' node. */
+ while ((parent = rb_parent(node)) && node == parent->rb_right)
+ node = parent;
+
+ return parent;
+}
+
+struct rb_node *rb_prev(struct rb_node *node)
+{
+ struct rb_node *parent;
+
+ if (rb_parent(node) == node)
+ return NULL;
+
+ /* If we have a left-hand child, go down and then right as far
+ as we can. */
+ if (node->rb_left) {
+ node = node->rb_left;
+ while (node->rb_right)
+ node=node->rb_right;
+ return node;
+ }
+
+ /* No left-hand children. Go up till we find an ancestor which
+ is a right-hand child of its parent */
+ while ((parent = rb_parent(node)) && node == parent->rb_left)
+ node = parent;
+
+ return parent;
+}
+
+void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root)
+{
+ struct rb_node *parent = rb_parent(victim);
+
+ /* Set the surrounding nodes to point to the replacement */
+ if (parent) {
+ if (victim == parent->rb_left)
+ parent->rb_left = new;
+ else
+ parent->rb_right = new;
+ } else {
+ root->rb_node = new;
+ }
+ if (victim->rb_left)
+ rb_set_parent(victim->rb_left, new);
+ if (victim->rb_right)
+ rb_set_parent(victim->rb_right, new);
+
+ /* Copy the pointers/colour from the victim to the replacement */
+ *new = *victim;
+}
+
+static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
+{
+ for (;;) {
+ if (node->rb_left)
+ node = node->rb_left;
+ else if (node->rb_right)
+ node = node->rb_right;
+ else
+ return (struct rb_node *)node;
+ }
+}
+
+struct rb_node *rb_next_postorder(const struct rb_node *node)
+{
+ const struct rb_node *parent;
+ if (!node)
+ return NULL;
+ parent = rb_parent(node);
+
+ /* If we're sitting on node, we've already seen our children */
+ if (parent && node == parent->rb_left && parent->rb_right) {
+ /* If we are the parent's left node, go to the parent's right
+ * node then all the way down to the left */
+ return rb_left_deepest_node(parent->rb_right);
+ } else
+ /* Otherwise we are the parent's right node, and the parent
+ * should be next */
+ return (struct rb_node *)parent;
+}
+
+struct rb_node *rb_first_postorder(const struct rb_root *root)
+{
+ if (!root->rb_node)
+ return NULL;
+
+ return rb_left_deepest_node(root->rb_node);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-05-12 13:33:49 +0000