Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc3b193a

Browse files
committed
Replace linear searches with binary searches in pg_dump's code to
lookup objects by OID. Per gripe from nikitathespider.
1 parentaabb700 commitc3b193a

File tree

1 file changed

+84
-42
lines changed

1 file changed

+84
-42
lines changed

‎src/bin/pg_dump/common.c

Lines changed: 84 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@
1111
*
1212
*
1313
* IDENTIFICATION
14-
* $PostgreSQL: pgsql/src/bin/pg_dump/common.c,v 1.97 2007/08/21 01:11:20 tgl Exp $
14+
* $PostgreSQL: pgsql/src/bin/pg_dump/common.c,v 1.98 2007/09/23 23:39:36 tgl Exp $
1515
*
1616
*-------------------------------------------------------------------------
1717
*/
@@ -41,7 +41,11 @@ static intnumCatalogIds = 0;
4141

4242
/*
4343
* These variables are static to avoid the notational cruft of having to pass
44-
* them into findTableByOid() and friends.
44+
* them into findTableByOid() and friends. For each of these arrays, we
45+
* build a sorted-by-OID index array immediately after it's built, and then
46+
* we use binary search in findTableByOid() and friends. (qsort'ing the base
47+
* arrays themselves would be simpler, but it doesn't work because pg_dump.c
48+
* may have already established pointers between items.)
4549
*/
4650
staticTableInfo*tblinfo;
4751
staticTypeInfo*typinfo;
@@ -51,12 +55,18 @@ static intnumTables;
5155
staticintnumTypes;
5256
staticintnumFuncs;
5357
staticintnumOperators;
58+
staticDumpableObject**tblinfoindex;
59+
staticDumpableObject**typinfoindex;
60+
staticDumpableObject**funinfoindex;
61+
staticDumpableObject**oprinfoindex;
5462

5563

5664
staticvoidflagInhTables(TableInfo*tbinfo,intnumTables,
5765
InhInfo*inhinfo,intnumInherits);
5866
staticvoidflagInhAttrs(TableInfo*tbinfo,intnumTables,
5967
InhInfo*inhinfo,intnumInherits);
68+
staticDumpableObject**buildIndexArray(void*objArray,intnumObjs,
69+
SizeobjSize);
6070
staticintDOCatalogIdCompare(constvoid*p1,constvoid*p2);
6171
staticvoidfindParentsByOid(TableInfo*self,
6272
InhInfo*inhinfo,intnumInherits);
@@ -104,11 +114,13 @@ getSchemaData(int *numTablesPtr)
104114
if (g_verbose)
105115
write_msg(NULL,"reading user-defined functions\n");
106116
funinfo=getFuncs(&numFuncs);
117+
funinfoindex=buildIndexArray(funinfo,numFuncs,sizeof(FuncInfo));
107118

108119
/* this must be after getFuncs */
109120
if (g_verbose)
110121
write_msg(NULL,"reading user-defined types\n");
111122
typinfo=getTypes(&numTypes);
123+
typinfoindex=buildIndexArray(typinfo,numTypes,sizeof(TypeInfo));
112124

113125
/* this must be after getFuncs, too */
114126
if (g_verbose)
@@ -122,6 +134,7 @@ getSchemaData(int *numTablesPtr)
122134
if (g_verbose)
123135
write_msg(NULL,"reading user-defined operators\n");
124136
oprinfo=getOperators(&numOperators);
137+
oprinfoindex=buildIndexArray(oprinfo,numOperators,sizeof(OprInfo));
125138

126139
if (g_verbose)
127140
write_msg(NULL,"reading user-defined operator classes\n");
@@ -154,6 +167,7 @@ getSchemaData(int *numTablesPtr)
154167
if (g_verbose)
155168
write_msg(NULL,"reading user-defined tables\n");
156169
tblinfo=getTables(&numTables);
170+
tblinfoindex=buildIndexArray(tblinfo,numTables,sizeof(TableInfo));
157171

158172
if (g_verbose)
159173
write_msg(NULL,"reading table inheritance information\n");
@@ -540,6 +554,70 @@ findObjectByCatalogId(CatalogId catalogId)
540554
returnNULL;
541555
}
542556

557+
/*
558+
* Find a DumpableObject by OID, in a pre-sorted array of one type of object
559+
*
560+
* Returns NULL for unknown OID
561+
*/
562+
staticDumpableObject*
563+
findObjectByOid(Oidoid,DumpableObject**indexArray,intnumObjs)
564+
{
565+
DumpableObject**low;
566+
DumpableObject**high;
567+
568+
/*
569+
* This is the same as findObjectByCatalogId except we assume we need
570+
* not look at table OID because the objects are all the same type.
571+
*
572+
* We could use bsearch() here, but the notational cruft of calling
573+
* bsearch is nearly as bad as doing it ourselves; and the generalized
574+
* bsearch function is noticeably slower as well.
575+
*/
576+
if (numObjs <=0)
577+
returnNULL;
578+
low=indexArray;
579+
high=indexArray+ (numObjs-1);
580+
while (low <=high)
581+
{
582+
DumpableObject**middle;
583+
intdifference;
584+
585+
middle=low+ (high-low) /2;
586+
difference=oidcmp((*middle)->catId.oid,oid);
587+
if (difference==0)
588+
return*middle;
589+
elseif (difference<0)
590+
low=middle+1;
591+
else
592+
high=middle-1;
593+
}
594+
returnNULL;
595+
}
596+
597+
/*
598+
* Build an index array of DumpableObject pointers, sorted by OID
599+
*/
600+
staticDumpableObject**
601+
buildIndexArray(void*objArray,intnumObjs,SizeobjSize)
602+
{
603+
DumpableObject**ptrs;
604+
inti;
605+
606+
ptrs= (DumpableObject**)malloc(numObjs*sizeof(DumpableObject*));
607+
for (i=0;i<numObjs;i++)
608+
ptrs[i]= (DumpableObject*) ((char*)objArray+i*objSize);
609+
610+
/* We can use DOCatalogIdCompare to sort since its first key is OID */
611+
if (numObjs>1)
612+
qsort((void*)ptrs,numObjs,sizeof(DumpableObject*),
613+
DOCatalogIdCompare);
614+
615+
returnptrs;
616+
}
617+
618+
/*
619+
* qsort comparator for pointers to DumpableObjects
620+
*/
543621
staticint
544622
DOCatalogIdCompare(constvoid*p1,constvoid*p2)
545623
{
@@ -630,80 +708,44 @@ removeObjectDependency(DumpableObject *dobj, DumpId refId)
630708
* findTableByOid
631709
* finds the entry (in tblinfo) of the table with the given oid
632710
* returns NULL if not found
633-
*
634-
* NOTE: should hash this, but just do linear search for now
635711
*/
636712
TableInfo*
637713
findTableByOid(Oidoid)
638714
{
639-
inti;
640-
641-
for (i=0;i<numTables;i++)
642-
{
643-
if (tblinfo[i].dobj.catId.oid==oid)
644-
return&tblinfo[i];
645-
}
646-
returnNULL;
715+
return (TableInfo*)findObjectByOid(oid,tblinfoindex,numTables);
647716
}
648717

649718
/*
650719
* findTypeByOid
651720
* finds the entry (in typinfo) of the type with the given oid
652721
* returns NULL if not found
653-
*
654-
* NOTE: should hash this, but just do linear search for now
655722
*/
656723
TypeInfo*
657724
findTypeByOid(Oidoid)
658725
{
659-
inti;
660-
661-
for (i=0;i<numTypes;i++)
662-
{
663-
if (typinfo[i].dobj.catId.oid==oid)
664-
return&typinfo[i];
665-
}
666-
returnNULL;
726+
return (TypeInfo*)findObjectByOid(oid,typinfoindex,numTypes);
667727
}
668728

669729
/*
670730
* findFuncByOid
671731
* finds the entry (in funinfo) of the function with the given oid
672732
* returns NULL if not found
673-
*
674-
* NOTE: should hash this, but just do linear search for now
675733
*/
676734
FuncInfo*
677735
findFuncByOid(Oidoid)
678736
{
679-
inti;
680-
681-
for (i=0;i<numFuncs;i++)
682-
{
683-
if (funinfo[i].dobj.catId.oid==oid)
684-
return&funinfo[i];
685-
}
686-
returnNULL;
737+
return (FuncInfo*)findObjectByOid(oid,funinfoindex,numFuncs);
687738
}
688739

689740
/*
690741
* findOprByOid
691742
* finds the entry (in oprinfo) of the operator with the given oid
692743
* returns NULL if not found
693-
*
694-
* NOTE: should hash this, but just do linear search for now
695744
*/
696745
OprInfo*
697746
findOprByOid(Oidoid)
698747
{
699-
inti;
700-
701-
for (i=0;i<numOperators;i++)
702-
{
703-
if (oprinfo[i].dobj.catId.oid==oid)
704-
return&oprinfo[i];
705-
}
706-
returnNULL;
748+
return (OprInfo*)findObjectByOid(oid,oprinfoindex,numOperators);
707749
}
708750

709751

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp