Pomoc - Szukaj - Użytkownicy - Kalendarz
Pełna wersja: Tree-Framework
Forum PHP.pl > Inne > Oceny
Jabol
Kiedyś dawno temu zrobiłem ładny system obsługi drzewek. Teraz leży u mnie na kompie i się marnuje a tutaj na forum conajmniej raz na tydzień ktoś o to pyta. Dlatego zamieszczam. Dodam tylko, że sama struktura nie jest moim pomysłem:
Struktura:
  1. CREATE SEQUENCE contents_increment
  2. START 1
  3. INCREMENT 1
  4. MAXVALUE 9223372036854775807
  5. MINVALUE 1
  6. CACHE 1;
  7. CREATE SEQUENCE nodes_increment
  8. START 1
  9. INCREMENT 1
  10. MAXVALUE 9223372036854775807
  11. MINVALUE 1
  12. CACHE 1;
  13. CREATE TABLE contents (
  14. id bigint DEFAULT NEXTVAL('contents_increment'::text) NOT NULL,
  15. content text
  16. );
  17. CREATE TABLE nodes (
  18. id bigint DEFAULT NEXTVAL('nodes_increment'::text) NOT NULL,
  19. parent bigint,
  20. name character varying(100)
  21. );
  22. CREATE TABLE asociations (
  23. first_id bigint DEFAULT 0 NOT NULL,
  24. second_id bigint DEFAULT 0 NOT NULL,
  25. depth bigint DEFAULT 0 NOT NULL
  26. );
  27. CREATE TABLE binds (
  28. node_id bigint DEFAULT 0 NOT NULL,
  29. content_id bigint DEFAULT 0 NOT NULL
  30. );
  31. CREATE INDEX nodes_parent_ind ON nodes USING btree (parent);
  32. CREATE INDEX asociations_second_id_depth_ind ON asociations USING btree (second_id, depth);
  33. CREATE INDEX asociations_first_id_depth_ind ON asociations USING btree (first_id, depth);
  34. CREATE INDEX asociations_first_id_ind ON asociations USING btree (first_id);
  35. CREATE INDEX asociations_second_id_ind ON asociations USING btree (second_id);
  36. ALTER TABLE ONLY nodes
  37. ADD CONSTRAINT nodes_parent_name_key UNIQUE (parent, name);
  38. ALTER TABLE ONLY nodes
  39. ADD CONSTRAINT nodes_pkey PRIMARY KEY (id);
  40. ALTER TABLE ONLY nodes
  41. ADD CONSTRAINT "$1" FOREIGN KEY (parent) REFERENCES nodes(id) ON UPDATE NO ACTION ON DELETE CASCADE;
  42. ALTER TABLE ONLY contents
  43. ADD CONSTRAINT contents_pkey PRIMARY KEY (id);
  44. ALTER TABLE ONLY binds
  45. ADD CONSTRAINT binds_node_id_content_id_key UNIQUE (node_id, content_id);
  46. ALTER TABLE ONLY binds
  47. ADD CONSTRAINT binds_pkey PRIMARY KEY (node_id, content_id);
  48. ALTER TABLE ONLY binds
  49. ADD CONSTRAINT "$1" FOREIGN KEY (content_id) REFERENCES contents(id) ON UPDATE CASCADE ON DELETE CASCADE;
  50. ALTER TABLE ONLY binds
  51. ADD CONSTRAINT "$2" FOREIGN KEY (node_id) REFERENCES nodes(id) ON UPDATE CASCADE ON DELETE CASCADE;
  52. ALTER TABLE ONLY asociations
  53. ADD CONSTRAINT asociations_pkey PRIMARY KEY (first_id, second_id);
  54. ALTER TABLE ONLY asociations
  55. ADD CONSTRAINT "$1" FOREIGN KEY (second_id) REFERENCES nodes(id) ON UPDATE NO ACTION ON DELETE CASCADE;
  56. ALTER TABLE ONLY asociations
  57. ADD CONSTRAINT "$2" FOREIGN KEY (first_id) REFERENCES nodes(id) ON UPDATE NO ACTION ON DELETE CASCADE;
  58. SELECT pg_catalog.SETVAL ('nodes_increment', 1, true);
  59. SELECT pg_catalog.SETVAL ('contents_increment', 1, true);
  60. INSERT INTO nodes (id, parent, name) VALUES (1, NULL, 'main');
  61. INSERT INTO asociations (first_id, second_id, depth) VALUES (1, 1, 0);
Api:
  1. -- get_path
  2. DROP FUNCTION get_path (bigint);
  3. CREATE FUNCTION get_path (bigint) RETURNS text
  4. AS '
  5. DECLARE
  6.  
  7. nid ALIAS FOR $1;
  8. path TEXT;
  9. item RECORD;
  10.  
  11. BEGIN path := ''/''::TEXT;
  12.  
  13. FOR item IN SELECT n.name FROM nodes n, asociations a WHERE n.id = a.first_id AND a.second_id = nid ORDER BY a.depth DESC LOOP
  14.  
  15. path := path || item.name || ''/''::TEXT;
  16.  
  17. END LOOP;
  18.  
  19. RETURN path;
  20.  
  21. END;
  22. '
  23. LANGUAGE plpgsql;
  24.  
  25. -- mkdir
  26. DROP FUNCTION mkdir (character varying, bigint);
  27. CREATE FUNCTION mkdir (character varying, bigint) RETURNS BOOLEAN
  28. AS '
  29. DECLARE
  30.  
  31. nn ALIAS FOR $1;
  32. np ALIAS FOR $2;
  33.  
  34. BEGIN INSERT INTO nodes (name, parent) VALUES (nn, np);
  35.  
  36. INSERT INTO asociations (first_id, second_id, depth) SELECT first_id, (SELECT id FROM nodes WHERE name = nn AND parent = np), depth + 1 FROM asociations WHERE second_id = np;
  37.  
  38. INSERT INTO asociations (first_id, second_id, depth) VALUES((SELECT id FROM nodes WHERE name = nn AND parent = np), (SELECT id FROM nodes WHERE name = nn AND parent = np), 0);
  39.  
  40. RETURN true;
  41.  
  42. END;
  43. '
  44. LANGUAGE plpgsql;
  45.  
  46. -- mv
  47. DROP FUNCTION mv (bigint, bigint);
  48. CREATE FUNCTION mv (bigint, bigint) RETURNS BOOLEAN
  49. AS '
  50.  
  51. DECLARE
  52.  
  53. nid ALIAS FOR $1;
  54. np ALIAS FOR $2;
  55. temp1 RECORD;
  56. temp2 RECORD;
  57.  
  58. BEGIN FOR temp1 IN SELECT MAX(depth) AS max, second_id FROM asociations WHERE first_id = nid GROUP BY second_id LOOP
  59.  
  60. DELETE FROM asociations WHERE second_id = temp1.second_id AND depth > temp1.max;
  61.  
  62. END LOOP;
  63.  
  64. UPDATE nodes SET parent = np WHERE id = nid;
  65.  
  66. INSERT INTO asociations (first_id, second_id, depth) SELECT first_id, nid, depth + 1 FROM asociations WHERE second_id = np;
  67.  
  68. FOR temp2 IN SELECT second_id, depth FROM asociations WHERE first_id = nid AND depth <> 0 LOOP
  69.  
  70. INSERT INTO asociations (first_id, second_id, depth)
  71. SELECT first_id, temp2.second_id, depth + temp2.depth
  72. FROM asociations WHERE second_id = nid AND depth <> 0;
  73.  
  74. END LOOP;
  75.  
  76. RETURN true;
  77.  
  78. END;
  79. '
  80. LANGUAGE plpgsql;
  81.  
  82. -- mknode
  83. DROP FUNCTION mknode (character varying, bigint);
  84. CREATE FUNCTION mknode (character varying, bigint) RETURNS BOOLEAN
  85. AS '
  86.  
  87. DECLARE
  88.  
  89. nn ALIAS FOR $1;
  90. np ALIAS FOR $2;
  91.  
  92. BEGIN INSERT INTO nodes (name, parent) VALUES (nn, np);
  93.  
  94. INSERT INTO asociations (first_id, second_id, depth) SELECT first_id, (SELECT id FROM nodes WHERE name = nn AND parent = np), depth + 1 FROM asociations WHERE second_id = np;
  95.  
  96. INSERT INTO asociations (first_id, second_id, depth) VALUES((SELECT id FROM nodes WHERE name = nn AND parent = np), (SELECT id FROM nodes WHERE name = nn AND parent = np), 0);
  97.  
  98. RETURN true;
  99.  
  100. END;
  101. '
  102. LANGUAGE plpgsql;
  103.  
  104. -- mkcontent
  105. DROP FUNCTION mkcontent (bigint);
  106. CREATE FUNCTION mkcontent (bigint) RETURNS bigint
  107. AS '
  108.  
  109. DECLARE
  110.  
  111. id ALIAS FOR $1;
  112. record RECORD;
  113.  
  114. BEGIN SELECT lastvalue AS id INTO record FROM contents_increment; INSERT INTO contents ( id, content ) VALUES ( record.id, cnt );
  115. INSERT INTO binds ( node_id, content_id ) VALUES ( id, record.id );
  116. RETURN true;
  117.  
  118. END;
  119. '
  120. LANGUAGE plpgsql;
  121.  
  122. -- link
  123. DROP FUNCTION link (bigint, bigint);
  124. CREATE FUNCTION link (bigint, bigint) RETURNS BOOLEAN
  125. AS '
  126. INSERT INTO binds (content_id, node_id) VALUES ($1, $2);
  127. SELECT TRUE;
  128. '
  129. LANGUAGE sql;
  130.  
  131. -- rm
  132. DROP FUNCTION rm (bigint);
  133. CREATE FUNCTION rm (bigint) RETURNS BOOLEAN
  134. AS '
  135. DELETE FROM nodes WHERE id = $1;
  136. SELECT TRUE;
  137. '
  138. LANGUAGE sql;


Polecam wszystkim, bo mi naprawdę szkoda, że moja praca się marnuje a sam nie mam co z tym zrobić.

Jeżeli jest odpowiedniejsze forum to proszę o przeniesienie.

Ojojoj, wyszedłem poza limit długości posta.

Teraz jeszcze jakby jacyś linuksiarze z Was chcieli potestować i potrzebowali danych testowych to polecam:
Kod
#include<stdlib.h>
#include<errno.h>
#include<dirent.h>
#include<stdio.h>
#include<fcntl.h>
#include<sys/stat.h>
#include<sys/types.h>

#define FALSE 0
#define TRUE !FALSE

int id;
int fid;

void *xmalloc(size_t size)
{
  void *ptr;

  if((ptr=malloc(size))==NULL)
    syserr("malloc");
  memset(ptr, 0, size);
  return ptr;
}

void xfree(void *ptr)
{
  if(ptr)
  free(ptr);
}

void writeFile(const char *path)
{
  FILE *fp;
  int c;
  if((fp=fopen(path, "r"))==NULL)
    syserr("fopen");
  while((c=fgetc(fp))!=EOF)
  {
    if(c=='\\'||c=='\'')
      printf("%c", '\\');
    printf("%c", c);
  }
  if(fclose(fp)!=0)
    syserr("fclose");
}

int isRegular(const char *path)
{
  struct stat st;

  if( stat( path, &st ) == -1 )
    return FALSE;
  return ( S_ISREG( st.st_mode ) );
}

int isDir(const char *path)
{
  struct stat st;

  if( stat( path, &st ) == -1 )
    return FALSE;
  return ( S_ISDIR( st.st_mode ) );
}

unsigned long int insertDir(const char *name, const int pid)
{
  extern int id;

  id++;
  printf("INSERT INTO nodes ( id, name, parent) VALUES ( %d, '%s', %d);\n", id, name, pid);
  printf("INSERT INTO asociations ( first_id, second_id, depth ) SELECT first_id, %d, depth + 1 FROM asociations WHERE second_id = %d;\n", id, pid);
  printf("INSERT INTO asociations ( first_id, second_id, depth ) VALUES ( %d, %d, 0 );\n", id, id);
  return id;
}

void insertFile(const char *path, const char *name, const int pid)
{
  extern int id;
  extern int fid;

  id++;
  fid++;
  printf("INSERT INTO nodes ( id, name, parent) VALUES ( %d, '%s', %d );\n", id, name, pid);
  printf("INSERT INTO asociations ( first_id, second_id, depth ) SELECT first_id, %d, depth + 1 FROM asociations WHERE second_id = %d;\n", id, pid);
  printf("INSERT INTO asociations ( first_id, second_id, depth ) VALUES ( %d, %d, 0 );\n", id, id);
  printf("INSERT INTO contents ( id, content ) VALUES ( %d, '", fid);
  writeFile(path);
  printf("' );\n");
  printf("INSERT INTO binds (node_id, content_id) VALUES (%d, %d);", id, fid);
}

int insert(const char *path, const int pid)
{
  DIR *dir;
  struct dirent *dent;
  char *nodepath;
  unsigned long int npid;


  if((dir=opendir(path))==NULL)
    return TRUE;
  while((dent=readdir(dir))!=NULL)
  {
     if((strcmp(dent->d_name, ".")==0)||(strcmp(dent->d_name,"..")==0)||(strcmp(dent->d_name,"dev")==0)||(strcmp( dent->d_name,"proc")==0))
     {
      continue;
    }
    nodepath=(char *)xmalloc(strlen(path)+strlen(dent->d_name)+2);
    sprintf(nodepath, "%s/%s", path, dent->d_name);
    if(isDir(nodepath))
    {
      npid=insertDir(dent->d_name, pid);
      insert(nodepath, npid);
    }
    else if(isRegular(nodepath))
    {
      insertFile(nodepath, dent->d_name, pid);
    }
    xfree(nodepath);
  }
  if(closedir(dir)==-1)
    syserr("closedir");
  return TRUE;
}

int main(int argc, char *argv[])
{
  extern int id;
  extern int fid;

  id=1;
  fid=0;
  if(argc<2)
    syserr("argc");
  if(insert(argv[1], id)==FALSE)
    syserr("insert");

  return 0;
}
oraz error.c
Kod
#include<stdio.h>
#include<errno.h>
#include<fcntl.h>

void syserr(char *msg)
{
  fprintf(stderr, "ERROR: %s ( %d", msg, errno);
  if(errno>0 && errno<sys_nerr)
    fprintf(stderr, "; %s )\n", strerror(errno));
  else
    fprintf(stderr, " )\n");
  exit(1);
}
Mam nadzieję, że nie muszę dodawać, że framework jest na pgsql (choć łatwo go przerobić, bo pgsql jest prostym językiem).
I mam też nadzieję, że nie muszę dodawać, że program kompiluje się
Kod
gcc -o pgins pgins.c error.c
a używa
Kod
./pgins /katalog/do/insertowania | insert.sql
mariuszn3
Drzewek to znaczy masz na myśli coś takiego jak XML?
To może dorzucę swoje pare groszy.
Też ostatnio stałem przed problemem jak zapisywać to w bazie. W pierwszej fazie poszukiwań trafiłem na dedykowane rozwiązania tego problemu - istnieją systemy bazodanowe stworzone do przechowywania tego typu danych ('Native XML database')
Sprawdzałem exist'a i działa bardzo sprawnie. W php można się z tym łączyć przez SOAP czy REST, brakowało mi jedynie cache'owania zapytań.
Ostatecznie jednak jako, że nie potrzebowałem aż tak zaawansowanych możliwości przeszukiwania danego drzewa (w zasadzie chodziło mi tylko o to by móc to drzewo gdzieś zapisać i je później odczytać) pozostałem przy MySQL i po prostu ładowania drzewa XML w jedno pole tabeli.

Podejrzewam, że Twój pomysł dla kogoś kto nie za bardzo łapie XML i nie planuje bądź nie ma czasu się uczyć formułowania zapytań poprzez XQuery może być bardzo przydatny.
LBO
Jak dla mnie Zyx'owy sposób jest najlepszy...
mariuszn3
Cytat(LBO @ 25.07.2006, 19:35 ) *
Jak dla mnie Zyx'owy sposób jest najlepszy...

Dziwi mnie, że w tym artykule w ogóle nie pada słowo XML czy może lepiej DOM przecież dokładnie o taką strukturę chodzi.
EDIT: angielski artykuł tam z linkowany już wspomina o XML
Seth
Drzewka to nie tylko XML (a raczej jego zagniezdzona struktura), ale to takze grafy czy inne struktury polaczonych list
mariuszn3
Cytat(Seth @ 25.07.2006, 20:32 ) *
Drzewka to nie tylko XML (a raczej jego zagniezdzona struktura), ale to takze grafy czy inne struktury polaczonych list

Nie bardzo rozumiem co masz na myśli, czym jest według Ciebie zagnieżdżona struktura XML? Co to są grafy i inne struktury połączonych list, które można zapisać w powyższej bazie a w XML'u już nie questionmark.gif
bela
A na matmie w podstawówce spałeś? http://pl.wikipedia.org/wiki/Graf_%28matematyka%29
http://pl.wikipedia.org/wiki/Lista
mariuszn3
Cytat(bela @ 25.07.2006, 20:53 ) *

Pytałem Setha co konkretnie miał na myśli, bo nie widzę tutaj niczego co można zapisać w tej bazie a nie można zapisać w XML.. moim zdaniem jest zupełnie odwrotnie.
Jabol
Że tak to nazwę. Dokładnie jak napisałeś - można zapisać w XML-u, można i w bazie. Nie negowałbym istnienia czegoś tylko dlatego, że można to zrobić w XML-u. Pamiętaj też, że XML to pliki które należy przetważać i nie wiem czy wszystkie parsery poradzą sobie z olbrzymimi plikami, które baza z taką strukturą obsługuje bez problemu. Osobiście też nie lubię XML'a.

A poza tym spójrz na to z innej strony - wiesz ile miałem zabawy jak to pisałem winksmiley.jpg. Zauważ, że to są naprawdę fajne algorytmy.
mariuszn3
Absolutnie tego nie neguję.. nie o to mi chodziło..
Po prostu uważam, że przy podawaniu tego typu przykładów trzeba wspomnieć o XML'owych bazach danych - nie mówię tu o plikach XML ale o natywnych XML'owych bazach danych, które mogą przechowywać i terrabajty danych.. są to pełnowartościowe bazy danych z takim samym podejściem do wydajności jak MySQL czy inne tradycjne bazy z tą różnicą, że one są dedykowane strukturze węzłowej, po prostu do szybkich operacji na przechowywanych drzewach DOM. Link dla zainteresowanych

Jednak nie wszyscy mają możliwość postawienia sobie serwera eXist czy innej XML'owej bazy danych pomijając, że nie każdy miał do czynienia z XML'em i dlatego dla wielu to co napisałeś na pewno może się okazać bardzo przydatne.
To jest wersja lo-fi głównej zawartości. Aby zobaczyć pełną wersję z większą zawartością, obrazkami i formatowaniem proszę kliknij tutaj.
Invision Power Board © 2001-2025 Invision Power Services, Inc.