keyset.c

/***************************************************************************
                          keyset.c  -  Methods for KeySet manipulation
                             -------------------
    begin                : Sun Oct 02 2005
    copyright            : (C) 2005 by Avi Alkalay
    email                : avi@unix.sh
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the BSD License (revised).                      *
 *                                                                         *
 ***************************************************************************/

/* Subversion stuff

$Id: keyset.c 593 2006-02-14 15:25:25Z mraab $

*/

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#ifdef HAVE_LANGINFO_H
#include <langinfo.h>
#endif

#include "kdb.h"
#include "kdbprivate.h"

KeySet *ksNew() {
    KeySet *new=(KeySet *)malloc(sizeof(KeySet));
    ksInit(new);
    return new;
}



int ksDel(KeySet *ks) {
    int rc;
    
    rc=ksClose(ks);
    free(ks);
    
    return rc;
}



ssize_t ksGetSize(KeySet *ks) {
    return ks->size;
}








/******************************************* 
 *           KeySet walking methods        *
 *******************************************/


int ksRewind(KeySet *ks) {
    ks->cursor=0;
    return 0;
}



Key *ksNext(KeySet *ks) {
    if (ks->cursor) ks->cursor=ks->cursor->next;
    else ks->cursor=ks->start;

    return ks->cursor;
}



Key *ksCurrent(const KeySet *ks) {
    return ks->cursor;
}



Key *ksHead(KeySet *ks) {
    return ks->start;
}



Key *ksTail(KeySet *ks) {
    return ks->end;
}











/******************************************* 
 *    Looking up Keys inside KeySets       *
 *******************************************/


Key *ksLookupByName(KeySet *ks, const char *name, unsigned long options) {
    Key *init=0;
    Key *current=0;
    size_t nameSize;
    size_t currentNameSize;
    char * keyname;

    nameSize=strblen(name);

    init=ks->cursor;

    while ((current=ksNext(ks))) {
        if (current->key == name) return current; /* for NULLs */


        if (name [0] == '/') {  /*Cascading search*/
            keyname = strchr(current->key, '/');
        } else {
            keyname = keyStealName (current);
        }

#ifdef VERBOSE
        fprintf (stderr, "Compare %s with %s\n", keyname, name);
#endif

        if ((current->key && name)) {
            if ((options & KDB_O_NOCASE) &&
                !strcasecmp(keyname,name)) return current;
            else if (!strcmp(keyname,name)) return current;
        }
    }

    /* Reached end of KeySet. Put cursor in initial position. */
    ks->cursor=init;

    return 0;
}



uint32_t ksLookupRE(KeySet *ks, uint32_t where,
        const regex_t *regexp, unsigned long options) {
#ifdef HAVE_REGEX_H
    regmatch_t offsets;
    uint32_t match=0;
    Key *init, *walker;
    char *parentName=0;
    size_t walkerNameSize=0,parentNameSize=0;
    
    init=ks->cursor;
    if (!init)
        /* I don't have a parent to match. Ignore this option. */
        options &= options & ~KDB_O_NOSPANPARENT;
    
    if (options & KDB_O_NOSPANPARENT) {
        /* User wants siblings. Prepare context. */
        parentNameSize=keyGetParentNameSize(init);
        parentName=(char *)malloc(parentNameSize);
        keyGetParentName(init,parentName,parentNameSize);
    }
    
    while ((walker=ksNext(ks))) {
        walkerNameSize=keyGetNameSize(walker);
        
        if (options & KDB_O_NOSPANPARENT) {
            /* User wants siblings. Check if walker is a sibling of init. */
            if (walkerNameSize < parentNameSize)
                /* we're out of out scope, so abort */
                break;
            
            if (memcmp(parentName,walker->key,parentNameSize))
                /* walker has a different parent, so abort */
                break;
        }
    
        if ((where & KEY_SWITCH_NAME) && walker->key)
            if (!regexec(regexp,walker->key,1,&offsets,0))
                match |= KEY_SWITCH_NAME;
        
        if ((where & KEY_SWITCH_VALUE) && walker->data &&
            !(KEY_TYPE_BINARY <= walker->type && walker->type < KEY_TYPE_STRING))
            if (!regexec(regexp,(char *)walker->data,1,&offsets,0))
                match |= KEY_SWITCH_VALUE;
        
        if ((where & KEY_SWITCH_OWNER) && keyIsUser(walker))
            if (!regexec(regexp,walker->userDomain,1,&offsets,0))
                match |= KEY_SWITCH_OWNER;
        
        if ((where & KEY_SWITCH_COMMENT) && walker->comment)
            if (!regexec(regexp,walker->comment,1,&offsets,0))
                match |= KEY_SWITCH_OWNER;
        
        if (match) return match;
    }
    
    if (parentName) free(parentName);
    ks->cursor=init;
#endif  
    return 0;
}


Key *ksLookupByValue(KeySet *ks, const char *value, unsigned long options) {
    Key *init=0;
    Key *current=0;
    size_t size=0;
    
    size=strblen(value);
    init=ks->cursor;
    
    while ((current=ksNext(ks))) {
        if (current->data == value) return current;
        
        if (size != current->dataSize) continue;
        
        if (KEY_TYPE_BINARY<= current->type && current->type < KEY_TYPE_STRING)
            continue;
        
        if ((current->data && value)) {
            if ((options & KDB_O_NOCASE) && 
                !strcasecmp(current->data,value)) return current;
            else if (!strcmp(current->data,value)) return current;
        }
    }
    
    /* reached end of KeySet */
    ks->cursor=init;
    
    return 0;
}



Key *ksLookupByBinaryValue(KeySet *ks, void *value, size_t size,
        unsigned long options) {
    Key *init=0;
    Key *current=0;
    
    init=ks->cursor;
    
    while ((current=ksNext(ks))) {
        if (current->data == value) return current;
        
        if (size != current->dataSize) continue;
        
        if ((current->data && value) && 
                !memcmp(current->data,value,size)) return current;
    }
    
    /* reached end of KeySet, so reset cursor */
    ks->cursor=init;
    
    return 0;
}







/******************************************* 
 *           Filling up KeySets            *
 *******************************************/

 
ssize_t ksInsert(KeySet *ks, Key *toInsert) {
    toInsert->next=ks->start;
    ks->start=toInsert;
    if (!ks->end) ks->end=toInsert;
    return ++ks->size;
}


Key *ksPop(KeySet *ks) {
    Key *key=0;
    
    if (ks->start) {
        key=ks->start;
        ks->start=key->next;
        if (ks->end == key) ks->end=0;
        ks->size--;
        if (ks->cursor == key) ks->cursor=0;
    }
    
    return key;
}


Key *ksPopLast(KeySet *ks) {
    Key *key=0;
    Key *prev=0;
    
    /* When ks is empty: */
    if (ks->end == 0) return 0;
    
    /* When ks has only one member: */
    if (ks->start == ks->end) {
        key=ks->end;
        ks->cursor=ks->start=ks->end=0;
        ks->size=0;
        
        return key;
    }
    
    prev=ks->start;
    while (prev->next!=ks->end) prev=prev->next;
    
    key=ks->end;
    prev->next=0;
    ks->end=prev;
    ks->size--;
    if (ks->cursor == key) ks->cursor=0;
    
    return key;
}


ssize_t ksInsertKeys(KeySet *ks, KeySet *toInsert) {
    if (toInsert->size) {
        toInsert->end->next=ks->start;
        ks->start=toInsert->start;

        ks->size+=toInsert->size;

        /* Invalidate the old KeySet */
        toInsert->start=toInsert->end=toInsert->cursor=0;
        toInsert->size=0;
    }
    return ks->size;
}



ssize_t ksAppend(KeySet *ks, Key *toAppend) {
    toAppend->next=0;
    if (ks->end) ks->end->next=toAppend;
    if (!ks->start) ks->start=toAppend;
    ks->end=toAppend;
    return ++ks->size;
}



ssize_t ksAppendKeys(KeySet *ks, KeySet *toAppend) {
    if (toAppend->size) {
        if (ks->end) {
            ks->end->next=toAppend->start;
            ks->end=toAppend->end;
        } else {
            ks->end=toAppend->end;
            ks->start=toAppend->start;
        }

        ks->size+=toAppend->size;
        
        /* Invalidate the old KeySet */
        toAppend->start=toAppend->end=toAppend->cursor=0;
        toAppend->size=0;
    }
    return ks->size;
}










/******************************************* 
 *    Other operations                     *
 *******************************************/


int ksCompare(KeySet *ks1, KeySet *ks2, KeySet *removed) {
    int flagRemoved=1;
    Key *ks1Cursor=0;
    Key *ks2Cursor=0;

    Key *ks1PrevCursor=0;

    ks1Cursor=ks1->start;
    while (ks1Cursor) {
        Key *ks2PrevCursor=0;
        flagRemoved=1;
        
        for (ks2Cursor=ks2->start; ks2Cursor; ks2Cursor=ks2Cursor->next) {
            uint32_t flags=keyCompare(ks1Cursor,ks2Cursor);
            
            if (!(flags & (KEY_SWITCH_NAME | KEY_SWITCH_DOMAIN))) {
                /* Comparing fullname-equal keys */
                flagRemoved=0; /* key was not removed */
                    
                /* First remove from ks2 */
                if (ks2PrevCursor) ks2PrevCursor->next=ks2Cursor->next;
                else ks2->start=ks2Cursor->next;
                if (ks2->end==ks2Cursor) ks2->end=ks2PrevCursor;
                ks2->size--;
                    
                if (flags) {
                    /* keys are different. Transfer to ks1. */
                    
                    /* Put in ks1 */
                    if (ks1PrevCursor) ks1PrevCursor->next=ks2Cursor;
                    else ks1->start=ks2Cursor;
                    if (ks1->end==ks1Cursor) ks1->end=ks2Cursor;
                    ks2Cursor->next=ks1Cursor->next;
                    
                    /* delete old version */
                    keyDel(ks1Cursor);
                    
                    /* Reset pointers */
                    ks1Cursor=ks2Cursor;
                } else {
                    /* Keys are identical. Delete ks2's key. */

                    /* Delete ks2Cusrsor */
                    keyDel(ks2Cursor);
                }
                /* Don't need to walk through ks2 anymore */
                break;
            }
            ks2PrevCursor=ks2Cursor;
            
        } /* ks2 iteration */
        
        if (flagRemoved) {
            /* This ks1 key was not found in ks2 */
            /* Transfer it from ks1 to removed */
            
            /* Remove from ks1 */
            if (ks1PrevCursor) ks1PrevCursor->next=ks1Cursor->next;
            else ks1->start=ks1Cursor->next;
            if (ks1->end==ks1Cursor) ks1->end=ks1PrevCursor;
            ks1->size--;

            /* Append to removed */
            ksAppend(removed,ks1Cursor);
            
            /* Reset pointers */
            if (ks1PrevCursor) ks1Cursor=ks1PrevCursor->next;
            else ks1Cursor=ks1->start;
        } else {
            ks1PrevCursor=ks1Cursor;
            ks1Cursor=ks1Cursor->next;
        }
    } /* ks1 iteration */
    
    /* Now transfer all remaining ks2 keys to ks1 */
    ksAppendKeys(ks1,ks2);
    
    return 0;
}




ssize_t ksToStream(const KeySet *ks, FILE* stream, unsigned long options) {
    size_t written=0;
    Key *key=0;
    char *codeset;

    /* If nl_langinfo or the CODESET info isn't available we default to UTF-8 
     * This might not be a very good default, but I'm not sure how else to do it*/
#if defined(HAVE_NL_LANGINFO) && defined(CODESET)
    codeset = nl_langinfo(CODESET);
#else
    codeset = "UTF-8";
#endif
    if (options & KDB_O_XMLHEADERS) {
        written+=fprintf(stream,"<?xml version=\"1.0\" encoding=\"%s\"?>\n",
            codeset);
        written+=fprintf(stream,
            "\n\n<!-- Generated by Elektra API. Total of %d keys. -->\n\n\n\n",ks->size);
        
        written+=fprintf(stream,"<keyset xmlns=\"http://www.libelektra.org\"\n\
        xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\"\n\
        xsi:schemaLocation=\"http://www.libelektra.org elektra.xsd\"");
        
        /* written+=fprintf(stream,
            "<!DOCTYPE keyset PUBLIC \"-//Avi Alkalay//DTD Elektra 0.1.0//EN\" \"http://elektra.sf.net/dtd/elektra.dtd\">\n\n\n"); */
    } else written+=fprintf(stream,"<keyset");

    if (options & KDB_O_HIER) {
        Key *smalest=0;
        size_t ssmalest=0;

        for (key=ks->start; key; key=key->next) {
            if (smalest) {
                size_t size=strblen(key->key);
                if (size<ssmalest) {
                    smalest=key;
                    ssmalest=size;
                }
            } else {
                smalest=key;
                ssmalest=strblen(smalest->key);
            }
        }

        if (keyIsUser(smalest) && (options & KDB_O_FULLNAME)) {
            char buffer[800];
            keyGetFullName(smalest,buffer,sizeof(buffer));
            written+=fprintf(stream,"\n\n        parent=\"%s\"",buffer);
        } else
            written+=fprintf(stream,"\n\n        parent=\"%s\"",smalest->key);

        written+=fprintf(stream,">\n\n\n");

        for (key=ks->start; key; key=key->next)
            written+=keyToStreamBasename(key,stream,smalest->key,0,options);
    } else { /* No KDB_O_HIER*/
        written+=fprintf(stream,">\n\n\n");
        for (key=ks->start; key; key=key->next)
            written+=keyToStream(key,stream,options);
    }
    
    written+=fprintf(stream,"</keyset>\n");
    return written;
}



/* Used as a callback by the qsort() function */
int keyCompareByName(const void *p1, const void *p2) {
    Key *key1=*(Key **)p1;
    Key *key2=*(Key **)p2;

    return strcmp(key1->key, key2->key);
}


void ksSort(KeySet *ks) {
    Key **keys = NULL;
    Key *cursor;
    size_t c=0;

    if (ks->size) {
        keys = (Key **)calloc(ks->size, sizeof(Key *));

        for (cursor=ks->start; cursor; cursor=cursor->next, c++)
            keys[c]=cursor;

        qsort(keys,ks->size,sizeof(Key *),keyCompareByName);

        ks->start=cursor=keys[0];
        for (c=1; c<ks->size; c++) {
            cursor->next=keys[c];
            cursor=cursor->next;
        }
        cursor->next=0;
        ks->end=cursor;
        free(keys);
    }
}






int ksInit(KeySet *ks) {
    ks->start=ks->end=ks->cursor=0;
    ks->size=0;
    
    return 0;
}


int ksClose(KeySet *ks) {
    if (ks->size) {
        while (ks->size) {
            Key *destroyer=ks->start;
            ks->start=destroyer->next;
            keyDel(destroyer);
            --ks->size;
        }
    }
    ks->cursor=ks->end=ks->start;
    return 0;
}

---