Module : dbase
<module title="Database system functions"
author="Jurjen Stellingwerff"
URL="www.unibase.org">
Here are the low level functions for handling the database.
<sub title="Future development">
There is room for improvements to the speed of some of this functions.
In the final version of the language some checks could be thrown out.
But meanwhile it is better to check everything twice so errors can be dealt
with.
<list heading="Known bugs">
<item name="Handling of longer indexes">
Indexes that get too long don't behave right. It a record is edited there is one
record overwritten and the old record is left. It looks like the routine to
fetch the next record is not correct for the new leafs in the index tree.
</list>
<variable name="dbstate" type="[Read Add Edit Update]"/>
<routine name="showidxs" use="Show then contence of the indexes to a table"
parameter="table" type="number" use="Table to use" system>
long int in; /* index of the table */
long int br; /* branch of the current index */
long int lf; /* leaf of the current branch */
for(in=1; in<u_indexes; in++)
{ if (u_index[in].tbl==v_table)
{ printf("\nIndex: %li of table %li size %li\n", in, v_table, u_index[in].scale);
for(br=0; br<u_index[in].scale; br++)
{ printf("%4li %4li ", br, u_index[in].len[br]);
for(lf=0; lf<u_index[in].len[br]; lf++)
{ if (lf!=0) printf(" ");
printf("%4li %4li\n", lf, u_index[in].ptr[br][lf]);
}
}
}
}
</routine>
<routine name="ptrinfo" use="Get the contence of a pointer in readable form"
type="string" use="A string with the contence"
parameter="ptr" type="pointer" use="The pointer to read"
system>
return scon(sadd(scon(sadd(scon(sadd(scpy("{"),get_int(v_ptr.branch)),", "),get_int(v_ptr.leaf)),", "),get_int(v_ptr.rec)),"}");
</routine>
<routine name="getrec" use="Get the recordnumber part of a pointer"
type="number"
parameter="ptr" type="pointer" use="The pointer"
parameter="index" type="number" system>
return v_ptr.rec;
</routine>
<routine name="tablelen" use="get the length of a table"
type="number" use="the length or 0 if no table found"
parameter="table" type="number" use="the table"
system>
if (v_table<1 || v_table>u_tables) return 0;
return u_table[v_table].len;
</routine>
<routine name="maxbranch"
type="number"
parameter="index" type="number" system>
if (v_index<1 || v_index>u_indexes) return -1;
return u_index[v_index].scale-1;
</routine>
<routine name="maxleaf"
type="number"
parameter="branch" type="number"
parameter="index" type="number" system>
if (v_branch<0 || v_index<1 || v_index>=u_indexes || u_index[v_index].len==0) return -1;
return u_index[v_index].len[v_branch]-1;
</routine>
<variable name="log" type="stream"/>
<routine name="initdb" use="initiate the database"
parameter="tables" type="number" use="the current number of tables"
parameter="indexes" type="number" use="the current number of indexes"
system>
v_log=fopen("log.txt", "w");
u_table=realloc(u_table, sizeof(struct table)*v_tables);
if (u_table==0) {printf("Could not startup"); exit(1);}
u_tables=v_tables;
u_index=realloc(u_index, sizeof(struct index)*v_indexes);
if (u_index==0) {printf("Could not startup"); exit(1);}
u_indexes=v_indexes;
</routine>
<routine name="addrecord" use="adds a record to a table"
type="pointer" use="a field-pointer to the new record"
parameter="table" type="number" use="the table to use"
system>
static struct pointer res;
long int p=u_table[v_table].len / 250;
long int r=u_table[v_table].len % 250;
if (u_table[v_table].ptr==0 || r==0)
{ u_table[v_table].ptr=realloc(u_table[v_table].ptr, (p+1) * sizeof(char*));
if (u_table[v_table].ptr==0) {printf("Out of memory 1\n"); exit(1);}
u_table[v_table].ptr[p]=0;
}
u_table[v_table].ptr[p]=realloc(u_table[v_table].ptr[p], (r+1) * u_table[v_table].size);
if (u_table[v_table].ptr[p]==0) {printf("Out of memory 2\n"); exit(1);}
u_table[v_table].len++;
res.leaf=-1;
res.branch=-1;
res.rec=u_table[v_table].len-1;
return res;
</routine>
<routine name="cpyrecord" use="adds a record to a table"
type="pointer" use="a pointer to the new record"
parameter="ptr" type="pointer" use="pointer to the current record"
parameter="table" type="number" use="the table to alter"
system>
static struct pointer res;
long int p=u_table[v_table].len / 250;
long int r=u_table[v_table].len % 250;
long int fp=v_ptr.rec / 250;
long int fr=v_ptr.rec % 250;
if (u_table[v_table].ptr==0 || r==0)
{ u_table[v_table].ptr=realloc(u_table[v_table].ptr, (p+1) * sizeof(char*));
if (u_table[v_table].ptr==0) {printf("Out of memory 3\n"); exit(1);}
u_table[v_table].ptr[p]=0;
}
u_table[v_table].ptr[p]=realloc(u_table[v_table].ptr[p], (r+1) * u_table[v_table].size);
if (u_table[v_table].ptr[p]==0) {printf("Out of memory 4\n"); exit(1);}
u_table[v_table].len++;
memcpy(u_table[v_table].ptr[p]+r* u_table[v_table].size,
u_table[v_table].ptr[fp]+fr* u_table[v_table].size,
u_table[v_table].size);
res.branch=v_ptr.branch;
res.leaf=v_ptr.leaf;
res.rec=u_table[v_table].len-1;
return res;
</routine>
<routine name="deleterecord" use="deletes the contents of a record"
parameter="record" type="number" use="the record to delete"
parameter="table" type="number" use="the table to use"
system> /* move the last record of the table to the current position */
long int p=v_record / 250;
long int r=v_record % 250;
long int lp=0;
long int lr=0;
if (v_record<0 || v_record>=u_table[v_table].len)
{ fprintf(v_log, "Error in deleting record %li from table %li.\n", v_record, v_table);
return;
}
lp=(u_table[v_table].len-1) / 250;
lr=(u_table[v_table].len-1) % 250;
memmove(u_table[v_table].ptr[p]+r*u_table[v_table].size,
u_table[v_table].ptr[lp]+lr*u_table[v_table].size,
u_table[v_table].size);
if (lr==0 && lp!=0)
{ u_table[v_table].ptr=realloc(u_table[v_table].ptr, lp * sizeof(char*));
if (u_table[v_table].ptr==0) {printf("Out of memory 5\n"); exit(1);}
} else
{ u_table[v_table].ptr[lp]=realloc(u_table[v_table].ptr[lp], lr * u_table[v_table].size);
if (lr>0 && u_table[v_table].ptr[lp]==0) {printf("Out of memory 6\n"); exit(1);}
}
u_table[v_table].len--;
</routine>
<routine name="changeindex" use="change the value in an index"
parameter="ptr" type="pointer"
parameter="rec" type="number"
parameter="index" type="number"
system>
if (v_ptr.branch<0 || v_ptr.branch>=u_index[v_index].scale ||
v_ptr.leaf<0 || v_ptr.leaf>=u_index[v_index].len[v_ptr.branch]) return;
u_index[v_index].ptr[v_ptr.branch][v_ptr.leaf]=v_rec;
</routine>
<routine name="searchindex" use="calculate new search position"
type="number" use="new position to search from or null when end"
parameter="current" type="number" use="position where was searched last"
parameter="level" type="byte" use="level of the search from 1 till last=current"
parameter="check" type="byte" use="is the current value higher or lower or the same"
parameter="max" type="number" use="number of elements in the index"
system>
long int factor=((v_max>>(v_level-1))+1)>>1;
if ((1<<v_level)>v_max*2) return -1;
if (v_current==-1) return factor-1;
if (v_check<=0) return (v_current<factor)?0:v_current-factor;
return (v_current+factor>=v_max)?v_max-1:v_current+factor;
</routine>
<routine name="getrecptr" use="get a pointer to a record number"
type="pointer" use="the created pointer"
parameter="rec" type="number"
parameter="table" type="number" system>
struct pointer res;
res.branch=-1;
res.leaf=-1;
res.rec=v_rec;
return res;
</routine>
<routine name="getpointer" use="get a pointer value"
type="pointer" use="the created pointer"
parameter="branch" type="number"
parameter="leaf" type="number"
parameter="index" type="number" system>
long int rec;
long int tbl;
struct pointer res;
if (v_branch<0 || v_leaf<0 || v_index<1 || v_index>u_indexes || v_branch>=u_index[v_index].scale || v_leaf>=u_index[v_index].len[v_branch])
{ res.branch=-1;
res.leaf=-1;
res.rec=-1;
return res;
}
rec=u_index[v_index].ptr[v_branch][v_leaf];
tbl=u_index[v_index].tbl;
res.branch=v_branch;
res.leaf=v_leaf;
res.rec=rec;
return res;
</routine>
<routine name="getbranch" type="number"
parameter="ptr" type="pointer"
system>
return v_ptr.branch;
</routine>
<routine name="ptrmin1" type="pointer"
parameter="ptr" type="pointer"
parameter="index" type="number"
system>
long int br=v_ptr.branch;
long int lf=v_ptr.leaf;
struct pointer res={-1, -1, -1};
if (lf==0 && br==0) return res;
if (lf==0)
{ br-=1;
lf=rtn_maxleaf(br, v_index);
} else lf--;
return rtn_getpointer(br, lf, v_index);
</routine>
<routine name="recalcptr" type="pointer"
parameter="ptr" type="pointer"
parameter="index" type="number"
system>
return rtn_getpointer(v_ptr.branch, v_ptr.leaf, v_index);
</routine>
<routine name="ptrplus1" type="pointer"
parameter="ptr" type="pointer"
parameter="index" type="number"
system>
long int br=v_ptr.branch;
long int lf=v_ptr.leaf;
struct pointer res={-1, -1, -1};
if (v_ptr.branch==-1) return res;
if (lf>=rtn_maxleaf(br, v_index))
{ if (br==rtn_maxbranch(v_index)) return res;
br+=1;
lf=0;
} else lf+=1;
return rtn_getpointer(br, lf, v_index);
</routine>
<routine name="subptr"
parameter="val" type="number"
parameter="index" type="number"
parameter="branch" type="number"
parameter="diff" type="number" system>
long int i;
struct pointer *p;
/* fprintf(v_log, "subptr value: %li index: %li table: %li branch: %li diff: %li\n", v_val, v_index, u_index[v_index].tbl, v_branch, v_diff);*/
for(i=0; i<u_index[v_index].ptrs; i++)
{ p=u_index[v_index].padm[i];
if (p==0) return;
if (p->branch==v_branch) {p->branch--; p->leaf+=v_diff;}
if (p->branch>v_branch) p->branch--;
if (p->rec==v_val && v_dbstate==3)
{ /* fprintf(v_log, "save pointer\n");*/
p->branch=-1;
p->leaf=-2;
} else if (p->rec>=v_val && u_index[v_index].patp[i]==0)
{ *p=rtn_ptrmin1(*p, v_index);
}
}
</routine>
<routine name="addptr"
parameter="val" type="number"
parameter="index" type="number"
parameter="branch" type="number"
parameter="leaf" type="number"
parameter="old" type="number" system>
long int i;
struct pointer *p;
/* fprintf(v_log, "addptr value: %li index: %li table: %li branch: %li leaf: %li old: %li\n", v_val, v_index, u_index[v_index].tbl, v_branch, v_leaf, v_old);*/
for(i=0; i<u_index[v_index].ptrs; i++)
{ p=u_index[v_index].padm[i];
if (p==0) return;
if (p->branch==-1 && p->leaf==-2)
{ /* fprintf(v_log, "recover pointer\n");*/
p->branch=v_branch;
p->leaf=v_leaf;
p->rec=v_val;
if (v_old>=0 && p->branch>v_branch) p->branch++;
if (v_old>=0 && p->branch==v_branch && p->leaf>=v_old)
{p->branch++; p->leaf-=v_old;}
} else
{ if (v_old>=0 && p->branch>v_branch) p->branch++;
if (v_old>=0 && p->branch==v_branch && p->leaf>=v_old)
{p->branch++; p->leaf-=v_old;}
if (p->rec>=v_val && u_index[v_index].patp[i]==0)
*p=rtn_ptrplus1(*p, v_index);
}
}
</routine>
<routine name="addindex" use="add record to an index"
parameter="ptr" type="pointer" use="pointer to the new position in the index"
parameter="rec" type="number" use="record number to add"
parameter="index" type="number" use="the index to add to"
system>
/* check existence of the index */
if (v_ptr.branch<0)
{ v_ptr.branch=rtn_maxbranch(v_index);
v_ptr.leaf=rtn_maxleaf(v_ptr.branch, v_index)+1;
}
if (v_ptr.branch<0) v_ptr.branch=0;
if (v_ptr.leaf<0) v_ptr.leaf=0;
if (u_index[v_index].scale==0)
{ u_index[v_index].len=realloc(u_index[v_index].len, sizeof(long int));
if (u_index[v_index].len==0) {printf("Out of memory 7\n"); exit(1);}
u_index[v_index].ptr=realloc(u_index[v_index].ptr, sizeof(char*));
if (u_index[v_index].ptr==0) {printf("Out of memory 8\n"); exit(1);}
u_index[v_index].len[0]=0;
u_index[v_index].ptr[0]=0;
u_index[v_index].scale=1;
}
u_index[v_index].len[v_ptr.branch]++;
u_index[v_index].ptr[v_ptr.branch]=realloc(u_index[v_index].ptr[v_ptr.branch], sizeof(long int)*u_index[v_index].len[v_ptr.branch]);
if (u_index[v_index].ptr[v_ptr.branch]==0) {printf("Out of memory 9\n"); exit(1);}
memmove(u_index[v_index].ptr[v_ptr.branch]+v_ptr.leaf+1, u_index[v_index].ptr[v_ptr.branch]+v_ptr.leaf,
(u_index[v_index].len[v_ptr.branch]-v_ptr.leaf-1)*sizeof(long int));
u_index[v_index].ptr[v_ptr.branch][v_ptr.leaf]=v_rec;
if (u_index[v_index].len[v_ptr.branch]>5000) /* normally 5000 */
{ long int new=2000; /* normally 2000 */
long int old=u_index[v_index].len[v_ptr.branch]-new;
rtn_addptr(v_rec, v_index, v_ptr.branch, v_ptr.leaf, old); /* branch too low after earlier concat */
u_index[v_index].scale++;
u_index[v_index].len=realloc(u_index[v_index].len, u_index[v_index].scale*sizeof(long int));
if (u_index[v_index].len==0) {printf("Out of memory 10\n"); exit(1);}
memmove(u_index[v_index].len+v_ptr.branch+1, u_index[v_index].len+v_ptr.branch,
(u_index[v_index].scale-v_ptr.branch-1)*sizeof(long int));
u_index[v_index].ptr=realloc(u_index[v_index].ptr, u_index[v_index].scale*sizeof(char*));
if (u_index[v_index].ptr==0) {printf("Out of memory 11\n"); exit(1);}
memmove(u_index[v_index].ptr+v_ptr.branch+1, u_index[v_index].ptr+v_ptr.branch,
(u_index[v_index].scale-v_ptr.branch-1)*sizeof(char*));
u_index[v_index].len[v_ptr.branch+1]=new;
u_index[v_index].ptr[v_ptr.branch+1]=malloc(new * sizeof(long int));
if (u_index[v_index].ptr[v_ptr.branch+1]==0) {printf("Out of memory 12\n"); exit(1);}
memmove(u_index[v_index].ptr[v_ptr.branch+1],
u_index[v_index].ptr[v_ptr.branch]+old,
new*sizeof(long int));
u_index[v_index].len[v_ptr.branch]=old;
u_index[v_index].ptr[v_ptr.branch]=realloc(u_index[v_index].ptr[v_ptr.branch], old * sizeof(long int));
if (u_index[v_index].ptr[v_ptr.branch]==0) {printf("Out of memory 13\n"); exit(1);}
} else rtn_addptr(v_rec, v_index, v_ptr.branch, v_ptr.leaf, -1);
</routine>
<routine name="mergeleft"
parameter="ptr" type="pointer" use="pointer to the old position in the index"
parameter="index" type="number" use="the index to delet from"
system>
long int left=u_index[v_index].len[v_ptr.branch-1];
long int old=u_index[v_index].len[v_ptr.branch];
u_index[v_index].len[v_ptr.branch-1]+=old;
u_index[v_index].ptr[v_ptr.branch-1]=realloc(u_index[v_index].ptr[v_ptr.branch-1],
(old + left) * sizeof(long int));
if (u_index[v_index].ptr[v_ptr.branch-1]==0) {printf("Out of memory 14\n"); exit(1);}
memmove(u_index[v_index].ptr[v_ptr.branch-1]+left,
u_index[v_index].ptr[v_ptr.branch],
old * sizeof(long int));
free(u_index[v_index].ptr[v_ptr.branch]);
/* move the next branches over the discarted one */
u_index[v_index].scale--;
memmove(u_index[v_index].len+v_ptr.branch, u_index[v_index].len+v_ptr.branch+1,
(u_index[v_index].scale-v_ptr.branch)*sizeof(long int));
u_index[v_index].len=realloc(u_index[v_index].len, u_index[v_index].scale*sizeof(long int));
if (u_index[v_index].len==0) {printf("Out of memory 15\n"); exit(1);}
memmove(u_index[v_index].ptr+v_ptr.branch, u_index[v_index].ptr+v_ptr.branch+1,
(u_index[v_index].scale-v_ptr.branch)*sizeof(char*));
u_index[v_index].ptr=realloc(u_index[v_index].ptr, u_index[v_index].scale*sizeof(char*));
if (u_index[v_index].ptr==0) {printf("Out of memory 16\n"); exit(1);}
</routine>
<routine name="mergeright"
parameter="ptr" type="pointer" use="pointer to the old position in the index"
parameter="index" type="number" use="the index to delet from"
system>
long int right=u_index[v_index].len[v_ptr.branch+1];
long int old=u_index[v_index].len[v_ptr.branch];
u_index[v_index].len[v_ptr.branch]+=right;
u_index[v_index].ptr[v_ptr.branch]=realloc(u_index[v_index].ptr[v_ptr.branch],
(old + right) * sizeof(long int));
if (u_index[v_index].ptr[v_ptr.branch]==0) {printf("Out of memory 17\n"); exit(1);}
memmove(u_index[v_index].ptr[v_ptr.branch]+old,
u_index[v_index].ptr[v_ptr.branch+1],
right * sizeof(long int));
free(u_index[v_index].ptr[v_ptr.branch+1]);
/* move the next branches over the discarted one */
u_index[v_index].scale--;
memmove(u_index[v_index].len+v_ptr.branch+1, u_index[v_index].len+v_ptr.branch+2,
(u_index[v_index].scale-v_ptr.branch-1)*sizeof(long int));
u_index[v_index].len=realloc(u_index[v_index].len, u_index[v_index].scale*sizeof(long int));
if (u_index[v_index].len==0) {printf("Out of memory 18\n"); exit(1);}
memmove(u_index[v_index].ptr+v_ptr.branch+1, u_index[v_index].ptr+v_ptr.branch+2,
(u_index[v_index].scale-v_ptr.branch-1)*sizeof(char*));
u_index[v_index].ptr=realloc(u_index[v_index].ptr, u_index[v_index].scale*sizeof(char*));
if (u_index[v_index].ptr==0) {printf("Out of memory 19\n"); exit(1);}
</routine>
<routine name="deleteindex" use="add record to an index"
parameter="ptr" type="pointer" use="pointer to the old position in the index"
parameter="index" type="number" use="the index to delet from"
system>
/* check existence of the index */
long int r;
if (v_ptr.branch==-1) return;
r=rtn_getrec(v_ptr, v_index);
u_index[v_index].len[v_ptr.branch]--;
memmove(u_index[v_index].ptr[v_ptr.branch]+v_ptr.leaf, u_index[v_index].ptr[v_ptr.branch]+v_ptr.leaf+1,
(u_index[v_index].len[v_ptr.branch]-v_ptr.leaf)*sizeof(long int));
u_index[v_index].ptr[v_ptr.branch]=realloc(u_index[v_index].ptr[v_ptr.branch], sizeof(long int)*u_index[v_index].len[v_ptr.branch]);
if (u_index[v_index].len[v_ptr.branch]!=0 && u_index[v_index].ptr[v_ptr.branch]==0) {printf("Out of memory 20\n"); exit(1);}
if (u_index[v_index].len[v_ptr.branch] < 1000 && u_index[v_index].scale > 1) /* < 3 should be 1000 */
{ /* check smallest branch (left? or right?) */
long int left=99999;
long int right=99999;
if (v_ptr.branch > 0) left=u_index[v_index].len[v_ptr.branch-1];
if (v_ptr.branch < u_index[v_index].scale-1) right=u_index[v_index].len[v_ptr.branch+1];
if (left < 6000 || right < 6000) /* left and right should be 6000 */
{ if (left < right)
{ rtn_mergeleft(v_ptr, v_index);
rtn_subptr(r, v_index, v_ptr.branch, rtn_maxleaf(v_ptr.branch-1, v_index));
} else
{ rtn_mergeright(v_ptr, v_index);
rtn_subptr(r, v_index, v_ptr.branch+1, rtn_maxleaf(v_ptr.branch, v_index));
}
} else rtn_subptr(r, v_index, 99999999, 0);
} else rtn_subptr(r, v_index, 99999999, 0);
</routine>
Copyright (C) 2001 Jurjen J. Stellingwerff