Back to index

lightning-sunbird  0.9+nobinonly
gs.c
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either of the GNU General Public License Version 2 or later (the "GPL"),
00026  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 
00038 
00039 // 39204897
00040 #include <stdlib.h>
00041 #include <string.h>
00042 #include <stdio.h>
00043 #include <ctype.h>
00044 #include "rdf-int.h"
00045 #include "gs.h"
00046 
00047 
00048 
00049 typedef struct _TrieNodeStruct {
00050     char c;
00051     struct _TrieNodeStruct* child;
00052     struct _TrieNodeStruct* next;
00053     struct _TrieTargetStruct* targets;
00054 } TrieNodeStruct;
00055 
00056 typedef TrieNodeStruct* TNS;
00057 
00058 typedef struct _TrieTargetStruct {
00059     RDF_Resource label;
00060     RDF_Resource target;
00061     struct _TrieTargetStruct* next;
00062     RDFT db;
00063 } TrieTargetStruct;
00064 
00065 typedef TrieTargetStruct* TTS;
00066 
00067 static TNS gRootNode = 0;
00068 
00069 int 
00070 addTarget (RDFT db, TNS node, RDF_Resource label, RDF_Resource targetNode) {
00071   TTS target ;
00072   int n = 0;
00073   /*  for (target = node->targets; target != null; target = target->next) {
00074     if (target->target == targetNode) return 0;
00075     n++;
00076   } */
00077   target = (TTS) fgetMem(sizeof(TrieTargetStruct));
00078   target->next = node->targets;
00079   node->targets = target;
00080   target->label = label;
00081   target->target = targetNode;
00082   target->db = db;
00083   return n;
00084 }
00085 
00086 TNS
00087 findChildOfChar (TNS node, char c) {
00088   TNS ch = node->child;
00089   char c1 = tolower(c);
00090   int n = 0;
00091   while (ch) {
00092     if (c1 == ch->c) return ch;
00093     ch = ch->next;
00094        n++;
00095   }
00096   return 0;
00097 }
00098 
00099 TNS 
00100 findChildOfString (TNS node, char* str) {
00101   size_t size = strlen(str);
00102   size_t n = 0;
00103   while (n < size) {
00104     char c = str[n++];
00105     node = findChildOfChar(node, c);
00106     if (!node) return 0;
00107   }
00108   return node;
00109 }
00110 
00111 void RDFGS_AddSearchIndex (RDFT db, char* string, RDF_Resource label, RDF_Resource target) {
00112     size_t size = strlen(string);
00113     size_t n    = 0;
00114     char* stk = 0;
00115     TNS    prev, next;
00116     if (!gRootNode) gRootNode = (TNS) getMem(sizeof(TrieNodeStruct));
00117     prev = gRootNode;
00118     next = 0;
00119     while (n < size) {
00120        char c = string[n++]; 
00121        if (!wsCharp(c) && (c != '/')) {
00122           if (!stk) stk = &string[n-1];
00123            next = (TNS) findChildOfChar(prev, c);
00124             if (!next) {
00125               next = (TNS)fgetMem(sizeof(TrieNodeStruct));
00126               next->next = prev->child;
00127               prev->child = next;
00128               next->c    = tolower(c);
00129             }
00130             prev = next;            
00131        } else if (next) {
00132            int n = addTarget(db, next, label, target);
00133             stk = 0;
00134            prev = gRootNode;
00135         next = 0;
00136        }
00137     }
00138     if (next)  {
00139               addTarget(db, next, label, target);
00140               prev = gRootNode;
00141         next = 0;
00142        }
00143 }    
00144 
00145 void
00146 countChildren (TNS node, size_t *n, size_t *m) {
00147   TNS ch;
00148   TTS tg ;
00149   if (node->targets) (*n)++;
00150   for (tg = node->targets; tg; tg = tg->next)  (*m)++;
00151   ch = node->child;
00152   while (ch) {
00153     countChildren(ch, n, m);
00154     ch = ch->next;
00155   }
00156 }
00157 
00158 void
00159 fillUpChildren (RDF_Cursor c, TNS node) {
00160   TNS ch;
00161   if (node->targets) *((TTS*)c->pdata1 + c->count++) = node->targets;
00162   ch = node->child;
00163   while (ch) {
00164     fillUpChildren(c, ch);
00165     ch = ch->next;
00166   }
00167 } 
00168   
00169            
00170 RDF_Cursor RDFGS_Search (RDFT db, char* searchString, RDF_Resource label) {
00171     RDF_Cursor c = (RDF_Cursor) getMem(sizeof(RDF_CursorStruct));
00172     size_t n = 0;
00173     size_t m = 0;
00174     c->searchString = searchString;
00175     c->s = label;
00176     c->db = db;
00177     c->pdata = findChildOfString(gRootNode, searchString);
00178     if (!c->pdata) return c;
00179     countChildren((TNS)c->pdata, &n, &m);
00180     c->pdata2 = (RDF_Resource*) getMem(sizeof(RDF_Resource) * (m+1)); 
00181     c->off1 = m;
00182     if (n > 0) {
00183       c->count = 0;
00184       c->pdata1 = getMem(sizeof(TTS) * (n+1));
00185       fillUpChildren(c, (TNS)c->pdata);
00186       c->count = 1;
00187     }
00188     if (c->pdata) c->pdata = ((TNS)c->pdata)->targets;
00189 
00190     return c;
00191 }
00192 
00193 void RDFGS_DisposeCursor (RDF_Cursor c) {
00194   if (c->pdata1) freeMem(c->pdata1);
00195   if (c->pdata2) freeMem(c->pdata2);
00196   freeMem(c);
00197 }
00198 
00199 int
00200 alreadyAdded(RDF_Resource node, RDF_Cursor c) {
00201   int n =0;
00202   while (c->pdata2[n] && (n < c->off)) {
00203     if (c->pdata2[n] == node) return 1;
00204     n++;
00205   }
00206   return 0;
00207 }
00208     
00209 RDF_Resource RDFGS_NextValue (RDF_Cursor c) { 
00210   if (!c->pdata) {
00211     return 0;
00212   } else  {
00213     TTS currentTTS = (TTS) c->pdata;
00214     while (currentTTS) {
00215       if (((!c->s) || (c->s == currentTTS->label)) && 
00216           (!alreadyAdded(currentTTS->target, c))) {
00217         RDF_Resource ans = currentTTS->target;
00218         c->pdata = currentTTS = currentTTS->next;
00219         if (!currentTTS && (c->pdata1)) { 
00220           c->pdata =  ((TTS*)c->pdata1)[c->count++];  
00221         }
00222         if (c->off < c->off1) c->pdata2[c->off++] = ans; 
00223         return ans;
00224       }       
00225       c->pdata = currentTTS =  currentTTS->next;
00226       if (!currentTTS  && (c->pdata1)) {
00227         c->pdata = currentTTS = ((TTS*)c->pdata1)[c->count++];  
00228       }
00229     }
00230   }
00231   return 0;
00232 }
00233        
00234     
00235     
00236 
00237 
00238 
00239 
00240 
00241 
00242 
00243 
00244 
00245 
00246 
00247 
00248