a99  V32.6
allegro Windows Hauptprogramm
 Alle Klassen Dateien Funktionen Variablen Typdefinitionen Aufzählungen Aufzählungswerte Makrodefinitionen
aiinskey.cpp
gehe zur Dokumentation dieser Datei
1 // aiinskey.c/.cpp : Indexeintrag einfuegen
2 // 1991-11-14 / 1995 / 2011
3 // Copyright 2011 Universitätsbibliothek Braunschweig, more see bottom
4 
5 
6 #include "includes.h" // einige Konventionen
7 #include "ai-const.h" // allg. Konstanten
8 #include "aisetup.h" // allg. Einstellungen
9 #include "aierrors.h" // Fehlernummern
10 #include "aistruc.h" // Strukturen
11 #include "aiglobal.h" // glob. Variablen
12 #include "aideclar.h" // Funktionsdeklarationen
13 
14 STATC CHAR kyarea[aiMXLG]; // Hilfsfeld f. einen Indexeintrag
15 
16 /* --------------------------------------------------------------------
17  aiEntIn ordnet den bei srcval stehenden String in das Register rgnum ein,
18  dabei wird airecnum als Satznummer eingetragen.
19  Return: 0 bei Erfolg
20  2 Schl. mit airecnum schon vorhanden, keine Aenderung im Index
21  >2 Fehler
22 */
23 
24 SHORT aiEntIn(SHORT rgnum, CHAR *srcval, PTRL airecnum, SHORT aiaddt)
25 // bei allegro ist stets aiaddt == 0 (add type 0 : volle Knoten in 2 halbe teilen)
26 {
27  CHAR *aikey;
28  aiINDX *aixf;
29  aiTRSTR *aibloc;
30  SHORT ai_nump;
31  STATC RECNR knot;
32 
33 
34  aiG_fhln = 0; // Fehlercode wird dann in der Funktion gesetzt
35  if((aixf = aichktf(rgnum)) == 0) // ist rgnum gueltige Registernummer?
36  return(aiG_fhln);
37  if(updted(aixf)) // read-only? Dann geht's nicht
38  return(aiG_fhln);
39  if(!airecnum) // Satznr muss positiv sein
40  return(aierro(FHLNULF));
41 
42  aicopy((aikey = aiG_dpky),srcval,aixf->kylgth);
43  setdpl(aikey,aixf,&airecnum);
44 
45  aiG_last = aiG_beb = 0;
46 
47 #ifndef aiIMMED
48  if(!(knot = aigrtrot(aixf))) // Leerer Baum oder aigrtrot-Fehler
49  {
50  if(aiG_fhln || aichkupt(aixf) ||
51  adwurz(aixf,airecnum,aiDRNULL,aikey) ||
52  updhd(aixf,(PTRL) 1))
53  return(aiG_fhln);
54  return(FHLNUL);
55  }
56 #else
57  if(!(knot = aigrtrot(aixf)))
58  {
59  if(aiG_fhln || aichkupt(aixf))
60  return(aiG_fhln);
61  else if((ai_nump = adwurz(aixf,airecnum,aiDRNULL,aikey)) == -1)
62  knot = aigrtrot(aixf);
63  else if(ai_nump || updhd(aixf,(PTRL) 1))
64  return(aiG_fhln);
65  else
66  return(FHLNUL);
67  }
68 
69 #endif
70 
71  while(knot) // Baum durchwandern bis Knoten lfflg gefunden
72  {
73  aiG_last = knot;
74  if((aibloc = aiknoget(knot,aixf)) == 0)
75  return(aiG_fhln);
76  if(aibloc->lfflg == BLATT)
77  break;
78 
79  if((ai_nump = aifkno(aibloc,aikey,'L')) != -1)
80  {
81  if(ai_nump == -2)
82  aiAbort(218);
83  if(++aiG_beb >= aiTRMAX)
84  aiAbort(240);
85  aiG_down[aiG_beb] = knot;
86  knot = aidatkno(aibloc,ai_nump);
87  }
88  else
89  knot = aibloc->rgtkey;
90  }
91 
92  if(!knot) // => no lfflg knot found
93  aiAbort(219);
94 
95 #ifdef aiIMMED
96  if(aiLok(knot,aixf) ||
97  (aibloc = mvrght(aikey,aixf,aiknoget(knot,aixf))) == 0)
98 #else
99  if(aiLok(knot,aixf) ||
100  (aibloc = mvrght(aikey,aixf,aibloc)) == 0)
101 #endif
102  return(aiG_fhln);
103  if(!aiG_cpr)
104  {
105  if(aiUnlk(aibloc->knotid,aixf))
106  return(aiG_fhln);
107  return(aierro(FHLKEXI)); // den Schl. gibt's schon, kein Problem
108  }
109 
110  if(aichkupt(aixf) || aiinsrt(aibloc,aixf,aikey,airecnum,aiaddt) ||
111  updhd(aixf,(PTRL) 1))
112  return(aiG_fhln);
113  return(FHLNUL);
114 }
115 
116 // --------------------
117 // Schluessel einfuegen
118 
119 SHORT aiinsrt(aiTRSTR *aibloc, aiINDX *aixf, CHAR *aikey, PTRL pntr, SHORT aiaddt)
120 
121 {
122  SHORT temp,spltel;
123  uSHORT temp2;
124  RECNR knot,oldknot;
125  aiTRSTR *neW;
126  CHAR *tp;
127 
128 
129  SHORT krest,mtst,eflgth;
130  SHORT kinc = 0;
131 
132  kinc++;
133  kinc++;
134 
135 again:
136  eflgth = aixf->kylgth + kinc;
137  if(aibloc->rglfflg & AI_NRML)
138  eflgth += sizeof(PTRL);
139 
140  temp = aibloc->ckyv + 1;
141 
142  // Fuer lfflg-Knoten, wenn schon voll, dann den hoechsten Schl. sichern
143  // (lfflg enth. mxkeys-1 Schl., ausser dem hoechsten)
144 
145 
146  if(aibloc->lfflg == BLATT)
147  aicopy(kyarea,aidathi(aibloc),aibloc->kylg);
148 
149  if(!aiG_pos || aiG_pos > aibloc->ckyv)
150  aiG_cpr = 0;
151  kyins(aibloc,aikey,pntr);
152  temp2 = aibloc->ckyb;
153 
154  if(temp2 <= aibloc->mxbyt)
155  {
156  knot = aibloc->knotid;
157  if(savekn(aibloc,temp) || aiUnlk(knot,aixf))
158  return(aiG_fhln);
159  return(FHLNUL);
160  }
161 
162  if((neW = nwknot(aixf,&aiG_newk,NO)) == 0)
163  return(aiG_fhln);
164  if(aibloc->lfflg == BLATT)
165  {
166  neW->mxkeys = aixf->maxkv;
167  neW->mxbyt = aixf->kylgmx;
168  neW->rglfflg = AI_DBLY;
169  }
170  else
171  {
172  neW->mxkeys = aixf->maxkn;
173  neW->mxbyt = aixf->kybmx;
174  neW->rglfflg = AI_DBLN;
175  }
176  if(aiaddt == aiRGAD)
177  spltel = temp / 2;
178  else if(aiaddt == aiINCA)
179  spltel = 6 * temp / 7;
180  else
181  spltel = temp / 7 + 1;
182  tp = aidatpoi(aibloc,spltel);
183 
184  // fstbyt zaehlt bis zu einem aiG_ky, der nicht passt, dann diesen pruefen
185  // aiINCA kann bei Komprimierung und fehlerhafter Ordnung Probleme machen
186 
187  {
188  if((mtst = aibloc->fstbyt + aibloc->realg) > aibloc->mxbyt)
189  {
190  spltel = 1;
191  krest = aibloc->mxbyt - eflgth;
192  }
193  else if(mtst < (krest = (2*eflgth - sizeof(PTRL) -kinc)))
194  {
195  spltel++;
196  }
197  else
198  krest = 0;
199  if(krest)
200  {
201  while(spltel < temp)
202  {
203  tp = aidatpoi(aibloc,spltel);
204  if((aibloc->fstbyt + aibloc->realg) >= krest)
205  break;
206  spltel++;
207  }
208  }
209  }
210 
211  aicopy(aiG_upky,tp,aibloc->kylg);
212 
213  pntr = aipoidor(aibloc,spltel + 1);
214  aiG_cpr = aiG_cpra = temp2 = 0;
215  if(!aibloc->cprv)
216  tp = aibloc->knptr + aibloc->fstbyt;
217  else
218  tp = aibloc->kyxpns;
219  if(aibloc->rglfflg & AI_NRML)
220  temp2 = sizeof(PTRL);
221  kyins(neW,tp + temp2,pntr);
222  temp2 = aibloc->fstbyt + aibloc->realg;
223  aicopy(neW->knptr + neW->ckyb,aibloc->knptr + temp2,
224  aibloc->ckyb - temp2);
225  neW->ckyb += (aibloc->ckyb - temp2);
226  aibloc->ckyb = aibloc->fstbyt;
227  aibloc->fstbyt = aibloc->realg = aibloc->kypst = 0;
228 
229 
230  if(aibloc->lfflg == BLATT) // hoechsten Schl. setzen
231  {
232  aicopy(aidathi(neW),kyarea,aibloc->kylg);
233 
234  // aiG_upky ist der hoechste Schl. des alten Knotens
235  aicopy(aidathi(aibloc),aiG_upky,aibloc->kylg);
236  }
237 
238  neW->rgtkey = aibloc->rgtkey;
239  oldknot = aibloc->knotid;
240  if((neW->lfflg = aibloc->lfflg) == BLATT)
241  neW->lftkey = oldknot;
242 
243  aibloc->rgtkey = aiG_newk;
244  if(savekn(neW,temp - spltel) || savekn(aibloc,spltel))
245  return(aiG_fhln);
246  if(neW->rgtkey && neW->lfflg == BLATT)
247  {
248  if(aiLok((RECNR) neW->rgtkey,aixf) ||
249  (aibloc = aiknoget((RECNR) neW->rgtkey,aixf)) == 0)
250  return(aiG_fhln);
251  aibloc->lftkey = aiG_newk;
252  if(savekn(aibloc,aibloc->ckyv) || aiUnlk((RECNR) neW->rgtkey,aixf))
253  return(aiG_fhln);
254  }
255 
256  aikey = aiG_upky;
257  pntr = oldknot;
258  if((knot = aiG_down[aiG_beb--])) // Vorgaengerknoten vorh., wiederholen
259  {
260  if(aiLok(knot,aixf) ||
261  (aibloc = mvrght(aikey,aixf,aiknoget(knot,aixf))) == 0)
262  return(aiG_fhln);
263  if(aidatkno(aibloc,aiG_pos) != oldknot)
264  /*
265  hier wurde anscheinend ein vorzeitig beendeter Knotensplit
266  gefunden. Der Vorgaenger hat keinen kompl. Satz von Zeigern
267  Bewegung nach rechts vermeidet Absturz
268  */
269  pntr = aidatkno(aibloc,aiG_pos);
270 
271  if(aiUnlk(oldknot,aixf))
272  return(aiG_fhln);
273 
274  aicopy((char *)(aibloc->knptr + aibloc->fstbyt),(char *)&aiG_newk,sizeof(PTRL));
275  if(aibloc->cprv)
276  aicopy((char *)aibloc->kyxpns,(char *)&aiG_newk,sizeof(PTRL));
277 #ifdef HITOLO
278  ai_exchg((CHAR*)aibloc->knptr + aibloc->fstbyt,sizeof(PTRL));
279  if(aibloc->cprv)
280  ai_exchg((CHAR *)aibloc->kyxpns,sizeof(PTRL));
281 #endif
282  goto again;
283  }
284  else // wurzel erzeugen
285  {
286  if(aiUnlk(oldknot,aixf) ||
287  adwurz(aixf,pntr,(PTRL) aiG_newk,aiG_upky))
288  return(aiG_fhln);
289  }
290  return(FHLNUL);
291 }
292 
293 
294 /* --------------------------------------------------------------------
295  Neue Wurzel zum Baum hinzufuegen.
296  lpntr , rpntr sind linker bzw. rechter Zeiger zum Schl. aikey
297 */
298 
299 SHORT adwurz(aiINDX *aixf, PTRL lpntr, PTRL rpntr, CHAR *aikey)
300 
301 {
302  CHAR *tp;
303  aiTRSTR *neW;
304  SHORT i;
305 
306 
307  /* Wenn letzter Parameter in nwknot() == YES, wird die Kopfsperre
308  aus nwknot() nicht von nwknot freigegeben, wenn nwknot() erfolgreich.
309  Wenn zwei oder mehr Prozesse nwknot() aufrufen, um einen frischen
310  Knoten zu erhalten, wird nur der erste einen Wert != 0 erhalten.
311  Die anderen Aufrufe von nwknot() liefern aiG_fhln=-1
312  um an aiEntIn() zu melden, die normale adwurz() zu uebergehen.
313  */
314  if((neW = nwknot(aixf,&aiG_newk,rpntr ? NO : YES)) == 0)
315  return(aiG_fhln);
316 
317  if(rpntr) // dann nicht links; naechsthoeheren Schl. zufuegen
318  {
319  neW->lfflg = NBLATT;
320  neW->mxkeys = aixf->maxkn;
321  neW->mxbyt = aixf->kybmx;
322  neW->rglfflg = AI_DBLN;
323  }
324  else // lfflg wurz (frischer Baum)
325  {
326  neW->lfflg = BLATT;
327  neW->mxkeys = aixf->maxkv;
328  neW->mxbyt = aixf->kylgmx;
329  neW->rglfflg = AI_DBLY;
330  tp = aidathi(neW);
331  }
332 
333  aiG_cpr = aiG_cpra = 0;
334  kyins(neW,aikey,lpntr);
335  if(neW->lfflg == NBLATT)
336  tp = kyarea;
337 
338  /* Wenn weitere Schl.typen aindex erweitern sollen, muss man die
339  folgenden Abschnitte erweitern, um zu jedem Schluesseltyp den
340  hoechstmoeglichen Eintrag zu konstruieren, beginnend mit dem
341  Byte, auf das tp zeigt.
342  */
343  i = aixf->kylgth;
344 
345 
346  while(i-- > 0) *tp++ = 0xff;
347 
348 
349  // Ende der Konstruktion des hoechstmoeglichen Werts
350 
351 
352  if(rpntr)
353  {
354  neW->ckyv = i = 2;
355  aidatpoi(neW,1); // letzte Position setzen
356  kyins(neW,kyarea,rpntr);
357  }
358  else
359  i = 1;
360  if(savekn(neW,i))
361  return(aiG_fhln);
362 
363 #ifdef aiIMMED
364  if(rpntr && (aiLok(aiNODNUL,aixf) || aiprefrd(aixf - aixf->regnm)))
365  return(aiG_fhln);
366 #endif
367 
368  aixf->wurz = aiG_newk;
369 
370 #ifdef aiFLAX
371  // keine Aktion noetig
372 #else
373  if(aiprefwr(aixf))
374  return(aiG_fhln);
375 #ifdef aiIMMED
376  if(aiUnlk(aiNODNUL,aixf))
377  return(aiG_fhln);
378 #endif
379 #endif
380 
381  return(FHLNUL);
382 }
383 
384 
385 // ------------------------
386 // Naechsten Knoten holen
387 
388 
389 aiTRSTR *nwknot(aiINDX *aixf, RECNR *pknot, SHORT fresh)
390 {
391  aiTRSTR *bloc;
392 
393 
394 #ifndef aiIMMED
395  aiDATEI *ainmb;
396 #endif
397 
398 
399 #ifdef aiIMMED
400  if(aiLok(aiNODNUL,aixf) || aiprefrd(aixf - aixf->regnm))
401  return(0);
402  if(fresh == YES && aixf->wurz)
403  {
404  /* Es hat schon jemand einen Baum zugefuegt
405  Sende Signal an adwurz um Neuerzeugung zu umgehen und normale
406  Einfuegung zu erledigen.
407  */
408  aiUnlk(aiNODNUL,aixf);
409  aiG_fhln = -1;
410  return(0);
411  }
412 #endif
413 
414 #ifndef aiIMMED
415  ainmb = aixf - aixf->regnm;
416  if(*pknot = ainmb->rmstk)
417  {
418  if((bloc = aiknoget(*pknot,ainmb)) == 0)
419  return(0);
420  if(bloc->lftkey != -1L)
421  {
422  aiG_fhln = FHLLNKF;
423  return(0);
424  }
425  ainmb->rmstk = bloc->rgtkey;
426  goto bloc_return;
427  }
428 #endif
429 
430  if(aixf->flgcls == aiVTCL)
431  aiAbort(225);
432  else if(!(*pknot = aidataxf(aixf,aixf->knotsz)))
433  {
434 #ifdef aiIMMED
435  aiUnlk(aiNODNUL,aixf);
436 #endif
437  return(0);
438  }
439 
440 #ifdef aiFLAX
441  // no action if single-user
442 #else
443  if(aiprefwr(aixf))
444  return(0);
445 #ifdef aiIMMED
446  // Kopf nicht aktualisieren, falls ganz neuer Knoten
447  if(fresh == NO && aiUnlk(aiNODNUL,aixf))
448  return(0);
449 #endif
450 #endif
451 
452  if((bloc = aidatlru(0)) == 0)
453  return(0);
454 bloc_return:
455  bloc->ckyv = bloc->ckyb = bloc->fstbyt = bloc->realg = bloc->kypst = 0;
456  bloc->cprv = aixf->ftyf;
457  bloc->kynum = aixf->usrfn;
458  bloc->kylg = aixf->kylgth;
459  bloc->knotid = *pknot;
460  bloc->coruf = 'y';
461  bloc->lftkey = bloc->rgtkey = aiNODNUL;
462  bloc->regnr = aixf->regnm;
463  return(bloc);
464 }
465 
466 void kyins(aiTRSTR *bp, CHAR *ip, PTRL pntr)
467 {
468  SHORT kl,kls,cntmov,cntmov2,cntpfx,cntpfx2,cntsfx,cntsfx2;
469  SHORT n,poff;
470  CHAR *kp;
471  CHAR *tp;
472  SHORT i;
473 
474  if(aiG_cpr > 0 || aiG_cpra < 0)
475  aiAbort(235);
476 
477  kp = ip; // ip f. evtl. spaeter aufbew.
478  kl = kls = bp->kylg;
479  if(bp->rglfflg == AI_DBLY || bp->rglfflg == AI_DBLN)
480  kls -= sizeof(PTRL);
481 
482 // Zaehler der sich wiederholenden Endstuecke
483 
484  cntsfx = i = 0;
485  tp = kp + kls;
486  while(i++ < kls && *--tp == 0)
487  cntsfx++;
488 
489 // Anfangsstueck-Zaehler
490 
491  n = kls - cntsfx;
492 
493  if((cntpfx = aiG_cpra - 1) > 0)
494  {
495  if(cntpfx > n)
496  cntpfx = n;
497  if( (cntpfx + aiG_sufc) > kls)
498  cntpfx = kls - aiG_sufc;
499  kp += cntpfx;
500  n -= cntpfx;
501  }
502  else
503  cntpfx = 0;
504 
505 // wird das Ende von aibloc verlaengert bzw. leerer aibloc?
506 
507  if(aiG_cpr == 0) // defaults setzen
508  tp = bp->knptr + bp->fstbyt + bp->realg;
509  else
510  {
511 
512 // Einfuegung im Innern oder am Anfang
513 
514  aiG_cpr = -aiG_cpr;
515  cntmov = n + kl - kls;
516 
517  cntmov++;
518  cntmov++;
519  // ist nachfolgender Wert weiter komprimiert? verschieben
520 
521  if(bp->rglfflg & AI_NRML)
522  cntmov += (poff = sizeof(PTRL));
523  else
524  poff = 0;
525 
526  tp = bp->knptr + bp->fstbyt;
527 
528  cntpfx2 = *(tp + poff) & 0x00ff;
529  cntsfx2 = *(tp + poff + 1) & 0x00ff;
530 
531  if(--aiG_cpr + cntsfx2 > kls)
532  aiG_cpr = kls - cntsfx2;
533  while((aiG_cpr + cntsfx) > kls)
534  if(ip[aiG_cpr - 1] == 0)
535  aiG_cpr--;
536  else
537  break;
538  if(aiG_cpr <= cntpfx2)
539  shiftr(cntmov,bp,bp->fstbyt);
540  else
541  {
542  if((cntmov2 = aiG_cpr - cntpfx2) > cntmov)
543  aiAbort(236);
544  bp->realg -= cntmov2;
545  *(tp + cntmov2 + poff) = (CHAR)aiG_cpr;
546  *(tp + cntmov2 + poff + 1) = (CHAR)cntsfx2;
547  if(poff)
548  {
549  shiftl(cntmov2,bp,bp->fstbyt + poff +
550  cntmov2);
551  bp->ckyb -= cntmov2;
552  shiftr(cntmov,bp,bp->fstbyt);
553  }
554  else
555  {
556  shiftr(cntmov - cntmov2,bp,
557  bp->fstbyt + cntmov2);
558  bp->ckyb -= cntmov2;
559  }
560  }
561 
562  tp = bp->knptr + bp->fstbyt;
563  bp->kypst++;
564  bp->fstbyt += cntmov;
565  }
566 
567  // Bytes an die richtige Stelle
568 
569  if(bp->rglfflg & AI_NRML)
570  {
571 #ifdef HITOLO
572  ai_exchg((CHAR *)&pntr,sizeof(PTRL)); // $$951222
573 #endif
574  aicopy((char *)tp,(char *)&pntr,sizeof(PTRL));
575  tp += sizeof(PTRL);
576  bp->ckyb += sizeof(PTRL);
577  }
578 
579  bp->ckyb++;
580  *tp++ = (CHAR)cntpfx;
581  bp->ckyb++;
582  *tp++ = (CHAR)cntsfx;
583 
584  aicopy(tp,kp,n);
585  bp->ckyb += n;
586 
587  if(kls < kl)
588  {
589  bp->ckyb += sizeof(PTRL);
590  aicopy(tp + n,ip + kls,sizeof(PTRL));
591  }
592 
593 }
594 
595 /*
596  Copyright 2011 Universitätsbibliothek Braunschweig
597 
598  Licensed under the Apache License, Version 2.0 (the "License");
599  you may not use this file except in compliance with the License.
600  You may obtain a copy of the License at
601 
602  http://www.apache.org/licenses/LICENSE-2.0
603 
604  Unless required by applicable law or agreed to in writing, software
605  distributed under the License is distributed on an "AS IS" BASIS,
606  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
607  See the License for the specific language governing permissions and
608  limitations under the License.
609 */
610