keyset.c

00001 /***************************************************************************
00002                           keyset.c  -  Methods for KeySet manipulation
00003                              -------------------
00004     begin                : Sun Oct 02 2005
00005     copyright            : (C) 2005 by Avi Alkalay
00006     email                : avi@unix.sh
00007  ***************************************************************************/
00008 
00009 /***************************************************************************
00010  *                                                                         *
00011  *   This program is free software; you can redistribute it and/or modify  *
00012  *   it under the terms of the BSD License (revised).                      *
00013  *                                                                         *
00014  ***************************************************************************/
00015 
00016 /* Subversion stuff
00017 
00018 $Id: keyset.c 845 2006-07-26 19:29:09Z aviram $
00019 
00020 */
00021 
00022 #ifdef HAVE_CONFIG_H
00023 #include "config.h"
00024 #endif
00025 
00026 #include <stdio.h>
00027 #include <stdlib.h>
00028 #include <errno.h>
00029 #include <string.h>
00030 #include <strings.h>
00031 #ifdef HAVE_LANGINFO_H
00032 #include <langinfo.h>
00033 #endif
00034 
00035 #include "kdb.h"
00036 #include "kdbprivate.h"
00037 
00038 
00039 
00040 /* Used as a callback by the qsort() function */
00041 int keyCompareByName(const void *p1, const void *p2) {
00042     Key *key1=*(Key **)p1;
00043     Key *key2=*(Key **)p2;
00044 
00045     return strcmp(key1->key, key2->key);
00046 }
00047 
00048 
00049 
00050 
00093 KeySet *ksNew() {
00094     KeySet *new=(KeySet *)malloc(sizeof(KeySet));
00095     ksInit(new);
00096     return new;
00097 }
00098 
00099 
00100 
00111 int ksDel(KeySet *ks) {
00112     int rc;
00113     
00114     rc=ksClose(ks);
00115     free(ks);
00116     
00117     return rc;
00118 }
00119 
00120 
00121 
00127 ssize_t ksGetSize(KeySet *ks) {
00128     return ks->size;
00129 }
00130 
00131 
00132 
00133 
00134 /*******************************************
00135  *           KeySet browsing methods       *
00136  *******************************************/
00137 
00138 
00155 int ksRewind(KeySet *ks) {
00156     ks->cursor=0;
00157     return 0;
00158 }
00159 
00160 
00161 
00177 Key *ksNext(KeySet *ks) {
00178     if (ks->cursor) ks->cursor=ks->cursor->next;
00179     else ks->cursor=ks->start;
00180 
00181     return ks->cursor;
00182 }
00183 
00184 
00185 
00196 Key *ksCurrent(const KeySet *ks) {
00197     return ks->cursor;
00198 }
00199 
00200 
00201 
00209 Key *ksHead(KeySet *ks) {
00210     return ks->start;
00211 }
00212 
00213 
00214 
00221 Key *ksTail(KeySet *ks) {
00222     return ks->end;
00223 }
00224 
00225 
00226 
00227 
00228 
00229 
00230 
00231 
00232 
00233 
00234 
00235 /******************************************* 
00236  *    Looking up Keys inside KeySets       *
00237  *******************************************/
00238 
00239 
00294 Key *ksLookupByName(KeySet *ks, const char *name, unsigned long options) {
00295     Key *init=0;
00296     Key *current=0;
00297     Key *end=0;
00298     size_t nameSize;
00299     char * keyname;
00300 
00301     nameSize=strblen(name);
00302 
00303     init=ks->cursor;
00304     if ( (init == NULL) || (init == ks->start) ) {
00305         /* Avoid looping if already in the begining of the keyset */
00306         options &= options & ~KDB_O_ALL;
00307     }
00308 
00309     while ( ((current=ksNext(ks)) != end) || (options & KDB_O_ALL) ) {
00310         if (current == NULL) {
00311             /* End of list reached.
00312              * Retry lookup from start to cursor */
00313             ksRewind(ks);
00314             end=init;
00315             options &= options & ~KDB_O_ALL;
00316             continue;
00317         }
00318         
00319         if (current->key == name) return current; /* for NULLs */
00320         
00321         /* This "optimization" makes comparing keys double when equals
00322         currentNameSize=current->key?strblen(current->key):0;
00323         if (currentNameSize != nameSize) continue; */
00324 
00325         if (name [0] == '/') /* Cascading search */
00326             keyname = strchr(current->key, '/');
00327         else keyname = keyStealName (current);
00328 
00329 #ifdef VERBOSE
00330         fprintf (stderr, "Compare %s with %s\n", keyname, name);
00331 #endif
00332 
00333         if ((current->key && name)) {
00334             if ((options & KDB_O_NOCASE) &&
00335                 !strcasecmp(keyname,name)) return current;
00336             else if (!strcmp(keyname,name)) return current;
00337         }
00338     }
00339 
00340     /* Reached end of KeySet. Put cursor in initial position. */
00341     ks->cursor=init;
00342 
00343     return 0;
00344 }
00345 
00346 
00347 
00438 uint32_t ksLookupRE(KeySet *ks, uint32_t where,
00439         const regex_t *regexp, unsigned long options) {
00440 #ifdef HAVE_REGEX_H
00441     regmatch_t offsets;
00442     uint32_t match=0;
00443     Key *init, *walker, *end;
00444     char *parentName=0;
00445     size_t walkerNameSize=0,parentNameSize=0;
00446     
00447     end=NULL;
00448     init=ks->cursor;
00449     if (!init) {
00450         /* I don't have a parent to match. Ignore this option. */
00451         options &= options & ~KDB_O_NOSPANPARENT;
00452     }
00453 
00454     if ( (init == NULL) || (init == ks->start) ) {
00455         /* Avoid looping if are already in the begining of the keyset */
00456         options &= options & ~KDB_O_ALL;
00457     }
00458     
00459     if (options & KDB_O_NOSPANPARENT) {
00460         /* User wants siblings. Prepare context. */
00461         parentNameSize=keyGetParentNameSize(init);
00462         parentName=(char *)malloc(parentNameSize);
00463         keyGetParentName(init,parentName,parentNameSize);
00464     }
00465     
00466     while ( (walker=ksNext(ks)) != end || (options & KDB_O_ALL) ) {
00467         if ( walker == NULL ) {
00468             /* Bottom of list reached
00469              * retry lookup from start to cursor */
00470             ksRewind(ks);
00471             end=init;
00472             options &= options & ~KDB_O_ALL;
00473             continue;
00474         }
00475         
00476         walkerNameSize=keyGetNameSize(walker);
00477         
00478         if (options & KDB_O_NOSPANPARENT) {
00479             /* User wants siblings. Check if walker is a sibling of init. */
00480             if (walkerNameSize < parentNameSize-1)
00481                 /* we're out of our scope, so abort */
00482                 break;
00483             
00484             if (memcmp(parentName,walker->key,parentNameSize-1))
00485                 /* walker has a different parent, so abort */
00486                 break;
00487         }
00488     
00489         if ((where & KEY_SWITCH_NAME) && walker->key)
00490             if (!regexec(regexp,walker->key,1,&offsets,0))
00491                 match |= KEY_SWITCH_NAME;
00492         
00493         if ((where & KEY_SWITCH_VALUE) && walker->data &&
00494             !(KEY_TYPE_BINARY <= walker->type && walker->type < KEY_TYPE_STRING))
00495             if (!regexec(regexp,(char *)walker->data,1,&offsets,0))
00496                 match |= KEY_SWITCH_VALUE;
00497         
00498         if ((where & KEY_SWITCH_OWNER) && keyIsUser(walker))
00499             if (!regexec(regexp,walker->userDomain,1,&offsets,0))
00500                 match |= KEY_SWITCH_OWNER;
00501         
00502         if ((where & KEY_SWITCH_COMMENT) && walker->comment)
00503             if (!regexec(regexp,walker->comment,1,&offsets,0))
00504                 match |= KEY_SWITCH_OWNER;
00505         
00506         if (match) return match;
00507     }
00508     
00509     if (parentName) free(parentName);
00510     ks->cursor=init;
00511 #endif
00512     return 0;
00513 }
00514 
00515 
00546 Key *ksLookupByValue(KeySet *ks, const char *value, unsigned long options) {
00547     Key *init=0;
00548     Key *current=0;
00549     size_t size=0;
00550     
00551     size=strblen(value);
00552     init=ks->cursor;
00553     
00554     while ((current=ksNext(ks))) {
00555         if (current->data == value) return current;
00556         
00557         if (size != current->dataSize) continue;
00558         
00560         if (KEY_TYPE_BINARY<= current->type && current->type < KEY_TYPE_STRING)
00561             continue;
00562         
00563         if ((current->data && value)) {
00564             if ((options & KDB_O_NOCASE) && 
00565                 !strcasecmp(current->data,value)) return current;
00566             else if (!strcmp(current->data,value)) return current;
00567         }
00568     }
00569     
00570     /* reached end of KeySet */
00571     ks->cursor=init;
00572     
00573     return 0;
00574 }
00575 
00576 
00577 
00596 Key *ksLookupByBinaryValue(KeySet *ks, void *value, size_t size,
00597         unsigned long options) {
00598     Key *init=0;
00599     Key *current=0;
00600     
00601     init=ks->cursor;
00602     
00603     while ((current=ksNext(ks))) {
00604         if (current->data == value) return current;
00605         
00606         if (size != current->dataSize) continue;
00607     
00609         if ((current->data && value) && 
00610                 !memcmp(current->data,value,size)) return current;
00611     }
00612     
00613     /* reached end of KeySet, so reset cursor */
00614     ks->cursor=init;
00615     
00616     return 0;
00617 }
00618 
00619 
00620 
00621 
00622 
00623 
00624 
00625 /******************************************* 
00626  *           Filling up KeySets            *
00627  *******************************************/
00628 
00629  
00645 ssize_t ksInsert(KeySet *ks, Key *toInsert) {
00646     toInsert->next=ks->start;
00647     ks->start=toInsert;
00648     if (!ks->end) ks->end=toInsert;
00649     return ++ks->size;
00650 }
00651 
00652 
00665 Key *ksPop(KeySet *ks) {
00666     Key *key=0;
00667     
00668     if (ks->start) {
00669         key=ks->start;
00670         ks->start=key->next;
00671         if (ks->end == key) ks->end=0;
00672         ks->size--;
00673         if (ks->cursor == key) ks->cursor=0;
00674     }
00675     
00676     return key;
00677 }
00678 
00679 
00692 Key *ksPopLast(KeySet *ks) {
00693     Key *key=0;
00694     Key *prev=0;
00695     
00696     /* When ks is empty: */
00697     if (ks->end == 0) return 0;
00698     
00699     /* When ks has only one member: */
00700     if (ks->start == ks->end) {
00701         key=ks->end;
00702         ks->cursor=ks->start=ks->end=0;
00703         ks->size=0;
00704         
00705         return key;
00706     }
00707     
00708     prev=ks->start;
00709     while (prev->next!=ks->end) prev=prev->next;
00710     
00711     key=ks->end;
00712     prev->next=0;
00713     ks->end=prev;
00714     ks->size--;
00715     if (ks->cursor == key) ks->cursor=0;
00716     
00717     return key;
00718 }
00719 
00720 
00732 ssize_t ksInsertKeys(KeySet *ks, KeySet *toInsert) {
00733     if (toInsert->size) {
00734         toInsert->end->next=ks->start;
00735         ks->start=toInsert->start;
00736 
00737         ks->size+=toInsert->size;
00738 
00739         /* Invalidate the old KeySet */
00740         toInsert->start=toInsert->end=toInsert->cursor=0;
00741         toInsert->size=0;
00742     }
00743     return ks->size;
00744 }
00745 
00746 
00747 
00762 ssize_t ksAppend(KeySet *ks, Key *toAppend) {
00763     toAppend->next=0;
00764     if (ks->end) ks->end->next=toAppend;
00765     if (!ks->start) ks->start=toAppend;
00766     ks->end=toAppend;
00767     return ++ks->size;
00768 }
00769 
00770 
00771 
00784 ssize_t ksAppendKeys(KeySet *ks, KeySet *toAppend) {
00785     if (toAppend->size) {
00786         if (ks->end) {
00787             ks->end->next=toAppend->start;
00788             ks->end=toAppend->end;
00789         } else {
00790             ks->end=toAppend->end;
00791             ks->start=toAppend->start;
00792         }
00793 
00794         ks->size+=toAppend->size;
00795         
00796         /* Invalidate the old KeySet */
00797         toAppend->start=toAppend->end=toAppend->cursor=0;
00798         toAppend->size=0;
00799     }
00800     return ks->size;
00801 }
00802 
00803 
00804 
00805 
00806 
00807 
00808 
00809 
00810 
00811 
00812 /******************************************* 
00813  *    Other operations                     *
00814  *******************************************/
00815 
00816 
00879 int ksCompare(KeySet *ks1, KeySet *ks2, KeySet *removed) {
00880     int flagRemoved=1;
00881     Key *ks1Cursor=0;
00882     Key *ks2Cursor=0;
00883 
00884     Key *ks1PrevCursor=0;
00885 
00886     ks1Cursor=ks1->start;
00887     while (ks1Cursor) {
00888         Key *ks2PrevCursor=0;
00889         flagRemoved=1;
00890         
00891         for (ks2Cursor=ks2->start; ks2Cursor; ks2Cursor=ks2Cursor->next) {
00892             uint32_t flags=keyCompare(ks1Cursor,ks2Cursor);
00893             
00894             if (!(flags & (KEY_SWITCH_NAME | KEY_SWITCH_DOMAIN))) {
00895                 /* Comparing fullname-equal keys */
00896                 flagRemoved=0; /* key was not removed */
00897                     
00898                 /* First remove from ks2 */
00899                 if (ks2PrevCursor) ks2PrevCursor->next=ks2Cursor->next;
00900                 else ks2->start=ks2Cursor->next;
00901                 if (ks2->end==ks2Cursor) ks2->end=ks2PrevCursor;
00902                 ks2->size--;
00903                     
00904                 /* Now check if we still can find differences between keys, but
00905                  * we are not interested in the NEEDSYNC flag: he allone is not
00906                  * enough to determine a key as different */
00907                 if (flags & ~KEY_SWITCH_NEEDSYNC) {
00908                     /* keys are different. Transfer to ks1. */
00909                     
00910                     /* Put in ks1 */
00911                     if (ks1PrevCursor) ks1PrevCursor->next=ks2Cursor;
00912                     else ks1->start=ks2Cursor;
00913                     if (ks1->end==ks1Cursor) ks1->end=ks2Cursor;
00914                     ks2Cursor->next=ks1Cursor->next;
00915                     
00916                     /* delete old version */
00917                     keyDel(ks1Cursor);
00918                     
00919                     /* Reset pointers */
00920                     ks1Cursor=ks2Cursor;
00921                 } else {
00922                     /* Keys are identical. Delete ks2's key. */
00923 
00924                     /* Delete ks2Cusrsor */
00925                     keyDel(ks2Cursor);
00926                 }
00927                 /* Don't need to walk through ks2 anymore */
00928                 break;
00929             }
00930             ks2PrevCursor=ks2Cursor;
00931             
00932         } /* ks2 iteration */
00933         
00934         if (flagRemoved) {
00935             /* This ks1 key was not found in ks2 */
00936             /* Transfer it from ks1 to removed */
00937             
00938             /* Remove from ks1 */
00939             if (ks1PrevCursor) ks1PrevCursor->next=ks1Cursor->next;
00940             else ks1->start=ks1Cursor->next;
00941             if (ks1->end==ks1Cursor) ks1->end=ks1PrevCursor;
00942             ks1->size--;
00943 
00944             /* Append to removed */
00945             ksAppend(removed,ks1Cursor);
00946             
00947             /* Reset pointers */
00948             if (ks1PrevCursor) ks1Cursor=ks1PrevCursor->next;
00949             else ks1Cursor=ks1->start;
00950         } else {
00951             ks1PrevCursor=ks1Cursor;
00952             ks1Cursor=ks1Cursor->next;
00953         }
00954     } /* ks1 iteration */
00955     
00956     /* Now transfer all remaining ks2 keys to ks1 */
00957     ksAppendKeys(ks1,ks2);
00958     
00959     return 0;
00960 }
00961 
00962 
00963 
00964 
01029 ssize_t ksToStream(const KeySet *ks, FILE* stream, unsigned long options) {
01030     size_t written=0;
01031     Key *key=0;
01032     char *codeset;
01033 
01034     /* If nl_langinfo or the CODESET info isn't available we default to UTF-8 
01035      * This might not be a very good default, but I'm not sure how else to do it*/
01036 #if defined(HAVE_NL_LANGINFO) && defined(CODESET)
01037     codeset = nl_langinfo(CODESET);
01038 #else
01039     codeset = "UTF-8";
01040 #endif
01041     if (options & KDB_O_XMLHEADERS) {
01042         written+=fprintf(stream,"<?xml version=\"1.0\" encoding=\"%s\"?>\n",
01043             codeset);
01044         written+=fprintf(stream,
01045             "\n\n<!-- Generated by Elektra API. Total of %d keys. -->\n\n\n\n",ks->size);
01046         
01047         written+=fprintf(stream,"<keyset xmlns=\"http://www.libelektra.org\"\n\
01048         xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\"\n\
01049         xsi:schemaLocation=\"http://www.libelektra.org elektra.xsd\"");
01050         
01051         /* written+=fprintf(stream,
01052             "<!DOCTYPE keyset PUBLIC \"-//Avi Alkalay//DTD Elektra 0.1.0//EN\" \"http://elektra.sf.net/dtd/elektra.dtd\">\n\n\n"); */
01053     } else written+=fprintf(stream,"<keyset");
01054 
01055     if (options & KDB_O_HIER) {
01056         /*
01057         Key *smalest=0;
01058         size_t ssmalest=0;
01059 
01060         for (key=ks->start; key; key=key->next) {
01061             if (smalest) {
01062                 size_t size=strblen(key->key);
01063                 if (size<ssmalest) {
01064                     smalest=key;
01065                     ssmalest=size;
01066                 }
01067             } else {
01068                 smalest=key;
01069                 ssmalest=strblen(smalest->key);
01070             }
01071         }
01072     */
01073         
01074         char commonParent[800];
01075 
01076         ksGetCommonParentName(ks,commonParent,sizeof(commonParent));
01077     
01078         if (commonParent[0]) {
01079             written+=fprintf(stream,"\n\n        parent=\"%s\">\n\n\n",
01080                 commonParent);
01081             for (key=ks->start; key; key=key->next)
01082                 written+=keyToStreamBasename(key,stream,commonParent,0,options);
01083         } else {
01084             written+=fprintf(stream,">\n\n\n");
01085             for (key=ks->start; key; key=key->next)
01086                 written+=keyToStream(key,stream,options);
01087         }
01088         
01089     /*
01090         if (keyIsUser(smalest) && (options & KDB_O_FULLNAME)) {
01091             char buffer[800];
01092             keyGetFullName(smalest,buffer,sizeof(buffer));
01093             written+=fprintf(stream,"\n\n        parent=\"%s\"",buffer);
01094         } else
01095             written+=fprintf(stream,"\n\n        parent=\"%s\"",smalest->key);
01096     
01097         
01098         written+=fprintf(stream,">\n\n\n");
01099     */
01100     } else { /* No KDB_O_HIER*/
01101         written+=fprintf(stream,">\n\n\n");
01102         for (key=ks->start; key; key=key->next)
01103             written+=keyToStream(key,stream,options);
01104     }
01105     
01106     written+=fprintf(stream,"</keyset>\n");
01107     return written;
01108 }
01109 
01110 
01111 
01112 
01148 ssize_t ksGetCommonParentName(const KeySet *ks,char *returnedCommonParent,const size_t maxSize) {
01149     ssize_t parentSize=0;
01150     Key *current=0;
01151 
01152     if (keyGetNameSize(ks->start) > maxSize) {
01153         errno=KDB_RET_TRUNC;
01154         returnedCommonParent[0]=0;
01155         return -1;
01156     }
01157 
01158     strcpy(returnedCommonParent,ks->start->key);
01159     parentSize=strblen(returnedCommonParent);
01160 
01161     while (*returnedCommonParent) {
01162         current=ks->start->next;
01163         while (current) {
01164             /* Test if a key desn't match */
01165             if (memcmp(returnedCommonParent,current->key,parentSize-1)) break;
01166             current=current->next;
01167         }
01168         if (current) {
01169             /* some key failed to be a child */
01170             /* parent will be the parent of current parent... */
01171             char *delim=0;
01172 
01173             if ((delim=strrchr(returnedCommonParent,RG_KEY_DELIM))) {
01174                 *delim=0;
01175                 parentSize=strblen(returnedCommonParent);
01176             } else {
01177                 *returnedCommonParent=0;
01178                 parentSize=0;
01179             }
01180         } else {
01181             /* All keys matched (current==0) */
01182             /* We have our common parent to return in commonParent */
01183             return parentSize;
01184         }
01185     }
01186     return parentSize; /* if reached, will be zero */
01187 }
01188 
01189 
01190 
01191 
01192 
01198 void ksSort(KeySet *ks) {
01199     Key **keys = NULL;
01200     Key *cursor;
01201     size_t c=0;
01202 
01203     if (ks->size) {
01204         keys = (Key **)calloc(ks->size, sizeof(Key *));
01205 
01206         for (cursor=ks->start; cursor; cursor=cursor->next, c++)
01207             keys[c]=cursor;
01208 
01209         qsort(keys,ks->size,sizeof(Key *),keyCompareByName);
01210 
01211         ks->start=cursor=keys[0];
01212         for (c=1; c<ks->size; c++) {
01213             cursor->next=keys[c];
01214             cursor=cursor->next;
01215         }
01216         cursor->next=0;
01217         ks->end=cursor;
01218         free(keys);
01219     }
01220 }
01221 
01222 
01223 
01224 
01225 
01226 
01239 int ksInit(KeySet *ks) {
01240     ks->start=ks->end=ks->cursor=0;
01241     ks->size=0;
01242     
01243     return 0;
01244 }
01245 
01246 
01258 int ksClose(KeySet *ks) {
01259     if (ks->size) {
01260         while (ks->size) {
01261             Key *destroyer=ks->start;
01262             ks->start=destroyer->next;
01263             keyDel(destroyer);
01264             --ks->size;
01265         }
01266     }
01267     ks->cursor=ks->end=ks->start;
01268     return 0;
01269 }
01270 
01271 
01272 
01273 
01274 
01275 

Generated on Sun Mar 25 21:37:09 2007 for Elektra Project by  doxygen 1.5.1