|
sounds pretty good.
it also is the kind of information Wikipedia handles rather well, see here[^].
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read formatted code with indentation, so please use PRE tags for code snippets.
I'm not participating in frackin' Q&A, so if you want my opinion, ask away in a real forum (or on my profile page).
|
|
|
|
|
thanks, but not the theoretical part is my problem, but the implementation itself (practically I'm asking for a simple code in C that shows the implementation of a hash table; how do i create it, how do I rehash it if the quota exceeds 0.5 for example, etc)
|
|
|
|
|
Here is the way I imagine it could be done:
- for each item, calculate the hash value any way you see fit (but consistently of course);
- use the lowest N bits of the hash as the bucket number;
- have a bucket array with 2^N entries, each holding one pointer (initially null);
- represent each bucket as a linked list.
So to find an existing item, calculate hash, mask away all but N bits, get the list head from the bucket array, start scanning the list.
When the linked lists start to grow beyond some threshold, increase N and recreate the entire hash table.
I'm not saying that is how it is done, I'm not claiming that is the best way to do it either, but I have done such things myself in such way (long before libraries or .NET offered them). The easiest way to store words of text would be to use the first letter as a hash (not a good probability distribution, but extremely fast!).
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read formatted code with indentation, so please use PRE tags for code snippets.
I'm not participating in frackin' Q&A, so if you want my opinion, ask away in a real forum (or on my profile page).
|
|
|
|
|
|
I've decided to write the code form scratch(inspiring myself from the internet) and this what i came up with:
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
typedef struct _List_t{
char *string;
struct _List_t *next;
}List_t;
typedef struct _HashTable_t{
int size;
List_t **table;
}HashTable_t;
HashTable_t *CreateTable(int);
HashTable_t *CreateTable(int size)
{
HashTable_t *NewTable;
NewTable=(HashTable_t*)malloc(sizeof(HashTable_t));
NewTable->table=(List_t**)malloc(sizeof(HashTable_t));
for(int i=0;i<size;i++)
NewTable->table[i]=NULL;
NewTable->size=size;
return NewTable;
}
unsigned int hash(HashTable_t *hashtable, char *str)
{
int a,b,p;
unsigned int hashval=0;
for(int i=0;i<<9; i++)
hashval = str[i] + (hashval << 5) - hashval;
return hashval%hashtable->size;
}
List_t *search(HashTable_t *hashtable, char *str)
{
List_t *list;
unsigned int hashval=hash(hashtable,str);
for(list=hashtable->table[hashval];list!=NULL;list=list->next)
if(strcmp(str,list->string)==0)
{
return list;
}
return NULL;
}
int insert(HashTable_t *hashtable, char *str)
{
List_t *NewList;
List_t *CurentList;
unsigned int hashval=hash(hashtable,str);
NewList=(List_t*)malloc(sizeof(List_t));
CurentList=search(hashtable,str);
if(CurentList !=NULL) return 2;
NewList->string=_strdup(str);
NewList->next=hashtable->table[hashval];
hashtable->table[hashval]=NewList;
return 0;
}
void ClearKey(HashTable_t *hashtable,char *str);
void ClearKey(HashTable_t *hashtable,char *str){
List_t *list,*temp;
int hashval=hash(hashtable,str);
list=hashtable->table[hashval];
while(list!=NULL){
if(list->string=str)
temp=list;
list=list->next;
free(temp);
}
}
void ClearTable(HashTable_t);
void ClearTable(HashTable_t *hashtable)
{
List_t *list,*temp;
if(hashtable!=NULL)
for(int i=0;i<hashtable->size;i++){
list=hashtable->table[i];
while(list!=NULL){
temp=list;
list=list->next;
free(temp); }
}
free(hashtable->table);
free(hashtable);
}
void main()
{
HashTable_t *MyHashTable;
char *s;
int sel,TableSize=12;
MyHashTable=CreateTable(TableSize);
printf("HashTable created!\n");
for(int i=0;i<MyHashTable->size;i++)
printf("%d",MyHashTable->table[i]);
printf("Select an operation\n");
printf("1. Insert 2. Search 3. Erase Other=Quit\n");
scanf("%c",&sel);
printf("Your selection is:%c",sel);
printf("\nEnter the key:");
s=(char*)malloc(sizeof(10));
scanf("%s",s);
printf("Key is %s",s);
while(sel<5){
if(sel=1)
insert(MyHashTable,s);
else if(sel=2)
search(MyHashTable,s);
else if(sel=3)
ClearKey(MyHashTable,s);
else
printf("Invalid Selection");
}
getch();
}
this is what i get when I compile it in Visual Studio
First-chance exception at 0x77052374 in HT.exe: 0xC0000005: Access violation reading location 0x00000004.
First-chance exception at 0x7703317f in HT.exe: 0xC0000005: Access violation reading location 0x00000004.
First-chance exception at 0x7707713d in HT.exe: 0xC0000005: Access violation reading location 0x00000014.
First-chance exception at 0x7708ac07 in HT.exe: 0xC0000005: Access violation reading location 0x06b2efe2.
First-chance exception at 0x66a2d914 (msvcr90d.dll) in HT.exe: 0xC0000005: Access violation writing location 0x06b2f010.
The thread 'Win32 Thread' (0x138) has exited with code -1073741510 (0xc000013a).
Unhandled exception at 0x66a2d914 (msvcr90d.dll) in HT.exe: 0xC0000005: Access violation writing location 0x06b2f010.
modified on Monday, June 21, 2010 8:00 PM
|
|
|
|
|
When I test following code, it cose more than 800M memory.
Why does it use so many memory?
#include "stdafx.h"
#include <windows.h>
#include <iostream>
#include <map>
using namespace std;
typedef std::map<int,int> IntMap;
int _tmain(int argc, _TCHAR* argv[])
{
IntMap testMap;
int i=0;
int j =0;
for( i=1; i< 10000000;i++)
{
int k =j++;
testMap.insert(IntMap::value_type(i,i));
if( 0 == i%10000)
{
cout << "Has Deal " << i << "lines" << endl;
}
}
getchar();
return 0;
}
modified on Wednesday, July 7, 2010 11:37 AM
|
|
|
|
|
You're storing 10 million pairs of integers in a map - the storage space for 20 million integers is 80M on it's own. Each node in the map contains at least two pointers for another 160M. Quite where the rest is is anyone's guess but it doesn't take much to clock up with multiple of 10M as the smallest denomination.
Cheers,
Ash
PS: Another way of looking at it is that's only 80 bytes an entry in the map.
|
|
|
|
|
I run the program in debug mode.
I find that it still cost 388,756K memories in Release mode.
It is still using more memories than 80 + 160M.
|
|
|
|
|
Cool, not surprised it eats RAM in debug - 80 bytes per tree node isn't that unreasonable.
As for release mode, have you considered looking at the source code for map to find out how big each node is? Presumably not as on one compiler I use each node contains three pointers, the data and the key. For a 32 bit machine that's 20 bytes and the allocator rounds everything up to the nearest multiple of 16 (so that 20 bytes becomes 32...) giving you ~ 320Mb.
So you're getting the correct magnitude, I wouldn't worry about it.
Ash
|
|
|
|
|
I agree, this is huge memory usage.Are you sure that the code is compiled into release mode.If you need to allocate such huge memory blocks why don't you consider dynamic allocation?This forum thread discusses how to estimate memory used by STL map.
Life is a stage and we are all actors!
|
|
|
|
|
Hi,
Are you checking the memory usage of a Debug build? Most compilers implement the debug memory allocator with extra padding around allocated memory.
Best Wishes,
-David Delaune
|
|
|
|
|
yu-jian wrote: ...it cose more than 800M memory.
How are you verifying this?
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Man who follows car will be exhausted." - Confucius
|
|
|
|
|
Hi everybody. I'm tring to save image form webBrowser control. and i have the following code
mshtml::HTMLDocument^ document = dynamic_cast<mshtml::HTMLDocument^>(this->webBrowser1->Document->DomDocument);
mshtml::IHTMLElementCollection^ collImages = document->getElementsByTagName(L"img");
for (int i = 0; i < collImages->length; ++i)
{
mshtml::IHTMLImgElement^ img = safe_cast<mshtml::IHTMLImgElement^>(collImages->item(nullptr, i));
mshtml::IHTMLElementRender^ render = dynamic_cast<mshtml::IHTMLElementRender^>(img);
Bitmap^ bmp = gcnew Bitmap(img->width, img->height);
Graphics^ g = Graphics::FromImage(bmp);
IntPtr hdc = g->GetHdc();
<big>render->DrawToDC(hdc); </big>
g->ReleaseHdc(hdc);
delete g; g = nullptr;
bmp->Save(L"C:\\Test\\SaveImage.Jpg", System::Drawing::Imaging::ImageFormat::Jpeg);
}
I get the following error message
Error C2664: 'mshtml::IHTMLElementRender::DrawToDC' : cannot convert parameter 1 from 'System::IntPtr' to 'mshtml::_RemotableHandle %'
is there any one who knows how to fix this?
|
|
|
|
|
Wrong forum.You should post you question to C++/CLI forum.
Life is a stage and we are all actors!
|
|
|
|
|
I did. But no one seems to know.
|
|
|
|
|
voo doo12 wrote: I did. But no one seems to know.
OK.
I would advice you to write your own managed wrapper for of IHTMLElementRender interface, never mix managed and unmaged code, and avoid using C++/CLI for anything- it's not stable enough, it's very slow and inefficient, it's dirty.You are supposed to use C# or VB.NET, when you are targeting .NET platform. If you need to create something using C++ you should better use MFC libraries.Good luck.
Life is a stage and we are all actors!
|
|
|
|
|
Can you show me how I could save image(picture) from webbrowser control using MFC?
|
|
|
|
|
voo doo12 wrote: Can you show me how I could save image(picture) from webbrowser control using MFC?
Of course I can.
In MFC you should use Doc/View framework and CHtmlView class to access HTML using DOM.
[EDIT]I used Gdi+ to handle the images[/EDIT]
Here is my demo sample:
int GetEncoderClsid(const WCHAR* format, CLSID* pClsid)
{
UINT num = 0;
UINT size = 0;
ImageCodecInfo* pImageCodecInfo = NULL;
GetImageEncodersSize(&num, &size);
if(size == 0)
return -1;
pImageCodecInfo = (ImageCodecInfo*)(malloc(size));
if(pImageCodecInfo == NULL)
return -1;
GetImageEncoders(num, size, pImageCodecInfo);
for(UINT j = 0; j < num; ++j)
{
if( wcscmp(pImageCodecInfo[j].MimeType, format) == 0 )
{
*pClsid = pImageCodecInfo[j].Clsid;
free(pImageCodecInfo);
return j;
}
}
free(pImageCodecInfo);
return -1;
}
void CWebBrowserAppView::OnFileSave()
{
LPDISPATCH pDisp=GetHtmlDocument();
IHTMLDocument2* pDoc;
HRESULT hr=0;
hr=pDisp->QueryInterface(IID_IHTMLDocument2,(void**)&pDoc);
if(FAILED(hr))
{
pDisp->Release();
AfxMessageBox(L"Sorry dude, cast failed!");
return;
}
IHTMLElementCollection* pImgs;
hr=pDoc->get_images(&pImgs);
if(FAILED(hr))
{
pDoc->Release();
pDisp->Release();
AfxMessageBox(L"Sorry dude, can't get images list from document!");
return;
}
long length;
pImgs->get_length(&length);
IDispatch *pdImg;
IHTMLImgElement *pImg;
CLSID jpgClsid;
GetEncoderClsid(L"image/jpeg", &jpgClsid);
for(int i=0;i<length;i++)
{
_variant_t index = i;
hr = pImgs->item( index, index, &pdImg);
if(SUCCEEDED(hr))
{
hr= pdImg->QueryInterface( IID_IHTMLImgElement, (void **) &pImg);
if(SUCCEEDED(hr))
{
long width,height;
pImg->get_width(&width);
pImg->get_height(&height);
IHTMLElementRender* pRend;
hr=pImg->QueryInterface(IID_IHTMLElementRender,(void**)&pRend);
if(SUCCEEDED(hr))
{
Bitmap* pBmp=new Bitmap(width,height,PixelFormat24bppRGB);
Graphics* pGr=Graphics::FromImage(pBmp);
HDC gDc=pGr->GetHDC();
hr=pRend->DrawToDC(gDc);
pGr->ReleaseHDC(gDc);
if(SUCCEEDED(hr))
{
CString name;
name.Format(L"%d.jpg",i);
pBmp->Save(name,&jpgClsid,NULL);
name.ReleaseBuffer();
}
pRend->Release();
delete pBmp;
}
pImg->Release();
}
pdImg->Release();
}
}
pImgs->Release();
pDoc->Release();
pDisp->Release();
}
Life is a stage and we are all actors!
modified on Sunday, June 6, 2010 9:14 AM
|
|
|
|
|
Thanks very much. I'm not familiar with MFC but I will be. Thanks again
|
|
|
|
|
You are always wellcome.Study hard and you will get results.
Life is a stage and we are all actors!
|
|
|
|
|
Hi, I'm getting "0xC0000138: Ordinal Not Found" when deploying an executable that uses an ActiveX control on another machine. I have no idea where to start debugging this problem.
Basically, what happens is that the visual studio output window displays
"Loaded (correct)path_to_ocx file"
"First-chance exception at 0x7c964ed1 in project_name.exe: 0xC0000138: Ordinal Not Found."
"project_name.exe: Unloaded 'path_to_ocx'"
The problem is that this does not happen on the development machine
Any kick in the right direction would be a godsend. Thanks
|
|
|
|
|
eusto wrote: Hi, I'm getting "0xC0000138: Ordinal Not Found"
As you have probably figured out by now that error essentially means: "I found that DLL you need and I loaded it. But when I walked the export table I could not find one of the functions that you need."
eusto wrote: Any kick in the right direction would be a godsend. Thanks
I would recommend using Dependency Walker[^] on the target machine to track down the problem. You should open the OCX file and look for missing dependencies.
Best Wishes,
-David Delaune
|
|
|
|
|
Thank you for your answer, Dependency Walker is cool, i didn't know about it. Unfortunately, there doesn't seem to be any missing stuff on that ocx. I've contacted the vendor and asked them about it
Regards,
Eugen
|
|
|
|
|
Hi Eugen,
Did you try the Profiling option in the Dependency Walker system menu? This option should allow you to log everything... including calls to LoadLibrary and GetProcAddress. You should point it at the executable loading the OCX object.
Best Wishes,
-David Delaune
|
|
|
|
|
Ok, at this point i'm almost sure this is a vendor issue because recompiling my application on the target machine gets rid of the problem. I'm now betting on a weird licence implementation issue.
Thanks again for your help David.
Regards,
Eugen.
|
|
|
|
|