Библиотека классов для программ на C++.
Давненько я обдумывал по ходу какими могли бы быть классы для стека, строки, словаря и пр. и естественно, управление памятью и сборка мусора.
И тут как то сел и написал симбиоз классов, стековых и требующих аллокатора. Основная идея, это что вместо конструктора используется функция производитель, деструктора нет, а удаление происходит всем скопом по стековому принципу mark-release, как в турбо пасскале. Вся библиотека в одном файле *.h. Это конечно, не заменить STL, но мне так удобнее, особенно для хеширования данных в быстрых программах.
#ifndef HASH_INC
#define HASH_INC
////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
/****
* Библиотека несложных классов с
* аллокатором памяти
* Stack
* String
* Vector
* Hash
* Dictionary
* FreeArray
* Utils - random hash keys
* Управление памяти подобно
* turbo pascal, классу Allocator
* в начале передается максимальное
* количество памяти и процедура
* Mark() запоминает состояние а
* Release() возвращает к последнему
* Mark(), удаляяя мгновенно все обьекты
* которые созданы после
* evgeniy-korniloff@yandex.ru, 2025
*/
//стековый обьект
template <int T, class D>
class Stack{
public:
D data[T]; int top;
Stack(){top=0;}
D Push(D d) { assert(top<T);return (data[top++]=d); }
D Pop(){assert(top>0);return data[--top]; }
D Top(){assert(top>0);return data[top-1]; }
bool Empty(){return top<=0; }
};
/////////
//стековый обьект + куча
class Allocator{
public:
char*data;int size;int cnt;Stack<100,int> st;
Allocator(int N=10000){
data=(char*)malloc(N);size=N;cnt=0;
assert(data!=NULL);
memset(data,0,N);
}
void Mark(){ st.Push(cnt);}
void Release(){ cnt=st.Pop();}
void* GetMem(int N){
void*q = (char*)&data[cnt];
cnt+=N;
if(cnt>size){
fprintf(stderr,"allocator: not memory \n");
abort();
}
return q;
}
void* GetTop(){ return (char*)&data[cnt]; }
Allocator(){free(data);}
};
/////////////
//создается по указателю
class String{
public:
char *data; int N; Allocator *a;
static String* Create(Allocator*a,const char* s){
String*q = (String*)a->GetMem(sizeof(String));
assert(s!=NULL);
q->a = a;
q->N=strlen(s);
q->data=(char*)a->GetMem(q->N+1);
strcpy(q->data,s);
return q;
}
char* Append(const char*s){
char buf[N]; strcpy(buf,data);
N += strlen(s);
data=(char*)a->GetMem(N);
strcpy(data,buf);
strcat(data,s);
return data;
}
char* Get(){ return data; }
int Len(){return N;}
};
/////////////
//создается по указателю
template <class D>
class Vector{
public:
D *data; int N; Allocator *a;
static Vector* Create(Allocator*a,
int N,
const D s[]){
Vector*q = (Vector*)a->GetMem(sizeof(Vector));
assert(s!=NULL);
q->N = N;
q->a = a;
q->data=(D*)a->GetMem(q->N*sizeof(D));
memcpy(q->data,s,q->N*sizeof(D));
return q;
}
D* Append(int Cnt, const D s[]){
int old_N=N;
if(GetTop()==a->GetTop()){//dobavlyaem v konec
N+=Cnt;
a->GetMem(Cnt*sizeof(D));
//??
//printf("-->\n");
}else{
D buf[old_N]; memcpy(buf,data,old_N*sizeof(D));
N+=Cnt;
data=(D*)a->GetMem(N*sizeof(D));
memcpy(data,buf,old_N*sizeof(D));
}
memcpy(&data[old_N],s,Cnt*sizeof(D));
return data;
}
D* Append(const D s){
return Append(1,&s);
}
D& ElementAt(int i){ return data[i]; }
int Len(){return N;}
void* GetTop(){return &data[N];}
void Sort(){ sort_sliyaniem(data,N);}
protected:
void swap(D v[],int a,int b){
D t = v[a];v[a]=v[b];v[b]=t;
}
void sort_vibor(D v[],int n){
int j,k,max_i; D max;
for(j=0;j<n-1;j++){
max=v[j]; max_i=j;
for(k=j+1;k<n;k++){
if(v[k]>max){
max=v[k];
max_i=k;
}
}
if(max_i!=j) swap(v,j,max_i);
}
}
void sort_sliyaniem(D v[], int n){
if(n<6) sort_vibor(v,n);
else{
int j,i,q,w,e;
int d = n/2+1;
D a[d], b[d];
for(j=0;j<d;j++) a[j]=v[j];
for(j=d,i=0; j<n; j++,i++) b[i]=v[j];
sort_sliyaniem(a,d);
sort_sliyaniem(b,i);
for(q=0,w=0,e=0;q<d && w<i;){
if(a[q]>b[w]){
v[e++] = a[q++];
}else{
v[e++] = b[w++];
}
}
while(q<d) v[e++] = a[q++];
while(w<i) v[e++] = b[w++];
}
}
};
//////////////////
typedef unsigned long long ULL;
static unsigned long int next_seed = 1;
class Utils{
public:
//случайные числа, всегда одинаковая последовательность
static int rand()
{
next_seed = next_seed * 1103515245 + 12345;
return (unsigned int)(next_seed / 65536) % 32768;
}
static ULL rand64(){
ULL A = rand();
A <<= 15; // сдвиг на 15, так как 7FFF покрывает 15 бит
A |= rand();
A <<= 15;
A |= rand();
A <<= 15;
A |= rand();
A <<= 3;
A |= rand() & 0b111; // дополнительные 3 случайных бита
return A;
}
static ULL ByteHashCode(unsigned char b){
static int first=0;
static ULL hash[256];
if(first==0){
first=1;
for(int i=0;i<256;i++)
hash[i]=rand64();
}
return hash[b];
}
static ULL GetHashKey(void*data,int N){
unsigned char*p=(unsigned char*)data;
int j=0; ULL w=0;
while(j<N){
w ^= ByteHashCode(p[j]);
j++;
}
return w;
}
};
///////////////////////////////////
class HKeyValue{
public:
void *data; int N; ULL hkey; Allocator*a;
static HKeyValue* Create(Allocator*a,void*data,
int N, ULL hkey=0){
HKeyValue*q=(HKeyValue*)a->GetMem(sizeof(HKeyValue));
q->data=a->GetMem(N);
memcpy(q->data,data,N);
q->a=a;q->N=N;q->hkey=hkey;
return q;
}
};
///////////////////////////////////////
class iHash{
public:
class HNode{
public:
HKeyValue*key, *value; HNode*next;
static HNode* Create(Allocator*a,
HKeyValue*key,
HKeyValue*value){
HNode*q = (HNode*)a->GetMem(sizeof(HNode));
q->key=key; q->value=value; q->next=NULL;
return q;
}
};
public:
HNode**tbl; int N; Allocator*a;
static iHash* Create(Allocator*a, int N=1000){
iHash*q=(iHash*)a->GetMem(sizeof(iHash*));
q->tbl = (HNode**)a->GetMem(N*sizeof(HNode*));
q->a=a; q->N=N;
return q;
}
int GetEntryIndex(ULL hkey){return hkey%N;}
HKeyValue* Find(HKeyValue* key){
int i = GetEntryIndex(key->hkey);
HNode*q = tbl[i];
while(q){
if(q->key->hkey==key->hkey &&
q->key->N==key->N &&
memcmp(q->key->data,key->data,key->N)==0)
return q->value;
q=q->next;
}
return NULL;
}
void Insert(HKeyValue* key,HKeyValue* value){
HNode*w = HNode::Create(a, key, value);
int i = GetEntryIndex(key->hkey);
w->next = tbl[i];
tbl[i] = w;
}
static ULL GetHashKey(void*data,int N){
unsigned char*p=(unsigned char*)data;
int j=0; ULL w=0;
while(j<N){
w ^= ~(((ULL)p[j]) << (j%48));
j++;
}
return w;
}
};
////////////////////////////
class SDictionary{
public:
iHash* h; Allocator*a;
char t[2][32];unsigned i;
static SDictionary* Create(Allocator*a){
SDictionary*q=(SDictionary*)a->GetMem(sizeof(SDictionary));
q->h = iHash::Create(a,1000);
q->a=a;
q->t[0][0]=q->t[1][0]='\0';
q->i=0;
return q;
}
char* ITOA(int d){
char *s=&t[(i++)%2][0];
sprintf(s,"%d",d);
return s;
}
int ATOI(char *s){
return atoi(s);
}
//itoa(number, str, 10);
void Insert(const char*key_,const char*value_){
HKeyValue* key=HKeyValue::Create(a,(void*)key_,
strlen(key_)+1,
iHash::GetHashKey( (void*)key_,strlen(key_)));
HKeyValue* value=HKeyValue::Create(a,(void*)value_,
strlen(value_)+1,
0);
h->Insert(key,value);
}
char* FindValue(const char *s){
a->Mark();
HKeyValue* key=HKeyValue::Create(a,(void*)s,
strlen(s)+1,
iHash::GetHashKey( (void*)s,strlen(s)));
int i = h->GetEntryIndex(key->hkey);
iHash::HNode*q = h->tbl[i];
while(q){
if(q->key->hkey==key->hkey &&
q->key->N==key->N &&
memcmp(q->key->data,key->data,key->N)==0)
{
a->Release();
return (char*)q->value->data;
}
q=q->next;
}
a->Release();
return NULL;
}
};
//////////////
template <class D>
class FreeArray{
public:
iHash* h; Allocator*a;
static FreeArray* Create(Allocator*a,int Hash_Size=1000){
FreeArray<D>*q=(FreeArray*)a->GetMem(sizeof(FreeArray<D>));
//???
// printf("stop size=%d cnt=%d\n",a->size,a->cnt);
// getchar();
q->h = iHash::Create(a,Hash_Size);
q->a=a;
return q;
}
D& ElementAt(D d){
a->Mark();
HKeyValue* key=HKeyValue::Create(a,(void*)&d,
sizeof(D),
iHash::GetHashKey( (void*)&d,sizeof(D)));
int i = h->GetEntryIndex(key->hkey);
iHash::HNode*q = h->tbl[i];
while(q){
if(q->key->hkey==key->hkey &&
memcmp(q->key->data,key->data,key->N)==0)
{
a->Release();
return *((D*)q->value->data);
}
q=q->next;
}
a->Release();
HKeyValue* k,*v; D foo=0;
k=HKeyValue::Create(a,(void*)&d,
sizeof(D),
iHash::GetHashKey( (void*)&d,sizeof(D)));
v=HKeyValue::Create(a,&foo,
sizeof(D),
0);
h->Insert(k,v);
return *((D*)v->data);
}
};
//////////////
/////////////////
#endif
Комментариев нет:
Отправить комментарий